运筹学第二章线性规划的对偶理论复习题

1、第二章线性规划的对偶理论1消序IIIIII单件 利润 (元)A321200B413300C223250可用工时604020农2-11、某厂生产A、B、C三种产品，每种产品要 经过I、II、III三道工序加工，设每件产品在每道 匸序上加匸所消耗的匸时，每道工序可供利用的工 时上限，以及每件产品的利润如表2-1所示.试列出使总利润最大的线性规划模型，并写出 它的对偶问题，同时，就这个对偶问题作出经济上的解释.解：设® x2,忑分别表示A、B、C各产品的数最，Z表示总产值则：)£)x z = 200兀 + 300.V, + 250x3st. 3x1 + 4x, + 2x3 <

2、; 602xx + x2 + 2x3 < 40X + 3x, + 3x3 < 20x(/ = l,2,3)>0原问题的对偶问题为niiii w = 60y】+ 40y2 + 20 y3st. 3j| + 2y2 + y3> 2004片+弘+ 3旳丫3002% + 2y2 + 3y3 > 250Ji »0,)3»0经济解释ms分别表示给别人代工时所得收入,对厂方而言,w越大越好,但定 价不能太高，耍对方容易接受，应考虑使总收入即对方的总支出尽可能少才比较合理, 厂方不会吃巧，对方也容易接受。2、写出下列线性规划问题的对偶问题:(1) maxz =

3、 lOXj +x2 + 2“s. t. +x2 +2x3 <10+x2 + x5 < 20Xj > 0(y = 1,2,3)解:win w= 10+ 20st. + y2 > 102% + 为2y2>0(2) ininz=2xt +2x2 +4x.s. t.2Xj + 3x2 + 5Xy > 23xt + 兀2 + 7兀3 < 3X + 4x2 + 6.v3 < 5Xj > 0(7 = 1,2,3)解 miax vv：=2% + 3y2 + 5y3$/. 2yx + 3% + % < 23yt + y2 + 4y3 <25y,

4、+ 7y2 + 6y3 <4Ji »0,)3<0(3) maxz = 5.v1 + 6.v, + 3x3s. t x1 +2x2 +2x3 = 5Xj + 5x«> x3 > 34血 + 7x2 + 3Xj < 8X无约束，x2 >0 , x5 <0解:Jilin vv = 5) + 3y2 + 8v3st yi-y2 + 4y3 = 52j| + 5% + 7% A 6 2%-力 + 33 53 川由，y2 <0, y3>0(4) nun z = 3召 + 2x2 一 3x, + Ax4X 2x2 一 3Xj + 4x

5、4 < 3x2 +3心 +4小 >-52兀-3x2 - 7x3 _ 4x4 = 2Xi >0,x4 <O,x2,x3无约束解：max w = 3y】一 5y2 + 2y3st. y + 2y2<3- 2% + 52-3%=2-3% + 3%_7%=-34+42-473 >4% <0, y2 >0, y3 <03、应用对偶理论证明线性规划问题.max z = xk+x2s. t. - x, + x2 + x3 <2-2x, +x2 -x3 < 12°有可行解，但无最优解.(o)证明：x= 0 是线性问题的可行解，即该问题

6、存在可行解;乂 其对偶问题为：nun w = 2y1 + y2st. -Ji - 2y2 > 1% + 为1X - % n 0Ji no, y2 >0yl9y2 >0'-y-2y2 <0这与约束条件(1)不符该对偶问题无可行解二原问题无最优解。4、应用弱对偶定理，证明线性规划问题niaxz = Xj +2x2 +x3s. t. xk+x2-x3 <2 xl-x2+xi = l2x, + x2 + x3 >2X >0,a2 <O,a35E约朿的最人值不超过1.证明：该线性问题的对偶问题为：nnn w = 2 + y2 + 2y3st. x

7、+2 + 2儿 n 1乳- +唇2丁 + 为+，3 = 1% >0,为自由，% <0易知丫 = (0,1,0) 丁是对偶问题的一个可行解，由对偶问题的对偶定理可得：(°)cx° < y°b = 1 (2,1,2) = 1BK1X Z < 1即最大值不超过15、应用对偶理论，证明线性规划问题niaxz = 3兀 +2x2s. t. - xt +2x2 <43兀 +2x, < 14 xt -x2 <3 xx2 >0有最优解，并证明其对偶问题也有最优解.证明：对偶问题nun w= +14 y2 + 3旳sf. -J. +

8、3y2 + y3 > 32) + 2y2 - y3 > 2爪0, y2>0,由题易知X二(3, 0)丫是原问题的一个可行解，Y= (0, 1, OF是对偶问题的一个可行解由对偶问题的推论2- 3可得它们都有最优解。即得证。6、已知标准线性规划问题niaxz = exAx - bQ0具有最优解，假设将右端向量b改为另一向量d,如果改变后的问题是可行的, 试证该问题一定有最优解.7、考虑下列原始线性规划niaxz = 2 兀i + x2 4- 3%,s. t a; +,r2 +2x3 5 52召 4-3x2 +4兀$ = 12勺 > 0(； = 1,2,3)(1) 写出其对

9、偶问题；(2) 己知(3,2,0)是上述原始问题的最优解，根据互补松弛定理，求出对偶 问题的最优解：(3) 如果上述规划中的第一个约束为资源约束，写出这种资源的影子价格.解:(1)对偶问题：imn iv = 5yt +12y.,st. + 2y2 > 2Ji + 3% » 12y + 4，2 n 3y >0, %无符号限制(2) 由题知原问题的最优解为/ = (3,2,0)7：由互补松弛定理得：在对偶问题中对应第一，二个约束为紧，第三个约束条件为松，即，y； + 2y； = 2.*21 f y 1 = 4+ 3y2 = 1 二>< t°才、2 ly：

10、 = i2” +4 >3对偶规划问题的垠优解y； =（44）（3）影子价格为Yi = 4 ：8、已知线性规划问题max 乙=X + 2.v7 + 3x5 + 4x4s. t. 斗 + 3.v, + 2x3 + 3x4 < 20+ x2 + 3.v3 + 2x4 < 20Xj > 0（y = l, -,4）其对偶问题的最优解为y； = 1.2,y： =0.2 ,试根据对偶理论求出原问题的最优解.解：先写出其对偶问题。nun iv = 20y）+ 20y2si. yx + 2y2 > 1 3% + y2>2 2yi+3y2- 3纳 + 2y2 n 4X no,

11、y2>0对偶规划问题的仗优解y： = 1.2, y； = 0.2,代入约束条件，知第1, 2约束条件成立严格不等式, 由互补松弛定理，原规划最优解中相应变Mx； = X： = 0乂#，），；不为0,则在原问题规划中对应的约束条件为紧,得J 2x3 + 3x4 = 20 Jx； = 43x3 + 2x4 = 20=>x； = 4原对偶规划问题的瑕优解 十=（0、044）9、已知某线性规划问题的最优单纯形表如2-2所示，表中兀，心为松弛变量，问题的约束为W形式(1) 写出原线性规划问题；(2) 写出原问题的对偶问题:M接山衣2-2写出对偶问题的最优解.解:(1)由表知B"N

12、=-p/20、-1/6 1/3丿；S/2、令8 =21 Xllj表2-2耳兀屯R兀b01/211/205/21-1/20-1/61/35/20、I =则p、0B* =ZN =1/20>(-1/61/3八兀211°nB =1/21/2 丿1/2(一1/61/3八b丿=> N =1 2、Q/2) f<5、A =；B"=>/? =-1 1丿2丿=(一4,一2)=>2< 1/2 0-1/6 1/3-(> C；)C广6C3 = 10C+(-4. -2)4、cl=-4 => C. = -2原线性问题为： max z = 6兀 一 2x2

13、+ 10x3 st. x2 + 2x3<53兀-x, + x3 <10 兀(i = i,2,3)no(2) niin w= +10y2st. 3y2 > 6 X-以-22y, + y2 >10 八0, y2>0 x= (5/2,0,5/2/； Z* = 40;即.= y5 = 0=6卜=4Ex + y2=> j > 2 = 2二 ior*=(4, 2)t w*=40；10、某厂拟生产甲、乙、丙三种产品， 都需要在A、B两种设备上加工,有关数 据如表2-3所示.（1）如何充分发挥设备能力，使产 品总产值最大？（2）若为了提高产量，以每台时350 元租金租

14、用外厂A设备，问是否合算？设备、单耗（台时/件）设备冇效台时（每月）甲乙丙A12 1400321 2500产值（T元/件）32 1表2-3解:（1）设勺耳，厲分别表示甲、乙、丙各产品的数屋，Z表示总产值则:i）ax Z = 3舌 + 2xz + x3st. 兀 + 2x2 + x3 <400lx、+ x2 + 2x3 < 500兀（心 1,2,3） 10化为标准形：z = 3兀 + 2x2 + Xyst. xL + 2x. + x5 +x4 = 4002" + x, + 2.v3+x5= 500兀(2 1,2,3,4,5) AOC32100bGXbXxX：Xsx；Xs0X

15、.121104000Xs21201500检验数321000X,03/201-1/21503X】11/2101/2250检验数01/2-20-3/225020102/3-1/31003X,101-1/32/3200检验数00-2-1/3- 4/3-800/= (200J 00/；ZJOO;(2)原问题的对偶问题为imn w = 400y)+ 500)、st. y + 2y2>i2ji + 为2Ji + 2y2>l八0, y2>0此时，八，y扮别表示出租A, B设备所得利润，由(1)中的最优表得y；=l/3,即如出租A设备可获得1000/3元，而1000/3<350所以不合

16、算。11、己知某实际问题的线性规划模型为inaxz =工 c內Xj >0(7 = 1,2/,/!)若第i项资源的影子价格为y, (/ = 1,2,7)(1)若第一个约束条件两端乘以2,变为£ （2列）形 < 2b., >-1久是对应丁这个新约束条件的影子价格，求人与儿的关系;10(2)令虬=3兀，用小/3替换模型中所有的勺，问影子价格是否变化？若召不可能在最优皋中出现，问x是否町能在最优基中岀现;(3) 如果目标函数变为max Z =工 2c jXj问影子价格有何改变？(4) 如果模型中约束条件变为n2(1宀=bi i = 1,2,a>=i问、(2)、(3)中

17、的结论是变化?解：(1)由影子价格的定义可得:送伶2(2) 由(1)可知几只与b的值有关.当的系数由3变为x的系数1/3时，y,的值并 不发生变化；&不可能在最优基中出现，x也不可能在绘优基中出现7 = 士。儿=士巧=w(3) 当目标函数由Z = tCJXj变为2C兀时,q增大了两倍>-iy-i影子价格y,也增大了两倍。(4) 分别相同。12. 用对偶单纯形法求解卜列线牲观划问题:(1) min z = 1 Ox, + 5x2 + 4 牙,3召 + 2x2 一 3Xj > 3+2x3 >10解：先将问题化为标准式n)ax z = 一10兀 一 5x2 - 4x3 +

18、0x4 + 0x5_3召 一 2x2 + 3x5 + x4 = 一 3- 2x3+x5= -10取初始1E则基B = (Pl P5) = I则原问题己化为关丁基B的典式,c23100BCBX.X,X2Xs人Xs0X：-3-2310-30x5-40-201-10检验数-10_5-40000£-9-2013/2-18-4x52010-1/25检验数-2_500-220-10X：12/90-1/9-1/62-4x50-4/912/9-1/61检验数0-41/90-2/9-7/324可得原问题的最优解为:24./ = (20J,0.0)Z4 = -24.Z = 24, / = (2/27/3

19、)$(2) nun z = 2Xj + 3忑 + 4x3s. t. 兀 +2x2 +x3 > 32Xj 一 x? + 3心 > 4Xnx19x5 >0将问题化为：imx Z = _2兀 一 3.v2 - 4x3st. _片_2忑_屯+兀=_3_2兀 + x2- 3x3+ x5 = -4x.(/= 1,2,3,4,5) > 0c32100BCBXbX：X：&X,Xs0X.-1-2-110-30Xs1-301-4检验数-2-3-4000Xi0-5/21/21-1/2-13X,1-1/23/20-1/22检验数0-4-10-12502x201-1/5-2/51/52/

20、53x>1014/10l/5-4/1011/5检验数00-9/5-8/5-1/5-28/5x= (11/5,2/5,0)f；Z" = -2 8 / 5; Z$ = 28/5(3) nun z = 2X +x2 s. t. 3兀 +x2 > 34xt + 3x: > 6x1 + 2x, < 3xx2 >0解：(3) max z = -2xt-x2st.- x2 + x4 =_3_纠_3耳+ x5 = -6 + 2x2+ 忑=3x,(/ = l,2,3,4,5,6)>0c350000BCbXbXxX：X,X,x5&0X4-3-10100-30X

21、s-40Z3010_60Xe1200013检验数-2-100000£z3-10100-30Xs4/3010-1/3020Xs1200013检验数-2-10000-2X】11/30-1/30010x50-4/914/9-1/302/3005/301/3012检验数0-1/30-2/3002(4) iiun z = 3石 + 2x2 + x3s. t.+ x2 + x3 <6X +x3> 4x2- Xj> 3Xj >0 (j = 1,2,3)解：化为：inax Z = _3勺-2x2 - x3st. 兀 + x2 + x3 + x4 = 6-x2+x3+ 兀=_3

22、兀(2 1,2,3,4,5,6)2 016Ci38000 58旺X2心兀4兀5D3101/20-2100000-3110500801001350检验数00-3/20-2-3100表2-3C-3-2-1000bCbXBXix2XsX.x5人0石11110060Xs-10zl010-400-11001-3检验数- 3-2-10000X,0101102-1xs1010-1040Xszl-10011r检验数-2-200-100£0101102-1Xs0211001-3-3Xx1100-1-1检验数0000-3-20£001111-1-2x201-100-13-3£1010

23、-104检验数0000_3-2由表知，此题无可行解。13、己知线性规划问题niaxz = 3.Vj +&匚s. t2jj +4x2 <16006x1 + 2x, < 1800x2 < 350XZ >0用单纯形法求解时得最终单纯形表如表2-3所示.17（1）要保持现有最优解不变，分别求sc,的变化范围；（2）要保持现有最优解不变,分别求blfb2, %的变化范围;（3）当®变为500时，求新的最优解.解：（1）由表知，CG为基变最的系数 、C； = max + ；= -rAC* = Jinn+d=iGw 0,4ACC = Jinx+t=-2AC* = J

24、JUll 4- 1 = co C, G 6,4-00)(2) 参见教材P67的方法求Z(3) .® = 500 任300,400故优解将发生变化;b = (00150).Ab=B_1Ab =5/2 0 -2Y-31 100 0 1 kJ00150300、=1500J C38000bcBxBXxx2X3X；x53Xx101/20z2-2000£00-311020008x201001500检验数00-3/20-20X5-1/20-1/4011000X：50-1/2101000188X：1/21100400检验数-10-200-3200/ = (0,400/； Ze = 3200

25、;14、己知线性规划问题niaxz = 10“ +5x?s. t. 3册 +4氐 <95x, + 2x2 < 8 xl9x2 20用单纯形法求得最终单纯形表如表2-4所示，试用灵敏皮分析的方法分别判断:(1) 目标函数系数q或°分别在什么范围内变动，现最优解不变；(2) 约束条件右端常数,*中，当保持一个不变时，另一个在什么范围内变化,现有的故优皋不变：(3) 问题的目标函数变为liiaxz = 12“ +4.v,时，最优解有什么变化；约束条件右端常数项由叫19 7时，最优解有什么变化?表2-453800bCb旺X.心5015/14-3/143/21010-1/72/71

26、检验数00-5/14-25/14-25/2解:1) . G变化时,L6OAIqR+-rvlqvlG.P n、vl0vlsslwq口 L_c l二03AI3Aq 尸g+qLxqv+82M赵氐J5押(zOAIq6cooL0LOLDQD61oOv-Hor-HoOv-Hi-Hoor-MoOC|QrrOJVLD 寸r-HLDOJLDV1CO><coLDCMof <oOX盘ooo9 Tvlqvl8Tr<= LVI0V1# I 走0 匚C L 二 q口龙Al龙A/ = (8/5,0,21/5,0/C-3-2-10bCbXbXxx2X,X,0Xs3410110X*52019检验数105

27、0000x3015/14-3/14212Xi10-1/711检验数00-5/14-25/1 1-20宀(l,2O0)T15、己知线性规划问题表2-5max z = 2xl- x2 + x338000bCrXRX|X2旺r斗s. t.2X|111106Xj + x2 + x5 < 600311110检验数03-1-20-12厂0 (; = 1,2,3)用单纯形法求得最终单纯形表如表2-5所示，试分别求当下列情况发生时的最优解：(1)冃标函数变为maxz = 2X+3卞2+心：约束条件右端项由变为L 4(3) 增加一个新的约束条件-x, +2x2 >2L8(0丿Z1解：由表知C2的影响

28、范Fhl为C2 (-8, 2:当忖标两数变为max乙=2兀+ 3x2 + “时，最优解将发生变化c23100BCbXBX,X2XsX.X,2X：1111660Xs0311110检验数01-1-202X,102/32/3-1/38/33Xz011/31/31/310/3检验数00-4/3-7/3-1/3-46/3化 F = (8/3J0/3.0/； Z，= 46/3;3C23100bCBXbXtX：XsX.X52X】1111030Xs031117检验数0-3-1-206x=(3X)A0,7)r； Zw = 6;b = B 仏/?=(3) JEx* = (6,0,0,0,10/代入约束条件- +

29、3>2 V -6 + 0 > 2不成立,该问题的最优解将发生变化, x _ 2x2 + x6 = -2C2-11000BCBXbXiX：XsX.Xs&2X：11110060X,031110100Xe1-20001-2检验数0-3-1-2002X,11110060X,031110100Xe0-3-1-101-8检验数0_3-1-2002X,102/32/301/310/30X,0000112-1X2011/31/30-1/38/3检验数00000-1-12/3F = (10/3,8/300,2)'； Z* =4;16、已知线性规划问题max z = -5x1 + 5.

30、v, +13.v3s. t. - £ + 兀 + 3x3 < 20A12xa +4x, +10x3 < 90B厂 >0 (; = 1,2,3)先用单纯形法求出垠优解，再分析在下列条件单独变化的情况下最优解的变化:(1) 约束条件B的右端项山90变为70；(2) 目标函数中心的系数由13变为&r- 2)(3)变最兀的系数(包括目标函数)由-1变为0丿5X(6)(4)变量匕的系数(包括目标函数)由1变为2420 增加一个约束条件2孔+ 3冬+ 5心 50 ；(6)原约束条件(2)变为10人+5兀+10小S100.解：化为:n)ax z = 一5兀 + 5x2 +

31、 13屯st. 一 召 + 兀 + 3“ + x4 = 20 12xl+4x1 + Qx3 +x5=901,2,3,4,5)2 0c-3-2-100BCBXBX：X：XsX：x50X,-11310200X,124100190检验数-j5130013X,-1/31/311/3020/30X,46/32/30-10/3170/3检验数-2/32/30-105x2-11310200x5160-2-4110检验数00-2_50-100(1)A/?=0、/ = (020,0,040/； Z# = 100;AZ? = B ' Nb =< 1 o) <-4 1 丿r020)0 )> =1-20,C_551300bCBXxX：X,X.：<55x2-11310200X,160z2-41-10检验数00-2_505X22310_53/2513X,-8012-1/25BJ21检验数-1600-1-1-90(2)C-55800bCBX»X,