第四版运筹学部分课后习题解答模板

1、运筹学部分课后习题解答P47 1.1用图解法求解线性规划问题min z=2x 3x24 4x1 6x2 _ 6 st4x1 +2x2 >4! x1，x2 -0解：由图1可知，该问题的可行域为凸集 MABCN且可知线段BA上的点都为3最优解，即该问题有无穷多最优解，这时的最优值为 Zm"2M e+3父0=32P47 1.3用图解法和单纯形法求解线性规划问题max z=10x1 5x2、3x1 4x2 M 9a ),s.t5x1 十2x2 E8x1, x2之 0解：由图1可知，该问题的可行域为凸集 OABCO且可知B点为最优值点,即户% +4% =9=/3,即最优解为父=”(5Xi

2、 +2x2 =8|x2 =-I 2 J这时的最优值为Zmax = 10 1 5 - =3522原问题化成标准型为max z=10x1 5x23x1 4x2 x3 = 9st 5x1 +2x2 +x4 =8xi,x2,x3,x4 -0cj T10500CbXbbx1x2x3x40x3934100x485201Cj-z105000x321/5014/51-3/510xi8/512/501/5Cj-Z010-25x23/2015/14-3/1410xi110-1/72/7Cj-z00-5/14-25/14T*33 35所以有 x i1, ,zmax =10 1 5 一=一 222P78 2.4已知线

3、性规划问题：max z = 2x1 4x2 x3 x4 x1 +3x2+x4 M 82% +x2<6x2 x3 x4 三 6 x1 + x2 + x3<9xi,x2,x3, x4 _0求：(1)写出其对偶问题；(2)已知原问题最优解为X*=(2,2,4,0),试根据对偶 理论，直接求出对偶问题的最优解。解：(1)该线性规划问题的对偶问题为：min w = 8y1 6 y26y39y4%+2y2+y4 之23y1十丫2十丫3十y4至4 y3 y4 -1 y+y3之 1y1，y2,y3,y4-0(2)由原问题最优解为X* =(224,0),根据互补松弛性得：y1 2 y2y4 = 23

4、y1 y2 y3 y4 =4 y3 y4 -1、 * . . . . . . . . . .把X =(224,0)代入原线性规划问题的约束中得第四个约束取严格不等号，即2 2 4 =8 ：二9= y4 =0火 2y2=2从而有3乂 +y2 +y3 =4、y3 =1阳 43得 y二二，y2 =二，y3 =1以二055所以对偶问题的最优解为y* =C3,1,0)T ,最优值为Wmin =165 5P79 2.7考虑如下线性规划问题:min z = 60xi 40x2 80x33xi +2x2 + & 之 24xi + X2 +3& >4，2xi+2x2+2& 之3xi

5、,x2,x3 >0(1)写出其对偶问题；(2)用对偶单纯形法求解原问题；解：(1)该线性规划问题的对偶问题为：max w = 2y1 4y2 3y3.3yi +4y2+2y3 M 60j2y#y2+2y3 M40Iyi 3y2 2y3 <80yi,y2,y3 -0(2)在原问题加入三个松弛变量x4,x5,x6把该线性规划问题化为标准型max z = -60x1 -40x2 -80x3- 3x 一 2x2 _ *3 + 42- 4x1 一 x2 - 3x3 x x5 4- 2 x1 2 x2 2 x3+ x6 = 3xj 2 0,j =1,川,6cj T-60-40-80000CbX

6、bbx1x2x3x4x5x60x4-2-3-2-11000x5-4-4-1-30100x6-3-2-2-2001Cj -Zj-60-40-800000x410-5/45/41-1/12080x1111/43/40-1/400x6-10-3-1/20-1/21C j -Z j0-25-350-1500x411/6005/311/3-5/680xi5/6102/30-1/31/640x22/3011/301/3-2/3C -Z J00-80/30-20/3-50/322305=60 40 80 0 =633*,5 2 tX (-,-,0) "x6 3P81 2.12某厂生产A、B、C三种

7、产品，其所需劳动力、材料等有关数据见 下表。要求：（a）确定获利最大的产品生产计划；（b）产品A的利润在什么范围 内变动时，上述最优计划不变；（c）如果设计一种新产品D,单件劳动力消耗为 8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？（d）如果劳动力数量不增，材料不足时可从市场购买，每单位 0.4元。问该厂要不 要购进原材料扩大生产，以购多少为宜。可用量（单位）消耗、产品ABC额材料6353454530产品利润（元/件）314解：由已知可得，设Xj表示第j种产品，从而模型为:max z = 3x1 x2 4x36% 3x2 5x3 < 45 st J3x1 +4x2

8、+5x3 W30L.x1, x2, x3 0a）用单纯形法求解上述模型为:cj T31400CbXbbXiX2X3X4X50X445635100X53034501C -Zj -314000X4153-101-14X363/54/5101/5Cj -Zj3/5-11/500-4/53Xi51-1/301/3-1/34X33011-1/52/5Cj -Zj0-20-1/5-3/5得到最优解为x =(5,0,3);最优值为Zmax =3父5 + 4父3 = 27b)设产品A的利润为3十九，则上述模型中目标函数xi的系数用3+八替代并求解得:cj T3+Z1400CbXbbX1X2X3X4X53X15

9、1-1/301/3-1/34X33011-1/52/5Cj -Zj九-20-1/5-3/53 -Zj )'0-2+ 八 /30-1/5- K/3-3/5+ 九/3要最优计划不变，要求有如下的不等式方程组成立rn-2+-<03一1_%W0 解得:5 36 九八十 < 05 3从而产品A的利润变化范围为:3 . 3,3+91,即，22,441_ 55,IL 5 5C）设产品D用X6表示，从已知可得i：-6 = C6 - Cb B P6 1/5P' =B，P6 = I把X6加入上述113 一3_1255模型中求1 "-811 1 =7JJ -.解得：2【 4 一

10、5一Cj T314003CbXbbX1X2X3X4X5X63X151-1/301/3-1/324X33011-1/52/5-4/5C -Zj -0-20-1/5-3/51/53X65/21/2-1/601/6-1/614X352/513/151-1/154/150Cj -Zj-1/10-59/300-7/30-17/300从而得最优解 x* =(0,0,5,0,0,5 /2)T ;最优值为 zmax =4父5+3父5 = 27.5 >272所以产品D值得生产。d）由已打耨。粉才抬13 了力"+#"咛勺占3。十八入Tr。今人号F夕X八*人州而即如'外州4&quo

11、t;固十同.加电题也咐将4Ml利 k滴掷小小叫P101 3.1已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题 的最优解及最小运费。表 3-3534解：因为z ai =£ bj ,即产销平衡.所以由已知和最小元素法可得初始方案为 i 1 j 1地B1B2B3B4J里A11515A20151025A3505销量5151510检验:Bl B2册预行位势kli2A31 ”初吧 2。上 引5曲狙15 巴 10。到1613列位势-11 1314由于有两个检验数小于零，所以需调整，调整一:151501510255055151510B1 B2 B3 B4 &巨 里广地A1A2A

12、3销量检验:由于还有检验数小于零，所以需调整，调整二:B1B2B3B4J里A151015A2101525A3505销量5151510检验:漫对 B2 E3 M行位势A1A2A3可运回5吧 封通41。- 2 5回吗而叫10 15刎 。168列位势61310从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：Zmin =2 5 2 5 7 10 9 15 11 10 18 0 =335表 3-36解：因为工ai =58>£ R =55,即产大于销，所以需添加一个假想的销地，销 i =1j 1量为3,构成产销平衡问题，其对应各销地的单位运费都为0B1B2B3B4B5J里A18

13、41207A26947025A35343026销量101020153由上表和最小元素法可得初始方案为地B1B2B3B4B5J里A177A2913325A31101526销量101020153检验:B5可必q3 B OrtaB身从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：zmin =6 9 5 1 3 10 1 7 4 13 3 15 0 3=193表 3-371%.七成地广地B1B2B3B4B5J里A18637520A25M84730A36396830销量252520102035解：因为Z ai =80<£ bj =100,即销大于产，所以需添加一个假想的产地，

14、产量为20,构成产销平衡问题，其对应各销地的单位运费都为0地B1B2B3B4B5J里A18637520A25M84730A36396830A40000020销量2525201020由上表和最小元素法可得初始万案为地B1B2B3B4B5J里A12020A25101530A325530A420020销量2525201020检验:遭Bl B2 B3 B4 B5行位势A1A2A3A4回出目20同5Ym1081 10 ZJ15 强生5回目目50J20 01 21 o Q 6134-2列位势2-1214由于有两个检验数小于零，所以需调整，调整一:地B1B2B3B4B5J里A12020A2201030A32

15、5530A4501520销量2525201020检验:邂Bl B2 B3 B4 B5行位势71A2A3A4秋可包3J 20 ZJ 5 52O M逊回的 10 11(+2) 即今比5 9| ©Q目50 崛 2115136-2列位势2-3212由于还有检验数小于零，所以需调整，调整二:地 广淤、B1B2B3B4B5J里A12020A2201030A3525030A402020销量2525201020检验:遭31 B2B3B4B5行位势A13 20翘4A2mo M通©10力8A3 5 ©25I 目09A4回呼0 5 05®)叱01列位势-3-6-4-1从上表可

16、以看出所有的检验数都大于零，即为最优方案最小运费为：zmin =3 20 5 20 4 10 6 5 3 25 8 0 0 20 0 0 =305P127 4.8用割平面法求解整数规划问题。max z =7x1 9x2工 x1 3x2-6 a7% x2 <35鼠,用至0,且为整数解：该问题的松弛问题为：max z = 7x1 9x2-xi 3x? - 6 « 7K +x2 <35 x1,x2 0则单纯形法求解该松弛问题得最后一单纯形表为:cj T7900CbXbbx1X2X3X49x27/2017/221/227x19/210-1/223/22C -Zj 乙j00-28/

17、11-15/11171c C 71二 一一x3 X4=x23M0= x3 + x42 22222222从而有cj T79000CbXbbXX2X3X4X59X27/2017/221/2207X19/210-1/223/2200X5-1/200-7/22-1/221c -ZJj 00-28/11-15/1109X23010017X132/71001/7-1/70X311/70011/7-22/7c -zJj 000-1-8割平面 1 为：（3+1/2） =X2 十（0 十7/22）X3 十（0 + 1/22）X4割平面 2 为：（4+4/7） =x1 +（0+1/7）x4+（1+6/7）x512

18、二4x4-6x5=X1-x5-4 M0= 1 x46 x5 -x6477 47 5157767cj T790003CbX Bbxix2x3x4x5x69x230i00i07xi32/7i00i/7-i/700x3ii/700ii/7-22/700x6-4/7000-i/7-6/7iC -Z乙j000-i-809x230i00i07xi4i000-ii0x3i00i0-4i0x44000i6-7Cj -Zj0000-2-7由上表可知该问题已经达到整数解了，所以该整数解就是原问题的最优解，即Tx =(4,3),最优值为 Zmax =7父4+9M3=55P144 5.3用图解分析法求目标规划模型mi

19、n Z = Pi di + P2 d2+4 P3 (2d3-+1d4-)c)X xi + X2 + di - di = 40xi + X2 + d2- - d2+= 40+i0=50-+,s.t./ xi+ d3 - d3 = 24X2 + d4 - d4+= 30L xi、x2、di+、di-、d2+、d2-、d3+、d3-、d4+、d4- > 0解：由下图可知，满足min di-的满意解为区域X2CDXi满足min d2+的满意解为闭区域BCDEB ;满足min 2d3-的满意解为图中的A点，满足min d4-的满意解为图中的A点，所以该问题的满意解为图中的点A (24,26)。用图

20、解分析法求目标规划模型min z = P1d1P2d3 - P3d2r_+-x1 +2x2 + d1 - d1 =4j x1 -2x2 +d2-d，=4x1 +2x2 +d3-d3+ = 8x1,x2 >0;di- di+之 0 i =1,2,3的满意解。解：由下图可知，满足min d1 +的满意解为区域CDOA满足mind3加勺满意解为闭区域 MCDOM ;满足mind2加满意解为图中的阴影部分，即为图中的凸多边形OABCDOP170 6.4求下图中的最小树解：避圈法为：(1)匕=(用居二$,CQ,邑艮GH1匕= 43,5,%=CQ凡发 (4)匕=H及GC必二艮刈(5)比0c,0 泾二国 民省一口凶比包CD.司必:瓦毋 彳二B,GCR昆句也二(尸) 心=(ABGCD,邑艮出=®得到最小树为：解：如下图所示:P 173 6.14用Ford-Fulkerson的标号算法求下图中所示各容量网络中从 vs至11vt的最大流，并标出其最小割集。图中各弧旁数字为容量