目标规划和整数规划.pptx

《目标规划和整数规划.pptx》由会员分享，可在线阅读，更多相关《目标规划和整数规划.pptx（66页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、3 31 1目标规划目标规划3 31 11 1单目标规划单目标规划 3 31 11 11 1单目标规划数学模型单目标规划数学模型 (1)(1)如何安排可获得最大利润如何安排可获得最大利润 Max ZMax Z（X X）=8x=8x1 1+6x+6x2 2 4 4x x1 1+2x+2x2 2 60 60 2x 2x1 1+4x+4x2 2 4848 x x1 1，x x2 2 00 x x1 1=12,x=12,x2 2=6,=6,Z(X*)=132AB42426860可使用量可使用量48设备（设备（hr)原料（原料（kg)利润（千元）利润（千元）例OR（线性规划）（线性规划）第1页/共66页

2、 (2)(2)利润目标为利润目标为140140（百元）（百元）此目标称之为预定目标，实际完成的量与预定目标此目标称之为预定目标，实际完成的量与预定目标 之间可能出现偏差，通常用之间可能出现偏差，通常用d d+、d d-（d d+、d d-00）表示，表示，称为偏差变量。称为偏差变量。其中：其中：d d+表示超过预定指标的部分，表示超过预定指标的部分，d d-表示未达到预定指标的部分表示未达到预定指标的部分 在客观条件下，最终完成的结果可能出现以下三种在客观条件下，最终完成的结果可能出现以下三种情况：情况：d d+0,0,d d-=0=0 表明超额完成预定指标表明超额完成预定指标 d d-0,0

3、,d d+=0=0 表明未达到预定指标表明未达到预定指标 d d+=d d-=0=0 表明恰好完成预定指标表明恰好完成预定指标上述三种情况可用模型表示上述三种情况可用模型表示OR第2页/共66页 8 8x x1 1+6x+6x2 2特征：特征：增加了目标约束、增加了目标约束、目标中只出现偏差变量且为求极小化问题、目标中只出现偏差变量且为求极小化问题、d d+d d-=0=0d d-,d d+d d-+d d-d d+=目标约束目标约束系统约束系统约束Z=Z=4x1+2x2 60 2x1+4x2 48 x1，x2，0 140MinOR第3页/共66页3 31 11 12 2 单目标规划解单目标规

4、划解 用单纯形法求满意解用单纯形法求满意解,注意求极小化问题最优性条件：注意求极小化问题最优性条件：标准型标准型:Min Z=Min Z=d d-8 8x x1 1+6x+6x2 2+d d-d d+=140=140 4 4x x1 1+2x+2x2 2+x+x3 3 =60 =60 2x 2x1 1+4x+4x2 2 +x +x4 4 =48 =48 x x1 1，x x2 2 x x3 3,x,x4 4,d d-,d d+0 0 X1 X2 X3 X4 d-d+0 0 0 0 1 0 8 6 0 0 1 -14 2 1 0 0 0 2 4 0 1 0 0-8 1406048d-X3X410

5、0OR -6 0 0 0 1第4页/共66页00 x x1 1=12=12，x x2 2 =6,6,d d-=8=8 d d+=0=0 完成利润完成利润132132（百元）（百元）OR第5页/共66页 由此可得：由此可得：x x1 1=12=12，x x2 2=6=6，d d+=0=0，d d-=8=8 完成利润完成利润132132（百元）（百元）3 31 12 2 级别相同的多目标规划级别相同的多目标规划3 31 12 21 1数学模型数学模型（1 1）实现利润目标）实现利润目标122122（百元）（百元）（2 2）产品）产品A A的产量不多于的产量不多于1010 设设：d di i+,d

6、di i-(i=1,2)(i=1,2)分分别别为为超超过过目目标标值值的的部部分分，及及未未完完成目标值的部分。成目标值的部分。8 8x x1 1+6x+6x2 2 minmin目标约束目标约束系统约束系统约束x14x1+2x2 60 2x1+4x2 48x1，x2，=122=10d1+,d1-，d2+,d2-0Z=+d1-d1+d2-d2+d1-+d2+OR第6页/共66页 8 8x x1 1+6x+6x2 2+d d1 1-d d1 1+=122=122 x x1 1 +d d2 2-d d2 2+=10=10 4x 4x1 1+2x+2x2 2 60 60 2x 2x1 1+4x+4x2

7、 2 48 48 x x1 1，x x2 2，d d1 1+,d d1 1-，d d2 2+,d d2 2-00 min Z=min Z=d d1 1-+d d2 2+目标约束目标约束系统约束系统约束3 31 12 22 2单纯形表单纯形表OR第7页/共66页3 31 12 22 2单纯形表单纯形表第8页/共66页x x1 1=10=10、x x2 2=7=7 x x3 3=6=6 x x4 4=0=0d d1 1+=d d1 1-=d d2 2+=d d2 2-=0=0，完成利润完成利润122122，两个目标均已实现。，两个目标均已实现。00第9页/共66页 3 31 13 3具有优先级的多

8、目标规划具有优先级的多目标规划 3 31 13 31 1数学模型数学模型 例：例：P P1 1:充分利用设备有效台时，不加班；充分利用设备有效台时，不加班；P P2 2:产品产品B B的产量不多于的产量不多于4 4；P P3 3:实现利润实现利润130130（百元）（百元）4 4x x1 1+2x+2x2 2+d d1 1-d d1 1+=60 =60 x x2 2+d d2 2-d d2 2+=4 =4 8x 8x1 1+6x+6x2 2+d d3 3-d d3 3+=130 =130 2x 2x1 1+4x+4x2 2 48 48 x x1 1，x x2 2，d di i+,d di i-

9、(i=1,2,3)0(i=1,2,3)0 Z=Z=(d d1 1-+d d1 1+)P1P2P3+d2+d3-MinOR第10页/共66页3 31 13 32 2目标规划图解法目标规划图解法 仍以例仍以例3 3为例为例 （1 1）根据系统约束）根据系统约束，确定可行域，如图，确定可行域，如图多边形多边形OABOAB为该目标规划的可行域；为该目标规划的可行域；（2 2）不考虑偏差，即：）不考虑偏差，即：d di i+=d di i-=0=0（i=1,2,3)i=1,2,3)，然后按然后按顺序作出目标约束相应的直线，并标出顺序作出目标约束相应的直线，并标出d di i+0,0,d di i-00的

10、方向的方向。（。（3 3）按优先顺序找出该目标的满意解：）按优先顺序找出该目标的满意解：4 4x x1 1+2x+2x2 2+d d1 1-d d1 1+=60 =60 x x2 2+d d2 2-d d2 2+=4 =4 8x 8x1 1+6x+6x2 2+d d3 3-d d3 3+=130 =130 2x 2x1 1+4x+4x2 2 48 48 x x1 1，x x2 2，d di i+,d di i-(i=1,2,3)0(i=1,2,3)0 Z=Z=(d d1 1-+d d1 1+)P1P2P3+d2+d3-MinOR第11页/共66页FECBADOX2X1d d1 1+00d d3

11、 3+00d d2 2+00d d2 2-00d d3 3-00d d1 1-00G 4 4x x1 1+2x+2x2 2+d d1 1-d d1 1+=60 =60 x x2 2+d d2 2-d d2 2+=4 =4 8x 8x1 1+6x+6x2 2+d d3 3-d d3 3+=130 =130 2x 2x1 1+4x+4x2 2 48 48 x x1 1，x x2 2，d di i+,d di i-(i=1,2,3)0(i=1,2,3)0 Z=Z=(d d1 1-+d d1 1+)P1P2P3+d2+d3-Min(1)(1)显然线段显然线段CDCD上的点满足第一目标上的点满足第一目标

12、 (2)(2)FDFD上的点同时满足第一目标与第二上的点同时满足第一目标与第二 目标目标第12页/共66页FECBADOX2X1d d1 1+00d d3 3+00d d2 2+00d d2 2-00d d3 3-00d d1 1-00G(1)(1)显然线段显然线段CDCD上的点满足第一目标上的点满足第一目标 (2)(2)FDFD上的点同时满足第一目标与第二目标上的点同时满足第一目标与第二目标(3)(3)E E点满足第一、第三目标点满足第一、第三目标,与第二目标矛盾与第二目标矛盾，G G点满足第二、第三目标点满足第二、第三目标 与第一目标矛盾与第一目标矛盾，因此允许第三目标有偏差，线段，因此允

13、许第三目标有偏差，线段FDFD上的上的F F点点可使可使d d3 3-取最小值，故取最小值，故F F点为所求满意解。其坐点为所求满意解。其坐标为（标为（1313，4 4）x x1 1=13=13，x x2 2=4=4，利润利润128128（百元）。（百元）。Operational Research第13页/共66页3 31 13 33 3单纯形法单纯形法 例例 Min Z=Min Z=P P1 1(d d1 1-+d d1 1+)+)+P P2 2 d d2 2+P P3 3 d d3 3-4 4x x1 1+2x+2x2 2+d d1 1-d d1 1+=60 =60 x x2 2+d d2

14、 2-d d2 2+=4 =4 8x 8x1 1+6x+6x2 2+d d3 3-d d3 3+=130 =130 2x 2x1 1+4x+4x2 2 48 48 x x1 1，x x2 2，d di i+,d di i-(i=1,2,3)0(i=1,2,3)0OR第14页/共66页0000第15页/共66页00000000第16页/共66页x x1 1*=13=13，x x2 2*=4=4，Z Z=128=128（百元）。百元）。3 31 14 4 目标规划的目标目标规划的目标（1 1）决策人希望恰好实现预定的第）决策人希望恰好实现预定的第i i个目标个目标 MinMin Z Z=d di

15、i+d di i-（2 2）决策人不希望超过预定的第决策人不希望超过预定的第i i个目标个目标 MinMin Z Z=d di i+（3 3）决策人希望超过预定的第决策人希望超过预定的第i i个目标个目标 minmin Z Z=d di i-OR第17页/共66页3.23.2整数规划整数规划3 32 21 1整数规划数学模型整数规划数学模型 Max ZMax Z（X X）=c=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn n a ai1i1x x1 1+a+ai2i2x x2 2+a+ainin x xn n(=,)b(=,)bi i x x1 1，x x2 2，x x

16、n n 0 0 纯整数规划纯整数规划:所有决策变量所有决策变量x xj j(j=1,2,(j=1,2,n),n)均取整数均取整数.混合整数规划混合整数规划:部分决策变量取整数部分决策变量取整数.0-1 0-1整数规划整数规划:所有决策变量只取所有决策变量只取0 0或或1.1.这类变量又称这类变量又称 为逻辑变量为逻辑变量.(i=1,2,m)全部或部分为整数 OR第18页/共66页3.2.23.2.2分枝限界法分枝限界法 例例 Max ZMax Z（X X）=3x=3x1 1+2x+2x2 2 2x 2x1 1+3x+3x2 2 14 14 （A A）：）：2x 2x1 1+x+x2 2 9 9

17、 x x1 1，x x2 2 0 0 且为整数且为整数 解；（解；（1 1）先不考虑变量的整数约束，求解相应的线性规划）先不考虑变量的整数约束，求解相应的线性规划 Max Z（X）=3x1+2x2 2x1+3x2 14（B0）：2x1+x2 9 x1，x2 0OR第19页/共66页CX2987654321X1876543210C/9 由于由于x x1 1 ，x x2 2均不满足整数条件均不满足整数条件，故可由，故可由x x1 1（或或x x2 2）进行分枝，使进行分枝，使x x1 1满足满足：x x1 13 3 或或 x x1 144 将将3 3 x x1 14 4 的非整数部分割掉的非整数部

18、分割掉于是问题于是问题B B0 0分成了两个子问题分成了两个子问题B B1 1 ,B B2 2然后分别求出其最优解。然后分别求出其最优解。最优解：最优解：x x1 1=13/4=13/4，x x2 2=5/2=5/2，Z Z0 0=14=143/43/4（2）分枝：Operational Research第20页/共66页 Max ZMax Z（X X）=3x=3x1 1+2x+2x2 2 2x 2x1 1+3x+3x2 2 14 14 （B B1 1）：）：2x 2x1 1+x+x2 2 9 9 x x1 1 3 3 x x1 1，x x2 2 0 0 Max ZMax Z（X X）=3x=

19、3x1 1+2x+2x2 2 2x 2x1 1+3x+3x2 2 14 14(B(B2 2）：）：2x 2x1 1+x+x2 2 99 x x1 1 44 x x1 1，x x2 2 0 0最优解最优解:X X2 2*=（4 4，1 1）Z Z2 2=14=14 此分枝已查清。此分枝已查清。最优解最优解:X X1 1*=（3 3，8/38/3）Z Z1 1=14=141/31/3 X1876543210Operational ResearchCX2987654321C/OR第21页/共66页CX2987654321X1876543210C/（3 3）定界：问题（）定界：问题（B B2 2）已获

20、得整数最优解，已获得整数最优解，可将可将Z Z2 2=14=14作为问题（作为问题（A A）的下界，同时将的下界，同时将 Z Z0 0=14=143/43/4作为问题（作为问题（A A）的上界。可以断定的上界。可以断定 Z Z2 2=14 Z Z=14 Z Z0 0=14=143/43/4（4 4）返回到（返回到（2 2）继续对）继续对B B1 1中的中的x x2 2进行分枝，进行分枝，使使x x2 2满足：满足：x x2 222或或x x2 233 将将2 2 x x2 2 3 3之间的非整数部分割掉之间的非整数部分割掉于是问题于是问题B B2 2又分成了两个子问题又分成了两个子问题B B3

21、 3和和B B4 4再分别求出其最优解再分别求出其最优解.Operational Research第22页/共66页CX2987654321X1876543210C/Max ZMax Z（X X）=3x=3x1 1+2x+2x2 2 2x 2x1 1+3x+3x2 2 14 14 （B B3 3）2x 2x1 1+x+x2 2 9 9 x x1 1 3 3 x x2 2 2 2 x x1 1，x x2 2 0 0 Max ZMax Z（X X）=3x=3x1 1+2x+2x2 2 2x 2x1 1+3x+3x2 2 14 14(B(B4 4）2x 2x1 1+x+x2 2 99 x x1 1

22、33 x x2 2 33 x x1 1，x x2 2 0 0最优解最优解X X3 3*=（3 3，2 2）Z Z3 3=13=13最优解最优解X X4 4*=（5/25/2，3 3）Z Z4 4=13=131/21/2Operational Research第23页/共66页 Z Z3 3=13=13和和Z Z4 4=13=131/21/2均小于界值均小于界值Z Z2 2，不可能成为最优值，将不可能成为最优值，将被剪掉（剪枝）。被剪掉（剪枝）。由此可得出问题（由此可得出问题（A A）的最优解就是问题（的最优解就是问题（B B2 2）的最优解。的最优解。即：即：X X*=（4 4，1 1）；）；

23、Z Z（X X*）=14=14OR第24页/共66页树状图树状图:B1 x1=3，x2=8/3Z1=141/3B2 x1=4，x2=1Z2=14B3 x1=3，x2=2Z3=13B4 x1=5/2，x2=3Z4=131/2B B0 0 x x1 1=13/4=13/4，x x2 2=5/2=5/2Z Z0 0=14=143/43/4x x2 233x x2 22 2 x x1 144x x1 13 3 OR第25页/共66页3.2.33.2.3割平面法割平面法例：例：Max ZMax Z（X X）=3x=3x1 1+2x+2x2 2 2 2x x1 1+3x+3x2 2 14 14 （A A）

24、：）：2x 2x1 1+x+x2 2 99 x x1 1，x x2 2 0 0 且为整数且为整数解解:(1)不考虑其整数条件不考虑其整数条件,用单纯形法求解相应的线性用单纯形法求解相应的线性 规划问题规划问题最终单纯形表如下最终单纯形表如下OR第26页/共66页（2）构造）构造Gomory约束（割平面）约束（割平面）在最终单纯形表中，任意选择一个非整数变量（如在最终单纯形表中，任意选择一个非整数变量（如x x2 2），），写出该变量所在行的方程式：写出该变量所在行的方程式：x x2 2+1/2x+1/2x3 3 1/2x1/2x4 4=5/2=5/2将各变量的系数及常数项分解为整数与非负真分数

25、之和；再将各变量的系数及常数项分解为整数与非负真分数之和；再将系数为整数的变量移到方程式左端，系数为分数的变量移将系数为整数的变量移到方程式左端，系数为分数的变量移到方程式右端到方程式右端 x x2 2 x x4 4-2=1/2-2=1/2-（1/2x1/2x3 3+1/2x+1/2x4 4）Gomory约束为：约束为：1/2-1/2-（1/21/2x x3 3+1/2x+1/2x4 4）00（3）将将Gomory约束化为方程，填入到最终单纯形表中，继约束化为方程，填入到最终单纯形表中，继续求问题的最优解续求问题的最优解OR第27页/共66页1/2-1/2-（1/21/2x x3 3+1/2x

26、+1/2x4 4）+x+x5 5=0=0该单纯形表中当前解不可行，而其对偶解满足可行性条该单纯形表中当前解不可行，而其对偶解满足可行性条件件 ，故用对偶单纯形法求解，最终表如下：，故用对偶单纯形法求解，最终表如下：OR第28页/共66页表中表中x x1 1仍不满足整数条件，返回到（仍不满足整数条件，返回到（2 2）构造构造Gomory约束（割平面）继续求解约束（割平面）继续求解 由：由：x x1 1+x+x4 4-1/2x-1/2x5 5=7/2=7/2 x x1 1+x+x4 4+(-1+1/2)x+(-1+1/2)x5 5=3+1/2=3+1/2得：得：Gomory约束为：约束为：1/2-

27、1/21/2-1/2x x5 50 0 或或 1/2-1/2 1/2-1/2x x5 5+x+x6 6=0=0 将该约束插入上述的最终单纯形表中得：将该约束插入上述的最终单纯形表中得：OR第29页/共66页OR第30页/共66页 最优解最优解X X*=（4 4，1 1）；）；Z Z（X X*）=14=14 3.2.4 0-13.2.4 0-1规化规化3 32 24 41 0-11 0-1规划问题及其数学模型规划问题及其数学模型3 32 24 42 0-12 0-1规划的隐枚举解法规划的隐枚举解法例例 MaxZMaxZ（X X）=3x=3x1 1-2x-2x2 2+5x+5x3 3 x x1 1

28、+2x+2x2 2-x-x3 3 2 2 x x1 1+4x+4x2 2+x+x3 3 4 4 x x1 1+x+x2 2 3 3 4x 4x2 2+x+x3 3 6 6 x x1,1,x x2,2,x x3 3=0=0 或或 1 1解：首先通过试探的方法找出一个可行解解：首先通过试探的方法找出一个可行解 X X=（x x1,1,x x2,2,x x3 3）=（1 1，0 0，0 0）Z Z（X X）=3x=3x1 1-2x-2x2 2+5x+5x3 3=3=3 增加约束：增加约束：3 3x x1 1-2x-2x2 2+5x+5x3 3 3 3（称为过滤条件称为过滤条件）OR第31页/共66页

29、例例 MaxZMaxZ（X X）=3x=3x1 1-2x-2x2 2+5x+5x3 3 x x1 1+2x+2x2 2-x-x3 3 2 2 x x1 1+4x+4x2 2+x+x3 3 4 4 x x1 1+x+x2 2 3 3 4x 4x2 2+x+x3 3 6 6 x x1,1,x x2,2,x x3 3=0=0 或或 1 1626N8021Y11N31110Y315N5-1101Y5-2N0N将不满足过滤条件的将不满足过滤条件的X X全部过滤掉，见下表全部过滤掉，见下表38OR第32页/共66页改进过滤条件：改进过滤条件：-2-2x x2 2+3x+3x1 1+5x+5x3 3 5 5

30、 改进过滤条件：改进过滤条件：-2-2x x2 2+3x+3x1 1+5x+5x3 3 8 8 注意：注意：（1 1）为进一步减少计算工作量，可及时改进过）为进一步减少计算工作量，可及时改进过滤条件。滤条件。（2 2）价值系数按递增排列，）价值系数按递增排列，如如 MaxZMaxZ（X X）=-2x=-2x2 2+3x+3x1 1+5x+5x3 3 第33页/共66页X*=(1,0,1)Z=8OROperational Research第34页/共66页3 32 25 5分派问题（分派问题（Assignment problemAssignment problem）一般描述一般描述:有有n n项

31、任务项任务,指派指派n n个人个人(广义广义)去完成去完成,第第i i个人完成第个人完成第j j项项任务的效率为任务的效率为C Cijij(i=1,2,(i=1,2,n;j=1,2,n;j=1,2,n),n)；要求每个人只要求每个人只能承担一项任务能承担一项任务,并且每一项任务都有一个人个来承担；问并且每一项任务都有一个人个来承担；问如何分派可以使总的效率达到最高。（如何分派可以使总的效率达到最高。（C Cijij）为效率矩阵。为效率矩阵。3 32 25 51 1建立数学模型建立数学模型 引入引入0-10-1变量变量 效率矩阵效率矩阵:x xij=ij=0 0 不分派第不分派第i i个人去承担

32、第个人去承担第j j项任务项任务1 1 分派第分派第i i个人去承担第个人去承担第j j项任务项任务OR第35页/共66页x x1111+x+x2121+x+xn1n1=1=1A1A2.B1B2.BnC11C12.C1n.AnC21C22.C2nCn1Cn2.CnnX21X22.X2nX11X12.X1nXn1Xn2.Xnn.x21+x22+x2n=1.xn1+xn2+xnn=1x12+x22+xn2=1.x1n+x2n+xnn=1x11+x12+x1n=1OR第36页/共66页(i=1,2,i=1,2,n),n)每人只能承担一项工作每人只能承担一项工作(j=1,2,j=1,2,n),n)每项

33、工作只允许一人承担每项工作只允许一人承担x21+x22+x2n=1.xn1+xn2+xnn=1x11+x12+x1n=1x x1111+x+x2121+x+xn1n1=1=1x12+x22+xn2=1.x1n+x2n+xnn=1OR第37页/共66页特点：特点：（1 1）特殊的）特殊的0-10-1规划规划 （2 2）m=n;am=n;ai i=b=bj j=1=1的特殊运输问题的特殊运输问题 （3 3）所有可行解的个数为）所有可行解的个数为n!n!(i=1,2,i=1,2,n),n)每人只能承担一项工作每人只能承担一项工作(j=1,2,j=1,2,n),n)每项工作只允许一人承担每项工作只允许

34、一人承担X Xijij=0=0 或或 1 1OR第38页/共66页3 32 25 52 2分派问题的匈牙利解法分派问题的匈牙利解法同解性原理：同解性原理：如果在效率矩阵（如果在效率矩阵（C Cijij）的第的第i i（i=1,2,i=1,2,n,n）行（列行（列）加（减）一个常数）加（减）一个常数k ki i，那么新效率矩阵与原效率矩阵有相那么新效率矩阵与原效率矩阵有相同的最优解。同的最优解。在求解的过程中可反复利用这个性质。在求解的过程中可反复利用这个性质。步骤：步骤：(1)(1)化简效率矩阵：使其每行、每列至少有一个零元素。化简效率矩阵：使其每行、每列至少有一个零元素。例：例：2 10 5

35、 715 4 14 8 13 14 12 11 4 15 13 9 0 8 3 511 0 10 4 2 3 1 0 0 11 9 5-2-4-11-4-1OR第39页/共66页(2)(2)检验：检验：用尽可能少的直线去覆盖所有的零元素，当覆盖线的用尽可能少的直线去覆盖所有的零元素，当覆盖线的条数条数n n0 0=n=n 时时,可转入（可转入（4 4）确定最优方案）确定最优方案,当当 n n0 0n n 时转入下时转入下一步一步(3)(3)继续化简继续化简观察法观察法标号法标号法 0 8 2 511 0 9 4 2 3 0 0 0 11 8 5 0 8 3 511 0 10 4 2 3 1 0

36、 0 11 9 5-1*（此时，n0=3 n=4）。OR第40页/共66页 （3 3）移动零元素：在未被直线覆盖的元素中找出最小元）移动零元素：在未被直线覆盖的元素中找出最小元，对不在覆盖线上的元素减去这个最小元，在两覆盖线交点，对不在覆盖线上的元素减去这个最小元，在两覆盖线交点上加上这个最小元，其他元素不变。上加上这个最小元，其他元素不变。0 8 2 511 0 9 4 2 3 0 0 0 11 8 5 0 6 0 313 0 9 4 4 3 0 0 0 9 6 3-2-0-0-2+2+0+0+0然后返回到（2）继续检验。（此时，n0=n=4），转入（4）Operational Resear

37、ch第41页/共66页（4）确定最优方案，写出解矩阵。0 6 0 313 0 9 4 4 3 0 0 0 9 6 3 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 Z=5+4+11+4=24 2 10 5 715 4 14 8 13 14 12 11 4 15 13 9OR第42页/共66页例：求费用矩阵为下表的 指派问题的最优解工作人费用A B C D E甲乙丙丁戊12 7 9 7 9 8 9 6 6 6 7 17 12 14 12 15 14 6 6 10 4 10 7 10 6-7-6-7-6-4+2-2-2最优指派方案：甲做B工作乙做C工作,丙做A工作丁做D工作,戊做

38、E工作=32第43页/共66页匈牙利法的具体步骤：第一步：变换指派问题的费用矩阵，使其在各行 各列都出现0元素：方法：首先每行元素减去该行的最小元素，然后每列减去该列的最小元素第二步：进行试指派（画）方法：从含0元素最少的行或列开始，圈出一个0 元素，用 表示，然后划去该所在的行 和列中的其余0元素，用表示，依次类推。若矩阵中的的个数等于n，则得最优解若矩阵中的的个数n，则进行第三步第44页/共66页第三步：做能复盖所有0元素的最小直线集合：1）对没有的行打号2）对打号的行上所有0元素的列打号3）再对打号的列上所有的行打号4）重复以上步骤直到得不出新的打号为止5）对没有打号的行画横线，所有打号

39、的 列画纵线，所得到的直线既是复盖所有0元 素的最小直线集合第四步：在没有被直线复盖的元素中找出最小元素，让打号的列加上这个元素，打号的行减 去这个元素。转第一步第45页/共66页 例：现有4份工作，4个人应聘，由于个人的技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总费用最小的分派方案。工作人收费用1 2 3 4123415 18 21 2419 23 22 1826 17 16 19 19 21 23 17最优方案：第一个人做第一件事；第二个人做第四件事；第三个人做第三件事；第四个人做第二件事；总费用：70第46页/共66页第

40、47页/共66页（1）多重最优解例：7 4 3 2 6 3 2 5 3 6 2 3 7 5 6 3-2-2-2-3 5 2 1 0 4 1 0 3 1 4 0 1 4 2 3 0-1-1 4 1 1 0 3 0 0 3 0 3 0 1 3 1 3 0 3 0 0 0 3 0 0 4 0 3 0 2 2 0 2 0 OR3.2.5.3 分派问题几种特殊情况 第48页/共66页 3 0 0 0 3 0 0 4 0 3 0 2 2 0 2 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 3 0 0 0 3 0 0 4 0 3 0 2 2 0 2 0 3 0 0 0 3 0 0 4

41、 0 3 0 2 2 0 2 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 确定解矩阵：确定解矩阵：一方案一方案二方案二方案三方案三方案第49页/共66页 7 4 3 2 6 3 2 5 3 6 2 3 7 5 6 3 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 一方案一方案二方案二方案三方案三方案Z=3+3+3+3=12Z=4+2+3+3=12Z=2+2+3+5

42、=12OR第50页/共66页化为求极小化问题化为求极小化问题（2）极大值的分派问题OR第51页/共66页极大值的分派问题例：10 15 12 5 12 17 12 1 16 20 6 2 4 6 3 1 10 5 8 15 8 3 8 19 4 0 14 18 16 14 17 19-5-3-0-14 5 0 3 10 5 0 5 16 4 0 14 18 2 0 3 5-2-0-3 3 0 0 5 3 0 2 11 2 0 11 13 0 0 0 0-5OR第52页/共66页 3 0 0 5 3 0 2 11 2 0 11 13 0 0 0 0 3 2 0 5 1 0 0 9 0 0 9 1

43、1 0 2 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 10 15 12 5 12 17 12 1 16 20 6 2 4 6 3 1Z=12+17+16+1=46OR第53页/共66页例：现有4份工作，4个人应聘，由于个人的技术专长不同，他们承担各项工作的效益如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总效益最大的分派方案。工作人收益1 2 3 412 7 9 7 7 17 12 14 15 14 6 6 4 10 7 10 1234分派方案：第1个人第3项工作，第2个人第2项工作第3个人第1项工作，第4个人第4项工作总效益=9+17+

44、15+10=51第54页/共66页（3）不平衡的分派问题化为平衡分派问题来处理第55页/共66页例：现有4份工作，6个人应聘，由于个人的技术专长不同，他们承担各项工作所需时间如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总时间最少的分派方案。工作人时间1 2 3 41234565 6 00000000000012 7 9 7 7 17 12 14 15 14 6 6 4 10 7 10 6 5 5 84 5 7 6 分派方案：第3个人第4项工作第4个人第1项工作第5个人第3项工作第6个人第2项工作第1、2个人没工作总时间=6+4+5+5=20第56页/共66页(4)一

45、个人可做几件事的指派问题设n个人中的第k个人可同时做t件事：把第k个人视为t个人，这t个人做同一件事的费用系数都一样问题化为人数为n-1+t个人的指派问题（5）某人一定不能做某事的指派问题如在minZ问题中，第k个人一定不能做第t件事：如在maxZ问题中，第k个人一定不能做第t件事，第57页/共66页例：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由3家建筑公司分别承建。已知第Ai(i=1,2,3)个建筑公司对第Bj(j=1,2,3,4,5)家新商店的建造费用的报价如下表，为保证工程进度，每家建筑公司最多只能承建两个商店，且由于某种原因，第B3家商店不能由第A1个建筑公司承办，

46、求使总费用最少的指派方案商店建筑公司报价B1 B2 B3 B4 B5A1A2A34 8 7 15 12 7 9 17 14 10 6 9 12 8 7 B1 B2 B3 B4 B5A11A12A21A22A31A32每家公司最多可承建两家商店：人数工作数：B1 B2 B3 B4 B5 B6A11A12A21A22A31A32B3不能由A1承办：5050第58页/共66页 B1 B2 B3 B4 B5 B6A11A12A21A22A31A32由A1承建B1、B2指派方案：，由A2承建B5由A3承建B3、B4总费用=42第59页/共66页第60页/共66页管理运筹学应用软件可解决:1、纯整数规划2

47、、0-1规划3、混合型整数规划要求：变量个数100约束方程个数50第61页/共66页例2.1 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4个小时，油漆工2小时。生产一个椅子需要木工3个小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？纯整数规划第62页/共66页数学模型：例 一登山队员做登山准备，他需要携带的物品及每件物品的重要系数、重量如下表，假定登山队员可携带的最大重量为25千克，问该队员该携带那些物品1 2 3 4 5 6 7序

48、号物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通讯设备 重量ai（千克）5 5 2 6 12 2 4重要系数ci 20 15 18 14 8 4 1010带第i个物品不带第i个物品Z表示总重要系数0-1规划第63页/共66页混合型第64页/共66页练习：6个人应聘4份工作，由于个人的技术专长不同，他们承担各项工作所获得的收益如下表，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总收益最大的指派方案。工作人收益1 2 3 41234563 5 4 5 6 7 6 8 8 9 8 10 10 10 9 1112 11 10 1213 12 11 13分派方案：第3个人第2项工作第4个人第3项工作第5个人第1项工作第6个人第4项工作第1、2个人没工作第65页/共66页感谢您的观看！第66页/共66页