运筹学课件第五章整数规划.ppt

《运筹学课件第五章整数规划.ppt》由会员分享，可在线阅读，更多相关《运筹学课件第五章整数规划.ppt（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第第1页页1第五章第五章 整数规划整数规划Integer linear programming第第2页页第一节第一节 整数规划的数学模型整数规划的数学模型一、整数规划问题一、整数规划问题 整数规划问题（整数规划问题（IP）:是指要求部分是指要求部分或全部决策变量的取值为整数的规划问或全部决策变量的取值为整数的规划问题。题。松弛问题：松弛问题：不考虑整数条件，由余不考虑整数条件，由余下的目标函数和约束条件构成的规划问下的目标函数和约束条件构成的规划问题。题。重点研究：重点研究：整数线性规划问题整数线性规划问题第第3页页二、整数线性规划问题的模型二、整数线性规划问题的模型j=1,2,ni=1,2,

2、mxj 中取部分或全部为整数中取部分或全部为整数第第4页页三、整数规划问题的类型：三、整数规划问题的类型：3.混合整数规划混合整数规划：部分决策变量取整数：部分决策变量取整数 值的线性规划值的线性规划 1.纯整数规划纯整数规划：全部决策变量都取整数：全部决策变量都取整数 值的线性规划值的线性规划2.0-1型整数规划型整数规划：决策变量只取：决策变量只取0 或或1的线性规划的线性规划第第5页页例例1:某服务部门各时段（每某服务部门各时段（每2h为一时段）需为一时段）需要的服务员人数见下表。按规定服务员连续要的服务员人数见下表。按规定服务员连续工作工作8h（即四个时段）为一班。现要求安排（即四个时

3、段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数服务员的工作时间，使服务部门服务员总数最少？最少？时段12345678服务员最少数目10891113853举例举例第第6页页minZ=x1+x2+x3+x4+x5x1 10 x1+x2 8x1+x2+x3 9x1+x2+x3+x4 11x2+x3+x4+x5 13x3+x4+x5 8x4+x5 5x5 3xj 0(j=1,5)且为整数且为整数解：设在第解：设在第j时段开始时上班的服务员人时段开始时上班的服务员人数为数为xj这是一个纯整数规划第第7页页例例2：现有资金总额为：现有资金总额为B。可供选择的投资项可供选择的投资项目有目有n个

4、，项目个，项目j所需投资额和预期收益分别所需投资额和预期收益分别为为aj和和cj,此外，因种种原因，有此外，因种种原因，有3个附加条件：个附加条件：若选择项目若选择项目1必须同时选择项目必须同时选择项目2，反之不一，反之不一定；项目定；项目3和项目和项目4中至少选择一个；第三，中至少选择一个；第三，项目项目5、6、7中恰好选择两个。应当怎样选择中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？投资项目，才能使总预期收益最大？第第8页页1 对项目对项目 j 投资投资0 对项目对项目 j 不投资不投资 xj=Max Z=cjxjajxjBx2 x1x3+x4 1x5+x6+x7=2xj=

5、0或或1（j=1,2,n）解：令解：令这是一个这是一个 0-1 0-1规划规划j=1,.,n第第9页页 例例3 3 工厂工厂A A1 1和和A A2 2生产某种物资，由于该种生产某种物资，由于该种物资供不应求，还需要再建一家工厂。由两物资供不应求，还需要再建一家工厂。由两个待选方案个待选方案A A3 3和和A A4 4。物资需求地为物资需求地为B Bj j(j(j=1,2,3,4)=1,2,3,4)。各工厂年生产能力、各地各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费年需求量、各厂至各需求地的单位物资运费见下表。工厂见下表。工厂A A3 3和和A A4 4的生产费用估计为的生产费

6、用估计为12001200万元或万元或15001500万元。选择哪一个方案才能使总万元。选择哪一个方案才能使总费用（包括物资运费和新工厂的生产费用）费用（包括物资运费和新工厂的生产费用）最小。最小。第第10页页B1B2B3B4生产能力A12934400A28357600A37612200A44525200需求量350400300150第第11页页 1 若建工厂若建工厂A3 0 若建工厂若建工厂A4再设再设xij为由为由Ai送往送往Bj 的物资数量的物资数量(i,j=1,.,4)则总费用为则总费用为解解:令令 y=第第12页页x11+x21+x31+x41=350 x12+x22+x32+x42=

7、400 x13+x23+x33+x43=300 x14+x24+x34+x44=150 x11+x12+x13+x14=400 x21+x22+x23+x24=600 x31+x32+x33+x34=200yx41+x42+x43+x44=200(1-y)xij0,y=0或或1混混合合整整数数规规划划第第13页页引例：某厂利用集装箱托运甲、乙两种货物，引例：某厂利用集装箱托运甲、乙两种货物，每箱体积、重量每箱体积、重量 、可获利润及托运限制如下：、可获利润及托运限制如下：体积重量利润甲5220乙4510托运限制2413两种货物各托运多少箱使利润最大？两种货物各托运多少箱使利润最大？四、解的特点

8、四、解的特点第第14页页Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20，且为整数且为整数第第15页页Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20，x2x1松弛问题：松弛问题：第第16页页Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20 x2x1第第17页页Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20 x2x1(4.8,0 )AZ=96第第18页页(4.8,0 )AZ=96Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x2

9、0 x2x1x1,x2 为整数为整数第第19页页Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20 x1,x2 为整数为整数x2x1(4.8,0 )AZ=96第第20页页Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20 x2x1(4.8,0 )AZ=96x1,x2 为整数为整数(4,0)Z=80(5,0)不在可行域不在可行域(4,1)max Z=90第第21页页（5）ILP是其中是其中LP的一个子问题，所有解的一个子问题，所有解也是也是LP的可行解，所以如果的可行解，所以如果LP的最优解满的最优解满足足ILP的整数条件，则已得最

10、优解。的整数条件，则已得最优解。注释：注释：（4）整数规划问题的可行域是它的松弛问）整数规划问题的可行域是它的松弛问题可行域的子集，所以松弛问题得最优解优题可行域的子集，所以松弛问题得最优解优于整数规划问题的最优解。于整数规划问题的最优解。（1）最优解不一定在顶点上达到）最优解不一定在顶点上达到（2）最优解不一定是放松问题最优解的邻）最优解不一定是放松问题最优解的邻近整数解近整数解（3）枚举法不可取）枚举法不可取第第22页页第二节第二节 解纯整数规划的割平面法解纯整数规划的割平面法考虑纯整数规划问题：考虑纯整数规划问题：其中其中ai j和和bi 皆为整数。皆为整数。(ILP)第第23页页一、一

11、、割平面法（割平面法（Gomory法）基本思想法）基本思想 利用单纯形法求得其松弛问题的最优解，利用单纯形法求得其松弛问题的最优解，若不满足整数条件，则若不满足整数条件，则将松弛问题的可行域将松弛问题的可行域切割一部分，但不切割掉任何整数解，只切切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。割掉包括松弛问题的最优解在内的非整数解。即增加线性约束条件于即增加线性约束条件于原松弛问题中，形成原松弛问题中，形成一个新的线性规划，逐渐缩小解的范围，又一个新的线性规划，逐渐缩小解的范围，又不去掉整数解，直至找到最优解为整数解为不去掉整数解，直至找到最优解为整数解为止。止。

12、第第24页页x0 x1x*第第26页页二、割平面约束的构造二、割平面约束的构造 在松弛问题的最优单纯性表中，记在松弛问题的最优单纯性表中，记s为基为基变量的下标集，变量的下标集，为非基变量的下标集。为非基变量的下标集。m个约束方程可表示为个约束方程可表示为:第第27页页将系数和常数分解为整数将系数和常数分解为整数N和正真分数和正真分数f之和，即：之和，即：割平面约束割平面约束上式左端是整数，右端上式左端是整数，右端1，因此，因此第第28页页割平面约束条件的性质割平面约束条件的性质(2)(2)有上面的推导知，有上面的推导知，凡是满足凡是满足ILPILP约束条件约束条件的整数可行解均满足该约束条件

13、。的整数可行解均满足该约束条件。因此因此约束条件满足两个基本性质，把它加约束条件满足两个基本性质，把它加入到松弛问题中得一新的线性规划。入到松弛问题中得一新的线性规划。(1)由于非基变量由于非基变量xj取值为取值为0 0，所以，所以第第29页页第第30页页三、割平面法求解举例三、割平面法求解举例Max Z=x1+x2-x1+x213x1+x2 4x1,x20且为整数且为整数Max Z=x1+x2-x1+x213x1+x2 4x1,x20-x1+x2+x3 =13x1+x2 +x4=4x1,x2 ,x3,x40松弛规划松弛规划例例1第第31页页松弛问题的最优单纯形表为：松弛问题的最优单纯形表为：

14、CBXBb1100 x1x2x3x40 x31-11100 x443101j11001x13/410-1/41/41x27/4013/41/4j00-1/2-1/2第第32页页第第33页页将将-3x3-x4+x5=-3（割平面方程割平面方程）代入最优表代入最优表CBXBb11000 x1x2x3x4x51x13/410-1/41/401x27/4013/41/400 x5-300-3-11j00-1/2-1/201x111001/31/121x2101001/40 x310011-1/3j000-1/3-1/3第第34页页MaxZ=3x1-x23x1-2x235x1+4x2102x1+x25x

15、1,x20 且为整数且为整数MaxZ=3x1-x23x1-2x235x1+4x2102x1+x25x1,x20例例2 用割平面法求解纯整数规划用割平面法求解纯整数规划松弛规划松弛规划最终单纯形表如下：最终单纯形表如下：第第35页页CBXBb3-1000 x1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70 x431/700-3/7122/7Z=30/7j00-5/70-3/7x1+1/7x3+2/7x5=13/7 x1+1/7x3+2/7x5=1+6/7x1-1=6/7-（1/7x3+2/7x5）6/7-（1/7x3+2/7x5）0-1/7x3-2/7x5-

16、6/7 第第36页页-1/7x3-2/7x5-6/7-1/7x3-2/7x5+x6=-6/7CBXBb3-10000 x1x2x3x4x5x63x113/7101/702/70-1x29/701-2/703/700 x431/700-3/7122/700 x6-6/700-1/70-2/71j00-5/70-3/70第第37页页CBXBb3-10000 x1x2x3x4x5x63x11100001-1x25/4010-1/40-5/40 x35/2001-1/20-11/20 x57/40001/41-3/4Z=7/400000-17/4-1/4x4-1/4x6-3/4-1/4x4-1/4x6

17、+x7=-3/4第第38页页CBXBb3-100000 x1x2x3x4x5x6x73x111000010-1x2201000-1-10 x3400100-5-20 x5100001-110 x43000101-4Z=-1j00000-4-1-1/4x4-1/4x6+x7=-3/4第第39页页第三节第三节 分支定界法分支定界法例例1松弛问题松弛问题第第40页页(11/4,9/4)Z=31/4(3,3/2)Z=15/2(2,2)Z=6无无 解解无无 解解(11/4,9/4)x12x13(2,2)(3,3/2)x21x22(19/6,1)Z=22/3(3,1)Z=7(19/6,1)x13x141

18、2 3 4 3 2 1最优值为最优值为Z=7，最优解为，最优解为(3,1)第第41页页一、基本思想一、基本思想（1 1）分支：）分支：如果松弛线性规划的最优解不符合如果松弛线性规划的最优解不符合整数要求，即至少有一个分量不是整数，整数要求，即至少有一个分量不是整数，假设假设 则构造两个约束条件则构造两个约束条件分别加入松弛问题中，把线性规划的可行域切分别加入松弛问题中，把线性规划的可行域切割成两部分，形成两个分支，分别求解这两个割成两部分，形成两个分支，分别求解这两个线性规划，线性规划，如果这两个线性规划的最优解还不如果这两个线性规划的最优解还不是整数解，分别把每一个可行域再进行分割。是整数解

19、，分别把每一个可行域再进行分割。如此继续下去，直到获得整数规划的最优解。如此继续下去，直到获得整数规划的最优解。不是整数，不是整数，第第42页页（2 2）定界：）定界：分支过程得到的整数解中，目标分支过程得到的整数解中，目标函数值最优的一个叫做整数规划目标函数值的函数值最优的一个叫做整数规划目标函数值的“界界”。分支过程中非整数的线性规划的最优。分支过程中非整数的线性规划的最优解，如果目标函数值劣于或等于这个解，如果目标函数值劣于或等于这个“界界”，就停止继续分支。就停止继续分支。一、基本思想一、基本思想第第43页页原问题原问题A MaxZ=40 x1+90 x29x1+7x2567x1+20

20、 x2 70 x1,x20 x1,x2 都为整数都为整数MaxZ=40 x1+90 x29x1+7x2567x1+20 x2 70 x1,x20 松弛问题松弛问题B例例2分支定界法如下分支定界法如下第第44页页 问题问题B x1=4.81,x2=1.82 Z=356Z=356Z=0 问题问题C1 x1=4,x2=2.1 Z=349 问题问题C2x1=5,x2=1.57 Z=341x14x15Z=349Z=0 x22x23问题问题D1 x1=4,x2=2 Z=340问题问题D2 x1=1.42 x2=3 Z=327Z=349 Z=340 x21x22问题问题D3 x1=5.44 x2=1 Z=3

21、08Z*=340问题问题D4无可行无可行解解第第45页页第四节第四节 0-1型整数规划型整数规划一、一、0-1变量的概念变量的概念 0-1变量变量：一种逻辑变量，常用来表示系统：一种逻辑变量，常用来表示系统处于某个特定状态，或者决策时是否取某处于某个特定状态，或者决策时是否取某个特定方案。个特定方案。x=1 当决策取方案当决策取方案P时时 0 当决策不取方案当决策不取方案P时时第第46页页现有资金总额为现有资金总额为B。可供选择的投资项目有可供选择的投资项目有n个，项个，项目目j所需投资额和预期收益分别为所需投资额和预期收益分别为aj和和cj,此外，因种此外，因种种原因，有种原因，有3个附加条

22、件：若选择项目个附加条件：若选择项目1必须同时选必须同时选择项目择项目2，反之不一定；项目，反之不一定；项目3和项目和项目4中至少选择一中至少选择一个；第三，项目个；第三，项目5、6、7中恰好选择两个。应当怎样中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？选择投资项目，才能使总预期收益最大？二、二、0-10-1变量的实际应用变量的实际应用1.1.制定相互排斥的计划制定相互排斥的计划例例1 1：投资场所的选定：投资场所的选定第第47页页1 对项目对项目 j 投资投资0 对项目对项目 j 不投资不投资 xj=Max Z=cjxjajxjBx2 x1x3+x4 1x5+x6+x7=2x

23、j=0或或1（j=1,2,n）解：令解：令j=1,.,n第第48页页2.相互排斥的约束条件问题相互排斥的约束条件问题例：集装箱运货（用车运或用船运）例：集装箱运货（用车运或用船运）车运车运 体积体积船运船运 体积体积单位单位 重量重量单位单位 利利润润甲甲57220乙乙43510托运托运限制限制244513两种货物各托运多少箱可以使利润最大？两种货物各托运多少箱可以使利润最大？第第49页页Max Z=20 x1+10 x25x1+4x224+yM7x1+3x245+(1-y)M2x1+5x213x1,x20，y=0或或1x1,x2为整数为整数y=1 船运船运 0 车运车运解：解：x1，x2 分

24、别为甲乙分别为甲乙两种货物托运的箱数两种货物托运的箱数第第50页页 产品产品资源资源资源量资源量A248500B234300C123100单件可变费用单件可变费用456固定费用固定费用100150200单价单价810123.固定费用问题固定费用问题 例：有三种资源被用于生产三种产品，资源量、产例：有三种资源被用于生产三种产品，资源量、产品单件可变费用、售价、资源单耗量及组织三种产品单件可变费用、售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划品生产的固定费用见下表。要求制定一个生产计划使总收益为最大。使总收益为最大。第第51页页解：设解：设xj 为生产第为生产第 j 种

25、产品的数量种产品的数量(件件)2x1+4x2+8x35002x1+3x2+4x3300 x1+2x2+3x3100 x1 M1y1 x2 M2y2 x3 M3y3xj 0且为整数，且为整数，j=1,2,3yj=0或或1，j=1,2,3 max Z=4x1+5x2+6x3-100y1-150y2-200y3第第52页页4.工件排序问题工件排序问题例：例：4 4台机床加工台机床加工3 3件产品，件产品，产品产品i在机床在机床j上的加工上的加工工时为工时为aij产品产品1a11 a13 a14机床机床1 机床机床3 机床机床4产品产品2a21 a22 a24机床机床1 机床机床2 机床机床4产品产品

26、3a32 a33 机床机床2 机床机床3制定加工方案，使最短的时间内加工完全部产品制定加工方案，使最短的时间内加工完全部产品第第53页页解：设解：设xi表示产品表示产品i在机床在机床j上上开始开始加工时间加工时间（1 1）同一产品在不同机床上的加工顺序约束）同一产品在不同机床上的加工顺序约束产品产品1a11 a13 a14机床机床1 机床机床3 机床机床4产品产品2a21 a22 a24机床机床1 机床机床2 机床机床4产品产品3a32 a33 机床机床2 机床机床3产品产品1 1：x11+a11x13及及 x13+a13x14产品产品2 2：x21+a21x22及及 x22+a22x24产品

27、产品3 3：x32+a32x33第第54页页（2 2）每台机床对不同产品加工顺序约束）每台机床对不同产品加工顺序约束产品产品1a11 a13 a14机床机床1 机床机床3 机床机床4产品产品2a21 a22 a24机床机床1 机床机床2 机床机床4产品产品3a32 a33 机床机床2 机床机床3机床机床1 1：x11+a11x21+My1及及:x21+a21x11+M(1-y1)机床机床2 2：x22+a22x32+My2及及:x32+a32x22+M(1-y2)机床机床3 3：x13+a13x33+My3及及:x33+a33x13+M(1-y3)机床机床4 4：x14+a14x24+My4及

28、及:x24+a24x14+M(1-y4)第第55页页（3 3）产品）产品2 2加工总时间约束加工总时间约束产品产品1a11 a13 a14机床机床1 机床机床3 机床机床4产品产品2a21 a22 a24机床机床1 机床机床2 机床机床4产品产品3a32 a33 机床机床2 机床机床3x24+a24-x21 d第第56页页（4 4）目标函数的建立）目标函数的建立产品产品1a11 a13 a14机床机床1 机床机床3 机床机床4产品产品2a21 a22 a24机床机床1 机床机床2 机床机床4产品产品3a32 a33 机床机床2 机床机床3W=max(x14+a14,x24+a24,x33+a3

29、3)设全部产品加工完毕的结束时间为设全部产品加工完毕的结束时间为W目标函数目标函数Z为为第第57页页模型为：模型为：x11+a11x13x13+a13x14x21+a21x22 x22+a22x24x32+a32x33x11+a11x21+My1x21+a21x11+M(1-y1)x22+a22x32+My2x32+a32x22+M(1-y2)x13+a13x33+My3x33+a33x13+M(1-y3)x14+a14x24+My4x24+a24x14+M(1-y4)x24+a24-x21 d第第58页页三、三、0-1型整数规划的解法型整数规划的解法 隐枚举法隐枚举法 隐枚举法隐枚举法：不同

30、于穷举法，只检查变量取：不同于穷举法，只检查变量取值组合的一部分就能找到问题的最优解。值组合的一部分就能找到问题的最优解。解题关键是寻找可行解，产生过滤条件。解题关键是寻找可行解，产生过滤条件。过滤条件：过滤条件：目标函数值优于计算过的可行目标函数值优于计算过的可行解目标函数值。解目标函数值。第第59页页(x1,x2,x3)Z值约束条件 过滤条件(0,0,0)0 Z0（0,0,1)5 Z5（0,1,0)-2（0,1,1)3（1,0,0)3（1,0,1)8 Z8（1,1,0)1（1,1,1)6maxZ=3X1-2X2+5X3X1+2X2-X3 2 X1+4X2+X3 4 X1+X2 3 4X2+

31、X3 6 X1,X2,X3 =0 或或 1 例例1第第60页页XZ值约束条件 过滤条件(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,0,1,1)(0,1,0,0)(1,1,1,1)例例2目标函数有大到小排列目标函数有大到小排列第第61页页第五节第五节 指派问题指派问题 一、典型的指派问题一、典型的指派问题 某单位需完成某单位需完成n项任务，恰有项任务，恰有n个人可个人可以承担，由于每个人的专长不同，各人完以承担，由于每个人的专长不同，各人完成任务的效率不同，各人完成一项任务的成任务的效率不同，各人完成一项任务的同时，不能同时去做其它任务，如何分配同时，不能同时去做其它任务，如何分

32、配任务会使所需的时间最小或成本最低。任务会使所需的时间最小或成本最低。第第62页页 例：有一份中文说明书，需译成英、日、例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记做德、俄四种文字，分别记做E、J、G、R。现有甲、乙、丙、丁现有甲、乙、丙、丁4人，他们将中文说明人，他们将中文说明书翻译成不同语种的说明书所需的时间如下，书翻译成不同语种的说明书所需的时间如下，问应指派何人去完成何种工作，使所需总时问应指派何人去完成何种工作，使所需总时间最少？间最少？第第63页页 任务人员EJGR甲215134乙1041415丙9141613丁78119 例：例：有一份中文说明书，需译成英、日、德、

33、俄四有一份中文说明书，需译成英、日、德、俄四种文字，分别记做种文字，分别记做E、J、G、R。现有甲、乙、丙、现有甲、乙、丙、丁丁4人，他们将中文说明书翻译成不同语种的说明书人，他们将中文说明书翻译成不同语种的说明书所需的时间如下，问应指派何人去完成何种工作，所需的时间如下，问应指派何人去完成何种工作，使所需总时间最少？使所需总时间最少？第第64页页指派问题的标准形式指派问题的标准形式 n个人，个人，n件事，第件事，第i个人做第个人做第j件事的费用为件事的费用为cij,确确定人和事之间一一对应的指派方案，使完成定人和事之间一一对应的指派方案，使完成n件件事的总费用最小。事的总费用最小。效率效率矩

34、阵矩阵或或系数系数矩阵矩阵C=(cij)nn=c11 c12 c1n c21 c22 c2n cn1 cn1 cnn 第第65页页C=(cij)nn=2151341041415914161378119第第66页页二、标准指派问题的数学模型二、标准指派问题的数学模型xij=1 指派第指派第 i 个人做第个人做第 j 件事件事0 不指派第不指派第 i 个人做第个人做第 j 件事件事j=1,2,ni=1,2,nxij=1或或0第第67页页 解矩阵：解矩阵：满足约束条件的可行解也可以满足约束条件的可行解也可以写成表格或矩阵的形式，称为解矩阵。写成表格或矩阵的形式，称为解矩阵。例：例：X=(xij)44

35、=010 000011 0 0 00 0 1 0第第68页页三、匈牙利解法三、匈牙利解法（1）关键性质关键性质：若从指派问题的系数矩阵若从指派问题的系数矩阵(cij)nn的某的某行或某列各元素中分别减一个常数行或某列各元素中分别减一个常数k,得到得到的新矩阵与原矩阵有相同的最优解。的新矩阵与原矩阵有相同的最优解。C=(cij)nn=2151341041415914161378119第第69页页C=(cij)nn=2151341041415914161378119第第70页页C=(cij)nn=01370606905320100匈牙利法的步骤匈牙利法的步骤1.变换系数矩阵变换系数矩阵第第71页页

36、C=(cij)nn=01370606905320100匈牙利法的步骤匈牙利法的步骤2.寻找独立寻找独立“0”元元素素若有若有n个，计算结束个，计算结束若少于若少于n个，转个，转3第第72页页C=(cij)nn=137669 532 1匈牙利法的步骤匈牙利法的步骤2.寻找独立寻找独立“0”元元素素若有若有n个，计算结束个，计算结束若少于若少于n个，转个，转3第第73页页C=(cij)nn=2151341041415914161378119Min Z=c31+c22+c43+c14=4+4+9+11=28第第74页页匈牙利法的步骤匈牙利法的步骤2.寻找独立寻找独立“0”元元素素若有若有n个，计算结

37、束个，计算结束若少于若少于n个，转个，转3130页例页例13C=(cij)nn=4 8 7 15 127 9 17 14 106 9 12 8 76 7 14 6 106 9 12 10 6第第75页页匈牙利法的步骤匈牙利法的步骤2.寻找独立寻找独立“0”元元素素若有若有n个，计算结束个，计算结束若少于若少于n个，转个，转3130页例页例13C=(cij)nn=0 4 3 11 80 2 10 7 30 3 6 2 10 1 8 0 40 3 6 4 0第第76页页匈牙利法的步骤匈牙利法的步骤2.寻找独立寻找独立“0”元元素素若有若有n个，计算结束个，计算结束若少于若少于n个，转个，转3130

38、页例页例13C=(cij)nn=0 3 0 11 80 1 7 7 30 2 3 2 10 0 5 0 40 2 3 4 0第第77页页匈牙利法的步骤匈牙利法的步骤4.继续变换系数矩阵继续变换系数矩阵1 3 11 80 0 6 6 20 1 2 1 01 5 41 2 3 4 （1）未被覆盖的）未被覆盖的元素中减去最小元元素中减去最小元素，出现新的素，出现新的0元元素素（2）打）打列中各元列中各元素都加上最小元素。素都加上最小元素。第第78页页匈牙利法的步骤匈牙利法的步骤4.继续变换系数矩阵继续变换系数矩阵1 3 11 80 0 6 6 20 1 2 1 01 5 41 2 3 4 （1）未被

39、覆盖的）未被覆盖的元素中减去最小元元素中减去最小元素，出现新的素，出现新的0元元素素（2）打）打列中各元列中各元素都加上最小元素。素都加上最小元素。第第79页页匈牙利法的步骤匈牙利法的步骤4.继续变换系数矩阵继续变换系数矩阵1 3 0 11 80 0 6 6 20 1 2 1 01 0 5 0 41 2 3 4 0（1）未被覆盖的）未被覆盖的元素中减去最小元元素中减去最小元素，出现新的素，出现新的0元元素素（2）打）打列中各元列中各元素都加上最小元素。素都加上最小元素。第第80页页匈牙利法的步骤匈牙利法的步骤5.重新寻找独立重新寻找独立0元素元素1 3 0 11 80 0 6 6 20 1 2

40、 1 01 0 5 0 41 2 3 4 0第第81页页匈牙利法的步骤匈牙利法的步骤5.重新寻找独立重新寻找独立0元素元素1 3 11 8 6 6 2 1 2 1 1 5 41 2 3 4 第第82页页X=(xij)nn=0 0 1 0 00 1 0 0 01 0 0 0 00 0 0 1 00 0 0 0 1第第83页页四、一般的指派问题四、一般的指派问题1.最大化指派问题（最大化指派问题（用最大元素用最大元素-所有元所有元素化成最小化问题素化成最小化问题）2.人数和事数不等人数和事数不等3.一个人可做几件事的指派问题一个人可做几件事的指派问题4.某件事一定不能由某人做某件事一定不能由某人做