运筹学目标规划与整数规划课件

《运筹学目标规划与整数规划课件》由会员分享，可在线阅读，更多相关《运筹学目标规划与整数规划课件（66页珍藏版）》请在装配图网上搜索。

1、Page:1QSC华东理工大学 工商经济学院运筹学运运筹筹学学目目标标规规划划Page:2QSC华东理工大学 工商经济学院运筹学多目标决策问题多目标决策问题实际问题决策经常面临的问题：实际问题决策经常面临的问题：方案优劣并不以单一准则为目标，而是以多重准则为目标方案优劣并不以单一准则为目标，而是以多重准则为目标约束条件并不完全符合严格的刚性条件，具有一定的弹性约束条件并不完全符合严格的刚性条件，具有一定的弹性可能的弹性约束可能的弹性约束：最好等于最好等于最好不大于最好不大于最好不小于最好不小于Page:3QSC华东理工大学 工商经济学院运筹学弹性约束的处理方法弹性约束的处理方法实际量 dd+

2、= 目标值负偏差变量负偏差变量正偏差变量正偏差变量 ddMin 最好等于：最好等于：dMin 最好不大于：最好不大于：dMin 最好不小于：最好不小于：Page:4QSC华东理工大学 工商经济学院运筹学顾客访问策略顾客访问策略 老顾客老顾客 新顾客新顾客 正常可用访问时间正常可用访问时间 访问每一顾客所需时间访问每一顾客所需时间 2 3 640 小时小时 平均可获销售利润平均可获销售利润 250 125 目标：目标：访问时间最好不超过访问时间最好不超过680680小时；小时；访问时间最好不少于访问时间最好不少于600600小时；小时；销售收入尽量不少于销售收入尽量不少于70,00070,000

3、；访问老顾客数最好不少于访问老顾客数最好不少于200200个；个；访问新顾客数最好不少于访问新顾客数最好不少于120120个个Page:5QSC华东理工大学 工商经济学院运筹学模型模型顾客访问策略顾客访问策略0 120 200000,70125250 60032 68032 5524413321222111215544332211所有变量ddxddxddxxddxxddxxStdPdPdPdPdPZMinPage:6QSC华东理工大学 工商经济学院运筹学目标规划解的几何分析目标规划解的几何分析X100300200600500400X21002003004005001(1)1d1d(2)2d2d

4、(3)3d3d(4)4d4d(5)5d5dPage:7QSC华东理工大学 工商经济学院运筹学0 120 200000,70125250 60032 68032 5524413321222111215544332211所有变量ddxddxddxxddxxddxxStdPdPdPdPdPZMin目标规划的求解目标规划的求解-序贯算法序贯算法Page:8QSC华东理工大学 工商经济学院运筹学068032 11211所有变量ddxxStdZMin068032 0 211所有变量xxd第一级目标第一级目标X100300200600500400X21002003004005001(1)1d1dPage:9

5、QSC华东理工大学 工商经济学院运筹学 060032 68032 2221212所有变量ddxxxxStdZMin第二级目标第二级目标06003268032 0 21212所有变量xxxxdX100300200600500400X21002003004005001(1)1d1d(2)2d2dPage:10QSC华东理工大学 工商经济学院运筹学第三级目标第三级目标 0000,701252506003268032 0 2121213所有变量xxxxxxdX100300200600500400X21002003004005001(1)1d1d(2)2d2d(3)3d3d 0 000,70125250

6、 60032 68032 332121213所有变量ddxxxxxxStdZMinPage:11QSC华东理工大学 工商经济学院运筹学X100300200600500400X21002003004005001(1)1d1d(2)2d2d(3)3d3d(4)4d4d 0 200000,70125250 60032 68032 4412121214所有变量ddxxxxxxxStdZMin第四级目标第四级目标 0200000,701252506003268032 0 12121214所有变量xxxxxxxdPage:12QSC华东理工大学 工商经济学院运筹学X100300200600500400X2

7、1002003004005001(1)1d1d(2)2d2d(3)3d3d(4)4d4d(5)5d5d第五级目标第五级目标Page:13QSC华东理工大学 工商经济学院运筹学目标规划的求解目标规划的求解-多阶段算法多阶段算法0 120 200000,70125250 60032 68032 5524413321222111215544332211所有变量ddxddxddxxddxxddxxStdPdPdPdPdPZMinPage:14QSC华东理工大学 工商经济学院运筹学初始单纯形表初始单纯形表000P1P20P30P40P50 x1x2d1-d1+d2-d2+d3-d3+d4-d4+d5-d

8、5+RHS比值比值0231-100000000680680/3P223001-1000000600600/3P325012500001-100007000070000/125P4100000001-100200-P501000000001-1120120/1P1000100000000P2-2-30001000000P3-250 -1250000010000P4-100000000100P50-10000000001d3-d1-d2-d4-d5-检验数检验数Page:15QSC华东理工大学 工商经济学院运筹学单纯形表运算单纯形表运算000P1P20P30P40P50 x1x2d1-d1+d2-

9、d2+d3-d3+d4-d4+d5-d5+RHS比值比值0201-1000000-33320320/3P220001-10000-33240240/3P3250000001-100-1251255500055000/125P4100000001-100200-001000000001-1120-P1000100000000P2-20000100003-3P3-250000000100125-125P4-100000000100P5000000000010d3-d1-d2-d4-x2检验数检验数Page:16QSC华东理工大学 工商经济学院运筹学单纯形表运算单纯形表运算000P1P20P30P4

10、0P50 x1x2d1-d1+d2-d2+d3-d3+d4-d4+d5-d5+RHS比值比值0001-1-1100000080-02/30001/3 -1/30000-118080/(2/3)P3500/3000-125/3-125/31-100004500045000/(500/3)P4100000001-100200200/102/31001/3 -1/3000000200200/(2/3)P1000100000000P2000011000000P3-500/3000125/3125/3010000P4-100000000100P5000000000010d3-d1-d5+d4-x2检验数

11、检验数Page:17QSC华东理工大学 工商经济学院运筹学运运筹筹学学整整数数线线性性规规划划Page:18QSC华东理工大学 工商经济学院运筹学整数线性规划问题的一般形式整数线性规划问题的一般形式max(min)zc xc xc xnn1122mnmnmmnnnnbxaxaxabxaxaxabxaxaxats).().().(. .22112222212111212111中部分或全部取整数nxxx,11Page:19QSC华东理工大学 工商经济学院运筹学整数线性规划问题的分类整数线性规划问题的分类全整数线性规划全整数线性规划混合整数线性规划混合整数线性规划0-1整数线性规划整数线性规划Pag

12、e:20QSC华东理工大学 工商经济学院运筹学整数规划与其松弛问题整数规划与其松弛问题当放弃整数约束时得到的线性规当放弃整数约束时得到的线性规划称为整数规划的松弛问题。划称为整数规划的松弛问题。整数规划的可行域是松弛问题的整数规划的可行域是松弛问题的可行域，反之不成立。可行域，反之不成立。Page:21QSC华东理工大学 工商经济学院运筹学全整数规划的求解全整数规划的求解-GomoryGomory割平面方法割平面方法为整数x,x 0 x,x 5x2x104x5x 3x23x . . x3xzmax 212121212121ts132X2X1 22.5154整数点整数点松弛问题最优解松弛问题最优

13、解Page:22QSC华东理工大学 工商经济学院运筹学松弛问题的最优解松弛问题的最优解3-1000 x1x2x3x4x5RHS3101/702/713/7-101-2/703/79/7000-3/7122/731/700-5/70-3/7x4x1x2检验数检验数Page:23QSC华东理工大学 工商经济学院运筹学GomoryGomory定理定理000,ijjiibxax在松弛问题的最优单纯形表中，假如有一常数在松弛问题的最优单纯形表中，假如有一常数项项 不是整数，且对应的方程为：不是整数，且对应的方程为：0ib000000,iiijijijifNbfNa分解分解 和和 成最大整数与正分数之和：

14、成最大整数与正分数之和：jia,00ibPage:24QSC华东理工大学 工商经济学院运筹学000,ijjiibxax00000)(,iijjijiifNxfNxjjiiijjiixffNxNx,000000,00jjiixff则则包含了整数规划的所有整数可行解，但不包括包含了整数规划的所有整数可行解，但不包括松弛问题的最优解松弛问题的最优解Page:25QSC华东理工大学 工商经济学院运筹学例题求解例题求解选择第一个方程：选择第一个方程：7137271531xxx分解为：分解为：5317271761xxxPage:26QSC华东理工大学 工商经济学院运筹学072717653xx在原松弛问题中

15、加入约束：在原松弛问题中加入约束：767271653xxx即即形成松弛问题形成松弛问题2Page:27QSC华东理工大学 工商经济学院运筹学3-10000 x1x2x3x4x5x6RHS3101/702/7013/7-101-2/703/709/7000-3/7122/7031/7000-1/70-2/71-6/700-5/70-3/70 x4x1x2检验数检验数x63-10000 x1x2x3x4x5x6RHS31000011-1010-1/40-5/45/40001-1/20-11/25/200001/41-3/47/4000-1/40-17/4x3x1x2检验数检验数x5Page:28Q

16、SC华东理工大学 工商经济学院运筹学132X2X1 22.5154整数点整数点松弛问题松弛问题2的最优解的最优解010727176153xxx或：割平面割平面Page:29QSC华东理工大学 工商经济学院运筹学选择第四个方程（具有最大分数部分）：选择第四个方程（具有最大分数部分）：474341645xxx分解为：分解为：64654141431xxxxPage:30QSC华东理工大学 工商经济学院运筹学在松弛问题在松弛问题2中加入约束：中加入约束：即即形成松弛问题形成松弛问题3041414364xx434141764xxxPage:31QSC华东理工大学 工商经济学院运筹学3-100000 x1

17、x2x3x4x5x6x7RHS310000101-1010-1/40-5/405/40001-1/20-11/205/200001/41-3/407/40 00 000-1/40-1/41 1-3/4000-1/40-17/40 x3x1x2检验数检验数x5x73-100000 x1x2x3x4x5x6x7RHS310000101-101000-1-12000100-5-24000001-1110 00 000101-4300000-40 x3x1x2检验数检验数x5x7得到最优解得到最优解Page:32QSC华东理工大学 工商经济学院运筹学割平面：割平面：52 1045 323767271

18、43414152142132165364xxxxxxxxxxxxxx3221 xx132X2X1 22.5154松弛问题松弛问题3的最优解的最优解松弛问题松弛问题2的最优解的最优解Page:33QSC华东理工大学 工商经济学院运筹学如果选择第二个方程：如果选择第二个方程：454541642xxx分解为：分解为：6464243434112xxxxxPage:34QSC华东理工大学 工商经济学院运筹学在松弛问题在松弛问题2中加入约束：中加入约束：即即形成松弛问题形成松弛问题3043434164xx414343764xxxPage:35QSC华东理工大学 工商经济学院运筹学3-100000 x1x2

19、x3x4x5x6x7RHS310000101-1010-1/40-5/405/40001-1/20-11/205/200001/41-3/407/40 00 000-3/40-3/41 1-1/4000-1/40-17/40 x3x1x2检验数检验数x5x73-100000 x1x2x3x4x5x6x7RHS310000101-101000-104/3000100-508/3000001-105/30 00 000101-4/31/300000-40 x3x1x2检验数检验数x5x4没有找到整数解，没有找到整数解，继续做下去继续做下去Page:36QSC华东理工大学 工商经济学院运筹学混合整数

20、规划的求解混合整数规划的求解-分枝定界方法分枝定界方法分枝：分枝：当当 不符合整数要求时，构造不符合整数要求时，构造两个约束条件：两个约束条件：iibx 1 iiiibxbx和加入松弛问题分别形成两个子问题（分枝）加入松弛问题分别形成两个子问题（分枝）定界：定界：当子问题获得整数规划的一个可行当子问题获得整数规划的一个可行解，则它的目标函数值就构成一个界限解，则它的目标函数值就构成一个界限Page:37QSC华东理工大学 工商经济学院运筹学例例取整数2121212121, 0,3121451149x . .xz maxxxxxxxxtsx132X254X1 231)310,23(AS解解S得：

21、得：941 310,23 :21zxxAPage:38QSC华东理工大学 工商经济学院运筹学132X254X1 231)310,23(AS2对对S分枝：分枝：构造约束：构造约束：21x和和11x形成分枝问题形成分枝问题S1和和S2，得解，得解B和和CS1)37, 1 (C)923, 2(B941923);(2, :zB31037);(1, :zCPage:39QSC华东理工大学 工商经济学院运筹学SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/911x21xPage:40QSC华东理工大学 工商经济学院运筹学13

22、2X254X1 231)310,23(AS2对对S1分枝：分枝：构造约束：构造约束：32x和和22x形成分枝问题形成分枝问题S11和和S12，得解，得解DS12)2 ,(1433D14611433);,2( :zDS11无可行解无可行解Page:41QSC华东理工大学 工商经济学院运筹学SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11无可行解无可行解S12D:x1=33/14,x2=2Z=61/1411x32x22x21xPage:42QSC华东理工大学 工商经济学院运筹学132X254X1 231)31

23、0,23(AS2对对S12分枝：分枝：构造约束：构造约束：31x和和21x形成分枝问题形成分枝问题S121和和S122，得解，得解E和和FS121) 1 , 3(E4);(3,1 :zES122)2 , 2(F4);(2,2 :zFPage:43QSC华东理工大学 工商经济学院运筹学SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11无可行解无可行解S12D:x1=33/14,x2=2Z=61/1411x32x22x21xS122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=431x21xPa

24、ge:44QSC华东理工大学 工商经济学院运筹学0-10-1整数规划整数规划变量只能取变量只能取0或或1的整数线性规划的整数线性规划Page:45QSC华东理工大学 工商经济学院运筹学0-10-1规划的应用规划的应用- -项目投资预算项目投资预算 资金需求资金需求(1000$) 项项 目目 估计现值估计现值 第一年第一年 第二年第二年 第三年第三年 第四年第四年 工厂扩建工厂扩建 90 15 20 20 15 销售网点扩建销售网点扩建 40 10 15 20 5 新生产流水线新生产流水线 10 10 0 0 4 新产品研究新产品研究 37 15 10 10 10 可用资金可用资金 40 50

25、40 35 Page:46QSC华东理工大学 工商经济学院运筹学模型模型变量假设变量假设:项目没有选中如果第选中目项第果如iixi 0 1max z= 90 x1+40 x2+10 x3+37x4s.t.15x1+10 x2+10 x3+15x44020 x1+15x2 + 10 x45020 x1+20 x2+ 10 x44015x1+5x2+4x3+10 x435x1, x2, x3, x4, =0,1模型模型:Page:47QSC华东理工大学 工商经济学院运筹学0-10-1规划的应用规划的应用- -工厂工厂- -销售点配置问题销售点配置问题生产厂生产厂顾客需求顾客需求销售点销售点45DC

26、BA7IIIII213IPage:48QSC华东理工大学 工商经济学院运筹学工厂工厂- -销售点配置问题销售点配置问题- -问题描述问题描述IIIIII生产能力生产能力1 18008001,0001,0001,2001,20030030035,00035,0002 240040050050070070020020045,00045,0003 380080060060050050030030040,00040,0004 450050060060070070020020042,00042,0005 570070060060050050040040040,00040,000ABCDI40408080

27、9090505040,00040,000II707040406060808020,00020,000III808030305050606060,00060,000需求量需求量200200300300150150250250运输成本运输成本: 工厂工厂-销售点销售点开设的固开设的固定成本定成本开设的固开设的固定成本定成本运输成本运输成本: 销售点销售点-客户客户问题问题: 为使经营成本最低为使经营成本最低,应开设那些工厂及销售点应开设那些工厂及销售点?Page:49QSC华东理工大学 工商经济学院运筹学工厂工厂- -销售点配置问题销售点配置问题- -销售点不开设第销售点开设第厂不开设第厂开设第j

28、jviiuji 0 1 0 1 客户运输量销售点到第第销售点运输量厂到第第客户需求量第厂供应能力第销售点开设成本第厂开设成本第客户运价销售点到第第销售点运价厂到第第kjyjixkDiBjcickjcjicjkijkijijkij Page:50QSC华东理工大学 工商经济学院运筹学工厂工厂- -销售点配置问题销售点配置问题- - KkDy,N,jvyxMiuBxStvcucycxcZMinkNjjkKkjjkMiijiiNjijjNjjiNjMiijkKkjkMiijNjij, 2 , 1 , 21 , )( , 2 , 1 , 1111111111客户需求：供销平衡：供应能力：Page:51

29、QSC华东理工大学 工商经济学院运筹学0-10-1规划的求解规划的求解隐枚举方法隐枚举方法10,x6 4 3 x44x22x . .523xz max3213221321321321或xxxxxxxxxtsxxPage:52QSC华东理工大学 工商经济学院运筹学(x1,x2,x3)z值值过滤条件过滤条件（1） （2） （3） （4）（0，0，0）0z0（0，0，1）5z5（0，1，0）-2（0，1，1）3（1，0，0）3（1，0，1）8z8（1，1，0）1（1，1，1）6约束条件约束条件最优解（最优解（x1,x2,x3)=(1,0,1); z=8隐枚举方法求解过程隐枚举方法求解过程Page:5

30、3QSC华东理工大学 工商经济学院运筹学经典指派问题经典指派问题n个员工分配作个员工分配作n项工作，一致项工作，一致的的i个员工作的个员工作的j项工作的成本为项工作的成本为cij，i=1,n; j=1,n。求最佳。求最佳分配方案。分配方案。Page:54QSC华东理工大学 工商经济学院运筹学指派问题的数学模型指派问题的数学模型 0 1否则项工作员工分配做第第jixijn1in1jijijc=zMin xn,1,2,=i 1xn1jijn ,1,2,=j 1xn1iijn,1,=jn;,1,2,=i 1,0 xij或s.t.Page:55QSC华东理工大学 工商经济学院运筹学nnnnnnnncc

31、ccccccccccccccC321333323122322211131211指派问题的解应对应于成本矩阵的不同指派问题的解应对应于成本矩阵的不同行与不同列，且总成本最小行与不同列，且总成本最小Page:56QSC华东理工大学 工商经济学院运筹学例例B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106cijPage:57QSC华东理工大学 工商经济学院运筹学指派问题的性质指派问题的性质定理：定理：对于指派问题，成本矩阵的任一对于指派问题，成本矩阵的任一行行(或列或列)减去减去(或加上或加上)一个相同的数得到一个相同的数得到的新指派问题与

32、原问题同解的新指派问题与原问题同解Page:58QSC华东理工大学 工商经济学院运筹学s)( s)(xcxc xs)(xcxc s)x(cxc=z n1jkjkjnki1in1jijijn1jkjn1jkjkjnki1in1jijijn1jkjkjnki1in1jijijzPage:59QSC华东理工大学 工商经济学院运筹学指派问题的求解指派问题的求解- -匈牙利方法匈牙利方法成本矩阵的每一行及每一列减去该行或成本矩阵的每一行及每一列减去该行或列的最小数，使每行每列至少有一个列的最小数，使每行每列至少有一个0。如果划去这些如果划去这些0所需要的直线数不少于所需要的直线数不少于n，则此时就可以求

33、得最优解。则此时就可以求得最优解。Page:60QSC华东理工大学 工商经济学院运筹学例题求解例题求解6101296106147678129610141797121578466674310463040810126303710208113400432040500123203771081103004320405001232037710811030Page:61QSC华东理工大学 工商经济学院运筹学043204050012320377108110300432140501012102110081103104321405010121021100811031Page:62QSC华东理工大学 工商经济学院运

34、筹学一般指派问题一般指派问题最大化指派问题最大化指派问题人数和工作数不等的指派问题人数和工作数不等的指派问题一个人可做几项工作的指派问题一个人可做几项工作的指派问题某项工作一定不能由某人做的指派问题某项工作一定不能由某人做的指派问题Page:63QSC华东理工大学 工商经济学院运筹学最大化指派问题最大化指派问题610129610617711781296101429121215784最大化指派问题最大化指派问题最大值最大值6171017121791761710176171717717111771781712179176171017141721791712171217151771781741711

35、75811711010610958117315855210913最最小小化化指指派派问问题题Page:64QSC华东理工大学 工商经济学院运筹学人数和工作数不等的指派问题人数和工作数不等的指派问题1012966177118129614291215784101296617711812961429121578400000Page:65QSC华东理工大学 工商经济学院运筹学一个人可做几项工作的指派问题一个人可做几项工作的指派问题78329824763195232154321BBBBBAAA 31952319527832982476319525432111321BBBBBAAAAAA1可同时做可同时做三项工作三项工作Page:66QSC华东理工大学 工商经济学院运筹学某项工作一定不能由某人做的指派问题某项工作一定不能由某人做的指派问题452782946178298247639525432154321BBBBBAAAAA4 5 2 782 9 4 6178298247639525432154321MMAAAAABBBBBA1不能做不能做B4;A3不能做不能做B3