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

1、运筹学部分课后习题解答P47用图解法求解线性规划问题minz=2x3x2、4为6x26a)st4为2x24x1,x20解：由图1可知，该问题的可行域为凸集MABC，且可知线段BA上的点都为3最优解，即该问题有无穷多最优解，这时的最优值为Zmin=2-30322P47用图解法和单纯形法求解线性规划问题maxz=10x.|5x2、3为4x29a)s.t5为2x28x1,x?0T1,32解：由图1可知，该问题的可行域为凸集OABCO且可知B点为最优值点,即3x14x2913，即最优解为x*5x12x28x2这时的最优值为Zmax=1。15|35Tv1图1单纯形法:原问题化成标准型为maxz=10x1

2、5x234x2x39s.t52x2x48Cj10500CbXbbX1X2X3X40X3934100x485201CjZj105000X321/5014/51-3/510Xi8/512/501/5CjZj010-25X23/2015/14-3/1410Xi110-1/72/7CjZj00-5/14-25/14Xi,X2,X3,X40maxz2为4x2X3X4X13x2X482咅x26x2x3x46xx2x39xz,X3,X40所以有x*131015i35"2P78已知线性规划问题:求：(1)写出其对偶问题；(2)已知原问题最优解为X*(2,2,4,0)，试根据对偶理论，直接求出对偶问题

3、的最优解。解：(1)该线性规划问题的对偶问题为:(2)minw8y16y26y39y4y12y2y423y1y2y3y44y3y41y1y31y1,y2,y3,y40由原问题最优解为*X(2,2,42),根据互补松弛性得y12y2y423y1y2y3y44y3y41把X*(2,2,4,0)代入原线性规划问题的约束中得第四个约束取严格不等号,即22489目40y12y22从而有3y1y2y34y31得y4得Y15,Y235山1，V40所以对偶冋题的最优解为y(,3,1,0)T，最优值为Wmin1655P79考虑如下线性规划问题:minz60xi40x280x33xi2x2X324xiX23x34

4、2xi2x22x33xi,x?,x30（1）写出其对偶问题；（2）用对偶单纯形法求解原问题；解：（1）该线性规划问题的对偶问题为：maxw2%4y23y33%4y22y3602yiy22y340,yi3y22y380%也30（2）在原问题加入三个松弛变量X4,X5,X6把该线性规划问题化为标准型maxz60x140x280x33x12x2X3X424x-iX23x3X542为2x22x3X63Xj0,j1L,6Cj-60-40-80000CbXbbX1X2X3X4X5X60X4-2-3-2-11000X5-4-4-1-30100X6-3-2-2-2001CjZj-60-40-800000X41

5、0-5/45/41-1/12080X1111/43/40-1/400X6-10-3/2-1/20-1/21CjZj0-25-350-1500X411/6005/311/3-5/680X15/6102/30-1/31/640X22/3011/301/3-2/3CjZj00-80/30-20/3-50/3x*(5,-,0)T,Zmax60540?800空63633P81某厂生产ABC三种产品，其所需劳动力、材料等有关数据见下表。要求：（a）确定获利最大的产品生产计划；（b）产品A的利润在什么范围内变动时，上述最优计划不变；（c）如果设计一种新产品D,单件劳动力消耗为8单位,材料消耗为2单位，每件可

6、获利3元，问该种产品是否值得生产（d）如果劳动力数量不增，材料不足时可从市场购买，每单位元。问该厂要不要购进原材料扩大生产，以购多少为宜。消耗产品ABC可用量（单位）定额劳动力63545材料34530产品利润（元/件）314解：由已知可得，设Xj表示第j种产品，从而模型为:maxz3为x24x36Xj3x25x345st34x25x330为KX0a)用单纯形法求解上述模型为:Cj31400CbXbbXiX2X3X4X50X445635100X53034501CjZj314000X4153-101-14X363/54/5101/5CjZj3/5-11/500-4/53Xi51-1/301/3-1

7、/34X33011-1/52/5CjZj0-20-1/5-3/5得到最优解为x*(5,0,3)T;最优值为Zmax354327b)设产品A的利润为3，则上述模型中目标函数xi的系数用3替代并求解得:Cj31400CbXbbX1X2X3X4X53X51-1/301/3-1/34X33011-1/52/5CjZj-20-1/5-3/5CjZj0-2+/30-1/5-/3-3/5+/3要最优计划不变，要求有如下的不等式方程组成立01-0解得：395355305323从而产品A的利润变化范围为：33,39,即22,445555C）设产品D用X6表示，从已知可得16C6CBBP61/5P'B1P

8、6把X6加入上述模型中求解得:Cj314003CbXbbX1X2X3X4X5X63X151-1/301/3-1/324X33011-1/52/5-4/5CjZj0-20-1/5-3/51/53X65/21/2-1/601/6-1/614X352/513/151-1/154/150CjZj-1/10-59/300-7/30-17/300c从而得最优解x*(0,0,5,0,0,5/2)t;最优值为zmax45327.5272所以产品D值得生产。34由必存冷许令粘才込弭力眩為k*声、（才t入為嗾讷处1切上卜捞乙f寸I一L、入少3十亍入=0fF'l卩I/匕門Lvlxk6-A？门»2氐

9、r百壮入f“-f入#25和期认岁冋52宀F風惋冰茂呛也吟抽4%A澜1沖星讣"P101已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。表3-35解：因为aibj,即产销平衡所以由已知和最小元素法可得初始方案为检验:B1B2B3M行位势A1A2A3创釣211520勺5珂迪诃0诃O16列位势-1113/由于有两个检验数小于零，所以需调整，调整一:产地销地B1B2B3B4产量A11515A20151025A3505销量5151510检验:进BlB!B3刑行位帮A1A215更珂®勺01百5诃刨15出10诃0164列位勢-21314由于还有检验数小于零，

10、所以需调整，调整二:B1B2EjA1辿11A2156A32列位势-61310检验:从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：Zmin252571091511101803353解：因为aii155，即产大于销，所以需添加一个假想的销地，销表3-36A84127A694725A534326销量10102015B2584bj产地销地B4产量销地r地xTB1B2B3B4B5产量A1841207A26947025A35343026j1量为3,构成产销平衡问题，其对应各销地的单位运费都为0销量101020153由上表和最小元素法可得初始方案为B1E2B3別BE行便勢A1）修1721141

11、3Q134A35110315%3列位势2000-4从上表可以看出所有的检验数都大于零，即为最优方案检验:解：因为ai80bj100，即销大于产，所以需添加一个假想的产地，产i1j1销地产地范B1B2B3B4B5产量A18637520A25M84730A36396830A40000020销量2525201020量为20，构成产销平衡问题，其对应各销地的单位运费都为0o最小运费为：zmin69513101741331503193由上表和最小元素法可得初始方案为检验:进BlB2B5行位勢A1创戛320Ilg)1U2邑5临甩3A36|259呃£54A4o2O21(+|),00咆翌-2列位势2

12、-1214由于有两个检验数小于零，所以需调整，调整一:销地产地WB1B2B3B4B5-r、曰.产量A12020A2201030A325530A401520销量2525201020检验:逬E1B2I5B4B5行位势A1201A252(363%护25g6A4210型15-2列位势2-3212由于还有检验数小于零，所以需调整，调整二:销地B1B2B3B4B5产量A12020A2201030A3525030A402020销量2525201020检验:31E2I!3B4B5行位势A1血A4導p35j20M|8525220U(+7)3包)10刃(g)(g)6|Q)s00204891列位势-3-6-1-4-

13、1从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：zmin320520410653258002000305P127用割平面法求解整数规划问题maxz7x19x2x.3x26a)°27%x235Xi,X20,且为整数解：该问题的松弛问题为:maxz7x.9x2Xi3x267xiX235x.,x20则单纯形法求解该松弛问题得最后一单纯形表为:Cj7900CbXbbX1X2X3X49X27/2017/221/227X19/210-1/223/22CjZj00-28/11-15/11割平面1为：(31/2)X2(07/22)X3(01/22)x41 71cc711X3X4X230

14、X3X4X5X1X5402 222222222从而有Cj79000CbXbbXX2X3X4X59X27/2017/221/2207X19/210-1/223/2200X5-1/200-7/22-1/221CjZj00-28/11-15/1109X23010017X132/71001/7-1/70X311/70011/7-22/7CjZj000-1-8割平面2为：(44/7)x,(01/7)x4(16/7)x5Cj790003477X4164严7X5X6-CbXBbXiX2X3X4X5X69X230i00i07xi32/7i00i/7-i/700X3ii/700ii/7-22/700X6-4/7

15、000-i/7-6/7iCjZj000-i-809X230i00i07Xi4i000-ii0X3i00i0-4i0X44000i6-7Cj乙0000-2-7由上表可知该问题已经达到整数解了，所以该整数解就是原问题的最优解，即*tx4,3，最优值为Zmax749355P144用图解分析法求目标规划模型minZ=Pidi+P2_d2+P3(2d3+1d4)厂xi+x2+di-di=40xi+x2+d2-d2+=40+i0=50<xi+d3-d3+=24x2+-d4+=30Xi、X2、di、di、d2、d2、d3、d3、d4、d40解：由下图可知，满足mindi的满意解为区域X2CDXi满足m

16、ind?+的满意解为闭区域BCDEB满足min2d3-的满意解为图中的A点，满足mind的满意解为图中的A点，所以该问题的满意解为图中的点A(24,26)x2用图解分析法求目标规划模型minzP1d1P2d3P3d2X12x2didi4Xi2x2d2d24Xi2X2d3d38Xi,X20；di、di0i1,2,3的满意解。解：由下图可知，满足mindi的满意解为区域CDOA满足mind3的满意解为闭区域MCDQM满足mind2的满意解为图中的阴影部分，即为图中的凸多边形OABCDOP170求下图中的最小树/h>7解：避圈法为：%=3卫®必=2月卫卫阳広匸SEGC必二DEFtH%

17、二且EGG”込二血武H)巧二AEGQ.D.閲耳=耳旳眄=SEGCDE月)耳二卩fGCQ耳F,均厲F得到最小树为：解：如下图所示:P173用Ford-Fulkerson的标号算法求下图中所示各容量网络中从Vs到Vt的最大流，并标出其最小割集。图中各弧旁数字为容量Cj，括弧中为流量B)解：对上有向图进行2F标号得到由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1,得由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK相交的弧的集合，即为(Vs,V3),(Vs,V4),(Vs,V5),(V!,Vt),(V2,Vt),(V2,V3)所以从Vs到Vt的最大流为：fs；12532114C)解：对上有向图进行2F标号得到由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1,得由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK相交的弧的集合，即为(Vs,Vi),(Vs,V