指派问题（经典运筹学）.ppt

《指派问题（经典运筹学）.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中有