运筹学部分课后习题解答

1、.妙单纯形法:原问题化成标准型为max z=10X+5x23xt + 4x2 +x3 =9s.t.0Cjf10500qXpbEA：心兀0X3934100X4852015-Zj105000X321/5014/51-3/5108/512/501/55-z)010-25X23/2015/14-3/1410xl110-1/72/7335= 10xl+5x- = 2 2C厂Z、00-5/14-25/14所以有/=h |YP78已知线性规划问题:max z = 2州 + 4x2 +x3+x4x, +3x2+x4 82州 +x2 6x2+x3 + x4 6x+x2 + x30求：写出其对偶问题；(2)已知原

2、问题最优解为=(224,0),试根据对偶理论，直接求出对偶问题的最优解。解：(1)该线性规划问题的对偶问题为：min w = 8” + 6y2 + 6y3 + 9y43 j+2y2+y4 23)1+儿+儿+儿4儿+儿1开 +儿 1.儿,儿(2)由原问题最优解为X=(2,2,4,0),根据互补松弛性得：必+2儿 +儿=2 3)1 + 比 + )3 + )4 = 4儿+九=1把x=(2,2,4,0)代入原线性规划问题的约束中得第四个约束取严格不 等号，即 2 + 2 + 4 = 8y4=0X + 2儿=2从而有 24Xj +x2 + 3x3 4 3xpx2,Xj 0（1）写出其对偶问题；（2）用对

3、偶单纯形法求解原问题；解：（1）该线性规划问题的对偶问题为：max w = 2y + 4y2 + 3儿3y +4y2 + 2儿 60、2y1+y2 + 2y3y+3y2+2儿 S80_（2）在原问题加入三个松弛变量勺,“，把该线性规划问题化为标准型：max z = 一60片 一 40x2 一 80x33| 2x1 Aj + 耳=_2Xj x, 3Xj + 忑 =_40,; = !,6勺T-60-40-800005Xrb兀2V50V4-2-3-2-11000V5-4-4-1-30100忑-3-2-2-2001CjJ-60-40-800000V410-5/45/41-1/12080111/43/4

4、0-1/400-10-3/21-1/20-1/21CjJ0-25-350-150011/6005/311/3-5/6805/6102/30-1/31/640V22/3011/301/3-2/3700-80/30-20/3-50/3气少5?730/=(|,f,0)z_=60x| + 40x + 80x0 = -o 3o33P81某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据 见下表。要求：（a）确定获利最大的产品生产计划；（b）产品A的利润在 什么范围内变动时，上述最优计划不变；（c）如果设计一种新产品D,单 件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产 品是否值得

5、生产（d）如果劳动力数量不增，材料不足时可从市场购买, 每单位 元。问该厂要不要购进原材料扩大生产，以购多少为宜。xrrr劳动力63545材料34530产品利润（元/件）314解：由已知可得，设表示第丿种产品，从而模型为:max z = 3x+x2 + 4x36. +3x2 +5x3 453x + 4x2 + 5x3 0a）用单纯形法求解上述模型为:勺-31400CbXrb州A：屯驻%04563510023034501C厂Z）314000153：-101-1463/54/5101/5C厂Z）3/5-11/500-4/53A151-1/301/3-1/343011-1/52/55-Zj0-20-

6、1/5-3/5得到最优解为F =（5,0,3八 最优值为z唤=3x5 + 4x3 = 27b）设产品A的利润为3+几，则上述模型中目标函数“的系数用3+2替代并求解得:C严3+久1400qXrbJ心勺X、351-1/301/3-1/343011-1/52/5c厂Z)2-20-1/5-3/5(q-zj0-2+2/30-1/5-2/3-3/5+2/3要最优计划不变，要求有如下的不等式方程组成立-2 + - 272所以产品D值得生产。d)P101已知运输问题的产销量与单位运价如下表所示，用表上作业法求各 题的最优解及最小运费。表 3-35解：由已知和最小元素法可得初始方案为A3销量 5151510检

7、验：BlB2B3别行位势ALA2A31 2 Im 1 O | 4| 7 | 20迥O1613列位势-111314由于有两个检验数小于零，所以需调整，调整一:检验:进BlB2B3 M行位势A1A2A3训丘诅15門毎1 咚015 辿io诃 0164列位势-21314由于还有检验数小于零，所以需调整，调整二:检验:进B1B2B3S4行位势A15巴马 101A210 915 21(+4)6A314炉08列位势_611310从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：7 in =2x5 + 2x5 + 7x10 + 9x15 + 11x10 + 18x0 = 335表 3-36解：因为巧

8、=55,即产大于销，所以需添加一个假想的销地, 销量为3,构成产销平衡问题，其对应各销地的单位运费都为0。BlB2B3B4B5产量Al7793A2101315251A326销量101020153检验:进BlB2 B3B4B5行位势A17能1血创9创哲13B 155 34A31 2J10 -%3列位势2 000-4从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：zmin = 6x9 + 5x1 + 3x10 + 1x7 + 4x13 + 3x15 + 0x3 = 193表 3-37解：因为巧=100,即销大于产，所以需添加一个假想的产地, r-i；-1产量为20,构成产销平衡问题，其

9、对应各销地的单位运费都为0。立 hhB1B2B3B4B5产量A18637520A25M84730A36396830A40000020销量2525201020检验:BlB2 B3 MB5行位势A1A2A3A48j6 3J 20目 5勾 10 刃 15125 9包创电）创5 020 510创包）134-2列位势2-1214由于有两个检验数小于零，所以需调整，调整一:之wB1B2B3B4B5产量A120202010A225530A3501530A420销量2525201020检验:进B1B2B3B4B5行位势A18_3 201A25J20皿迪%3A36辭25创y6A40匕21。Oj 15-2列位势2

10、-3212由于还有检验数小于零，所以需调整，调整二：Bl B2 B3 B4 B5 产量亦 llh、A1A2A3A4202030302020525010020销量2525201020检验:逬11B2B3B4B5行位势1如320勺同4A25 208折6 599A40201列位势36-14-1从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：zmin = 3x20 + 5x20 + 4x10 + 6x5 + 3x25 + 8x0 + 0x20 + 0x0 = 305P127用割平面法求解整数规划问题。max z = 7| +9x2 -x + S 6a)7X| +x2 0,且为整数解：该问题

11、的松弛问题为：max z = 7. +9x2 一召 + 3x2 6 7州 +x2 0则单纯形法求解该松弛问题得最后一单纯形表为:勺1790005Xrb為V2X、心X、9X27/2017/221/2207V19/210-1/223/2200-1/00-7/22-1/2212c厂Z)00-28/1-15/10119X23010017V132/1001/7-1/77011/0011/7-22/77= x.-3 x3 + 22 3 22 4 5从而有勺T7900qXpbxi*2心9X27/2017/221/227x9/210-1/223/22C厂Zj00-28/1-15/111割平面 1 为:(3 +

12、 1/2)=勺+( + 7/22)兀 + (0+1/22)耳1 71 .V, XA2 22 -22 4C厂Z,000-1-8割平面 2 为:(4 + 4/7) =召+(0 + 1/7)“+(-1+6/7)禺CL790003qXrbV2V3q七兀9X230100107xx32/1001/7-1/707011/0011/7-22/0770应-4/000-1/-6/7177000-1-809*23010010741000-11010010-410400016-7C厂Z）0000-2-7由上表可知该问题已经达到整数解了，所以该整数解就是原问题的最优 解,即/=（4,3）最优值为仏=7x4 + 9x3

13、= 55P144用图解分析法求目标规划模型min Z = Px 4+ P2 g+ Ps （2苗+ldT）c）厂Xi + X2 + d； - d；= 40Xi + X2 + 血- = 40+10=50.X1 + 苗-&= 24X2 + & - &二 30x,、X2、d：、&、底、&、（t、&、広 N 0解：由下图可知，满足目标函数的满意解为图中的A点。P170求下图中的最小树解：避圈法为:(1) = % = (A,幼耳= (C,D,E,F,G,咼(4) = (A,B,Gfa) = (D,Er FtH(5) % = CtD) y2 = F, H)(6) 眄工4R,G,U, DE,眄二兄丹 %=几及

14、G,C,D,E,H)% = (F(8) HG6D,艮玖咼耳=得到最小树为:P171用标号法求下图中点儿到各点的最短路。P 173用Ford-Fulkerson的标号算法求下图中所示各容量网络中从人到 儿的最大流，并标出其最小割集。图中各弧旁数字为容量括弧中为流 量人B)/5(4) X1CD5(5)r 3(2) V32(2) 5(2) /V5(5)1(1)解：对上有向图进行2F标号得到(055(5)2(2)5G)也仏1)%,1)5C2J1(1)2(2)4 43(3)由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量, 最小割为与直线KK相交的弧的集合，即为（匕必），（儿），（匕*5）心）“2沱）,“巴）所以从儿到的最大流为：/： =1 + 2 + 5 + 3 + 2 + 1 = 14C)解：对上有向图进行2F标号得到由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量, 最小割为与直线KK相交的弧的集合，即为（匕,U）,（f）（卩2*5），所以从儿到气的最大流为：/： =5 + 3 + 5 =