《管理運(yùn)籌學(xué)》(第二版)課后習(xí)題參考答案

1、23管理運(yùn)籌學(xué)(第二版)課后習(xí)題參考答案第1章線性規(guī)劃(復(fù)習(xí)思考題)1 .什么是線性規(guī)劃？線性規(guī)劃的三要素是什么？答：線性規(guī)劃(LinearProgramming,LP)是運(yùn)籌學(xué)中最成熟的一個(gè)分支，并且是應(yīng)用最廣泛的一個(gè)運(yùn)籌學(xué)分支。線性規(guī)劃屬于規(guī)劃論中的靜態(tài)規(guī)劃，是一種重要的優(yōu)化工具，能夠解決有限資源的最佳分配問(wèn)題。建立線性規(guī)劃問(wèn)題要具備三要素：決策變量、約束條件、目標(biāo)函數(shù)。決策變量是決策問(wèn)題待定的量值，取值一般為非負(fù)；約束條件是指決策變量取值時(shí)受到的各種資源條件的限制，保障決策方案的可行性；目標(biāo)函數(shù)是決策者希望實(shí)現(xiàn)的目標(biāo)，為決策變量的線性函數(shù)表達(dá)式，有的目標(biāo)要實(shí)現(xiàn)極大值，有的則要求極小值。2

2、 .求解線性規(guī)劃問(wèn)題時(shí)可能出現(xiàn)幾種結(jié)果，哪種結(jié)果說(shuō)明建模時(shí)有錯(cuò)誤？答：(1)唯一最優(yōu)解：只有一個(gè)最優(yōu)點(diǎn)；(2)多重最優(yōu)解：無(wú)窮多個(gè)最優(yōu)解；(3)無(wú)界解：可行域無(wú)界，目標(biāo)值無(wú)限增大；(4)沒(méi)有可行解：線性規(guī)劃問(wèn)題的可行域是空集。當(dāng)無(wú)界解和沒(méi)有可行解時(shí)，可能是建模時(shí)有錯(cuò)。3 .什么是線性規(guī)劃的標(biāo)準(zhǔn)型？松弛變量和剩余變量的管理含義是什么？答：線性規(guī)劃的標(biāo)準(zhǔn)型是：目標(biāo)函數(shù)極大化，約束條件為等式，右端常數(shù)項(xiàng)bi>0,決策變量滿足非負(fù)性。如果加入的這個(gè)非負(fù)變量取值為非零的話，則說(shuō)明該約束限定沒(méi)有約束力，對(duì)企業(yè)來(lái)說(shuō)不是緊缺資源，所以稱為松弛變量；剩余變量取值為非零的話，則說(shuō)明“冊(cè)約束的左邊取值大于右邊

3、規(guī)劃值，出現(xiàn)剩余量。4 .試述線性規(guī)劃問(wèn)題的可行解、基礎(chǔ)解、基可行解、最優(yōu)解的概念及其相互關(guān)系。答：可行解：滿足約束條件AX=b,X之0的解，稱為可行解?；尚薪猓簼M足非負(fù)性約束的基解，稱為基可行解可行基：對(duì)應(yīng)于基可行解的基，稱為可行基。最優(yōu)解：使目標(biāo)函數(shù)最優(yōu)的可行解，稱為最優(yōu)解。最優(yōu)基：最優(yōu)解對(duì)應(yīng)的基矩陣，稱為最優(yōu)基。它們的相互關(guān)系如右圖所示：5 .用表格單純形法求解如下線性規(guī)劃maxZ=4x1x22x38x1+3x2+x3M2s.t.<6x1+x2+x3<8x1,x2,x3之0解：標(biāo)準(zhǔn)化列出單純形表maxZ=4x1+x2+2x3s.t8x1+3x2+x3+x46x1+x2+x3

4、+x5Xi,X2,X3,X4,X5>0=2=8cj41200CbXBbX1X2u1X3X4X50x42831102/80x58611018/6412004x11/413/81/81/80(1/4)/(1/8)0x513/265/41/43/41(13/2)/(1/4)01/23/2-1/202*32831100x56-2-20-11仃j-12-50-20故最優(yōu)解為X*=(0,0,2,0,6)T,即x1=0,x2=0,X3=2,此時(shí)最優(yōu)值為Z(X*)=4.6 .表115中給出了求極大化問(wèn)題的單純形表，問(wèn)表中a1,a2,c1,c2,d為何值及變量屬于哪一類型時(shí)有：（1）表中解為唯一最優(yōu)解；（

5、2）表中解為無(wú)窮多最優(yōu)解之一；（3）下一步迭代將以x1代替基變量x5；（4）該線性規(guī)劃問(wèn)題具有無(wú)界解；（5）該線性規(guī)劃問(wèn)題無(wú)可行解。表115某極大化問(wèn)題的單純形表cjc1c2000仇CbXBbx1x2x3x4x50*3d4a11000x42-1-50100x53a2-3001c1c2000解：（1）d之0，a<0,c2<0；(2) d之0,c1<0,c2<0(c1,c2中至少有一個(gè)為零)；(3) ci>0,a2>0,d;4a2(4) C2>0,a1<0;(5) %為人工變量，且ci為包含M的大于零的數(shù)，;或者X2為人工變量,4a2且C2為包含M的

6、大于零的數(shù)，ai>0,d>0.7.用大M法求解如下線性規(guī)劃。maxZ=5x13x26x3x1+2x2+x3<182x1+x2+3x3<16s.t.x1x2x3=10x1,x2,x3-0解：加入人工變量，進(jìn)行人造基后的數(shù)學(xué)模型如下：maxZ=5x13x26x30x40x5-Mx6x1+2x2+x3+x4=182x1x23x3x5=16s.t.x1x2x3x6=10.xi-0(i=1,2,6)列出單純形表cj53600一M仇CBXbbX1X2X3X4X5X6i0X41812110018/10X51621301016/3一MX61011100110/15+M3+M6+M000

7、0X438/31/35/301-1/3038/56X316/32/31/3101/3016一MX614/31/32/300-1/3114/211+M31+-M3001-2M300X411/20011/2-5/2一6X3310101/2-1/263X271/2100-1/23/2141/2000-3/23n”M20X4400111-35Xi610201-13X2401-10-1200-10-2一1一M故最優(yōu)解為X*=(6,4,0,4,0,0)T,即Xi=6,X2=4,X3=0,此時(shí)最優(yōu)值為Z(X*)=42.8 .A,B,C三個(gè)城市每年需分別供應(yīng)電力320,250和350單位，由I,II兩個(gè)電站提

8、供，它們的最大可供電量分別為400單位和450單位，單位費(fèi)用如表116所示。由于需要量大于可供量，決定城市A的供應(yīng)量可減少030單位，城市B的供應(yīng)量不變，城市C的供應(yīng)量不能少于270單位。試建立線性規(guī)劃模型，求將可供電量用完的最低總費(fèi)用分配方案。表116單位電力輸電費(fèi)(單位：元)ABCI151822II212516解：設(shè)Xj為“第i電站向第j城市分配的電量"(i=1,2;j=1,2,3),建立模型如下:maxZ=15xii18x1222xi321x2125x2216x23x11+x12+x13=400x21+x22+x23=450x11+x21>290,。F<320s.t

9、.x12+x22=250x13+x23之270x13+x23<350Xj之0,i=1,2;j=1,2,39 .某公司在3年的計(jì)劃期內(nèi)，有4個(gè)建設(shè)項(xiàng)目可以投資：項(xiàng)目I從第一年到第三年年初都可以投資。預(yù)計(jì)每年年初投資，年末可收回本利120%,每年又可以重新將所獲本利納入投資計(jì)劃；項(xiàng)目II需要在第一年初投資，經(jīng)過(guò)兩年可收回本利150%,又可以重新將所獲本利納入投資計(jì)劃，但用于該項(xiàng)目的最大投資不得超過(guò)20萬(wàn)元；項(xiàng)目III需要在第二年年初投資，經(jīng)過(guò)兩年可收回本利160%,但用于該項(xiàng)目的最大投資不得超過(guò)15萬(wàn)元；項(xiàng)目IV需要在第三年年初投資，年末可收回本利140%,但用于該項(xiàng)目的最大投資不得超過(guò)10

10、萬(wàn)元。在這個(gè)計(jì)劃期內(nèi)，該公司第一年可供投資的資金有30萬(wàn)元。問(wèn)怎樣的投資方案，才能使該公司在這個(gè)計(jì)劃期獲得最大利潤(rùn)？解：設(shè)xi表示第一次投資項(xiàng)目i,設(shè)xi表示第二次投資項(xiàng)目i,設(shè)xi表示第三次投資項(xiàng)目i,(i=1,2,3,4),則建立的線性規(guī)劃模型為maxZ=1.2x1(3)1.6x3"，1.4比1)xx2"-30x：2)-x31)<1.2x1(1)-30-x-x21)(3)(1)(2)(1)(1)(1)(1)(2)xx4-1.2x11.5x21.2x130-x1-'x2-'x1s.t.x2"M20x31)-15x41)<10xi(1)

11、,x(2),x(3)0,i=123,4通過(guò)LINGO軟件計(jì)算得：x=10,x21)=？。/?=0戈2)=12»2)=44.10 .某家具制造廠生產(chǎn)五種不同規(guī)格的家具。每種家具都要經(jīng)過(guò)機(jī)械成型、打磨、上漆幾道重要工序。每種家具的每道工序所用的時(shí)間、每道工序的可用時(shí)間、每種家具的利潤(rùn)由表117給出。問(wèn)工廠應(yīng)如何安排生產(chǎn)，使總利潤(rùn)最大？表117家具生產(chǎn)工藝耗時(shí)和利潤(rùn)表生產(chǎn)工序所需時(shí)間（小時(shí)）每道，序引用時(shí)間（小時(shí)）12345346233600打磨435643950上漆233432800利潤(rùn)（百元）2.734.52.53解：設(shè)x表示第i種規(guī)格的家具的生產(chǎn)量（i=1,2,5）,則maxZ=2.

12、7x13x24.5x32.543x53x1+4x2+6x3+2x4+3x5<36004x1+3x2+5x3+6x4+4x5<3950s.t.2x13x23x34x43x5<2800為一0=1,2,5通過(guò)LINGO軟件計(jì)算得：x1=0,x2=38,x3=254,刈=0,x5=642,Z=3181.11 .某廠生產(chǎn)甲、乙、丙三種產(chǎn)品，分別經(jīng)過(guò)A,B,C三種設(shè)備加工。已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)數(shù)、設(shè)備的現(xiàn)有加工能力及每件產(chǎn)品的利潤(rùn)如表2-10所示,表118產(chǎn)品生產(chǎn)工藝消耗系數(shù)甲乙丙設(shè)備能力A（小時(shí)）111100B（小時(shí)）1045600C（小時(shí)）226300單位產(chǎn)品利潤(rùn)（元）10

13、64（1）建立線性規(guī)劃模型，求該廠獲利最大的生產(chǎn)計(jì)劃。（2）產(chǎn)品內(nèi)每件的利潤(rùn)增加到多大時(shí)才值得安排生產(chǎn)？如產(chǎn)品內(nèi)每件的利潤(rùn)增加到6,求最優(yōu)生產(chǎn)計(jì)劃。（3）產(chǎn)品甲的利潤(rùn)在多大范圍內(nèi)變化時(shí)，原最優(yōu)計(jì)劃保持不變？（4）設(shè)備A的能力如為100+10q,確定保持原最優(yōu)基不變的q的變化范圍（5）如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品丙，試確定最優(yōu)計(jì)劃的變化。解：（1）設(shè)Xi,X2,X3分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量，建立線性規(guī)劃模型maxZ=10x16x24x3x1+x2+x3<10010x1+4x2+5x3<600s.t.2x12x26x3<300x1,x2,x3_0標(biāo)準(zhǔn)化得maxZs.t.

14、列出單純形表=10x1+6x2+4x3+0x4+0x5+0x6x1+x2+x3+x4=10010x1+4x2+5x3+x5=600'2xi+2x2+6x3+x6=300為？2,乂3,人“5,乂6之0cj10640004CBXBbxix2x3x4x5x6000x4x5*610060030011110010450102260011006015010640000100x4xix6406018003/51/21-1/10012/51/201/10006/5501/51200/3150150j0210106100x2xix6200/3100/3100015/65/3-1/60101/62/31/

15、60004-201008/310/32/30故最優(yōu)解為x1=100/3.2=200/3%=0，又由于xi,x2,x3取整數(shù)，故四舍五入可得最優(yōu)解為*=33,x2=67,x3=0,Zmax=732.(2)產(chǎn)品內(nèi)的利潤(rùn)C(jī)3變化的單純形法迭代表如下:cj106C30006iCBXBbx1x2X3x4x5x66x2200/3015/65/31/6010x1100/3101/62/31/600x6100004-20100C320/310/32/30要使原最優(yōu)計(jì)劃保持不變，只要仃3=C3-20E0,即c3M62之6.67.故當(dāng)產(chǎn)品內(nèi)每33件的利潤(rùn)增加到大于6.67時(shí)，才值得安排生產(chǎn)。如產(chǎn)品內(nèi)每件的利潤(rùn)增加

16、到6時(shí)，此時(shí)6<6.67,故原最優(yōu)計(jì)劃不變。(3)由最末單純形表計(jì)算出121仃3=-1C1三0,。4=一10+C1<0,a5=1一一ciW0,636解得6WgW15,即當(dāng)產(chǎn)品甲的利潤(rùn)g在6,15范圍內(nèi)變化時(shí)，原最優(yōu)計(jì)劃保持不變5/3-1/60'(4)由最末單純形表找出最優(yōu)基的逆為B'=-2/31/60,新的最優(yōu)解為2015/3-2/3-1/61/600、0 b100 +10q600300200 50q100 -20q3(100 -20q)解得-4WqM5,故要保持原最優(yōu)基不變的q的變化范圍為-4,5.(5)如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品內(nèi)，則線性規(guī)劃模型變成max

17、Z=10x16x24x3x1+x2+x3W10010x1+4x2+5x3<600s.t.<2x1+2x2+6x3W300x3>10x1,x2,x30通過(guò)LINGO軟件計(jì)算得到：x1=32,x2=58,x3=10,Z=708第2章對(duì)偶規(guī)劃(復(fù)習(xí)思考題)1 .對(duì)偶問(wèn)題和對(duì)偶向量(即影子價(jià)值)的經(jīng)濟(jì)意義是什么?答：原問(wèn)題和對(duì)偶問(wèn)題從不同的角度來(lái)分析同一個(gè)問(wèn)題，前者從產(chǎn)品產(chǎn)量的角度來(lái)考察利潤(rùn)，后者則從形成產(chǎn)品本身所需要的各種資源的角度來(lái)考察利潤(rùn)，即利潤(rùn)是產(chǎn)品生產(chǎn)帶來(lái)的，同時(shí)又是資源消耗帶來(lái)的。對(duì)偶變量的值yi表示第i種資源的邊際價(jià)值，稱為影子價(jià)值?？梢园褜?duì)偶問(wèn)題的解Y定義為每增加一個(gè)

18、單位的資源引起的目標(biāo)函數(shù)值的增量。2 .什么是資源的影子價(jià)格？它與相應(yīng)的市場(chǎng)價(jià)格有什么區(qū)別？答：若以產(chǎn)值為目標(biāo)，則%是增加單位資源i對(duì)產(chǎn)值的貢獻(xiàn)，稱為資源的影子價(jià)格(ShadowPrice)。即有“影子價(jià)格=資源成本+影子利潤(rùn)”。因?yàn)樗⒉皇琴Y源的實(shí)際價(jià)格，而是企業(yè)內(nèi)部資源的配比價(jià)格，是由企業(yè)內(nèi)部資源的配置狀況來(lái)決定的，并不是由市場(chǎng)來(lái)決定，所以叫影子價(jià)格?？梢詫①Y源的市場(chǎng)價(jià)格與影子價(jià)格進(jìn)行比較，當(dāng)市場(chǎng)價(jià)格小于影子價(jià)格時(shí)，企業(yè)可以購(gòu)進(jìn)相應(yīng)資源，儲(chǔ)備或者投入生產(chǎn)；當(dāng)市場(chǎng)價(jià)格大于影子價(jià)格時(shí)，企業(yè)可以考慮暫不購(gòu)進(jìn)資源，減少不必要的損失。3 .如何根據(jù)原問(wèn)題和對(duì)偶問(wèn)題之間的對(duì)應(yīng)關(guān)系，找出兩個(gè)問(wèn)題變量之間

19、、解及檢驗(yàn)數(shù)之間的關(guān)系？答：(1)最優(yōu)性定理：設(shè)X,Y分別為原問(wèn)題和對(duì)偶問(wèn)題的可行解，且cX=bTY,則X,Y分別為各自的最優(yōu)解。(2)對(duì)偶性定理：若原問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解，而且兩者的目標(biāo)函數(shù)值相等。(3)互補(bǔ)松弛性：原問(wèn)題和對(duì)偶問(wèn)題的松弛變量為Xs和Ys,它們的可行解X*,Y*為最優(yōu)解的充分必要條件是Y*Xs=0,YsX*=0.(4)對(duì)偶問(wèn)題的最優(yōu)解對(duì)應(yīng)于原問(wèn)題最優(yōu)單純形表中，初始基變量的檢驗(yàn)數(shù)的負(fù)值。若-Ys對(duì)應(yīng)于原問(wèn)題決策變量x的檢驗(yàn)數(shù)，則-Y對(duì)應(yīng)于原問(wèn)題松弛變量xs的檢驗(yàn)4 .已知線性規(guī)劃問(wèn)題maxZ=4x1x22x38x1+3x2+x3M2(第一種資源)5 .t.*6

20、x1+x2+x3<8(第二種資源)x1,x2,x3之0(1)求出該問(wèn)題產(chǎn)值最大的最優(yōu)解和最優(yōu)值。(2)求出該問(wèn)題的對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)值。(3)給出兩種資源的影子價(jià)格，并說(shuō)明其經(jīng)濟(jì)含義；第一種資源限量由2變?yōu)?,最優(yōu)解是否改變？(4)代加工產(chǎn)品丁，每單位產(chǎn)品需消耗第一種資源2單位，消耗第二種資源3單位，應(yīng)該如何定價(jià)？解：(1)標(biāo)準(zhǔn)化，并列出初始單純形表cj412006CbXBbx1x2x3x4x50x42831102/80*58611018/6:j412004x11/413/81/81/8020x513/265/41/43/4126巧;j0-1/23/2-1/202*32831100x

21、56-2-20-11a:j-12-50-20由最末單純性表可知，該問(wèn)題的最優(yōu)解為：X*=(0,020,6)T,即x1=0,x2=0,x3=2,最優(yōu)值為Z=4.(2)由原問(wèn)題的最末單純形表可知，對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)值為:yi=2,y2=0,w=4.(3)兩種資源的影子價(jià)格分別為2、0,表示對(duì)產(chǎn)值貢獻(xiàn)的大??；第一種資源限量由2變?yōu)?,最優(yōu)解不會(huì)改變。(4)代加工產(chǎn)品丁的價(jià)格不低于2父2+0父3=4.5.某廠生產(chǎn)A,B,C,D4種產(chǎn)品，有關(guān)資料如表26所示。表26源消耗資源產(chǎn)品資源供應(yīng)量(公斤)原料成本(元/公斤)ABCD甲23128002.0乙543412001.0丙345310001.5單位產(chǎn)

22、品售價(jià)(元)14.52115.516.5(1)請(qǐng)構(gòu)造使該廠獲利潤(rùn)最大的線性規(guī)劃模型，并用單純形法求解該問(wèn)題(不計(jì)加工成本)。(2)該廠若出租資源給另一個(gè)工廠，構(gòu)成原問(wèn)題的對(duì)偶問(wèn)題，列出對(duì)偶問(wèn)題的數(shù)學(xué)模型，資源甲、乙、丙的影子價(jià)格是多少？若工廠可在市場(chǎng)上買到原料丙，工廠是否應(yīng)該購(gòu)進(jìn)該原料以擴(kuò)大生產(chǎn)？(3)原料丙可利用量在多大范圍內(nèi)變化，原最優(yōu)生產(chǎn)方案中生產(chǎn)產(chǎn)品的品種不變(即最優(yōu)基不變)？(4)若產(chǎn)品B的價(jià)格下降了0.5元，生產(chǎn)計(jì)劃是否需要調(diào)整？解：(1)設(shè)Xi,X2,X3,X4分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量，建立線性規(guī)劃模型maxZ=x15x23x34x42x1+3x2+x3+2x4<80

23、05x1+4x2+3x3+4x4<1200s.t.3x14x25x33x4,1000X.0,i=1,2,3,4初始單純形表cj1534000ACBXBbx1x2x3x4xsx6X7Ui0x58002312100800/30*6120054340101200/40x7100034530011000/41534000最末單純形表cj15340001ACBXBbx1x2x3x4x5x6X7°i0x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/410;j-13/40-11/400-1/4-1解得最優(yōu)解為：X=(0,100,

24、0,200,100)，最優(yōu)值Z=1300.(2)原問(wèn)題的對(duì)偶問(wèn)題的數(shù)學(xué)模型為minw=80(y112002100032y1+5y2+3y3之13y1+4y2+4y3之5s.ty1+3y2+5y3之12y1+4y2+3y3之4y1,y2,y3-0解得影子價(jià)格分別為2、1.25、2.5。對(duì)比市場(chǎng)價(jià)格和影子價(jià)格，當(dāng)市場(chǎng)價(jià)低于影子價(jià)格時(shí)購(gòu)進(jìn)。(3)原料丙可利用量在900,1100范圍內(nèi)變化，原最優(yōu)生產(chǎn)方案中生產(chǎn)產(chǎn)品的品種不變(即最優(yōu)基不變)。(4)若產(chǎn)品B的價(jià)格下降了0.5元，生產(chǎn)計(jì)劃不需要調(diào)整。6.某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，產(chǎn)品生產(chǎn)的工藝路線如圖21所示，試統(tǒng)計(jì)單位產(chǎn)品的設(shè)備工時(shí)消耗，填入表27。又

25、已知材料、設(shè)備C和設(shè)備D等資源的單位成本和擁有量如表27所小。表27資源消耗與資源成本表品資源消耗資源成本資源擁啟量資源甲乙元/單位資源材料(公斤)60502004200設(shè)備C(小時(shí))3040103000設(shè)備D(小時(shí))6050204500據(jù)市場(chǎng)分析，甲、乙產(chǎn)品銷售價(jià)格分別為13700元和11640元，試確定獲利最大的產(chǎn)品生產(chǎn)計(jì)劃。(1)設(shè)產(chǎn)品甲的計(jì)劃生產(chǎn)量為不，產(chǎn)品乙的計(jì)劃生產(chǎn)量為X2,試建立其線性規(guī)劃的數(shù)學(xué)模型；若將材料約束加上松弛變量X3,設(shè)備C約束加上松弛變量X4,設(shè)備D約束加上松弛變量x5,試化成標(biāo)準(zhǔn)型。(2)利用LINDO軟件求得：最優(yōu)目標(biāo)函數(shù)值為18400,變量的最優(yōu)取值分別為X=

26、20,X2=60,X3=0,X4=0,X5=300,則產(chǎn)品的最優(yōu)生產(chǎn)計(jì)劃方案是什么？并解釋X3=0,X4=0,X5=300的經(jīng)濟(jì)意義。(3)利用LINDO軟件對(duì)價(jià)值系數(shù)進(jìn)行敏感性分析，結(jié)果如下：ObjCoefficientRangesVariableCurrentCoefAllowableIncreaseAllowableDecreaseXi2008820x224026.6773.33試問(wèn)如果生產(chǎn)計(jì)劃執(zhí)行過(guò)程中，甲產(chǎn)品售價(jià)上升到13800元，或者乙產(chǎn)品售價(jià)降低60元，所制定的生產(chǎn)計(jì)劃是否需要進(jìn)行調(diào)整？(4)利用LINDO軟件對(duì)資源向量進(jìn)行敏感性分析，結(jié)果如下：RighthandSideRang

27、esResourceCurrentRhsAllowableIncreaseAllowableDecrease材料4200300450設(shè)備C3000360900設(shè)備D4500Infinity300試問(wèn)非緊缺資源最多可以減少到多少，而緊缺資源最多可以增加到多少?解：(1)建立的線性規(guī)劃模型為maxZ=200x1240x260x1+50x2<420030x1+40x2<3000s.t.60x150x2三4500x1,x2-0將其標(biāo)準(zhǔn)化maxZ=200x1240x260x1+50x2+x3=420030x1+40x2+x4=3000s.t.60x150x2x5=4500X0,i=12,5(

28、2)甲生產(chǎn)20件，乙生產(chǎn)60件，材料和設(shè)備C充分利用，設(shè)備D剩余600單位(3)甲上升到13800需要調(diào)整，乙下降60不用調(diào)整。(4)非緊缺資源設(shè)備D最多可以減少到300,而緊缺資源一材料最多可以增加到300,緊缺資源一設(shè)備C最多可以增加到360。第3章整數(shù)規(guī)劃(復(fù)習(xí)思考題)1.整數(shù)規(guī)劃的類型有哪些？答：純整數(shù)規(guī)劃、0-1規(guī)劃和混合整數(shù)規(guī)劃。2.試述整數(shù)規(guī)劃分枝定界法的思路。答：(1)首先不考慮整數(shù)條件，求解整數(shù)規(guī)劃相應(yīng)的線性規(guī)劃問(wèn)題。若相應(yīng)的線性規(guī)劃問(wèn)題沒(méi)有可行解，停止計(jì)算，這時(shí)原整數(shù)規(guī)劃也沒(méi)有可行解。(2)定界過(guò)程。對(duì)于極大化的整數(shù)規(guī)劃問(wèn)題，當(dāng)前所有未分枝子問(wèn)題中最大的目標(biāo)函數(shù)值為整數(shù)規(guī)劃

29、問(wèn)題上界；在滿足整數(shù)約束的子問(wèn)題的解中，最大的目標(biāo)函數(shù)值為整數(shù)規(guī)劃問(wèn)題的下界。當(dāng)上下界相同時(shí)，則已得最優(yōu)解；否則，轉(zhuǎn)入剪枝過(guò)程。(3)剪枝過(guò)程。在下述情況下剪除這些分枝：若某一子問(wèn)題相應(yīng)的線性規(guī)劃問(wèn)題無(wú)可行解；在分枝過(guò)程中，求解某一線性規(guī)劃所得到的目標(biāo)函數(shù)值Z不優(yōu)于現(xiàn)有下界。(4)分枝過(guò)程。當(dāng)有多個(gè)待求分枝時(shí)，應(yīng)先選取目標(biāo)函數(shù)值最優(yōu)的分枝繼續(xù)進(jìn)行分枝。選取一個(gè)不符合整數(shù)條件的變量為作為分枝變量，若Xi的值是b；,構(gòu)造兩個(gè)新的約束條件：XiMbi或Xi之屹+1,分別并入相應(yīng)的數(shù)學(xué)模型中，構(gòu)成兩個(gè)子問(wèn)題。對(duì)任一個(gè)子問(wèn)題，轉(zhuǎn)步驟(1).3.試用分枝定界法求如下線性規(guī)劃:上界；349F 界7上界:34

30、0 卜界：327人最優(yōu)整數(shù)解為：x1=4,x2=2,Z=340.4 .有4名職工，由于各人的能力不同，每個(gè)人做各項(xiàng)工作所用的時(shí)間不同，所花費(fèi)時(shí)間如表37所示。表37（單位：分鐘）7J間務(wù)人ABCD甲15182124乙19232218丙26171619丁19212317問(wèn)指派哪個(gè)人去完成哪項(xiàng)工作，可使總的消耗時(shí)間最少?解：設(shè)Xj=1'任?1»員）1成,上，tj為個(gè)人i對(duì)于彳務(wù)j的時(shí)間耗費(fèi)矩陣，則j0,任務(wù)i不由人員j完成j建立整數(shù)規(guī)劃模型為:4zXj=1i=14st.J工Xij=1j3Xj=(M1,i,j=1,2,3,4解得：X12=1,X21=1,X33=1,X44=1,其余

31、均為零，Z=70,即任務(wù)A由乙完成，任務(wù)B由甲完成，任務(wù)C由內(nèi)完成，任務(wù)D由丁完成。5 .某部門一周中每天需要不同數(shù)目的雇員：周一到周四每天至少需要50人，周五至少需要80人，周六周日每天至少需要90人，先規(guī)定應(yīng)聘者需連續(xù)工作5天,試確定聘用方案，即周一到周日每天聘用多少人，使在滿足需要的條件下聘用總?cè)藬?shù)最少。解：設(shè)x表示在第i大應(yīng)聘的雇員人數(shù)(i=1,2,3,4,5,6,7)。數(shù)學(xué)模型為minZ=x1x2x3x4x5x6x7x1+x4+x5+x6+x7至50x1+x2+x5+x6+x7>50x1+x2+x3+x6+x7>50xi+x2+x3+x4+x7>506 .t.<

32、;x+x2+x3+“+x5>80x2+x3+x4+A+x6之90x3+x4+x5+x6+x7之90xi之0,i=1,2,，7ki取整數(shù)，i=1,2,，7解得：x1=0,x2=4,x3=32,x4=10,x5=34,x6=10,x7=4,Z=94.第4章目標(biāo)規(guī)劃(復(fù)習(xí)思考題)1 .某計(jì)算機(jī)公司生產(chǎn)A,B,C三種型號(hào)的筆記本電腦。這三種筆記本電腦需要在復(fù)雜的裝配線上生產(chǎn)，生產(chǎn)一臺(tái)A,B,C型號(hào)的筆記本電腦分別需要5小時(shí)、8小時(shí)、12小時(shí)。公司裝配線正常的生產(chǎn)時(shí)間是每月1700小時(shí)，公司營(yíng)業(yè)部門估計(jì)A,B,C三種筆記本電腦每臺(tái)的利潤(rùn)分別是1000元、1440元、2520元，而且公司預(yù)測(cè)這個(gè)月生

33、產(chǎn)的筆記本電腦能夠全部售出。公司經(jīng)理考慮以下目標(biāo)：第一目標(biāo)：充分利用正常的生產(chǎn)能力，避免開(kāi)工不足；第二目標(biāo)：優(yōu)先滿足老客服的需求，A,B,C三種型號(hào)的電腦各為50臺(tái)、50臺(tái)、80臺(tái)，同時(shí)根據(jù)三種電腦三種電腦的純利潤(rùn)分配不同的加權(quán)系數(shù)；第三目標(biāo)：限制裝配線加班時(shí)間，最好不超過(guò)200小時(shí)；第四目標(biāo)：滿足各種型號(hào)電腦的銷售目標(biāo)，A,B,C三種型號(hào)分別為100臺(tái)、120臺(tái)、100臺(tái)，再根據(jù)三種電腦的純利潤(rùn)分配不同的加權(quán)系數(shù)；第五目標(biāo)：裝配線加班時(shí)間盡可能少。請(qǐng)列出相應(yīng)的目標(biāo)規(guī)劃模型，并用LINGO軟件求解。解：建立目標(biāo)約束。(1)裝配線正常生產(chǎn)設(shè)生產(chǎn)A,B,C型號(hào)的電腦為X1,X2,X3(臺(tái)),d為裝

34、配線正常生產(chǎn)時(shí)間未利用數(shù)，d；為裝配線加班時(shí)間，希望裝配線正常生產(chǎn)，避免開(kāi)工不足，因此裝配線目標(biāo)約束為mind15x18x212x3d-d1=17003(2)銷售目標(biāo)優(yōu)先滿足老客戶的需求，并根據(jù)三種電腦的純利潤(rùn)分配不同的權(quán)因子，A,B,C三種型號(hào)的電腦每小時(shí)的利潤(rùn)是,252°,因此，老客戶的銷售目標(biāo)約束為5812min20d2-18d3-21d4x1d2I-d2=50x2d3-d3=50x3d4r-d4:80再考慮一般銷售。類似上面的討論，得到min20d5-18d6-21d7x1d5d5=100X2d6-d6=120x3d7-d7=100(3)加班限制首先是限制裝配線加班時(shí)間，不允

35、許超過(guò)200小時(shí)，因此得到mind85x18x212x3d8-d8=1900388其次裝配線的加班時(shí)間盡可能少，即mind15x18x212x3dj-d1=17003寫(xiě)出目標(biāo)規(guī)劃的數(shù)學(xué)模型minG=RdP2(20d2-18dl21d4一)P3d8P4(20d5-18d6_21d7-)P5d15x1+8x2+12x3+dj-d1=1700x1+d2-d：=50x2+dj-d3'=50x3+d1-d：=80st.,Xi+d5-d5+=100x2+d6_d6+=120x3+d7-d7+=1005x1+8x2+12x3+d-d：=1900xi>0,i=1,2_+d,dl0,l=1,2,8

36、經(jīng)過(guò)LINGO軟件計(jì)算，得到xi=100,X2=55,x3=80,裝配線生產(chǎn)時(shí)間為1900小時(shí)，滿足裝配線加班不超過(guò)200小時(shí)的要求。能夠滿足老客戶的需求，但未能達(dá)到銷售目標(biāo)。銷售總利潤(rùn)為100X1000+55X1440+80X2520=380800（元）。2.已知3個(gè)工廠生產(chǎn)的產(chǎn)品供應(yīng)給4個(gè)客戶，各工廠生產(chǎn)量、用戶需求量及從各工廠到用戶的單位產(chǎn)品的運(yùn)輸費(fèi)用如表4-3所示。由于總生產(chǎn)量小于總需求量，上級(jí)部門經(jīng)研究后，制定了調(diào)配方案的8個(gè)目標(biāo)，并規(guī)定了重要性的次序。表43工廠產(chǎn)量一用戶需求量及運(yùn)費(fèi)單價(jià)（單位：元）1234生1里152672354634523需求量（單位）200100450250第

37、一目標(biāo)：用戶4為重要部門，需求量必須全部滿足；第二目標(biāo)：供應(yīng)用戶1的產(chǎn)品中，工廠3的產(chǎn)品不少于100個(gè)單位；第三目標(biāo)：每個(gè)用戶的滿足率不低于80%;第四目標(biāo)：應(yīng)盡量滿足各用戶的需求；第五目標(biāo)：新方案的總運(yùn)費(fèi)不超過(guò)原運(yùn)輸問(wèn)題（線性規(guī)劃模型）的調(diào)度方案的10%;第六目標(biāo)：因道路限制，工廠2到用戶4的路線應(yīng)盡量避免運(yùn)輸任務(wù)；第七目標(biāo)：用戶1和用戶3的滿足率應(yīng)盡量保持平衡；第八目標(biāo)：力求減少總運(yùn)費(fèi)。請(qǐng)列出相應(yīng)的目標(biāo)規(guī)劃模型，并用LINGO軟件求解。解：假設(shè)三個(gè)工廠對(duì)應(yīng)的生產(chǎn)量分別為300,200,400.（1）求解原運(yùn)輸問(wèn)題由于總生產(chǎn)量小于總需求量，虛設(shè)工廠4,生產(chǎn)量為100個(gè)單位，到各個(gè)用戶間的運(yùn)費(fèi)單價(jià)為0o用LINGO軟件求解，得到總運(yùn)費(fèi)是2950元，運(yùn)輸方案如下表所示。1234生1里11002003002200200325015040041001002001004