资源描述:
《指派问题(经典运筹学).ppt》由会员上传分享,免费在线阅读,更多相关内容在PPT专区-天天文库。
1、3.40-1整数规划一、决策问题与0-1变量10做第i件事不做第i件事n件事中必须做k件并只做k件事n件事中最多做k件事n件事中至少做k件事做第i件事的充要条件是做第j件事做第i件事的充要条件是不做第j件事只在做了第i件事前提下才考虑是否做第j件事该公司只有600万资金可用于投资,由于技术上的原因,投资受到以下约束:1、在项目1、2和3中必须有一项被选中2、项目3和4只能选中一项3、项目5被选中的前提是项目1被选中;如何在满足上述条件下选择一个最好的投资方案,使投资收益最大例1(投资问题)华美公司有5个项目
2、被列入投资计划,每个项目的投资额和期望的投资收益见下表:项目投资额(万元)投资收益(万元)12101502300210310060413080526018010投资第i个项目不投资第i个项目Z表示投资效益投资项目模型:例2(布点问题)某城市共有6个区,每个区都可以建消防站。市政府希望设置的消防站最少,但必须满足在城市任何地区发生火火警时,消防车要在15分钟内赶到现场。据实地测定,各区之间消防车行驶的时间见右表。地区12345610101628272021002432171031624012272142832
3、1201525527172715014620102125140请为该市制定一个最节省的计划在第i个地区建站Z表示全区消防站总数不在第i个地区建站i=1,2,…,6布点问题模型:最优解x2=1,x4=1最优值Z=2二、过滤隐枚举法(适合于变量个数较少的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
4、次√√√√三、指派问题与匈牙利法设有n个工作,要由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、指派问题的数学模型i=1,2,…,nj=1,2,…,n当n=4时,有16变量,8个约束方程例:现有4份工作,4个人应聘,由于各人技术专长不同,他们承担各项工作所需
5、费用如下表所示,且规定每人只能做一项工作,每一项工作只能由一人承担,试求使总费用最小的分派方案。工作人费用123412343545676889810101091110第i人做第j件事Z表示总费用i=1,2,3,4;j=1,2,3,4第i人不做第j件事2、费用矩阵设有n个工作,要由n个人来承担,每个工作只能由一个人承担,且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用12…j…n12…i…ncij表示第i个人做第j件事的费用费用矩阵例:现有4份工作,4个人应聘,由于个
6、人的技术专长不同,他们承担各项工作所需费用如下表所示,且规定每人只能做一项工作,每一项工作只能由一个人承担,试求使总费用最小的分派方案。工作人收费用1234123435456768898101010911费用矩阵对应一个5个人5个工作的指派问题第2个人做第4个工作的费用5第4个人做第2个工作的费用0定理:在费用矩阵C=(cij)的任一行(列)中减去一个常数或加上一个常数不改变本问题的最优解。n个人n个工作的指派问题1-b3、匈牙利法n个人n个工作的指派问题2i=1,2,…,nj=1,2,…,ni=1,2,…
7、,nj=1,2,…,n-b-bi=1,2,…,nj=1,2,…,ni=1,2,…,nj=1,2,…,n任务:对C的行和列减去某个常数,将C化的尽可能简单,简单到可一眼看出该问题的最优解-b3.40-1整数规划三、指派问题与匈牙利法费用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、指派问题的数学模型设有n个工作,要由n个人来承担,每个工作只能由一个人承担,且每个人只能承担一个工作。cij
8、表示第i个人做第j件事的费用,求总费用最低的指派方案。2、费用矩阵设有n个工作,要由n个人来承担,每个工作只能由一个人承担,且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用12…j…n12…i…ncij表示第i个人做第j件事的费用费用矩阵定理:在费用矩阵C=(cij)的任一行(列)中减去一个常数或加上一个常数不改变本问题的最优解。-b3、匈牙利法指派问题的最优解:若C中有