运筹学部分课后习题解答

1、运筹学部分课后习题解答P47 1.1用图解法求解线性规划问题min z=2x 3x2、4为 +6x2 兰6a )st 0解：由图1可知，该问题的可行域为凸集 MABC，且可知线段BA上的点都为最优解，即该问题有无穷多最优解，这时的最优值为Zmin =2 - 3 0 = 32P47 1.3用图解法和单纯形法求解线性规划问题max z=10x1 5x23为 4x2込9a )s.t彳5为+2x2兰8xz _0解：由图1可知，该问题的可行域为凸集 OABCO且可知B点为最优值点,即3x1 =9二.13，即最优解为八1,35X1 2X2=8x2=32L 2335这时的最优值为zmax=10 1 5 一二

2、一2 2原问题化成标准型为max z=10x1 5x23 4x2 x3 = 9 s.t 5 +2x2 +x4 =8Xi,X2,X3,X4 0Cj T10500CbXbbX1X2X3X40X3934100X485201Cj -Zj105000X321/5014/51-3/510Xi8/512/501/5Cj -Zj010-25X23/2015/14-3/1410Xi110-1/72/7Cj -Zj00-5/14-25/14z T所以有1,3 ,Zmax=10 1 5I 2 丿22P78 2.4已知线性规划问题：max z =2x 4x2 x3 x4/ +3x2+x4 兰 82咅 +x26彳x2

3、+x3 +x4 兰 6x, + x2 + x39XZX, X4 一0求：(1)写出其对偶问题；(2)已知原问题最优解为X(2,2,410)，试根据对偶理论，直接求出对偶问题的最优解。解：(1)该线性规划问题的对偶问题为：min w = 8y, 6y2 6y3 9y4i+2y2+y4 兰23yrHyHyrHy4彳yyiyi, y2,y3,y40(2)由原问题最优解为X* =(2,2,4,0)，根据互补松弛性得：y1 2y2y4 = 23y1 y2 ya y4Iya + yU把X* = (2,2,4,0)代入原线性规划问题的约束中得第四个约束取严格不等号，即 2 2 4 =8 42xi +2X2

4、+2x3 兰3xi,x?,x 0(1)写出其对偶问题；(2)用对偶单纯形法求解原问题;解：(1)该线性规划问题的对偶问题为:max w = 2% 4y2 3y33% +4y2 +2y3 兰602% *2 +2y3 兰40yi 3y2 2y3 80yi,y2,y3 0(2)在原问题加入三个松弛变量X4,X5,X6把该线性规划问题化为标准型max z = -60旨-40x2 -80x33xi 2x? X3 + X4= -24xi x? 3X3 + X5 _4-2 Xi 2 X2 2 X3+ = _3Xj j =1川,6Cj T-60-40-80000CbXbbX1X2X3X4X5X60X4-2-3

5、-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/2-1/20-1/21Cj -Zj0-25-350-1500X411/6005/311/3-5/680X15/6102/30-1/31/640X22/3011/301/3-2/3Cj -Zj00-80/30-20/3-50/3x* =(5,?,O)T,Zmax =60 540 -80 0 二空6 3633P81 2.12某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见 下表。要求：（a）确

6、定获利最大的产品生产计划；（b）产品A的利润在什么范围 内变动时，上述最优计划不变；（c）如果设计一种新产品D,单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？ （d） 如果劳动力数量不增，材料不足时可从市场购买，每单位 0.4元。问该厂要不要购进原材料扩大生产，以购多少为宜消产品ABC可用量（单位）劳动力 材料6353454530产品利润（元/件）314解：由已知可得，设Xj表示第j种产品，从而模型为:max z = 3片 x2 4x36凶 3x2 5x3 乞 45st3为 +4x2 +5x3 兰 30冷 X2,X3-0a）用单纯形法求解上述模型为:Cj t

7、31400CBXbbX1xX3X4X50X445635100X53034501Cj -Zj314000X4153-101-14X363/54/5101/55 -Zj3/5-11/500-4/53Xi51-1/301/3-1/34X33011-1/52/55 0-20-1/5-3/5得到最优解为x* = (5,0,3)T ;最优值为zax =3 5 4 3 = 27b ）设产品A的利润为3，贝U上述模型中目标函数xi的系数用3替代并求解得:5 t3+Z1400CBXbbX1X2X3X4X53X51-1/301/3-1/34X33011-1/52/55 -Zjk-20-1/5-3/5(5 -Zj

8、i0-2+ 九 /30-1/5-人/3-3/5+ 九/3要最优计划不变，要求有如下的不等式方程组成立-203-10解得:53_3一955从而产品A的利润变化范围为:3却 91 即 _2r4lC)设产品D用X6表示，从已知可得；6 = 4 -cbB_P6 =1/5-F6 = B F6 =把X6加入上述1 13_31 255模型中求J kTJ解得：2【4一5一Cj T314003CbXbbX1X2X3X4X5X63X151-1/301/3-1/324X33011-1/52/5-4/55 -Zj0-20-1/5-3/51/53X65/21/2-1/601/6-1/614X352/513/151-1/

9、154/1505 N-1/10-59/300-7/30-17/300从而得最优解 x(0,0,5,0,0,5 /2)t ;最优值为 zx =4 5 327.5272所以产品D值得生产。d)P101 3.1已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题 的最优解及最小运费。表 3-35解：由已知和最小元素法可得初始方案为检验:进B1E2 I1391行位势AI胆A3冏崗违20 头丄 |5珂辿览陶專3)15 出 10 0诃1&13列位势-U 1314由于有两个检验数小于零，所以需调整，调整一:检验:BlB2B3B4行位势A1A2A3训15 20両场）1IJ 0 旬话 辺迪）迥迪）训o1

10、64列位势-21314调整二:检验:由于还有检验数小于零，所以需调整,B2B3B4行位势A1昶51A2吨釣10勺156A38列位势-61310从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：zmin -2 5 2 5 7 10 9 15 11 10 18 0 =335解：因为ai =58八bj =55，即产大于销，所以需添加一个假想的销地，销i =1j =1量为3,构成产销平衡问题，其对应各销地的单位运费都为0由上表和最小元素法可得初始方案为检验:BlB2B354B5行位勢A1172J,倒1A26g 9|130IT4A35 1 创10%3列位势2 000-4从上表可以看出所有的检验

11、数都大于零，即为最优方案最小运费为：Zmin =6 9 5 1 3 10 - 1 7 4 13 3 15 0 3=193表 3-37A18637520A25M84730A36396830销量252520102035解：因为ai =80八口 =100，即销大于产，所以需添加一个假想的产地，产i =1j d量为20,构成产销平衡问题，其对应各销地的单位运费都为0产地销地B1B2B3B4B5产量A18637520A25M84730A36396830A40000020销量2525201020由上表和最小元素法可得初始方案为销地 产地弋、B1B2B3B4B5产量A12020A25101530A32553

12、0A420020销量2525201020检验:BlB2B3B4B5行位势A1A2A3A4逅地355皿倂 也血gCJ20 21(+3)220啊山0力15 )创迪创50210丛134-2列位势2-1214由于有两个检验数小于零，所以需调整，调整一:产地销地B1B2B3B4B5产量A12020A2201030A325530A4501520销量2525201020检验:由于还有检验数小于零，所以需调整，调整二:销地 产地，B1B2B3B4B5产量A12020A2201030A3525030A402020销量2525201020检验:31B2B3B4B5行位势A1320i-i施4A2创20皿胡虬08A3

13、目5勺了g1、二 创09A40a倒201列位势-3-6-1-4-1从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：zmin =3 20 5 20 4 10 6 5 3 25 8 0 0 20 0 0 = 3055B2P127 4.8用割平面法求解整数规划问题。max z = 7为 9x2-x1 3x2 6a)“7为+x2 兰35x1,x2 0,且为整数解：该问题的松弛问题为:max z = 7 9x2-x 3屜 _ 6 7为 + x2 兰 35 xx2 3 0 则单纯形法求解该松弛问题得最后一单纯形表为:Cj T7900CBXbbX1X2X3X49x7/2017/221/227X1

14、9/210-1/223/22Cj _Zj00-28/11-15/11割平面 1 为：(3 1/2) =x2 (0 7 / 22) x3 (0 1/22)x4丄X3 -丄XX2 -3汕匚Z%丄X4f2 22 22 22 22从而有Cj T79000CBXbbX1X2X3X4X59X27/2017/221/2207X19/210-1/223/2200X5-1/200-7/22-1/221Cj -Zj00-28/11-15/1109X23010017X132/71001/7-1/70X311/70011/7-22/7Cj -Zj000-1-8割平面 2 为：(4 4/7) =x, (0 1/7)x4

15、 1 6/7)x5Cj T790003CBX BbXiX2X3X4X5X69X230i00i07Xi32/7i00i/7-i/700X3ii/700ii/7-22/700X6-4/7000-i/7-6/7i5 -Zj000-i-809X230i00i07Xi4i000-ii0X3i00i0-4i0X44000i6-75 -Zj0000-2-77 774 - 7-6+X41 一 7由上表可知该问题已经达到整数解了，所以该整数解就是原问题的最优解，即*tx =(4,3)，最优值为 Zmax =7X4+93=55P144 5.3用图解分析法求目标规划模型min Z = Pi di-+ P2 d2+

16、P3( 2d3- +1d4-)c)xi + X2 + di- - di+= 40- +Xi + X2 + d2 - d2 = 40+10=50s.t. 00 i =1,2,3的满意解。解：由下图可知，满足mind的满意解为区域CDOA满足min d3的满意解为闭区域 MCDOM ；OABCDO满足min d2的满意解为图中的阴影部分，即为图中的凸多边形P170 6.4求下图中的最小树96解：避圈法为:(1) %二同巴二民匚6尺了耳歼二&甜耳二CQ,艮孔(33 % = (AEGj 耳=CD总玖咼(4) VKA.B.Q.OE, FfHQ) % 十,BGggEH巧二SEG.GDS)必二此旳%二隅5G

17、CD卫咼耳= (F) J=IABG：D、E.叭咼込=得到最小树为:解：如下图所示:P 173 6.14用Ford-Fulkerson的标号算法求下图中所示各容量网络中从乂到V的最大流，并标出其最小割集。图中各弧旁数字为容量Cj，括弧中为流量fj.由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1, 得由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小 割为与直线KK相交的弧的集合，即为XVs,V3),(Vs,V4),(Vs,V5),(V!,Vt),(V2,Vt),(V2,V3)/所以从Vs到Vt的最大流为：fst =1 2 5 3 2 14C)解：对上有向图进行 2F标号得到，得由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量， 最小割为与直线KK相交的弧的集合，即为(VsN), Vs