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

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

3、于右邊規(guī)劃值，出現(xiàn)剩余量。4試述線性規(guī)劃問題的可行解、基礎(chǔ)解、基可行解、最優(yōu)解的概念及其相互關(guān)系。答：可行解：滿足約束條件AXb，X0的解，稱為可行解。基可行解：滿足非負(fù)性約束的基解，稱為基可行解。可行基：對應(yīng)于基可行解的基，稱為可行基。最優(yōu)解：使目標(biāo)函數(shù)最優(yōu)的可行解，稱為最優(yōu)解。最優(yōu)基：最優(yōu)解對應(yīng)的基矩陣，稱為最優(yōu)基。它們的相互關(guān)系如右圖所示：5用表格單純形法求解如下線性規(guī)劃。maxZ4 x 1x22x 3x22x 35x528x 13x 2x32s.t. 6x 1x2x 38x 1,x2,x30解：標(biāo)準(zhǔn)化m a x Z4x 18x 13x2x 3x4s.t. 6x 1x2x3x4,x8x

4、1,x2,x3,0列出單純形表jc4 1 2 0 0 i2/8 8/6 (1/4)/(1/8) (13/2)/(1/4) CBXBbx 12xx 3x 45x0 x42 8 3 1 1 0 0 x 58 6 1 1 0 1 j4 1 2 0 0 4 x 11/4 1 3/8 1/8 1/8 0 0 x 513/2 6 5/4 1/4 3/4 1 Z(X*)4j0 1/2 3/2 -1/2 0 2 x 32 8 3 1 1 0 0 x 56 2 2 0 1 1 j12 5 0 2 0 故最優(yōu)解為X*(,0 0 2, , ,0 6 )T，即x 10 ,x 20 ,x32，此時最優(yōu)值為6表 115

5、中給出了求極大化問題的單純形表，問表中a 1,a2,c 1,c 2,d為何值及變量屬于哪一類型時有：（1）表中解為唯一最優(yōu)解；（2）表中解為無窮多最優(yōu)解之一； （3）下一步迭代將以1x 代替基變量x ；（4）該線性規(guī)劃問題具有無界解； （5）該線性規(guī)劃問題無可行解。jc表 115 某極大化問題的單純形表0 0 1cc 20 i且CBXBbx 1x 2x 3d4x；或者x 50 0 0 3xd 4 a 11 0 4x2 1 5 0 1 0 0 1 0 5x3 a 23 0 j1cc 20 0 0 解：（1）d0 ,c 1,0c20；（2）d0 ,c 10 ,c20（c 1,c2 中至少有一個為零

6、）；（3）c 1,0a20 ,d3；4a23x 為人工變量，（4）c2,0a 10；（5）1x 為人工變量，且1c 為包含 M 的大于零的數(shù)，4a2c 為包含 M 的大于零的數(shù)，a 1,0d07用大 M 法求解如下線性規(guī)劃。maxZ5 x 13 x26x 3s.t. x 12x2x 3182x 1x23x316x 1x2x310 x1,x 2,x 30解：加入人工變量，進(jìn)行人造基后的數(shù)學(xué)模型如下：maxZ5x 13x 26x 3,0 x40 x5Mx6s.t. x 12x2x3x4182x 1x23x 3x516x1x2x3x610 xi0(i,12,6)列出單純形表CBjc5 3 x 16

7、0 x 30 M(XiXBbx 12xx 3x 45xx60 1 2 1 1 0 0 18/1 x 418 0 x 516 2 1 3 0 1 0 16/3 Mx 610 1 1 1 0 0 1 10/1 0 5+M3+M6+M0 0 0 j38/5 x 438/3 1/3 5/3 0 11/3 0 6 x 316/3 2/3 1/3 1 0 1/3 0 16 Mx 614/3 1/3 2/3 0 0 1/3 1 14/2 0 11M12M21M0 0 0 j333x 41 0 1 1/2 0 1/2 5/2 6 x 33 1/2 0 1 0 1/2 1/2 6 3 x 27 1/2 1 0

8、0 1/2 3/2 14 0 j1/2 0 0 0 3/2 3M*)422x 44 0 0 1 1 1 3 5 x 16 1 0 2 0 1 1 3 x 24 0 1 1 0 1 2 0 0 1 0 2 1 Mj故最優(yōu)解為X*(,6 4 0, , ,4 ,0 0 )T，即6 ,x 2,40，此時最優(yōu)值為Z8A，B，C 三個城市每年需分別供應(yīng)電力320，250 和 350 單位，由 I，II 兩個電站提供，它們的最大可供電量分別為 400 單位和 450 單位，單位費用如表 116 所示。由于需要量大于可供量，決定城市 A 的供應(yīng)量可減少 030 單位，城市 B 的供應(yīng)量不變，城市 C 的供應(yīng)量

9、不能少于 低總費用分配方案。270 單位。試建立線性規(guī)劃模型， 求將可供電量用完的最表 116 單位電力輸電費（單位：元）電站 城市 A B C I 15 18 22 II 21 25 16 解：設(shè) ijx 為“ 第 i 電站向第 j 城市分配的電量” （i=1,2; j=1,2,3），建立模型如下：max Z 15 x 11 18 x 12 22 x 13 21 x 21 25 x 22 16 x 23x 11 x 12 x 13 400 x 21 x 22 x 23 450 x 11 x 21 290 x 11 x 21 320s.t. x 12 x 22 250 x 13 x 23 27

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

11、 10 萬元。在這個計劃期內(nèi)， 該公司第一年可供投資的資金有 30 萬元。問怎樣的投資方案，才能使該公司在這個計劃期獲得最大利潤？解：設(shè)( 1 )ix表示第一次投資項目i，設(shè)( ix2)表示第二次投資項目i，設(shè)( ix3)表示第三次投資項目 i，（i=1,2,3,4），則建立的線性規(guī)劃模型為maxZ1 2.( x 13)1 6.( 1 )x 34.1x( 1 )( 1 )x 22)( x 12)( 1x 3)4( x 12)( x 11 )( 1 )x 230 x( 1)1 2.( 1 )x 130( x 11 )3( x 13)( 1 )x 4(.1 2 x 12)1 . 5( 1 )x 2

12、1 2.( x 11 )30( 1 )x 1x(1)2s.t. x(1 )2012 ,( x 1442( 1x 3)15x(1)104通過 LINGO 軟件計算得：( x 11 )( x i1),( x i2),x(3 )0 ,i,1,2,3 4i10 ,( 1x 2)20 ,x( 1),0( x 12)310某家具制造廠生產(chǎn)五種不同規(guī)格的家具。每種家具都要經(jīng)過機(jī)械成型、打磨、上漆幾道重要工序。每種家具的每道工序所用的時間、每道工序的可用時間、每種家具 的利潤由表 117 給出。問工廠應(yīng)如何安排生產(chǎn)，使總利潤最大？表 117 家具生產(chǎn)工藝耗時和利潤表Z每道工序可用生產(chǎn)工序1 所需時間（小時）4

13、 5 2 3 時間（小時）成型3 4 6 2 3 3600 打磨4 3 5 6 4 3950 上漆2 3 3 4 3 2800 利潤（百元）2.7 3 4.5 2.5 3 解：設(shè)ix 表示第 i 種規(guī)格的家具的生產(chǎn)量（ i=1,2, ,5），則maxZ2 7.x 13x 2.45 x 3.2 5 x43 x 53x 14x26x32x43x 53600s.t. 4x 13x25 x36x44x 539502x13x23 x34x43x 528003181xi0,i,12,5通過 LINGO 軟件計算得：x 10 ,x238 ,x 3254 ,x 40 ,x5642 ,11某廠生產(chǎn)甲、乙、丙三種

14、產(chǎn)品，分別經(jīng)過A，B，C 三種設(shè)備加工。已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時數(shù)、設(shè)備的現(xiàn)有加工能力及每件產(chǎn)品的利潤如表 210 所示。表 118 產(chǎn)品生產(chǎn)工藝消耗系數(shù)甲 乙 丙 設(shè)備能力A（小時）1 1 1 100 B（小時）10 4 5 600 C（小時）2 2 6 300 單位產(chǎn)品利潤（元）10 6 4 （1）建立線性規(guī)劃模型，求該廠獲利最大的生產(chǎn)計劃。（2）產(chǎn)品丙每件的利潤增加到多大時才值得安排生產(chǎn)？如產(chǎn)品丙每件的利潤增加到 6，求最優(yōu)生產(chǎn)計劃。（3）產(chǎn)品甲的利潤在多大范圍內(nèi)變化時，原最優(yōu)計劃保持不變？（4）設(shè)備 A 的能力如為 100+10q，確定保持原最優(yōu)基不變的 q 的變化范圍。（5）如

15、合同規(guī)定該廠至少生產(chǎn)10 件產(chǎn)品丙，試確定最優(yōu)計劃的變化。解：（1）設(shè)x 1,x 2,x3分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量，建立線性規(guī)劃模型maxs.t. Z10 x 16 x24 x 3x1x2x310010 x 14x25x 36002x12x26x3300 x 1,x2,x30標(biāo)準(zhǔn)化得maxZ10 x 16x 24 x30 x 40 x 50 x 6s.t. x1x 23,x3x 410010 x 14x25 x3x56002x 12x26x3x 6300 x 1,x2,xx 4,x5,x60列出單純形表jcb10 /6 04 0 0 0 CBXB5xx 6i1xx 23xx 40 4x1

16、 1 1 1 0 0 100 100 0 5x600 10 4 5 0 1 0 60 0 6x300 2 2 6 0 0 1 150 j40 10 6 4 0 0 0 0 4x0 3/5 1/2 1 1/10 0 200/3 10 1x60 1 2/5 1/2 0 1/10 0 150 0 6x180 0 6/5 5 0 1/5 1 150 j200/3 0 2 1 0 1 0 6 2x0 1 5/6 5/3 1/6 0 10 1x100/3 1 0 1/6 2/3 1/6 0 0 6x100 0 0 4 2 0 1 j100/,30 0 8/3 10/3 2/3 0 故最優(yōu)解為x 1x 22

17、00,3x3，又由于x 1,x 2,x 3取整數(shù)，故四舍五入可得最優(yōu)解為x 133 ,x 267 ,x 30,Zmax732（2）產(chǎn)品丙的利潤c 變化的單純形法迭代表如下：0 0 jc10 6 c 30 CBXBb1xx23xx 45xx 6i1/6 0 6 2x200/3 0 1 5/6 5/3 10 1x100/3 1 0 1/6 2/3 1/6 0 0 6x100 0 0 4 2 0 1 j0 0 3c 20/3 10/3 2/3 0 626. 67故當(dāng)產(chǎn)品丙每要使原最優(yōu)計劃保持不變， 只要3c3200，即c333件的利潤增加到大于6.67 時，才值得安排生產(chǎn)。如產(chǎn)品丙每件的利潤增加到6

18、 時，此時 66.67，故原最優(yōu)計劃不變。（3）由最末單純形表計算出解得311c 10,4102c 10 ,511c 10，636解得61c15，即當(dāng)產(chǎn)品甲的利潤c 在,6 15 范圍內(nèi)變化時，原最優(yōu)計劃保持不變。5/31/60（4）由最末單純形表找出最優(yōu)基的逆為B12/31/60，新的最優(yōu)解為201X BB1b5/31/6010010q1320050q)02/31/6060010020q3201300( 10020q4q5，故要保持原最優(yōu)基不變的q 的變化范圍為45,（5）如合同規(guī)定該廠至少生產(chǎn)maxZ10 x 126x 24x 3x 1xx310010 件產(chǎn)品丙，則線性規(guī)劃模型變成10 x

19、 14x 25x3x 1600 x258 ,x 310 ,Z708s.t. 2x12x26x 3300 x31032 ,x1,x2,x30通過 LINGO 軟件計算得到：第 2 章 對偶規(guī)劃（復(fù)習(xí)思考題）1對偶問題和對偶向量（即影子價值）的經(jīng)濟(jì)意義是什么？答：原問題和對偶問題從不同的角度來分析同一個問題，前者從產(chǎn)品產(chǎn)量的角度來 考察利潤，后者則從形成產(chǎn)品本身所需要的各種資源的角度來考察利潤，即利潤是產(chǎn)品 生產(chǎn)帶來的，同時又是資源消耗帶來的。對偶變量的值 iy 表示第 i 種資源的邊際價值，稱為影子價值。可以把對偶問題的解Y 定義為每增加一個單位的資源引起的目標(biāo)函數(shù)值的增量。2什么是資源的影子價

20、格？它與相應(yīng)的市場價格有什么區(qū)別？答：若以產(chǎn)值為目標(biāo)，則iy 是增加單位資源 i 對產(chǎn)值的貢獻(xiàn)，稱為資源的影子價格（Shadow Price）。即有“ 影子價格 =資源成本 +影子利潤” 。因為它并不是資源的實際價 格，而是企業(yè)內(nèi)部資源的配比價格，是由企業(yè)內(nèi)部資源的配置狀況來決定的，并不是由 市場來決定，所以叫影子價格。可以將資源的市場價格與影子價格進(jìn)行比較，當(dāng)市場價 格小于影子價格時，企業(yè)可以購進(jìn)相應(yīng)資源，儲備或者投入生產(chǎn)；當(dāng)市場價格大于影子 價格時，企業(yè)可以考慮暫不購進(jìn)資源，減少不必要的損失。3如何根據(jù)原問題和對偶問題之間的對應(yīng)關(guān)系，找出兩個問題變量之間、解及檢 驗數(shù)之間的關(guān)系？則答：（1

21、）最優(yōu)性定理：設(shè)X ,Y分別為原問題和對偶問題的可行解，且CXbTY，X ,Y分別為各自的最優(yōu)解。（2）對偶性定理：若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，而且兩者的目 標(biāo)函數(shù)值相等。（3）互補(bǔ)松弛性：原問題和對偶問題的松弛變量為X 和Y ，它們的可行解X* ,Y*為最優(yōu)解的充分必要條件是Y*XS,0Y SX*0（4）對偶問題的最優(yōu)解對應(yīng)于原問題最優(yōu)單純形表中，初始基變量的檢驗數(shù)的負(fù)值。若Y 對應(yīng)于原問題決策變量x 的檢驗數(shù)，則Y 對應(yīng)于原問題松弛變量x 的檢驗數(shù)。4已知線性規(guī)劃問題maxZ4x 1x 22x 3s.t. 8x 13x2x 32（第一種資源）6x 1x2x38（第二種資源）x

22、 1,x2,x30（1）求出該問題產(chǎn)值最大的最優(yōu)解和最優(yōu)值。（2）求出該問題的對偶問題的最優(yōu)解和最優(yōu)值。（3）給出兩種資源的影子價格，并說明其經(jīng)濟(jì)含義；第一種資源限量由 2 變?yōu)?4，最優(yōu)解是否改變？（4）代加工產(chǎn)品丁，每單位產(chǎn)品需消耗第一種資源2 單位，消耗第二種資源3 單位，應(yīng)該如何定價？解：（1）標(biāo)準(zhǔn)化，并列出初始單純形表jc4 1 2 0 0 iCBXBbx 1x 2X*x 34xx 1x 50 ,x 32/8 ，1 1 0 0 4x2 8 3 0 5x8 6 1 1 0 1 8/6 j4 1 2 0 0 2 4 1x1/4 1 3/8 1/8 1/8 0 0 5x13/2 6 5/4

23、 1/4 3/4 1 26 j0 1/2 3/2 -1/2 0 22 3x2 8 3 1 1 0 0 5x6 2 2 0 1 1 j12 5 0 2 0 由最末單純性表可知， 該問題的最優(yōu)解為：( 0 0, , ,2 0 6, )T，即,0 x2最優(yōu)值為Z4（2）由原問題的最末單純形表可知，對偶問題的最優(yōu)解和最優(yōu)值為：y 12 ,y20 ,w4（3）兩種資源的影子價格分別為 由 2 變?yōu)?4，最優(yōu)解不會改變。2、0，表示對產(chǎn)值貢獻(xiàn)的大小；第一種資源限量（4）代加工產(chǎn)品丁的價格不低于 2 2 0 3 45某廠生產(chǎn) A，B，C，D4 種產(chǎn)品，有關(guān)資料如表 26 所示。表 26 資源消耗A 產(chǎn)品D

24、資源供應(yīng)量原料成本資源B C （公斤）（元/公斤）甲2 3 1 2 800 2.0 乙5 4 3 4 1200 1.0 丙3 4 5 3 1000 1.5 單位產(chǎn)品售價（元）14.5 21 15.5 16.5 （1）請構(gòu)造使該廠獲利潤最大的線性規(guī)劃模型，并用單純形法求解該問題（不計加工成本）。（2）該廠若出租資源給另一個工廠，構(gòu)成原問題的對偶問題，列出對偶問題的數(shù)學(xué)模型，資源甲、乙、丙的影子價格是多少？若工廠可在市場上買到原料丙，工廠是否應(yīng)該購進(jìn)該原料以擴(kuò)大生產(chǎn)？（3）原料丙可利用量在多大范圍內(nèi)變化，原最優(yōu)生產(chǎn)方案中生產(chǎn)產(chǎn)品的品種不變（即最優(yōu)基不變）？（4）若產(chǎn)品 B 的價格下降了 0.5 元

25、，生產(chǎn)計劃是否需要調(diào)整？解：（1）設(shè)x 1,x2,x3,x 4分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量，建立線性規(guī)劃模型maxs.t. Zx 15 x23x 34 x42x13x2x32x48005x 14x23x34x412003x 14x25x33x41000 xi0 ,i,123, ,4初始單純形表CBjcb1 5 3 4 0 0 0 iXBx 12xx 3x 45xx 67x0 x 52 3 1 2 1 0 0 800/3 800 x60 1200 5 4 3 4 0 1 0 1200/4 0 x71000 3 4 5 3 0 0 1 1000/4 j1 5 3 4 0 0 0 最末單純形表jc

26、1 5 3 4 0 0 0 iCBXBb*x 1x23xx 4Z5xx 6x 70 1/4 0-13/4 0 1 1/4 -1 x 5100 4 x 4200 2 0 - 2 1 0 1 -1 5 x 2100 -3/4 1 11/4 0 0 -3/4 1 j-13/4 0 -11/4 0 0 -1/4 -1 解得最優(yōu)解為：X(,0 100 0, , 200 , 100 )T，最優(yōu)值1300（2）原問題的對偶問題的數(shù)學(xué)模型為min w 800 y 1 1200 y 2 1000 y 32 y 1 5 y 2 3 y 3 13 y 1 4 y 2 4 y 3 5s.t. y 1 3 y 2 5

27、y 3 12 y 1 4 y 2 3 y 3 4y 1 , y 2 , y 3 0解得影子價格分別為 2、1.25、2.5。對比市場價格和影子價格，當(dāng)市場價低于影子價格時購進(jìn)。（3）原料丙可利用量在 900,1100范圍內(nèi)變化，原最優(yōu)生產(chǎn)方案中生產(chǎn)產(chǎn)品的品種不變（即最優(yōu)基不變） 。（4）若產(chǎn)品 B 的價格下降了 0.5 元，生產(chǎn)計劃不需要調(diào)整。6某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，產(chǎn)品生產(chǎn)的工藝路線如圖 21 所示，試統(tǒng)計單位產(chǎn)品的設(shè)備工時消耗，填入表27。又已知材料、設(shè)備C 和設(shè)備 D 等資源的單位成本和擁有量如表 27 所示。表 27 資源消耗與資源成本表產(chǎn)品資源消耗資源成本資源擁有量資源甲乙元/單

28、位資源4200 材料（公斤）60 50 200 設(shè)備 C（小時）30 40 10 3000 設(shè)備 D（小時）60 50 20 4500 據(jù)市場分析，甲、乙產(chǎn)品銷售價格分別為 產(chǎn)品生產(chǎn)計劃。13700 元和 11640元，試確定獲利最大的（1）設(shè)產(chǎn)品甲的計劃生產(chǎn)量為 1x ，產(chǎn)品乙的計劃生產(chǎn)量為 x ，試建立其線性規(guī)劃的數(shù)學(xué)模型；若將材料約束加上松弛變量 x ，設(shè)備 C 約束加上松弛變量 x ，設(shè)備 D 約束加上松弛變量 5x ，試化成標(biāo)準(zhǔn)型。（2）利用 LINDO 軟件求得：最優(yōu)目標(biāo)函數(shù)值為18400，變量的最優(yōu)取值分別為x 120 ,x 260 ,x 3,0 x40 ,x 5300，則產(chǎn)品的

29、最優(yōu)生產(chǎn)計劃方案是什么？并解釋x 30 ,x 4,0 x 5300的經(jīng)濟(jì)意義。（3）利用 LINDO 軟件對價值系數(shù)進(jìn)行敏感性分析，結(jié)果如下：Obj Coefficient Ranges Variable Current Coef Allowable Increase Allowable Decrease 1x200 88 20 2x240 26.67 73.33 試問如果生產(chǎn)計劃執(zhí)行過程中，甲產(chǎn)品售價上升到 60 元，所制定的生產(chǎn)計劃是否需要進(jìn)行調(diào)整？13800元，或者乙產(chǎn)品售價降低（4）利用 LINDO 軟件對資源向量進(jìn)行敏感性分析，結(jié)果如下：Right hand Side Ranges

30、Resource Current Rhs Allowable Increase Allowable Decrease 材料4200 300 450 設(shè)備 C 3000 360 900 4500 Infinity 300 設(shè)備 D 試問非緊缺資源最多可以減少到多少，而緊缺資源最多可以增加到多少？解：（1）建立的線性規(guī)劃模型為maxZ200 x 12240 x260 x 150 x4200s.t. 30 x140 x2300060 x 150 x24500 x 1,x20將其標(biāo)準(zhǔn)化maxZ200 x 1240 x2420060 x 150 x2x3s.t. 30 x140 x2x4300060 x

31、 150 x2x54500 x i0,i,1,25,（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ī)劃問題。若相應(yīng)的線性 規(guī)劃問題沒有可行解，停止計算，這時原整數(shù)規(guī)

32、劃也沒有可行解。（2）定界過程。對于極大化的整數(shù)規(guī)劃問題，當(dāng)前所有未分枝子問題中最大的目 標(biāo)函數(shù)值為整數(shù)規(guī)劃問題上界；在滿足整數(shù)約束的子問題的解中，最大的目標(biāo)函數(shù)值為整數(shù)規(guī)劃問題的下界。當(dāng)上下界相同時，則已得最優(yōu)解；否則，轉(zhuǎn)入剪枝過程。（3）剪枝過程。在下述情況下剪除這些分枝：若某一子問題相應(yīng)的線性規(guī)劃問 題無可行解； 在分枝過程中， 求解某一線性規(guī)劃所得到的目標(biāo)函數(shù)值 Z 不優(yōu)于現(xiàn)有下 界。（4）分枝過程。當(dāng)有多個待求分枝時，應(yīng)先選取目標(biāo)函數(shù)值最優(yōu)的分枝繼續(xù)進(jìn)行分枝。選取一個不符合整數(shù)條件的變量 ix 作為分枝變量，若 ix 的值是 ib ，構(gòu)造兩個新的 *約束條件：x i b * 或 x

33、i b i * 1，分別并入相應(yīng)的數(shù)學(xué)模型中，構(gòu)成兩個子問題。對任一個子問題，轉(zhuǎn)步驟（1）3試用分枝定界法求如下線性規(guī)劃：maxZ40 x 190 x 29x 17x256s.t.7x 120 x270 x 1,x20 x1,x2取整數(shù)解：最優(yōu)整數(shù)解為：x 1,4x 22 ,Z3404有 4 名職工，由于各人的能力不同，每個人做各項工作所用的時間不同，所花費時間如表 37 所示。表 37（單位：分鐘）時 間甲任 務(wù)A B C D 人員15 18 21 24 乙19 23 22 18 丙26 17 16 19 丁19 21 23 17 問指派哪個人去完成哪項工作，可使總的消耗時間最少？解：設(shè)xi

34、j1，任務(wù)i由人員j完成，ijt 為個人 i 對于任務(wù) j 的時間耗費矩陣，則0，任務(wù)i不由人員j完成建立整數(shù)規(guī)劃模型為：minZi4j41x ijtij14解得：x 12,1x 21,1s.t.xij1Z70，即任務(wù) A 由乙完成，任i1 4xij1x 33j1xij0 或,1i,j,12 ,3 ,4,1x441，其余均為零，務(wù) B 由甲完成，任務(wù) C 由丙完成，任務(wù) D 由丁完成。5某部門一周中每天需要不同數(shù)目的雇員：周一到周四每天至少需要 50 人，周五至少需要 80 人，周六周日每天至少需要 90 人，先規(guī)定應(yīng)聘者需連續(xù)工作 5 天，試確定聘用方案，即周一到周日每天聘用多少人，使在滿足

35、需要的條件下聘用總?cè)藬?shù)最少。解：設(shè) ix 表示在第 i 天應(yīng)聘的雇員人數(shù)（ i=1,2,3,4,5,6,7）。數(shù)學(xué)模型為minZx 1x2x 3x4x 5x 6x 7Z94x 1x 4x5x 6x 750 x 1x 2x5x 6x 750 x 1x 2x3x 6x 750 x 1x 2x3x 4x 750s.t.x 1x 2x 3x 4x580 x 2x 3x4x 5x 690 x 3x 4x 5x 6x 790 x i,0i,1 ,2, 7xi取整數(shù),i2,1 ,7,解得：x 10 ,x 24 ,x332 ,x 410 ,x 534 ,x 610 ,x 74 ,第 4 章目標(biāo)規(guī)劃（復(fù)習(xí)思考題

36、）1某計算機(jī)公司生產(chǎn) A，B，C 三種型號的筆記本電腦。這三種筆記本電腦需要在復(fù)雜的裝配線上生產(chǎn)，生產(chǎn)一臺 A，B，C 型號的筆記本電腦分別需要 5 小時、 8 小時、12 小時。公司裝配線正常的生產(chǎn)時間是每月 1700 小時，公司營業(yè)部門估計 A，B，C三種筆記本電腦每臺的利潤分別是1000 元、1440 元、2520 元，而且公司預(yù)測這個月生產(chǎn)的筆記本電腦能夠全部售出。公司經(jīng)理考慮以下目標(biāo)：第一目標(biāo)：充分利用正常的生產(chǎn)能力，避免開工不足；第二目標(biāo)：優(yōu)先滿足老客服的需求，A，B，C 三種型號的電腦各為50 臺、 50 臺、80 臺，同時根據(jù)三種電腦三種電腦的純利潤分配不同的加權(quán)系數(shù)；第三目標(biāo)

37、：限制裝配線加班時間，最好不超過200 小時；100 臺、 120第四目標(biāo)：滿足各種型號電腦的銷售目標(biāo)，A，B，C 三種型號分別為臺、 100 臺，再根據(jù)三種電腦的純利潤分配不同的加權(quán)系數(shù)；第五目標(biāo)：裝配線加班時間盡可能少。請列出相應(yīng)的目標(biāo)規(guī)劃模型，并用 解：建立目標(biāo)約束。（1）裝配線正常生產(chǎn)LINGO 軟件求解。設(shè)生產(chǎn) A，B，C 型號的電腦為x 1,x 2,x 3（臺），d 為裝配線正常生產(chǎn)時間未利用數(shù)，d 為裝配線加班時間，希望裝配線正常生產(chǎn)，避免開工不足，因此裝配線目標(biāo)約束為mind112 x3d1d 117005 x 18 x 2（2）銷售目標(biāo)優(yōu)先滿足老客戶的需求，并根據(jù)三種電腦的純

38、利潤分配不同的權(quán)因子，A，B，C三種型號的電腦每小時的利潤是 1000, 1440, 2520，因此，老客戶的銷售目標(biāo)約束為5 8 12min 20 d 2 18 d 3 21 d 4 x 1 d 2 d 2 50 x 2 d 3 d 3 50 x 3 d 4 d 4 80再考慮一般銷售。類似上面的討論，得到min20 d518 d621 d7x 1d5d5100 x 2d6d6120 x 3d 7d7100（3）加班限制首先是限制裝配線加班時間，不允許超過mind8200 小時，因此得到5 x 18 x 212 x3d8d81900其次裝配線的加班時間盡可能少，即mind112 x3d1d

39、117005 x 18 x 2寫出目標(biāo)規(guī)劃的數(shù)學(xué)模型min G P 1 d 1 P 2 ( 20 d 2 18 d 3 21 d 4 ) P 3 d 8 P 4 ( 20 d 5 18 d 6 21 d 7 ) P 5 d 15 x 1 8 x 2 12 x 3 d 1 d 1 1700 x 1 d 2 d 2 50 x 2 d 3 d 3 50 x 3 d 4 d 4 80 x 1 d 5 d 5 100s.t.x 2 d 6 d 6 120 x 3 d 7 d 7 1005 x 1 8 x 2 12 x 3 d 1 d 1 1900 x i ,0 i ,1 2d l , d l 0 , l

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

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