运筹学复习题.ppt

1、1,复习题,2,1. 用单纯形法求解下列规划问题,Max Z = 5x1 + 2x2 + 3x3 - x4 x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 0,3,2.已知运输问题的供需关系表与运价表, 试用表上作业法求最优解,4,3.某钻井队要从以下10个可供选择的井位中确定5个钻井探油,使得总的钻探费用为最小。若10个井位的代号为s1，s2，s10，相应的钻探费用为c1，c2，c10，并且井位选择上要满足下列限制条件： 或选择s1和s7，或选择钻探s8； 选择了s3或s4就

2、不选s5，反之亦然； 在s5，s6，s7，s8中最多只能择两个； 试建立这个问题的整数规划模型。,5,4某彩色电视机组装厂，生产A，B，C三种规格的电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6小时，8小时和10小时。生产线每月正常工作时间为200小时；三种规格电视机销售后，每台可获利分别为500元，650元和800元。每月销量预计为12台，10台，6台。该厂经营目标如下： P1:利润指标定为每月 16000元； P2:充分利用生产能力； P3:加班时间不超过24小时； P4:产量以预计销量为标准； 为确定生产计划,试建立该问题的目标规划模型。,6,5.用求 V1 至 V

3、6 的最短距离与最短路径,13,9,18,10,7,12,19,12,5,V1,V2,V3,V5,V4,V6,7,6.用标号算法,求 V1 至 V6 的最大流,8,1. 用单纯形法求解下列规划问题,9,10,最优解为：,最优值为：,11,Max Z= 5x1+ 2x2+ 3x3-x4 -M x5-M x6 x1+ 2x 2+ 3 x3+ x5 =15 2 x1+ x2+ 5 x3+ x6 = 20 x1+ 2 x2+ 4 x3+ x4 = 26 x1 ,x2 ,x3 ,x4 ,x5 ,x6 0,Max Z = 5x1 + 2x2 + 3x3 - x4 x1 + 2x2 + 3x3 = 15 2

4、x1 + x2 + 5x3 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 0,12,13,得到最优解：(25/3，10/3，0，11)T ，最优目标值：112/3,Max Z = 5x1 + 2x2 + 3x3 - x4 x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 0,14,2已知运输问题的供需关系表与运价表, 试用表上作业法求最优解,15,解:(1)以最小元素法确定初始基本可行解 并以闭回路法判别,16,解:(1)以最小元

5、素法确定初始基本可行解 并以闭回路法判别,17,解:(2) 以闭回路法调整,并判别,由于所有检验数均大于等于零,此解是最优解.,18,3.某钻井队要从以下10个可供选择的井位中确定5个钻井探油,使得总的钻探费用为最小。若10个井位的代号为s1，s2，s10，相应的钻探费用为c1，c2，c10，并且井位选择上要满足下列限制条件： 或选择s1和s7，或选择钻探s8； 选择了s3或s4就不选s5，反之亦然； 在s5，s6，s7，s8中最多只能择两个； 试建立这个问题的整数规划模型。,19,3. 解:设0-1变量,该问题的整数规划模型为:,x1x8 =1 x3x5 1 x7x8 =1 x4x5 1 x

6、5x6 x7x8 2 xi 0 ,且xi为0-1变量, (i=1,2 ,10),20,4某彩色电视机组装厂，生产A，B，C三种规格的电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6小时，8小时和10小时。生产线每月正常工作时间为200小时；三种规格电视机销售后，每台可获利分别为500元，650元和800元。每月销量预计为12台，10台，6台。该厂经营目标如下： P1:利润指标定为每月 16000元； P2:充分利用生产能力； P3:加班时间不超过24小时； P4:产量以预计销量为标准； 为确定生产计划,试建立该问题的目标规划模型。,21,4. 解:设生产A型电视机x1台，B

7、型电视机x2台，C型电视机x3台,该问题的目标规划模型为:,Min z= P1（d1-）+P2（d2-） +P3（d3+） + P4（d4+ + d4- + d5+ d5- + d6+ + d6-） 500 x1650 x2 800 x3 -d1+d1- =16000 6x1 8x2 10 x3 d2+d2- =200 6x1 8x2 10 x3 d3+d3- =224 x1-d4+d4-=12 x2-d5+d5-=10 x3-d6+d6-=6 x1,x2, x3 0 ; di+,di-0 (i=1,2 ,6),22,5.解:,23,.给出点 V1 以标号 (0，s) 2. s12=l1+c1

8、2 =0 + 13 =13 s13=l1+c13 =0 + 9 =9 MIN (s12 , s13) = s13 =9 给出点 V3 以标号 (9，1) 3. s12=l1+c12 =0 + 13 =13 s34=l3+c34 =9 + 18 =27 s35=l3+c35 =9 + 12 =21 MIN (s12 , s34 , s35) = s12 =13 给出点 V2 以标号 (13，1) 4. s24=l2+c24 =13 + 10 =23 s34=l3+c34 =9 + 18 =27 s35=l3+c35 =9 + 12 =21 MIN (s24 , s34 , s35) = s35

9、=21 给出点 V5以标号 (21，3),5. s24=l2+c24 =13 + 10 =23 s56=l5+c56 =21 + 19 =40 MIN (s24 , s56) = s24 =23 给出点 V4以标号 (23，2) 6. s46=l4+c46 =23 + 12 =35 s56=l5+c56 =21 + 19 =40 MIN (s46 , s56) = s46 =35 给出点 V6以标号 (35，4) 7.计算结束,得到最短路 V1 至 V6 的最短距离为35 最短路径为V1-V2-V4-V6,24,6.解 (1)通过标号求寻找可增广链V1-V2-V4-V6,，+,+ V1 ， 1 ,+ V1 ， 6 ,+ V2 ， 5 ,- V2 ， 2 ,+ V4 ， 2 ,25,6.解 (2)调整值为2,26,6.解 (3)再通过标号求寻找可增广链V1-V2-V5-V6,，+,+ V1 ， 4 ,+ V1 ， 1 ,+ V2 ， 3 ,- V2 ， 2 ,+ V5 ， 2 ,27,6.解 (4)调整值为2,28,6.解 (5)再通过标号求寻找可增广链V1-V3-V5-V6,，+,+ V1 ， 2 ,+ V2 ， 2 ,+ V1 ， 1