运筹学复习资料

1、Au分别用图解法和单纯形法求解下面的线性规划问题Max z=2xl+x2s.t 3xl+5x215 6xl+2x20解：1)图解法：由上图可知，E点为最优点，最优解为(15/4,3/4),最优值为z=33/42)单纯形法：将上述线性规划问题化为标准形：Max z=2xl+x2s.t 3xl+5x2+x3=56xl+2x2+x4=24Xl,x2,x3/4N0利用单纯形法运算得到表一至表三：表2100CbbXIX2X3X40X31535100X42462012100表二2100CbXbbXIX2X3X40X33041-1/22XI41in01/601/30-132100CbXbbXIX2X3X41

2、X23/4011/4-1/82XI15/410-1/125/2400-1/12-7Z24由表三可知，线性规划问题的最优解为X*=(15/4,3/4Q0)T 目标函数的最优值为max z=33/4Az已知线性规划问题Max Z=xl+2x2+3x3+4x4s.Tx 14-2x2+2x3+3x4 W 202xl+x2+3x3+2x4W20xl ,x2、x3，x4 , $0其对偶问题的最优解为W=(1.2,0.2)T,试根据对偶理论求出原问题的最优解 解，该原问题的对偶问题为：nun Y=20wl+20w2s.T wl+2w2 $12wl+w2 2 22wl+3w2 2 3(1) wl+2w2l x

3、l=0(2) 2wl+w22x2=0(3) 2wl+3w2=33wl+2w2 $ 4（4）3wl+2w2=4wl、w2 2 0将对偶问题的最优解代入，得到（1）,（2）为严格不等式，故由互补松驰性质得到 Xl=x2=0又wl,w20,由松驰性质得到原问题约束条件应取等号即wl02x3+3x4=20w2 03x3+2x4=20, 解方程组，得 x3=x4=4所以原问题的最优解为：X=（0,0,4,4）T3已知线性规划问题Max Z=2xl+x2+5x3+6x4s.T2x1+ x3+x4 W 82xl+2x2+x3+2x4W12xl ,x2、x3，x4、$0其对偶问题的最优解为v=（4,l）T，试

4、根据对偶理论求出原问题的最优解 解，该原问题的对偶问题为：inin Y=8wl+12w2s.T 2wl+2w2 $2(1)2wl+2w22 xl=02w2 2 1(2)2w2lwl+ w2 鼻 5(3)wl+w2=5wl+2w2 2 6(4)wl+2w2=6wl、w2 鼻 0将对偶问题的最优解代入,x2=0得到（1）,（2）为严格不等式，故由互补松驰性质得到Xl=x2=0又wl,w20,由松驰性质得到原问题约束条件应取等号即Wl0x3+x4=8W20x3+2x4=12,解方程组，得 x3=x4=4所以原问题的最优解为X=(0Q4,4)TA4 a工厂计划生产甲、乙两种产品。每T克产品的销售价格和

5、能源消耗量.以及能源资源见表3-26,怎样安排生产计划才能使A工厂获益最人?表 3-26Pp甲门乙门资源限壘卩煤（吨）p32360电（千瓦4） Q4p5a200油（吨）a3p10p300单价（万元）心7p12p-P解：X1：产品甲的计划生产量；X2：产品乙的计划生产量，则有如下线性规划问题: max z=7xl + 12x2（总销售收入）s.t. 9xl+4x2W 360（煤资源限制）4x1 + 5x2 W 200（电资源限制）3x1 + 10x2W300（油资源限制）xl $ 0, x2 $ 0 （非负条件）用单纯形法求解得：xl=20, x2=24oXhbXlx2*3*50Xa224.40

6、01-3.121.160Xi201000.4-0.212X224010-0.120.04-428000-1.36-0.52712000QXbbXi2%0X3360941000200450100X53003100010712000XbbXix2X3&02407.8010-0.40&502.5001-0.512X2300.31000.1-3603.4000-1.2原问题的最优解为X=(20,24)T、对应的对偶价格, 也就是影子价格为(0,1.36,0.52)A5已知企业关于获利的线性规划问题如卞所示:Max z=5xl+5x2+13x3s.T-xl+x2+3x3 W 2012x1+4x2+10x

7、390xl ,x2、x3$0(1) 试确定获得最大利润的产品计划。(2) 产品E的利润(即X2)在什么范围内变化时，上述的最优生产计划不变。(3) 如果设计一种新产品D,单位劳动力(即第一种资源)消耗为2单位，材料(第二种资源)消耗为3单位，每件可获利12元，问该产品是否值得生产？(1) 将原问题引入松驰变量化为标准，通过两步迭代得到最优单纯形表：即最优生产计划为：表三-551300CbXbBX.x2卷X4X55x220-113100X5101602-41002-50即最优生产计划为：xl=0Q=20、x3=0，最优值为max z=100(2)假设B产品的变化量为AC表三-551300Xbbb

8、X】X2X3X4X55X：20-113100X510160-2-410Ac-2-50解得:-2/3 AC W0故产品E在I3/3W AC W5时，最优生产计划为不变(3)由最优表可知，第一种资源的影子价格为5,第二种资源的影子价格为0,因此D产品的生产成本为：生产成本：5*2+0*3 = 1012 即生产成本小于12,企业有利图，值得生产。A6.P114 页。4.3 题解：设生产A、B、C三种产品的数量分别为XbX2,X3,依题意得:Max z=3xi+xz+4x3s.t 6x1+3x2+5x3453xi+4x：+5x330Xi, X：, x30利用单纯形法求解得表一至表三：表31400bXi

9、g&X5X44563510X,303450131400表二31400xbbXi%XsXfXi153-101-1X,63/54/5101/53/5-11/500-4/5表三31400xBbXix2X3X4X5Xi51-1/301/3-1/3X33011-1/52/50-20-1/5-3/5由表三可知，所有的检验数均小于等于0,所以表三为最优表, 最优解为X二(5, 0, 3)1(2) 设A产品的变化范闱为利用灵敏度分析得表四：表四31400XbbX1X：X3X4X5Xi511/301/3-1/3X33011-1/52/50Ac/3-20c/3-1/5c/3-3/5要使表四为最优表须：c/32W0

10、 -Ac/3-1/50 Ac/3-3/50解不等式得：-3/5WZcW9/5所以产品A的最优变化范围为12/5, 24/5(3) 由表三可知两种资源的影子价格分别为：1/5, 3/5增加新产品的成本为：1/5*8+2*3/5=14/5 01210 0 0 3(3)调整并试求最优解(4)调整并试求最优解(5)原问题的最优解为即最优解:00110 0 02 6 103 32 50011101004130100051000001000010100其余为0Xll=x24=x32=x43=l最优值为：z=15+18+21+16=70地7 9由4个人完成4项任务，由于能力不同，完成所需要的时间不同，具体如

11、下表：问 应如何指派才使总效率最高即总用时最少？人任务1234A!21097154148a313141611415139解：使效能矩阵每行每列出现0元2 10 9 715 4 14 813 14 16 114 15 13 9使每行 出现0元01120试求最优解解：(3)调整并试求最优解10 4使每列5 0出现0元9 5)(4)故原问题的最优解为0 8 2 511 0 5 42 3 0 00 11 4 50 8 2 511 0 5 42 3 0 0 0 11 4 50 8 0 311 0 3 24 5 0 00 11 2 310 0 00 0 0 10 10 00 0 10即 xll=x24=x

12、32=x43=最优值为：z=2+7+5+6=2010现要从A地出发，铺设一条天然气管道到F地，中间要经过4站, 每站都有几条路可供选择，并且已知各地间的距离(单位：百米)， 如下图所示，问应选择哪条路径使总的铺设路径最短？11现要从A地出发，铺设一条天然气管道到G地，中间要经过5站,每站都有几条路可供选择，并且已知各地间的距离(单位：百米), 如下图所示，问应选择哪条路径使总的铺设路径最短？下面再向t5方向开拓，当t5时，首先遇到o40,故此时，x4应进基,V5由上图可以得出最优的决策路径为：A-B1.C2-D1-E2.F2-G最短的铺设路径为1800米Xl, X20解：当t=0时，经过三次迭

13、代得到最终单纯形表一所示:12求下列线性参数规划问题max (3 + 2/)xi + (5 - t)xi t 0 d 4I 2a-2 12 3xi + 2x2 0X1 + X3 = 42x2 + X4 = 123x1 + 2x2 + X5 = 18X爲 0表一35000BX1X2*片0X320011Z3-1/3560101/203X12100-1/31/3Cj-Zj000-3/2-1将要求解的参数线性规划看成 xl的目标函数系数从3T3+2t 变化，取厶tl=2t,同理x2系 数的 x2=利用灵敏度分析得:表二3500()BxiX2X3X4X50X320011/3-1/35X260101/20

14、32100-1/31/3CjZj0003/2+7M6-l-2/3t解不等式：t0 -3/2+7t/60 -l-2/3t0坯9/7t-2/3故当0WW9/7时，最优解为：X=(2,6,2Q0)T 最优值 z=36-2t下面向t9/7方向开拓，当t9/7时，首先遇到。40,故此时，X4应进基, 利用最小比原则可得X3应为出基表二35000Bxix2X3X4X50X4600315301-3/201/23Xi410100C广Zj009/2-7t/205/2+t/2要使表二为最优表，须有：9/2-71/2 9/7-5/2+t/2 0 t 5时，首先遇到。40,故此时，x4应进 基，表=35000BxiX

15、2gX5012020100602-3013X1410100CjZj05-t-3-2t00综上所述:124-8/t5要使表三为最优表，须有：5-t 5-3-2t -3/2故当C5时，最优解为：X=（4,0,0,12,6）T 最优值 z=12+8t27+5/9/7/5z（）=36-2/0/9/70 r -3A13某地有10个村庄，它们之间的交通道路如下图所示， 图中边旁权为道路长度（单位：百米），现在要沿道架设电线， 实现村村通电话工程，问应如何架设电线才能使总长度最短?解如架设电线最短长度为18（百米）。附判断定理3.1 （对称性定理）对偶问题的对偶问题是原问题根据对称性定理，在任一对偶问题中，可以把其中的任何一个称为原问题，而把另一个