运筹学复习题PPT课件

1、2021/7/231复习题2021/7/2321. 用单纯形法求解下列规划问题用单纯形法求解下列规划问题 0,63422. .3Min 43214213214321xxxxxxxxxxtsxxxxZ Max Z = 5x1 + 2x2 + 3x3 - x4 x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 02021/7/2332.2.已知运输问题的供需关系表与运价表已知运输问题的供需关系表与运价表, ,试用表上作业法求最优解试用表上作业法求最优解 销地销地产地产地甲甲乙乙丙丁丁

2、产量产量1 13 32 27 76 650502 27 75 52 23 360603 32 25 54 45 52525销量销量60604040202015152021/7/2343.3.某钻井队要从以下某钻井队要从以下1010个可供选择的井位中确定个可供选择的井位中确定5 5个钻井个钻井探油探油, ,使得总的钻探费用为最小。若使得总的钻探费用为最小。若1010个井位的代号为个井位的代号为s s1 1，s s2 2，ss1010，相应的钻探费用为，相应的钻探费用为c c1 1，c c2 2，c c1010，并且井位，并且井位选择上要满足下列限制条件：选择上要满足下列限制条件：或选择或选择s

3、s1 1和和s s7 7，或选择钻探，或选择钻探s s8 8；选择了选择了s s3 3或或s s4 4就不选就不选s s5 5，反之亦然；，反之亦然；在在s s5 5，s s6 6，s s7 7，s s8 8中最多只能择两个；中最多只能择两个；试建立这个问题的整数规划模型。试建立这个问题的整数规划模型。2021/7/2354 4某彩色电视机组装厂，生产某彩色电视机组装厂，生产A A，B B，C C三种规格的电视机。三种规格的电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为分别为6 6小时，小时，8 8小时和小时和1010小时

4、。生产线每月正常工作时间为小时。生产线每月正常工作时间为200200小时；三种规格电视机销售后，每台可获利分别为小时；三种规格电视机销售后，每台可获利分别为500500元，元，650650元和元和800800元。每月销量预计为元。每月销量预计为1212台，台，1010台，台，6 6台。台。该厂经营目标如下：该厂经营目标如下：P1:P1:利润指标定为每月利润指标定为每月 1600016000元；元；P2:P2:充分利用生产能力；充分利用生产能力；P3:P3:加班时间不超过加班时间不超过2424小时；小时；P4:P4:产量以预计销量为标准；产量以预计销量为标准；为确定生产计划为确定生产计划, ,试

5、建立该问题的目标规划模型。试建立该问题的目标规划模型。2021/7/2365.5.用求用求 V V1 1 至至 V V6 6 的最短距离与最短路径的最短距离与最短路径13139 9181810107 71212191912125 5V V1 1V V2 2V V3 3V V5 5V V4 4V V6 62021/7/2376.6.用标号算法用标号算法, ,求求 V V1 1 至至 V V6 6 的最大流的最大流(14,8)(14,8)(10,9)(10,9)(10,2)(10,2)(15,10)(15,10)(6,6)(6,6)(15,1)(15,1)(8,3)(8,3)(5,0)(5,0)V

6、 V1 1V V2 2V V3 3V V5 5V V4 4V V6 6(18,16)(18,16)2021/7/2381. 用单纯形法求解下列规划问题用单纯形法求解下列规划问题 0,63422. .3Min 43214213214321xxxxxxxxxxtsxxxxZ解解: 令令ZZ于是原线性规划问题变为标准形式：于是原线性规划问题变为标准形式：0,63422. .3Max 43214213214321xxxxxxxxxxtsxxxxZ2021/7/239迭代迭代次数次数基基C CB Bx x1 1x x2 2x x3 3x x4 4b b比值比值-3-3-1-1-1-1-1-10 0 x

7、x3 3-1-1-2-22 21 10 04 42 2x x4 4-1-13 31 10 01 16 66 6z zj j-1-1-3-3-1-1-1-1 j j= = c cj j - -z zj j-2-22 20 00 01 1x x2 2-1-1-1-11 11/21/20 02 2- -x x4 4-1-14 40 0-1/2-1/21 14 41 1z zj j-3-3-1-10 0-1-1 j j= = c cj j - -z zj j0 00 0-1-10 02 2x x2 2-1-10 01 13/83/81/41/43 3- -x x1 1-3-31 10 0-1/8-1/

8、81/41/41 11 1z zj j1 10 00 0-1-1 j j= = c cj j - -z zj j0 00 0-1-10 02021/7/231010100314020*2*1*2*1其中XXXXX6*ZZ2021/7/2311 Z Z= 5= 5x1 1+ 2+ 2x2 2+ 3+ 3x3 3- -x4 4 - - x5 5- - x6 6 x1 1+ 2+ 2x 2 2+ 3 + 3 x3 3+ + x5 5 =15 =15 2 2 x1 1+ + x2 2+ 5 + 5 x3 3+ + x6 6 = 20 = 20 x1 1+ 2 + 2 x2 2+ 4 + 4 x3 3+

9、 + x4 4 = 26 = 26 x1 1 , ,x2 2 , ,x3 3 , ,x4 4 , ,x5 5 , ,x6 6 0 0 Max Z = 5= 5x1 1 + 2+ 2x2 2 + 3+ 3x3 3 - - x4 4 x1 1 + 2+ 2x2 2 + 3+ 3x3 3 = 15 = 15 2 2x1 1 + + x2 2 + 5+ 5x3 3 = 20 = 20 x1 1 + 2+ 2x2 2 + 4+ 4x3 3 + + x4 4 = 26= 26 x1 1 , , x2 2 , , x3 3 , , x4 4 0 02021/7/2312 基基C CB Bx x1 1x x2

10、 2x x3 3x x4 4x x5 5x x6 6b b比值比值5 52 23 3-1-1-M-M-M-Mx x5 5-M-M1 12 23 30 01 10 01 51 55 5x x6 6-M-M2 21 1(5)(5)0 00 01 12 02 04 4x x4 4-1-11 12 24 41 10 00 02 62 66.56.5 j j3 M +63 M +63 M+43 M+48 M+78 M+70 00 00 035 M+2635 M+26x x5 5-M-M-1 / 5-1 / 57 / 57 / 50 00 01 1-3/5-3/53 315/715/7x x3 33 32

11、 / 52 / 51 / 51 / 51 10 00 01/51/54 42 02 0 x x4 4-1-1-3 / 5-3 / 56 / 56 / 50 01 10 0-4/5-4/51 01 025/325/3 j j-M / 5-M / 5+16/5+16/57/5M7/5M+13/5+13/50 00 00 0-8/5M-8/5M-7/5-7/53 M-23 M-2x x2 22 2-1/7-1/71 10 00 05/75/7-3/7-3/715 / 715 / 7x x3 33 3(3/7)(3/7)0 01 10 0-1/7-1/72/72/725 / 725 / 725/325

12、/3x x4 4-1-1-3/7-3/70 00 01 1-6/7-6/7-2/7-2/752 / 752 / 7 j j25/725/70 00 00 0-M-M-13/7-13/7-M-2/7-M-2/7-53 / 7-53 / 7x x2 22 20 01 11 / 31 / 30 02 / 32 / 3-1/3-1/310 / 310 / 3x x1 15 51 10 07 / 37 / 30 0-1 / 3-1 / 32/32/325 / 325 / 3x x4 42021/7/2313得到最优解：得到最优解：(25/3(25/3，10/310/3，0 0，11)11)T T ，最优

13、目标值：，最优目标值：112/3112/3 Max Z = 5= 5x1 1 + 2+ 2x2 2 + 3+ 3x3 3 - - x4 4 x1 1 + 2+ 2x2 2 + 3+ 3x3 3 = 15 = 15 2 2x1 1 + + x2 2 + 5+ 5x3 3 = 20 = 20 x1 1 + 2+ 2x2 2 + 4+ 4x3 3 + + x4 4 = 26= 26 x1 1 , , x2 2 , , x3 3 , , x4 4 0 02021/7/23142 2已知运输问题的供需关系表与运价表已知运输问题的供需关系表与运价表, ,试用表上作业法求最优解试用表上作业法求最优解 销地销

14、地产地产地甲甲乙乙丙丁丁产量产量1 13 32 27 76 650502 27 75 52 23 360603 32 25 54 45 52525销量销量60604040202015152021/7/2315 销地销地产地产地甲甲乙乙丙丙丁丁 产量产量13276 501040 9 727523 6025-1 201532545 2525 4 77 销量销量 60 4020 15 135135解解:(1)以最小元素法确定初始基本可行解以最小元素法确定初始基本可行解 并以闭回路法判别并以闭回路法判别2021/7/2316 销地销地产地产地甲甲乙乙丙丙丁丁 产量产量13276 50 10 01040

15、9727523 60 40 2525-1201532545 25 025477 销量销量 60 25 40 020 0 15 0 135135解解:(1)以最小元素法确定初始基本可行解以最小元素法确定初始基本可行解 并以闭回路法判别并以闭回路法判别2021/7/2317 销地销地产地产地甲甲乙乙丙丙丁丁 产量产量13276 503515 8 627523 60125 201532545 2525 466 销量销量 60 4020 15 135135解解:(2) 以闭回路法调整以闭回路法调整,并判别并判别由于所有检验数均大于等于零由于所有检验数均大于等于零,此解是最优解此解是最优解.2021/7

16、/23183.3.某钻井队要从以下某钻井队要从以下1010个可供选择的井位中确定个可供选择的井位中确定5 5个钻井个钻井探油探油, ,使得总的钻探费用为最小。若使得总的钻探费用为最小。若1010个井位的代号为个井位的代号为s s1 1，s s2 2，ss1010，相应的钻探费用为，相应的钻探费用为c c1 1，c c2 2，c c1010，并且井位，并且井位选择上要满足下列限制条件：选择上要满足下列限制条件：或选择或选择s s1 1和和s s7 7，或选择钻探，或选择钻探s s8 8；选择了选择了s s3 3或或s s4 4就不选就不选s s5 5，反之亦然；，反之亦然；在在s s5 5，s

17、s6 6，s s7 7，s s8 8中最多只能择两个；中最多只能择两个；试建立这个问题的整数规划模型。试建立这个问题的整数规划模型。2021/7/23193. 3. 解解: :设设0-10-1变量变量, ,没被选用当被选用当iiiSSx, 0, 1该问题的整数规划模型为该问题的整数规划模型为: :jjjxcz101min5101jjxx1x8 =1 x3x5 1 x7x8 =1 x4x5 1 x5x6 x7x8 2xi 0 ,且xi为0-1变量, (i=1,2 ,10) 2021/7/23204 4某彩色电视机组装厂，生产某彩色电视机组装厂，生产A A，B B，C C三种规格的电视机。三种规格

18、的电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为分别为6 6小时，小时，8 8小时和小时和1010小时。生产线每月正常工作时间为小时。生产线每月正常工作时间为200200小时；三种规格电视机销售后，每台可获利分别为小时；三种规格电视机销售后，每台可获利分别为500500元，元，650650元和元和800800元。每月销量预计为元。每月销量预计为1212台，台，1010台，台，6 6台。台。该厂经营目标如下：该厂经营目标如下：P1:P1:利润指标定为每月利润指标定为每月 1600016000元；元；P2:P2:充分利用生产能

19、力；充分利用生产能力；P3:P3:加班时间不超过加班时间不超过2424小时；小时；P4:P4:产量以预计销量为标准；产量以预计销量为标准；为确定生产计划为确定生产计划, ,试建立该问题的目标规划模型。试建立该问题的目标规划模型。2021/7/23214. 4. 解解: :设生产设生产A A型电视机型电视机x x1 1台，台，B B型电视机型电视机x x2 2台，台，C C型电视机型电视机x x3 3台台, ,该问题的目标规划模型为该问题的目标规划模型为: :Min z= PMin z= P1 1（d d1 1- -）+P+P2 2（d d2 2- -） +P+P3 3（d d3 3+ +） +

20、 P+ P4 4（d d4 4+ + + + d d4 4- - + + d d5 5+ + + d d5 5- - + + d d6 6+ + + + d d6 6- -） 500 x500 x1 1650 x650 x2 2 800 x800 x3 3 -d-d1 1+ +d+d1 1- - =16000=16000 6x 6x1 1 8x8x2 2 10 x10 x3 3 dd2 2+ +d+d2 2- - =200=200 6x 6x1 1 8x8x2 2 10 x10 x3 3 dd3 3+ +d+d3 3- - =224=224 x x1 1-d-d4 4+ +d+d4 4- -=

21、12=12 x x2 2-d-d5 5+ +d+d5 5- -=10=10 x x3 3-d-d6 6+ +d+d6 6- -=6=6 x x1 1,x,x2 2, x, x3 3 0 ; d0 ; di i+ +,d,di i- -0 (i=1,2 ,6)0 (i=1,2 ,6)2021/7/23225.5.解解: :13139 9181810107 71212191912125 5V V1 1(0,s)(0,s)V V2 2(13,1)(13,1)V V3 3(9,1)(9,1)V V5 5(21,3)(21,3)V V4 4(23,2)(23,2)V V6 6(35,4)(35,4)20

22、21/7/2323. .给出点给出点 V V1 1 以标号以标号 (0(0，s)s)2. s2. s1212=l=l1 1+c+c1212 =0 + 13 =13 =0 + 13 =13 s s1313=l=l1 1+c+c1313 =0 + 9 =9 =0 + 9 =9 MIN (s MIN (s12 12 , , s s1313) =) = s s13 13 =9=9 给出点给出点 V V3 3 以标号以标号 (9(9，1)1)3. s3. s1212=l=l1 1+c+c1212 =0 + 13 =13 =0 + 13 =13 s s3434=l=l3 3+c+c3434 =9 + 18

23、 =27 =9 + 18 =27 s s3535=l=l3 3+c+c3535 =9 + 12 =21 =9 + 12 =21 MIN (s MIN (s12 12 , , s s34 34 , , s s3535) =) = s s12 12 =13=13 给出点给出点 V V2 2 以标号以标号 (13(13，1)1)4. s4. s2424=l=l2 2+c+c2424 =13 + 10 =23 =13 + 10 =23 s s3434=l=l3 3+c+c3434 =9 + 18 =27 =9 + 18 =27 s s3535=l=l3 3+c+c3535 =9 + 12 =21 =9

24、 + 12 =21 MIN (s MIN (s24 24 , , s s34 34 , , s s3535) =) = s s35 35 =21=21 给出点给出点 V V5 5以标号以标号 (21(21，3)3)5. s5. s2424=l=l2 2+c+c2424 =13 + 10 =23 =13 + 10 =23 s s5656=l=l5 5+c+c5656 =21 + 19 =40 =21 + 19 =40 MIN (s MIN (s24 24 , , s s5656) =) = s s24 24 =23=23 给出点给出点 V V4 4以标号以标号 (23(23，2)2)6. s6.

25、 s4646=l=l4 4+c+c4646 =23 + 12 =35 =23 + 12 =35 s s5656=l=l5 5+c+c5656 =21 + 19 =40 =21 + 19 =40 MIN (s MIN (s46 46 , , s s5656) =) = s s46 46 =35=35 给出点给出点 V V6 6以标号以标号 (35(35，4)4)7.7.计算结束计算结束, ,得到最短路得到最短路 V V1 1 至至 V V6 6 的最短距离为的最短距离为3535 最短路径为最短路径为V V1 1-V-V2 2-V-V4 4-V-V6 62021/7/23246.6.解解 (1)(

26、1)通过标号求寻找可增广链通过标号求寻找可增广链V V1 1-V-V2 2-V-V4 4-V-V6 6(14,8)(14,8)(10,9)(10,9)(10,2)(10,2)(15,10)(15,10)(6,6)(6,6)(15,1)(15,1)(8,3)(8,3)(5,0)(5,0)V V1 1V V2 2V V3 3V V5 5V V4 4V V6 6(18,16)(18,16) ，+ + V1 ， 1 + V1 ， 6 + V2 ， 5 - V2 ， 2 + V4 ， 2 2021/7/23256.6.解解 (2)(2)调整值为调整值为2 2(14,10)(14,10)(10,9)(10

27、,9)(10,2)(10,2)(15,12)(15,12)(6,6)(6,6)(15,1)(15,1)(8,3)(8,3)(5,0)(5,0)V V1 1V V2 2V V3 3V V5 5V V4 4V V6 6(18,18)(18,18)2021/7/23266.6.解解 (3)(3)再通过标号求寻找可增广链再通过标号求寻找可增广链V V1 1-V-V2 2-V-V5 5-V-V6 6(14,10)(14,10)(10,9)(10,9)(10,2)(10,2)(15,12)(15,12)(6,6)(6,6)(15,1)(15,1)(8,3)(8,3)(5,0)(5,0)V V1 1V V2 2V V3 3V V5 5V V4 4V V6 6(18,18)(18,18) ，+ + V1 ， 4 + V1 ， 1 + V2 ， 3 - V2 ， 2 + V5 ， 2 2021/7/23276.6.解解 (4)(4)调整值为调整值为2 2(14,12)(14,12)(10,9)(10,9)(10,0)(10,0)(15,12)(15,12)(6,6)(6,6)(15,3)(15,3)(8,3)(8,3)(5,0)(5,0)V V1 1V V2 2V V3 3V V5 5V V4 4V V6 6(18,18)