指派问题(经典运筹学).ppt

-、决策问题与0-,由于技术上的原因,投资受到以下约束:1、在项目1、2和3中必须有一项被选中2、项目3和4只能选中一项3、项目5被选中的前提是项目1被选中;如何在满足上述条件下选择一个最好的投资方案,使投资收益最大例1(投资问题)华美公司有5个项目被列入投资计划,每个项目的投资额和期望的投资收益见下表:项目投资额(万元)投资收益(万元)12101502300210310060413080526018010投资第i个项目不投资第i个项目Z表示投资效益投资项目模型:.例2(布点问题)某城市共有6个区,每个区都可以建消防站。市政府希望设置的消防站最少,但必须满足在城市任何地区发生火火警时,消防车要在15分钟内赶到现场。据实地测定,各区之间消防车行驶的时间见右表。地区123456101016282720210024321710316240122721428321201525527172715014620102125140请为该市制定一个最节省的计划在第i个地区建站Z表示全区消防站总数不在第i个地区建站i=1,2,…,6布点问题模型:最优解x2=1,x4=1最优值Z=、过滤隐枚举法(适合于变量个数较少的0-1规划)(x1x2x3)Z值约束条件(1)(2)(3)(4)过滤条件(000)(001)(010)(100)(101)(110)(011)(111)√√√√0Z≥0枚举法:检验可行解:32次运算-25√√√√Z≥5318×36运算次数:21计算目标函数值:8次√√√√.三、,要由n个人来承担,每个工作只能由一个人承担,且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用12…j…n12…i…n指派问题模型:i=1,2,…,nj=1,2,…,n第i个人做第j人件事Z表示总费用i=1,2,…,n;j=1,2,…,n第i个人不做第j人件事1、=1,2,…,nj=1,2,…,n当n=4时,有16变量,:现有4份工作,4个人应聘,由于各人技术专长不同,他们承担各项工作所需费用如下表所示,且规定每人只能做一项工作,每一项工作只能由一人承担,试求使总费用最小的分派方案。工作人费用1234123435456768898**********第i人做第j件事Z表示总费用i=1,2,3,4;j=1,2,3,、费用矩阵设有n个工作,要由n个人来承担,每个工作只能由一个人承担,且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用12…j…n12…i…ncij表示第i个人做第j件事的费用费用矩阵.