管理运筹学 整数规划与指派问题.pptx

《管理运筹学 整数规划与指派问题.pptx》由会员分享，可在线阅读，更多相关《管理运筹学 整数规划与指派问题.pptx（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 线性规划的决策变量取值可以是任意非负实数，但线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才许多实际问题中，只有当决策变量的取值为整数时才有意义。有意义。例如，产品的件数、机器的台数、装货的车数、完例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。成工作的人数等，分数或小数解显然是不合理的。要求全部或部分决策变量的取值为整数的线性规划要求全部或部分决策变量的取值为整数的线性规划问题，称为问题，称为整数线性规划整数线性规划，简称，简称整数规划整数规划(Integer Programming)。第1页/共76页第一节

2、第一节 整数线性规划问题的数学模型整数线性规划问题的数学模型第二节第二节 整数规划的求解方法整数规划的求解方法*第三节第三节 指派问题及匈牙利解法指派问题及匈牙利解法本章内容的安排本章内容的安排第2页/共76页第一节第一节 整数线性规划问题的数学模型整数线性规划问题的数学模型1.引例引例2.逻辑变量在整数规划建模中的作用逻辑变量在整数规划建模中的作用3.整数规划问题的特征与性质整数规划问题的特征与性质4.整数规划模型的分类整数规划模型的分类第3页/共76页例例1（装载问题）（装载问题）有一辆卡车的最大载重量为有一辆卡车的最大载重量为b 吨吨,现有现有n 种货物可供装种货物可供装载。设第载。设第

3、j 种货物每件重种货物每件重aj 吨吨,每件的装载费用为每件的装载费用为cj 元元(j=1,n)。问应该采用怎样的装载方案才能使卡车问应该采用怎样的装载方案才能使卡车一次装载货物的收入最大一次装载货物的收入最大?解解:设设xj为卡车装载第为卡车装载第j 种货物的件数种货物的件数(j=1,2,n),z表示卡车一次装载的收入表示卡车一次装载的收入,则该问题的数学模型为则该问题的数学模型为max z=c1x1+c2x2+c n x ns.t.a1x1+a2x2+a n x n b x j 0 且为整数且为整数(j=1,2,n)1.1.引例引例第4页/共76页 例例2.（选址问题（选址问题相互排斥的计

4、划）相互排斥的计划）某公司准备投资某公司准备投资100万元在甲、乙两座城市修建健身中心，万元在甲、乙两座城市修建健身中心，经过多方考察，最后选定经过多方考察，最后选定A1,A2,A3,A4和和A5五个位置，五个位置，并且决定在甲城市的并且决定在甲城市的A1、A2、A3三个位置中最多投建三个位置中最多投建两个；在乙城市的两个；在乙城市的A4、A5两个位置中最少投建一个。如两个位置中最少投建一个。如果已知各点的投资金额和年利润如下表。果已知各点的投资金额和年利润如下表。问：健身中心投建在哪些位置才会使总的年利润最大？问：健身中心投建在哪些位置才会使总的年利润最大？待定地址待定地址A1A2A3A4A

5、5投资总额投资总额投资金额投资金额（万元）（万元）2030254045100年利润年利润（万元）（万元）1025202530第5页/共76页解：设解：设则该问题的数学模型为则该问题的数学模型为第6页/共76页例例 3 工厂选址问题：工厂选址问题：某商品有某商品有n 个销地，各销地的需求量为个销地，各销地的需求量为bj 吨吨/天；现拟在天；现拟在m个地点中选址建生产厂，一个地点最多只能建一个工厂；个地点中选址建生产厂，一个地点最多只能建一个工厂；若选若选i 地建厂，生产能力为地建厂，生产能力为ai吨吨/天，固定费用为天，固定费用为di元元/天；天；已知已知i 地至第地至第j 销地的单位运费为销地

6、的单位运费为cij元元/吨。问如何选址和安吨。问如何选址和安排调运，才能使总费用最小？排调运，才能使总费用最小？设：设：yi=1，表示选择第表示选择第i 地建厂，地建厂，yi=0，表示不选择第表示不选择第i 地建地建厂；从厂址厂；从厂址i 至销地至销地j 运量为运量为xij，总费用为，总费用为z。该问题的数该问题的数学模型为学模型为第7页/共76页例例4 某公司制造小、中、大某公司制造小、中、大3种尺寸的金属容器，所用的资种尺寸的金属容器，所用的资源为金属板、劳动力和机时。制造一只容器所需的各种资源源为金属板、劳动力和机时。制造一只容器所需的各种资源数量如下表所示，不考虑固定费用，每售出一只小

7、、中、大数量如下表所示，不考虑固定费用，每售出一只小、中、大号容器所得的利润分别为号容器所得的利润分别为4元、元、5元、元、6元，可使用的金属板元，可使用的金属板有有500张，劳动力有张，劳动力有300个，机时有个，机时有100小时，如果生产某种小时，如果生产某种容器，不管生产数量多少，都要支付一笔固定费用，小、中、容器，不管生产数量多少，都要支付一笔固定费用，小、中、大号容器的固定费用分别为大号容器的固定费用分别为100元、元、150元、元、200元，现要制元，现要制订一生产计划，使获得的利润最大。订一生产计划，使获得的利润最大。资源资源小号容器小号容器中号容器中号容器大号容器大号容器资源拥

8、有量资源拥有量金属板（张）金属板（张）248500劳动力（个）劳动力（个）234300机时（小时）机时（小时）123100利润利润456第8页/共76页解：设解：设x1,x2,x3分别表示小、中、大号容器的生产数量，分别表示小、中、大号容器的生产数量，M为很大的正数，为很大的正数，z表示总利润表示总利润引入逻引入逻辑变量辑变量若若xj=0时，时，yj=0,若若xj0时，时，yj=1。第9页/共76页2.逻辑变量在整数规划建模中的作用逻辑变量在整数规划建模中的作用(1)m个约束条件中只有个约束条件中只有k个起作用。个起作用。定义定义则上述条件可以表示成则上述条件可以表示成第10页/共76页(2)

9、(2)约束条件的右端可能是约束条件的右端可能是 r r个值中的某一个个值中的某一个定义定义则上述条件可以表示成则上述条件可以表示成第11页/共76页(3)两组条件中满足其中的一组两组条件中满足其中的一组定义定义则问题可以表示为则问题可以表示为第12页/共76页4 4 用以表示含固定费用的函数用以表示含固定费用的函数总费用总费用目标函数是总费用最小目标函数是总费用最小定义定义则目标函数可以表示成则目标函数可以表示成第13页/共76页3.整数规划问题的特征与性质整数规划问题的特征与性质n特征特征变变量整数性要求量整数性要求n来源来源 问题本身的要求问题本身的要求 引入的逻辑变量的需要引入的逻辑变量

10、的需要n性质性质可可行域是离散集合行域是离散集合第14页/共76页第15页/共76页4.4.整数规划的分类整数规划的分类n纯整数规划纯整数规划 要求全部决策变量的取值都为整数要求全部决策变量的取值都为整数,则称为纯整数规划则称为纯整数规划(All IP)；n混合整数规划混合整数规划仅要求部分决策变量的取值为整数，则称为混合整数规仅要求部分决策变量的取值为整数，则称为混合整数规划划(Mixed IP)；0-1整数规划整数规划要求决策变量只能取要求决策变量只能取0或或1值，则称为值，则称为0-1规划规划(0-1 Programming)。第16页/共76页第二节第二节 整数规划的求解方法整数规划的

11、求解方法1.分支定界法分支定界法2.割平面法割平面法第17页/共76页1.1.分支定界法分支定界法整数规划整数规划ILP放松的线性规划放松的线性规划LP分枝定界法是本世纪分枝定界法是本世纪60年代初由年代初由Land Doig和和Dakin等等人提出的，可用于解纯整数规划或混合整数规划。人提出的，可用于解纯整数规划或混合整数规划。第18页/共76页整数规划问题的最整数规划问题的最优目标函数等值线优目标函数等值线放松问题的最优目放松问题的最优目标函数等值线标函数等值线n整数规划的最优解不一定在顶点上达到；整数规划的最优解不一定在顶点上达到；n整数规划的最优解不一定是放松问题最优解的邻近整数整数规

12、划的最优解不一定是放松问题最优解的邻近整数解；解；n整数可行解的个数远多于顶点个数，枚举法不可取。整数可行解的个数远多于顶点个数，枚举法不可取。第19页/共76页整数规划整数规划ILP和放松问题和放松问题LP的关系的关系 ILP的可行区域是的可行区域是LP的可行区域的子集；的可行区域的子集；如果如果LP无可行解，则无可行解，则ILP无可行解；无可行解；LP的最优值是的最优值是ILP的最优值的一个上界；的最优值的一个上界；若若LP的最优解为整数向量，则它也是的最优解为整数向量，则它也是ILP的最优解的最优解。整数规划整数规划ILP放松的线性规划放松的线性规划LP第20页/共76页分枝定界法的基本

13、思想分枝定界法的基本思想先求放松的先求放松的LP的最优解，若放松的最优解，若放松LP问题无解，则原问题无解，则原ILP问题也无解。问题也无解。若放松若放松LP问题的最优解符合整数要求，则是原问题的最优解符合整数要求，则是原ILP的的最优解；最优解；若放松若放松LP问题的最优解含非整数分量，则问题的最优解含非整数分量，则将将ILP问题问题分为几个子问题，试图做到：要么找到某个子问题的分为几个子问题，试图做到：要么找到某个子问题的最优解，要么判断原问题最优解，要么判断原问题ILP的最优解一定不在子问的最优解一定不在子问题的可行区域内。题的可行区域内。第21页/共76页分枝定界法的算法流程：分枝定界

14、法的算法流程：解解LP无可行解无可行解问题无界问题无界ILP无解无解或无界或无界解解x0为整数向量为整数向量x0为为ILP的解的解x0有非整分量有非整分量将原问题分解为两个子问题，使得非整分量恰好排除在外将原问题分解为两个子问题，使得非整分量恰好排除在外而又没有去掉原问题的可行解，再分别判断两个子问题。而又没有去掉原问题的可行解，再分别判断两个子问题。第22页/共76页如果最优解如果最优解x i中某个分量中某个分量 非整非整 分枝定界法的两个要点：分枝和定界分枝定界法的两个要点：分枝和定界如何分枝？如何分枝？第23页/共76页分枝定界法的两个要点：分枝和定界分枝定界法的两个要点：分枝和定界如何

15、定界？如何定界？整数规划整数规划ILP的最优解不会优于松弛的最优解不会优于松弛LP的最优解；的最优解；对极大化问题来说，松弛对极大化问题来说，松弛 LP 的目标函数最优值是原的目标函数最优值是原整数规划整数规划ILP目标函数值的上界；目标函数值的上界；如果当前的如果当前的ILP最好的整数解的目标函数值不小于某最好的整数解的目标函数值不小于某一一 子问题的目标函数值，则可剪枝。子问题的目标函数值，则可剪枝。第24页/共76页例例5 5：求解下列整数线性规划问题：求解下列整数线性规划问题解：先求与之对应的线性规划问题（放松问题）解：先求与之对应的线性规划问题（放松问题）第25页/共76页(18/1

16、1,40/11)z 0=218/11 第26页/共76页B:(1,3),z 1=16C:(2,10/3),z2=56/3 分枝分枝 x1 1,x1 2(LP0)的解不是的解不是(ILP0)的解的解BC第27页/共76页（LP0）z0=218/11x 1=18/11,x 2=40/11（LP1）z1=16x 1=1,x 2=3（LP2）z2=18.66x 1=2,x 2=10/3x 1 1x 1 2LP1有整数解有整数解,已探明已探明,剪枝剪枝,定下界定下界z1=16LP2:z2=18.66 z1=16,可能有比可能有比z1更优的解更优的解分枝分枝:在在LP2 中加入中加入x2 3 x2 4 分

17、成分成(LP3),(LP4)(LP3)max z=x1+5x2 s.t.x1+x2 2 5x1+6x2 30 2 x1 4 x2 3 x1 0,x2 0(LP4)max z=x1+5x2 s.t.x1+x2 2 5x1+6x2 30 2 x1 4 x2 4 x1 0,x2 0第28页/共76页（LP0）z0=218/11x 1=18/11,x 2=40/11（LP1）z1=16x 1=1,x 2=3（LP2）z2=18.66x 1=2,x 2=10/3x 1 1x 1 2 x 2 3x 2 4（LP3）z3=17.4x 1=2.4,x 2=3 LP4 无可行解无可行解(LP5)z 5=17x

18、1=2,x 2=3(LP6)z 6=15.5x 1=3,x 2=5/2x 1 2x 1 3第29页/共76页分枝的方法分枝的方法第30页/共76页定界的方法定界的方法n当前得到的最好整数解的目标函数值当前得到的最好整数解的目标函数值n分枝后计算放松的线性规划的最优解分枝后计算放松的线性规划的最优解整数解整数解非整数解非整数解目标值大于原有最好的目标值：目标值大于原有最好的目标值：替代原有目标值替代原有目标值目标值小于原有最好的目标值：目标值小于原有最好的目标值：删除该分枝删除该分枝目标值大于原有最好的目标值：目标值大于原有最好的目标值：继续分支继续分支目标值小于等于原有最好的目标值：目标值小于

19、等于原有最好的目标值：删除该分枝删除该分枝第31页/共76页2.割平面解法割平面解法（ILP）（LP0）问题问题ILP的放松问题的放松问题第32页/共76页割平面法的基本思想：割平面法的基本思想：如果放松问题如果放松问题(LP0)无解，则无解，则(ILP)无解；无解；如果如果(LP0)的最优解为整数向量，则也是的最优解为整数向量，则也是(ILP)的最优解；的最优解；如果如果(LP0)的解含有非整数分量，则对的解含有非整数分量，则对(LP0)增加增加割平面条件：割平面条件：即对即对(LP0)增加一个线性约束，将增加一个线性约束，将(LP0)的可行区域割掉一块，的可行区域割掉一块，使得非整数解恰好

20、在割掉的一块中，但又没有割掉原问题使得非整数解恰好在割掉的一块中，但又没有割掉原问题(ILP)的可行解，得到问题的可行解，得到问题(LP1)，重复上述的过程。，重复上述的过程。第33页/共76页 割平面法的算法流程：割平面法的算法流程：解解LP0无可行解无可行解问题无界问题无界ILP无解无解或无界或无界解解x0为整数向量为整数向量x0为为ILP的解的解x0有非整分量有非整分量对对LP0增加线性约束将增加线性约束将LP0的可行区域割掉一块的可行区域割掉一块,使得使得x0在割掉在割掉的区域中的区域中,而原问题而原问题ILP的任意可行解都没有割去的任意可行解都没有割去,得到得到LP1第34页/共76

21、页例例6 6：求解下列整数规划问题：求解下列整数规划问题1 1、去掉整数约束，得到松弛问题，化成标准形、去掉整数约束，得到松弛问题，化成标准形第35页/共76页1100CBBbx1x2x3x40 x31-11100 x443101 j011001x13/410-1/41/41x27/4013/41/4 j-5/200-1/2-1/2初始单纯形表初始单纯形表最终单纯形表最终单纯形表最优解（最优解（3/43/4，7/47/4）不是整数向量，需要引入割平面以）不是整数向量，需要引入割平面以得到改进的松弛问题。得到改进的松弛问题。如何引入割平面？如何引入割平面？第36页/共76页由最终的单纯形表得到变

22、量间的关系：由最终的单纯形表得到变量间的关系：将系数和常数项分解成整数和非负真分数之和，移项得将系数和常数项分解成整数和非负真分数之和，移项得由于由于x1,x2是整数，由原问题可知，是整数，由原问题可知，x3,x4也是整数，因此，也是整数，因此，上式左端必为整数。上式左端必为整数。右端右端()内是正数，所以等式右端必为内是正数，所以等式右端必为非正数，即非正数，即切割方程切割方程第37页/共76页引入松弛变量引入松弛变量x5，得到等式，得到等式将这个新的约束加到最优单纯形表中，得到将这个新的约束加到最优单纯形表中，得到11000CBBbx1x2x3x4x51x13/410-1/41/401x2

23、7/4013/41/400 x5-300-3-11 j-5/200-1/2-1/201x111001/3-1/121x2101001/40 x310011/3-1/3 j-2000-1/3-1/6用用对对偶偶单单纯纯形形法法迭迭代代得得第38页/共76页割平面方程等价于割平面方程等价于:即即第39页/共76页第40页/共76页可见，割平面就是结合松弛问题的最优表和原问可见，割平面就是结合松弛问题的最优表和原问题的整数约束，而增加的线性约束。题的整数约束，而增加的线性约束。割平面割掉了包含非整数解的一块可行区域，但割平面割掉了包含非整数解的一块可行区域，但没有割掉任何整数格点。没有割掉任何整数格

24、点。第41页/共76页求割平面的步骤求割平面的步骤：把线性规划最优解中取值为非整数的基变量找出来。把线性规划最优解中取值为非整数的基变量找出来。将该基变量在最优单纯形表中对应的约束的常数和变量将该基变量在最优单纯形表中对应的约束的常数和变量系数分解成整数和非负真分数之和。系数分解成整数和非负真分数之和。提出变量为整数的条件构成切割方程。提出变量为整数的条件构成切割方程。第42页/共76页第三节第三节 指派问题及匈牙利解法指派问题及匈牙利解法1.问题的提出及数学模型问题的提出及数学模型2.匈牙利解法匈牙利解法3.两点说明两点说明4.指派问题的求解软件指派问题的求解软件第43页/共76页1.1.问

25、题的提出及数学模型问题的提出及数学模型例例7：设设某某工工程程有有B1,B2,B3,B4 四四项项任任务务，需需由由四四个个工工人人A1,A2,A3,A4去去完完成成，由由于于任任务务性性质质和和每每个个工工人人的的技技术术水水平平不不相相同同，他他们们完完成成各各项项任任务务所所需需的的时时间间也也不不一一样样（见见下下表表）。问问应应当当如如何何指指派派，即即哪哪个个人人去去完完成成哪哪项任务，才能使完成四项任务的总时间最少？项任务，才能使完成四项任务的总时间最少？任务任务人员人员B1B2B3B4A1215134A21041415A39141613A478119第44页/共76页设设该问题

26、的解为该问题的解为用矩阵形式表示为用矩阵形式表示为:解矩阵解矩阵第45页/共76页设有设有n 项任务，需有项任务，需有n 个人去完成，每个人只能完成一个人去完成，每个人只能完成一项任务，每项任务只能由一个人去完成，设第项任务，每项任务只能由一个人去完成，设第i 人完成人完成第第j 项任务需要的时间是项任务需要的时间是aij,问如何指派才能使完成任问如何指派才能使完成任务的总时间最少务的总时间最少？设设一般指派问题一般指派问题指派问题是一种特殊的运输问题，特殊在哪里？指派问题是一种特殊的运输问题，特殊在哪里？高度退化！高度退化！因而一般不使用表上作业法求解。因而一般不使用表上作业法求解。第46页

27、/共76页2.2.匈牙利解法匈牙利解法定义定义 1 1 效率矩阵效率矩阵其中其中aij 0表示第表示第i 人完成第人完成第j项任务的效率（时间、费项任务的效率（时间、费用等）。用等）。定义定义 2 2 任务的一种分配方法称为一个任务的一种分配方法称为一个匹配匹配。（指。（指派问题的一个解），使目标函数取得最小值的匹配派问题的一个解），使目标函数取得最小值的匹配称为称为最优匹配最优匹配（最优解最优解）特点：每行恰有一个特点：每行恰有一个1 1；每列恰有一个每列恰有一个1 1。第47页/共76页匈牙利方法的基本思想匈牙利方法的基本思想如果效率矩阵的所有元素如果效率矩阵的所有元素aij0,而其中存在

28、一组位于而其中存在一组位于不同行不同列的不同行不同列的0元素元素,则只要令对应于这些位置的则只要令对应于这些位置的xij=1，其余其余xij=0，就可以得到指派问题的最优解。就可以得到指派问题的最优解。效率矩阵：效率矩阵：最优解最优解问题：如何产生这组独立问题：如何产生这组独立0 0元素？元素？定义定义 3 3 位于效率矩阵的不同行不同列的位于效率矩阵的不同行不同列的0 0元素称为独立元素称为独立0 0元素。元素。第48页/共76页定理定理 1：如果从效率矩阵如果从效率矩阵A的每一行元素中分别减去（或的每一行元素中分别减去（或加上）一个常数加上）一个常数ui，从每一列元素中分别减去（或加上）从

29、每一列元素中分别减去（或加上）一个常数一个常数vj，得到一个新的效率矩阵得到一个新的效率矩阵B，其中其中bij=aij-ui-vj,则则B对应的指派问题与对应的指派问题与A对应的指派问题同解。对应的指派问题同解。定理定理 2 2 效率矩阵中独立效率矩阵中独立0 0元素的最多个数等于能覆元素的最多个数等于能覆盖所有盖所有0 0元素的最少直线数。元素的最少直线数。00 000 独立独立0 0元最多两个；元最多两个；至少需用两条直线至少需用两条直线覆盖所有覆盖所有0 0元素。元素。证明证明:将将B B中的数据代入目标函数中的数据代入目标函数,有有:第49页/共76页匈牙利解法的基本步骤匈牙利解法的基

30、本步骤第一步：初始变换获得第一步：初始变换获得0 0元素。元素。从效率矩阵的每行减去该行的最小元素；然后从所得矩从效率矩阵的每行减去该行的最小元素；然后从所得矩阵的每列减去该列的最小元素，令所得矩阵为阵的每列减去该列的最小元素，令所得矩阵为B.第二步：在第二步：在B B中寻找位于不同行、不同列的中寻找位于不同行、不同列的0 0元素。元素。（1 1）检查）检查B B的每行每列，从中找出未加标记的的每行每列，从中找出未加标记的0 0元素最少元素最少的一排（即行列的统称），在该排用的一排（即行列的统称），在该排用()()标出一个标出一个0 0元，若元，若该排有多个该排有多个0 0元，则任意标出一个即

31、可；元，则任意标出一个即可；（2 2）把刚得到）把刚得到()()号标记的号标记的0 0元所在的行、列中的其余元所在的行、列中的其余0 0元元划去，用划去，用表示；表示；（3 3）凡是）凡是(0 0)，就成为加了标记的就成为加了标记的0 0元，返回（元，返回（1 1）重复（重复（1 1）、（）、（2 2）、（）、（3 3），直到所有），直到所有0 0元都加上标记为元都加上标记为止。若得到的加止。若得到的加()()号的号的0 0元素个数等于元素个数等于n n，则结束；否则则结束；否则转第三步转第三步第50页/共76页第三步：找出能覆盖矩阵中所有第三步：找出能覆盖矩阵中所有0 0元素的最少直线集合。

32、元素的最少直线集合。（1 1）对没有）对没有(0 0)的行打的行打；（2 2）对已经打）对已经打的行中所有的行中所有元素所在的列打元素所在的列打；（3 3）再对打）再对打的列中所有的列中所有(0 0)元素所在的行打元素所在的行打；（4 4）重复（）重复（2 2）（）（3 3）直到得不出新的打）直到得不出新的打的行、列为至；的行、列为至；（5 5）对没有打）对没有打 的行和打的行和打的列划线，即为覆盖所有的列划线，即为覆盖所有0 0元素的最少直线。元素的最少直线。第四步：修改矩阵第四步：修改矩阵B B以增加独立以增加独立0 0元素的个数。元素的个数。（1 1）在未被直线覆盖的所有元素中，找出最小

33、元素；）在未被直线覆盖的所有元素中，找出最小元素；（2 2）所有打）所有打的行都减去此最小元素，然后所有打的行都减去此最小元素，然后所有打的列都加上此最小元素，令这个新矩阵为的列都加上此最小元素，令这个新矩阵为B B，返回第二步。返回第二步。第51页/共76页例例8：用匈牙利解法解例：用匈牙利解法解例7 7效率矩阵效率矩阵第一步：初始变换第一步：初始变换2151341041415914161378119249701311260101105740142004201370606905320100第52页/共76页得解矩阵得解矩阵找独立找独立0 0元素元素01370606905320100总时间为总

34、时间为:4+4+9+11=28:4+4+9+11=28第53页/共76页例例3 3：用匈牙利解法解下列指派问题：用匈牙利解法解下列指派问题效率矩阵效率矩阵第一步：初始变换第一步：初始变换00000127979896667171214915146610410710912797989666717121491514661041071097676450202230000105729800406365第54页/共76页50202230000105729800406365第二步：寻找独立第二步：寻找独立0 0元素元素最小元素为最小元素为 min10,5,7,2,6,3,6,5=2-2-2+2第55页/共7

35、6页70202430000835011800404143它有它有5 5个独立个独立0 0元，得到最优解相应的解矩阵为元，得到最优解相应的解矩阵为最优目标值：最优目标值：7+6+9+6+4=32第56页/共76页课堂练习：求解下列指派问题课堂练习：求解下列指派问题效率矩阵效率矩阵10978587754652345 工作工作人员人员ABCD甲甲10978乙乙5877丙丙5465丁丁2345第57页/共76页 109785877546523457542320103221021012300013200032110200122-1-1+1第58页/共76页420002102020001142000210

36、20200011第一组最优解第一组最优解第二组最优解第二组最优解第59页/共76页两点说明两点说明1.1.效率矩阵不是方阵的情况。（即人员与工作数不效率矩阵不是方阵的情况。（即人员与工作数不相等）相等）处理方法处理方法：增加虚拟人或工作，使两者相等。虚：增加虚拟人或工作，使两者相等。虚拟人或工作对应的效率矩阵中元素为拟人或工作对应的效率矩阵中元素为0 0。2.2.最大化指派问题的处理。最大化指派问题的处理。如果给出的效率矩阵中的数字表示每个人完成各项如果给出的效率矩阵中的数字表示每个人完成各项任务的收益，则问题变成了如何指派任务才能使总任务的收益，则问题变成了如何指派任务才能使总收益最大？收益

37、最大？处理方法处理方法：用效率矩阵中的最大元减去矩阵中的各：用效率矩阵中的最大元减去矩阵中的各个元素得到一个新的矩阵，对这个新的矩阵用匈牙个元素得到一个新的矩阵，对这个新的矩阵用匈牙利方法求解。利方法求解。第60页/共76页例例9 9：有四项工作分配给六个人去完成，每个人分别完：有四项工作分配给六个人去完成，每个人分别完成各项工作的时间如下表所示，仍然规定每个人只能完成各项工作的时间如下表所示，仍然规定每个人只能完成一项工作，每项工作只交给一个人去完成，问挑选哪成一项工作，每项工作只交给一个人去完成，问挑选哪四个人去完成工作，花费的总时间最少？四个人去完成工作，花费的总时间最少？工作工作人员人

38、员B1B2B3B4A13626A27144A33658A46437A55243A65762 工作工作人员人员B1B2B3B4B5B6A1362600A2714400A3365800A4643700A5524300A6576200第61页/共76页例例10 指派甲、乙、丙、丁四个人去完成指派甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每个人完成各项任务的时间如下表，由于任务数五项任务，每个人完成各项任务的时间如下表，由于任务数多于人数，故考虑：多于人数，故考虑：任务任务 人员人员ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁2442362345（

39、1 1）任务任务E必须完成，其他必须完成，其他4项中任选项中任选3项完成；项完成；（2）其中有一人完成两项，其他每人完成一项；）其中有一人完成两项，其他每人完成一项；（3）任务）任务A由甲或丙完成，任务由甲或丙完成，任务C由丙或丁完成，任务由丙或丁完成，任务E 由由甲、乙或丁完成，且规定甲、乙或丁完成，且规定4人中丙或丁完成两项任务，其他人中丙或丁完成两项任务，其他每人完成一项；每人完成一项；试分别确定最优指派方案，使完成任务的总时间最少。试分别确定最优指派方案，使完成任务的总时间最少。第62页/共76页 任务任务 人员人员ABCDE甲甲2529314237乙乙3938262033丙丙3427

40、284032丁丁2442362345戊戊0000M（1）任务）任务E必须完成，其他必须完成，其他4项中任选项中任选3项完成；项完成；第63页/共76页（2）其中有一人完成两项，其他每人完成一项；）其中有一人完成两项，其他每人完成一项；任务任务 人员人员ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁2442362345戊戊2427262032由于虚拟人完成的工作需要转给甲乙丙丁，因此，虚由于虚拟人完成的工作需要转给甲乙丙丁，因此，虚拟人完成各项工作的时间等于四个人完成该工作的最拟人完成各项工作的时间等于四个人完成该工作的最短时间。短时间。第64页/共76页

41、（3）任务）任务A由甲或丙完成，任务由甲或丙完成，任务C由丙或丁完成，任由丙或丁完成，任务务E 由甲、乙或丁完成，且规定由甲、乙或丁完成，且规定4人中丙或丁完成两人中丙或丁完成两项任务，其他每人完成一项；项任务，其他每人完成一项；任务任务 人员人员ABCDE甲甲2529M4237乙乙M38M2033丙丙34272840M丁丁M42362345戊戊3427282345虚拟人完成某项工作的时间等于丙、丁完成该工作虚拟人完成某项工作的时间等于丙、丁完成该工作的时间中较小者。的时间中较小者。第65页/共76页例例1111：假设有：假设有3 3项工作项工作A,B,C需要指派给需要指派给3个工人甲、乙、个

42、工人甲、乙、丙去做，由于每个人的工作能力和技术水平不同，因而丙去做，由于每个人的工作能力和技术水平不同，因而完成各项工作的收益也不同，完成各项工作的收益也不同，3 3个人的工作收益如下表所个人的工作收益如下表所示，问如何安排工作才能使总收益达到最大？示，问如何安排工作才能使总收益达到最大？工作工作工人工人ABC甲甲1024乙乙787丙丙395效率矩阵效率矩阵102478739508632371510-10-各元素各元素021086101604001085100603解矩阵解矩阵指派甲完成工作指派甲完成工作A，乙完成工作乙完成工作C，丙完成工作丙完成工作B，总收益为总收益为10+7+9=26。第

43、66页/共76页指派问题的求解软件指派问题的求解软件（WINQSB）(1)进入进入WINQSB选择选择Network Modeling模块模块(2)选取选取Assignment Problem；输入问题名称、人员输入问题名称、人员数、工作数，选择目标函数类型，数据输入方式，数、工作数，选择目标函数类型，数据输入方式，按按OK进入数据输入窗口；进入数据输入窗口；(3)输入效率矩阵；输入效率矩阵；(4)按按Solve Problem求解求解。第67页/共76页第68页/共76页第69页/共76页第70页/共76页第71页/共76页第72页/共76页第73页/共76页第74页/共76页P144 必做：必做：4（1）选做：选做：7、8作业：作业：第75页/共76页感谢您的观看。感谢您的观看。第76页/共76页