二三版兼用《運(yùn)籌學(xué)教程》胡運(yùn)權(quán)主編課后習(xí)題答案(第二章)

1、第二章習(xí)題解答第二章習(xí)題解答 2.1 寫出下列線性規(guī)劃問題的對(duì)偶問題。寫出下列線性規(guī)劃問題的對(duì)偶問題。 無約束321321321321321,0,534332243422min)1(xxxxxxxxxxxxstxxxZ無限制對(duì)偶問題321321321321321, 0, 0433424322532max:yyyyyyyyyyyystyyyW第二章習(xí)題解答第二章習(xí)題解答0, 0,8374335522365max)2(321321321321321xxxxxxxxxxxxstxxxZ無約束0, 0,3332675254835max321321321321321yyyyyyyyyyyystyyyW無

2、約束對(duì)偶問題：.), 1, 1(0), 1(), 1(min)3(1111njmixnjbxmiaxstxcZijnijijnjiijminjijij第二章習(xí)題解答第二章習(xí)題解答mniynjmicyystybyaWiijmjiminjmjjii, 1), 1, 1(.max11無限制，對(duì)偶問題：）無約束（nnjxnnjxmmmibxammibxastxcZjjnjijijnjijijmjjj, 1), 1(0), 2, 1(), 1(max)4(11111111第二章習(xí)題解答第二章習(xí)題解答）無約束（對(duì)偶問題：mmjymiynnnjcyanjcyastybybybWiimijiijmijiijm

3、m, 1), 1(0), 2, 1(), 2 , 1(min11111112211第二章習(xí)題解答第二章習(xí)題解答第二章習(xí)題解答第二章習(xí)題解答 2.2 判斷下列說法是否正確，為什么判斷下列說法是否正確，為什么? (1)如果線性規(guī)劃的原問題存在可行解，則其對(duì)偶如果線性規(guī)劃的原問題存在可行解，則其對(duì)偶問題也一定存在可行解；問題也一定存在可行解； 答：不對(duì)！如原問題是無界解，對(duì)偶問題無可行答：不對(duì)！如原問題是無界解，對(duì)偶問題無可行解。解。 (2)如果線性規(guī)劃的對(duì)偶問題無可行解，則原問題如果線性規(guī)劃的對(duì)偶問題無可行解，則原問題也一定無可行解；也一定無可行解； 答：不對(duì)！道理同上。答：不對(duì)！道理同上。 第二

4、章習(xí)題解答第二章習(xí)題解答 (3)在互為對(duì)偶的一對(duì)原問題與對(duì)偶問題中，不管原在互為對(duì)偶的一對(duì)原問題與對(duì)偶問題中，不管原問題是求極大或極小，原問題可行解的目標(biāo)函數(shù)值一問題是求極大或極小，原問題可行解的目標(biāo)函數(shù)值一定不超過其對(duì)偶問題可行解的目標(biāo)函數(shù)值；定不超過其對(duì)偶問題可行解的目標(biāo)函數(shù)值； 答：不對(duì)！如果原問題是求極小，結(jié)論相反。答：不對(duì)！如果原問題是求極小，結(jié)論相反。 (4)任何線性規(guī)劃問題具有惟一的對(duì)偶問題。任何線性規(guī)劃問題具有惟一的對(duì)偶問題。 答：結(jié)論正確！答：結(jié)論正確！第二章習(xí)題解答第二章習(xí)題解答 2.3 已知某求極大化線性規(guī)劃問題用單純形已知某求極大化線性規(guī)劃問題用單純形法求解時(shí)的初始單純

5、形表及最終單純形表如下表法求解時(shí)的初始單純形表及最終單純形表如下表所示，求表中各括弧內(nèi)未知數(shù)的值。所示，求表中各括弧內(nèi)未知數(shù)的值。 解：解： l=1, k=0 , h=-1/2, a=2, c=3, b=10, e=5/4, f=-1/2, d=1/4, g=-3/4, i=-1/4, j=-1/4Cj322000CB基基bX1X2X3X4X5X60X1(b)1111000X215(a)120100X3202(c)1001CjZj 322000 0X45/400(d)(l)-1/4 -1/43X125/410(e)03/4(i)2X25/201(f)0(h)1/2CjZj 0(k)(g)0-5

6、/4(j)第二章習(xí)題解答第二章習(xí)題解答 2.4 給出線性規(guī)劃問題給出線性規(guī)劃問題 )4 , 1( , 0332232.6532min432143214321jxxxxxxxxxstxxxxZj (1)寫出其對(duì)偶問題；寫出其對(duì)偶問題；(2)用圖解法求解對(duì)偶問題；用圖解法求解對(duì)偶問題；(3)利用利用(2)的結(jié)果及根據(jù)對(duì)偶問題性質(zhì)寫出原問題最優(yōu)的結(jié)果及根據(jù)對(duì)偶問題性質(zhì)寫出原問題最優(yōu)解。解。 0,063533222.32min)1(212121212121yyyyyyyyyystyyW對(duì)偶問題： (2) 最優(yōu)解是：最優(yōu)解是：y1=-8/5,y2=1/5,目標(biāo)函數(shù)值目標(biāo)函數(shù)值-19/5。 (3)由于由于

7、 y1=-8/5,y2=1/5都不等于零，原問題中的都不等于零，原問題中的約束取等號(hào)。又上面第約束取等號(hào)。又上面第4個(gè)約束不等號(hào)成立，故個(gè)約束不等號(hào)成立，故x4=0，令令x3=0就可以得到最優(yōu)解：就可以得到最優(yōu)解： x1=8/5,x2=1/5。第二章習(xí)題解答第二章習(xí)題解答第二章習(xí)題解答第二章習(xí)題解答 2.5 給出線性規(guī)劃問題給出線性規(guī)劃問題 ., 0, 022122max321321321321321無約束xxxxxxxxxxxxstxxxZ (1)寫出其對(duì)偶問題；寫出其對(duì)偶問題；(2)利用對(duì)偶問題性質(zhì)證利用對(duì)偶問題性質(zhì)證明原問題目標(biāo)函數(shù)值明原問題目標(biāo)函數(shù)值z(mì)1。 0, 012122min)1

8、 (321321321321321yyyyyyyyyyyystyyyW無約束對(duì)偶問題： (2)y1=y3=0,y2=1時(shí)對(duì)偶問題的一個(gè)可行解，目時(shí)對(duì)偶問題的一個(gè)可行解，目標(biāo)函數(shù)值為標(biāo)函數(shù)值為1，故原問題的目標(biāo)函數(shù)值小于等于，故原問題的目標(biāo)函數(shù)值小于等于1。 第二章習(xí)題解答第二章習(xí)題解答第二章習(xí)題解答第二章習(xí)題解答 試根據(jù)對(duì)偶問題性質(zhì)證明上述線性規(guī)劃問題目標(biāo)試根據(jù)對(duì)偶問題性質(zhì)證明上述線性規(guī)劃問題目標(biāo)函數(shù)值無界。函數(shù)值無界。 )3 , 1( , 0122.65max3213214321jxxxxxxxstxxxxZj 2.6 已知線性規(guī)劃問題已知線性規(guī)劃問題 第二章習(xí)題解答第二章習(xí)題解答 由于由于

9、(1)和和(4)是矛盾約束，故對(duì)偶問題無可行解。是矛盾約束，故對(duì)偶問題無可行解。所以原問題目標(biāo)函數(shù)值無界。所以原問題目標(biāo)函數(shù)值無界。)4(0,)3(0)2(1)1 (12.2min2121212121yyyyyyyystyyW 解：解：x1=1,x2=x3=0是原問題的可行解。原問題的是原問題的可行解。原問題的對(duì)偶問題為：對(duì)偶問題為： 第二章習(xí)題解答第二章習(xí)題解答 要求：要求：(1)寫出其對(duì)偶問題；寫出其對(duì)偶問題；(2)已知原問題最優(yōu)解已知原問題最優(yōu)解為為X*=(2，2，4，0)，試根據(jù)對(duì)偶理論，直接求出對(duì)偶，試根據(jù)對(duì)偶理論，直接求出對(duì)偶問題的最優(yōu)解。問題的最優(yōu)解。 )4 , 1( , 096

10、6283.42min321432214214321jxxxxxxxxxxxxstxxxxZj 2.7 2.7 給出線性規(guī)劃問題給出線性規(guī)劃問題第二章習(xí)題解答第二章習(xí)題解答 (2)已知原問題最優(yōu)解為已知原問題最優(yōu)解為X*=(2，2，4，0)，代入原，代入原問題，第問題，第4個(gè)約束不等式成立，故個(gè)約束不等式成立，故y4=0。有由于。有由于x1,x2,x3大于大于0，上面對(duì)偶問題前，上面對(duì)偶問題前3個(gè)約束取等號(hào)，故得到最優(yōu)個(gè)約束取等號(hào)，故得到最優(yōu)解：解： y1=4/5, y2,=3/5, y3=1, y4=0)4 , 1( , 01113229668min) 1 (314343214214321jy

11、yyyyyyyyyyyyyyyWj對(duì)偶問題：), 1( ,0.min1333122211111njxybxaybxaybxastxcZAjnjjjnjjjnjjjnjjj影子價(jià)格問題 2.8 已知線性規(guī)劃問題已知線性規(guī)劃問題A和和B如下：如下： 第二章習(xí)題解答第二章習(xí)題解答), 1( , 03)3(515155.min13*131312*2211*111njxybbxaaybxaybxastxcZBjnjjjjnjjjnjjjnjjj影子價(jià)格問題 試分別寫出試分別寫出yi同同y*i(i1，2，3)間的關(guān)系式。間的關(guān)系式。 第二章習(xí)題解答第二章習(xí)題解答*3*2*1321*3*2*1321005/

12、3050005/1100010005/1100050001003010001yyyyyyyyyyyy第二章習(xí)題解答第二章習(xí)題解答)3 , 1( , 052233.18124min)1 (3231321jxxxxxstxxxZj 2.9 用對(duì)偶單純形法求解下列線性規(guī)劃問題。用對(duì)偶單純形法求解下列線性規(guī)劃問題。 )3 , 1( , 010536423.425min)2(321321321jxxxxxxxstxxxZj第二章習(xí)題解答第二章習(xí)題解答1,2/3,0)3 , 1( ,053233.18124min)1 (3213231321xxxjxxxxxstxxxZj最優(yōu)解：0,2, 3/2)3 ,

13、1( ,010536423.425min)2(321321321321xxxjxxxxxxxstxxxZj最優(yōu)解：第二章習(xí)題解答第二章習(xí)題解答第二章習(xí)題解答第二章習(xí)題解答 要求：要求：(1)寫出其對(duì)偶問題；寫出其對(duì)偶問題；(2)用對(duì)偶單純形法用對(duì)偶單純形法求解原問題；求解原問題；(3)用單純形法求解其對(duì)偶問題；用單純形法求解其對(duì)偶問題；(4)對(duì)比對(duì)比(2)與與(3)中每步計(jì)算得到的結(jié)果。中每步計(jì)算得到的結(jié)果。 .0,3222434223804060min321321321321321xxxxxxxxxxxxstxxxZ 2.10 考慮如下線性規(guī)劃問題：考慮如下線性規(guī)劃問題： (4)3230 Z

14、,350y ,320y 0,y(3)3230 Z0, x,32 x,65x(2)0,8023402260243342max)1 (321321321321321321321略對(duì)偶問題：yyyyyyyyyyyystyyyW第二章習(xí)題解答第二章習(xí)題解答第二章習(xí)題解答第二章習(xí)題解答 先用單純形法求出最優(yōu)解，再分析在下列條件單獨(dú)先用單純形法求出最優(yōu)解，再分析在下列條件單獨(dú)變化的情況下最優(yōu)解的變化。變化的情況下最優(yōu)解的變化。 解：最優(yōu)解為解：最優(yōu)解為x x1 1=6,x=6,x2 2=x=x3 3=0,Z=12 =0,Z=12 )3 , 1( , 0426.2max21321321jxxxxxxstxx

15、xZj 2.11 已知線性規(guī)劃問題：已知線性規(guī)劃問題： 46/3Z0,x10/3,x8/3,xx3x2xmax Z(1)321321最優(yōu)解：目標(biāo)函數(shù)變?yōu)榈诙铝?xí)題解答第二章習(xí)題解答6, 0, 34346 (2)321Zxxx最優(yōu)解：變?yōu)榧s束右端項(xiàng)由28/3Z8/3,x0,x10/3,x22xx(3)32131最優(yōu)解：增添一個(gè)新的約束條件第二章習(xí)題解答第二章習(xí)題解答 2.12 2.12 給出線性規(guī)劃問題給出線性規(guī)劃問題 用單純形法求解得最終單純形表見下表：用單純形法求解得最終單純形表見下表： )3 , 1( ,033734311313131.32max321321321jxxxxxxxstxxx

16、Zj項(xiàng)項(xiàng) 目目23100CB 基基 bX1X2X3X4X52 X1 610-14-13 X2 1012-11CjZj00-3-5-1 試分析下列各種條件下最優(yōu)解試分析下列各種條件下最優(yōu)解(基基)的變化：的變化：第二章習(xí)題解答第二章習(xí)題解答31213213x,xx,x10Z1,x0,x,2,x ；6的系數(shù)變x目標(biāo)標(biāo)函數(shù)中變(1)最優(yōu)基從最優(yōu)解：為量第二章習(xí)題解答第二章習(xí)題解答時(shí)最優(yōu)解不變。時(shí)最優(yōu)解不變；最定確9, 4c3,43c優(yōu)解不變；在什 么什么范圍內(nèi)變動(dòng)c,c的系數(shù)x和x目標(biāo)標(biāo)函數(shù)中變 分別(2)212121。其他變量為優(yōu)解變?yōu)椋涸瓎栴}最有基不變，最01,x5,x； 32變?yōu)?1 約束條件

17、右端項(xiàng)由(3)21第二章習(xí)題解答第二章習(xí)題解答。其他變量為最優(yōu)解為：量0,31x2, x；7c， 11=P,x加一個(gè)新的 變(4)62666。其他變量為最優(yōu)解為：束01,x2,x。4x+2x+x添一個(gè)新的約(5)51321第二章習(xí)題解答第二章習(xí)題解答 2.13 分析下列線性規(guī)劃問題中，當(dāng)入變化時(shí)最優(yōu)分析下列線性規(guī)劃問題中，當(dāng)入變化時(shí)最優(yōu)解的變化，并畫出解的變化，并畫出Z(入入)對(duì)入的變化關(guān)系圖。對(duì)入的變化關(guān)系圖。) 4 , 1( , 0532222.2)(min) 1 (4214314321jxxxxxxxstxxxxZj25, 0, 2, 5, 0)1 (3, 0, 0, 2, 1 121(

18、22,21(2, 1, 0, 2, 00432143214321ZxxxxZxxxxZZxxxx時(shí)，最優(yōu)解：，時(shí)，最優(yōu)解：，時(shí)，最優(yōu)解不變，最優(yōu)解：第二章習(xí)題解答第二章習(xí)題解答.0,11261052)2()3 ()(min) 2(21212121321xxxxxxxxstxxZ24, 3,10, 0, 2, 0)20, , 1,12,10, 0, 0:)2(12, 3,10, 0, 2, 00543215432154321ZxxxxxZxxxxxZxxxxx時(shí)，最優(yōu)解：，時(shí)，最優(yōu)解，最優(yōu)解：第二章習(xí)題解答第二章習(xí)題解答) 3 , 1( , 01222.2)(max) 3(4324314321j

19、xxxxxxxstxxxxZj2,34,31, 0, 0)4(6, 0, 1, 0,4:4(6, 0, 1, 0, 40432143214321ZxxxxZxxxxZxxxx最優(yōu)解：時(shí)，時(shí)，最優(yōu)解，最優(yōu)解：，第二章習(xí)題解答第二章習(xí)題解答160, 0, 0, 0,30, 5, 00.0,730426023402523max) 4(6543213212131321321ZxxxxxxxxxxxxxxxxstxxxZ，最優(yōu)解：第二章習(xí)題解答第二章習(xí)題解答第二章習(xí)題解答第二章習(xí)題解答Cj325000CB基基bX1X2X3X4X5X62X25-1/4101/2 -1/405X3303/20101/200

20、X610200-211CjZj-700-1-20第二章習(xí)題解答第二章習(xí)題解答Cj325000CB基基bX1X2X3X4X5X62X25- -1/4101/2 -1/405X330+ 3/20101/200X610-3 200-211CjZj-700-1-20第二章習(xí)題解答第二章習(xí)題解答Cj325000CB基基bX1X2X3X4X5X62X215-7/4 1/410001/45X330+ 3/20101/200X43 /2 -5-1001-1/2-1/2CjZj-700-1-20其他情況原問題無解。，最優(yōu)解：時(shí)，最優(yōu)解：時(shí)，231650, 0, 527,30,47215, 07303103160

21、310, 0, 0,30,5, 0)31030654321654321ZxxxxxxZxxxxxx第二章習(xí)題解答第二章習(xí)題解答第二章習(xí)題解答第二章習(xí)題解答 2.14 2.14 某廠生產(chǎn)某廠生產(chǎn)A A，B B，C C三種產(chǎn)品，其所需勞動(dòng)三種產(chǎn)品，其所需勞動(dòng)力、材料等有關(guān)數(shù)據(jù)見力、材料等有關(guān)數(shù)據(jù)見下下表表：產(chǎn)品產(chǎn)品資源資源ABC可用量可用量（單位）（單位）勞動(dòng)力勞動(dòng)力63545材料材料34530產(chǎn)品利潤(rùn)產(chǎn)品利潤(rùn)（元（元/件）件）314 要求：要求： (1)(1)確定獲利最大的產(chǎn)品生產(chǎn)計(jì)劃；確定獲利最大的產(chǎn)品生產(chǎn)計(jì)劃； 答：最優(yōu)生產(chǎn)計(jì)劃為：答：最優(yōu)生產(chǎn)計(jì)劃為：x x1 1=5,x=5,x2 2=0,

22、x=0,x3 3=3,Z=27=3,Z=27； 第二章習(xí)題解答第二章習(xí)題解答項(xiàng)項(xiàng) 目目31400CB 基基 bX1X2X3X4X53 X1 51-1/301/3-1/34 X3 3011-1/52/5CjZj0-20-1/5-3/5 (2) (2)產(chǎn)品產(chǎn)品A A的利潤(rùn)在什么范圍內(nèi)變動(dòng)時(shí)，上述最優(yōu)的利潤(rùn)在什么范圍內(nèi)變動(dòng)時(shí)，上述最優(yōu)計(jì)劃不變；計(jì)劃不變； 答：產(chǎn)品答：產(chǎn)品A A的利潤(rùn)在的利潤(rùn)在2.42.4，4.84.8內(nèi)變動(dòng)，生產(chǎn)計(jì)內(nèi)變動(dòng)，生產(chǎn)計(jì)劃不變劃不變(-3/5 (-3/5 9/59/5 ) )； 第二章習(xí)題解答第二章習(xí)題解答項(xiàng)項(xiàng) 目目3+ 1400CB 基基 bX1X2X3X4X53+ X1

23、 51-1/301/3-1/34 X3 3011-1/52/5CjZj0 /3 -20- /3 -1/5 /3 -3/5 (3) (3)如果設(shè)計(jì)一種新產(chǎn)品如果設(shè)計(jì)一種新產(chǎn)品D D，單件勞動(dòng)力消耗為，單件勞動(dòng)力消耗為8 8單位，材料消耗為單位，材料消耗為2 2單位，每件可獲利單位，每件可獲利3 3元，問該種產(chǎn)元，問該種產(chǎn)品是否值得生產(chǎn)品是否值得生產(chǎn)? ? 答：增加新產(chǎn)品答：增加新產(chǎn)品D D，最優(yōu)解為，最優(yōu)解為x x1 1=0,x=0,x2 2=0,x=0,x3 3=5, =5, x x6 6=2.5 Z=27.5 =2.5 Z=27.5 第二章習(xí)題解答第二章習(xí)題解答項(xiàng)項(xiàng) 目目3140 0 3CB 基基 bX1X2X3X4 X5 X63 X1 51-1/301/3 -1/3 2 4 X3 3011-1/5 2/5 -4/5CjZj0-20-1/5 -3/5 1/5 (4) (4)如果勞動(dòng)力數(shù)量不增，材料不足時(shí)可從市場(chǎng)如果勞動(dòng)力數(shù)量不增，材料不足時(shí)可從市場(chǎng)購(gòu)買，每單位購(gòu)買，每單位0.40.4元。問該廠要不要購(gòu)進(jìn)原材料擴(kuò)大元。問該廠要不要購(gòu)進(jìn)原材料擴(kuò)大生產(chǎn)，以購(gòu)多少為宜。生產(chǎn)，以購(gòu)多少為宜。 答：由（答：由（1 1）可知材料的對(duì)偶價(jià)格是）可知材料的對(duì)偶價(jià)格是0.60.6元，大于元，大于市場(chǎng)價(jià)格。故應(yīng)該購(gòu)進(jìn)原