《管理運籌學(xué)》(第二版)課后習(xí)題參考答案.精心總結(jié)

1、管理運籌學(xué)(第二版)課后習(xí)題參考答案第1章 線性規(guī)劃(復(fù)習(xí)思考題)1. 什么是線性規(guī)劃？線性規(guī)劃的三要素是什么?答：線性規(guī)劃(Lin ear P rogrammi ng, 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ù)項bi>0， 決策變量滿足非負(fù)性。如果加入的這個非負(fù)變量取值為非零的話，則說明該約束限定沒有約束力，對企業(yè)“拠約束來說不是緊缺資源，所以稱為松弛變量；剩余變量取值為非零的話，則說

3、明 的左邊取值大于右邊規(guī)劃值，出現(xiàn)剩余量。4試述線性規(guī)劃問題的可行解、基礎(chǔ)解、基可行解、最優(yōu)解的概念及其相互關(guān)系。稱為可行解。答：可行解：滿足約束條件 AX =b, X >0的解, 基可行解：滿足非負(fù)性約束的基解，稱為基可行解?？尚谢鶎?yīng)于基可行解的基，稱為可行基。使目標(biāo)函數(shù)最優(yōu)的可行解，稱為最優(yōu)解。最優(yōu)基：最優(yōu)解對應(yīng)的基矩陣，稱為最優(yōu)基。 它們的相互關(guān)系如右圖所示：基可行解生活不會辜負(fù)努力的人5用表格單純形法求解如下線性規(guī)劃。maxZ =4xi +X2 +2x38x4 +3x2 +X3 <2StV6為 +X2 + X3 <8Xi, X2 , X3 > 0解：標(biāo)準(zhǔn)化ma

4、XZ =4x4 +X2 +2x38xi +3x2 + X3 +X4=2s.t. / 6xi +X2 + X3+ X5 = 8iXi,X2,X3,X4,X5 >0列出單純形表Cj41200CbXbbX1X2X3X4X50X42831102/80X58611018/6bj412004X11/413/81/81/80(1/4)/(1/8)0X513/265/41/43/41(13/2)/(1/4)bj01/23/2-1/202X32831100X56-22011Dj125020故最優(yōu)解為 X* =（O,O2O,6）T，即 X=O,X2 =0,X3 =2，此時最優(yōu)值為 Z（X*） =4 .6.表

5、1 15中給出了求極大化冋題的單純形表，冋表中ai, a2 ,Ci,C2,d為何值及變量屬于哪一類型時有：（1）表中解為唯一最優(yōu)解；（2）表中解為無窮多最優(yōu)解之一；（3）下一步迭代將以Xi代替基變量X5 ；（ 4）該線性規(guī)劃問題具有無界解；（5）該線性規(guī)劃問題無可行解。生活不會辜負(fù)努力的人表1 15某極大化冋題的單純形表CjC1C2000CbXbbX1X2X3X4X50X3d4a11000X42-1-50100X53a2-3001bjC1C2000解：(1) d >0,& v0,C2 c 0 ;(2)d >0,c, <0,C2 <0 ( Ci,C2中至少有一個為

6、零)(3)C0,a0,d > 4a?生活不會辜負(fù)努力的人C2 > 0, aj < 0 ;(5)xi為人工變量，且Ci為包含M的大于零的數(shù), > ;或者X2為人工變量,4 a?且C2為包含M的大于零的數(shù)，ai A 0, d > 0 .7用大M法求解如下線性規(guī)劃。maxZ =5x1 +3x2 +6x3Xj +2x2 +x3 乞 182X1 +X2 + 3X3 <16 s.t. Xj +X2 +X3 =10X1, X2, X3 >0解：加入人工變量，進(jìn)行人造基后的數(shù)學(xué)模型如下:max Z =5x4 +3x2 +6x3 +0x4 +0x5 -Mx6+ 3X3

7、+X5 =16+ X3 + X6 =10(i =1,2,6)s.t.產(chǎn)IX1L Xi為 + 2x2 + X3 + x4 = 18 + X2+ X2>0列出單純形表Cj53600MeiCBXbbX1X2X3X4X5X62 i0X41812110018/10X51621301016/3MX61011100110/1bj5+M3+M6+M0000X438/31/35/3011/3038/56X316/32/31/3101/3016MX614/31/32/3001/3114/2J11 +-M31 +-M3001-2M300X411/20011/25/26X331/20101/21/263X271

8、/21001/23/214J1/20003/2-M20X440011135X161020113X24011012001 0-21 MZ(X*) =42 .I，II兩個電1 16所示。故最優(yōu)解為X* =(6,4,O4O,O)T，即X1 =6,X2 =4,X3 =0，此時最優(yōu)值為8. A，B，C三個城市每年需分別供應(yīng)電力 320, 250和350單位，由 站提供，它們的最大可供電量分別為 400單位和450單位，單位費用如表由于需要量大于可供量，決定城市 A的供應(yīng)量可減少030單位，城市B的供應(yīng)量不變，城市C的供應(yīng)量不能少于270單位。試建立線性規(guī)劃模型，求將可供電量用完的最低總費用分配方案。表1

9、 16單位電力輸電費(單位：元)ABCI151822II212516解：設(shè)Xj為“第i電站向第j城市分配的電量” (i=1,2; j=1,2,3),建立模型如下:max Z =15x11 +18x12 +22x13 +21x21 +25x22 +16x23X11+ X21>290X11+ X21<320X12+ X22= 250X13+ X23>270X13+ X23<350>0,i =1,2; j =1s.t. «Xij+ x12 +為3 =400X21 +X22 +X23 = 4509 某公司在3年的計劃期內(nèi)，有4個建設(shè)項目可以投資：項目I從第一年到

10、第三 年年初都可以投資。預(yù)計每年年初投資，年末可收回本利120%，每年又可以重新將所獲本利納入投資計劃；項目II需要在第一年初投資，經(jīng)過兩年可收回本利150%，又可以重新將所獲本利納入投資計劃，但用于該項目的最大投資不得超過20萬元；項目III需要在第二年年初投資，經(jīng)過兩年可收回本利160%，但用于該項目的最大投資不得超過15萬元；項目IV需要在第三年年初投資，年末可收回本利 140%，但用于該項目的 最大投資不得超過10萬元。在這個計劃期內(nèi)，該公司第一年可供投資的資金有 30萬元。 問怎樣的投資方案，才能使該公司在這個計劃期獲得最大利潤？解：設(shè)xi(1)表示第一次投資項目i，設(shè)xi(2)表示

11、第二次投資項目i，設(shè)xi表示第三次 投資項目i, (i=1,2,3,4),則建立的線性規(guī)劃模型為max1.2x1(31.6x31) +1.4x41)s.t. *X1(1) + xJ < 30x1(2x31) <1.2x1(1) +30 - xJ -x2x+x；1) =1.2X1 +1.5x211.2x1(130-xV 蘭 20xJ 蘭 15xf 蘭 10Xi,Xi(2),Xi >0,i =123,4(1)X1X21)-xf-xj通過 LINGO 軟件計算得：X-exj =20,x31) =0,X1=12,X1 =4410. 某家具制造廠生產(chǎn)五種不同規(guī)格的家具。每種家具都要經(jīng)過

12、機械成型、打磨、上漆幾道重要工序。每種家具的每道工序所用的時間、每道工序的可用時間、每種家具 的利潤由表1 17給出。問工廠應(yīng)如何安排生產(chǎn)，使總利潤最大?表1 17家具生產(chǎn)工藝耗時和利潤表生產(chǎn)工序所需時間（小時）每道工序可用 時間（小時）12345成型346233600打磨435643950上漆233432800利潤（百元）2.734.52.53解：設(shè)Xi表示第i種規(guī)格的家具的生產(chǎn)量（i=1,2,5）,則maxZ =2.7捲 +3x2 +4.5x3 +2.5x4 +3x5pXj +4X2 + 6x3 +2x4 +3x5 <3600 4% +3X2 +5X3 +6X4 +4X5 <3

13、950 s.t.|2x1 +3x2 +3x3 +4x4 +3x5 <2800I Xi 二 0，i =建立線性規(guī)劃模型，求該廠獲利最大的生產(chǎn)計劃。 產(chǎn)品丙每件的利潤增加到多大時才值得安排生產(chǎn)？如產(chǎn)品丙每件的利潤增加 到6,求最優(yōu)生產(chǎn)計劃。 產(chǎn)品甲的利潤在多大范圍內(nèi)變化時，原最優(yōu)計劃保持不變？ 設(shè)備A的能力如為100+10q，確定保持原最優(yōu)基不變的q的變化范圍。（5）如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品丙，試確定最優(yōu)計劃的變化。生活不會辜負(fù)努力的人,2,，5通過 LINGO 軟件計算得：X1 =0,X2 =38,x3 =254, X4 =0,X5 =642,Z =3181.11. 某廠生產(chǎn)甲、乙

14、、丙三種產(chǎn)品，分別經(jīng)過A，B，C三種設(shè)備加工。已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時數(shù)、設(shè)備的現(xiàn)有加工能力及每件產(chǎn)品的利潤如表210所示。表1 18產(chǎn)品生產(chǎn)工藝消耗系數(shù)甲乙丙設(shè)備能力A （小時）111100B （小時）1045600C （小時）226300單位產(chǎn)品利潤（元）1064解：（1）設(shè)X1,X2,X3分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量，建立線性規(guī)劃模型max Z =10x4 +6X2 +4x3 Xj +X2 +X3 <10010x1 +4X2 +5X3 <600 s.t.I ZXr +2X2 +6X3 <300 X1,X2,X3 >0標(biāo)準(zhǔn)化得max Z = 10xi +6x

15、2 +4x3 + 0x4 +0x5 +0x6Xj +X2 +X3 +X4 =10010x1 + 4x2 + 5x3 + Xs = 600 s.t. «2X4 +2X2 +6X3 +X6 =300X1,X2,X3,X4,X5,X6 > 0列出單純形表Cj1064000CBXbbX1X2X3X4XsX60X41001111001000X56001045010600X6300226001150bj10640000X44003/51/211/100200/310X16012/51/201/1001500X618006/5501/51150J02-10106X2200/3015/65/3

16、1/6010X1100/3101/62/31/600X6100004201bj008/310/32/30故最優(yōu)解為xi T00/3, X2 =200/3, X3 =0，又由于x1, x2, x3取整數(shù)，故四舍五入可得最優(yōu)解為 X1 33, x 67, x 0 , Z mg 732 .(2)產(chǎn)品丙的利潤C3變化的單純形法迭代表如下:Cj106C30000iCBXbbX1X2X3X4X5X66X2200/3015/65/31/6010X1100/3101/62/31/600X6100004201bj00C3 20/310/32/30202要使原最優(yōu)計劃保持不變，只要b3=C3-<0，即c 6

17、- 6.67 .故當(dāng)產(chǎn)品丙每33件的利潤增加到大于6.67時，才值得安排生產(chǎn)。如產(chǎn)品丙每件的利潤增加到6時，此時6V6.67，故原最優(yōu)計劃不變。(3)由最末單純形表計算出cr3 = -1 -G <0,5 = -10+ 蘭0Q5 =1<0，原最優(yōu)計劃保持不變。636解得6<ci <15，即當(dāng)產(chǎn)品甲的利潤Ci在6,15范圍內(nèi)變化時,(4)由最末單純形表找出最優(yōu)基的逆為5/3-2/3.一2-1/61/600"0 ，新的最優(yōu)解為b5/3-2/3.一2-1/61/600"01丿q00+10q'600、-300 丿h 200 +50q '100

18、-20q0(100 -20q)>0解得-4 <q <5，故要保持原最優(yōu)基不變的q的變化范圍為-4,5.(5)如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品丙，則線性規(guī)劃模型變成maxZ =10捲 +6x2 +4x3為 +X2 + X3 蘭 10010% +4X2 +5x3 <600 s.t. < 2x1 +2x2 + 6X3 蘭300 x3 >10I X1,X2,x0通過 LINGO 軟件計算得到：X1 =32,x2 =58,x3 =10,Z =708第2章 對偶規(guī)劃(復(fù)習(xí)思考題)1對偶問題和對偶向量(即影子價值)的經(jīng)濟(jì)意義是什么?答：原問題和對偶問題從不同的角度來分析同

19、一個問題，前者從產(chǎn)品產(chǎn)量的角度來考察利潤，后者則從形成產(chǎn)品本身所需要的各種資源的角度來考察利潤，即利潤是產(chǎn)品 生產(chǎn)帶來的，同時又是資源消耗帶來的。對偶變量的值yi表示第i種資源的邊際價值，稱為影子價值。可以把對偶問題的解Y定義為每增加一個單位的資源引起的目標(biāo)函數(shù)值的增量。2.什么是資源的影子價格？它與相應(yīng)的市場價格有什么區(qū)別?答：若以產(chǎn)值為目標(biāo)，則yi是增加單位資源i對產(chǎn)值的貢獻(xiàn)，稱為資源的影子價格(Shadow Price)。即有“影子價格=資源成本+影子利潤”。因為它并不是資源的實際價格，而是企業(yè)內(nèi)部資源的配比價格，是由企業(yè)內(nèi)部資源的配置狀況來決定的，并不是由 市場來決定，所以叫影子價格。

20、可以將資源的市場價格與影子價格進(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)最優(yōu)性定理：設(shè)X,Y分別為原問題和對偶問題的可行解，且 cX=bTY, 則X,Y分別為各自的最優(yōu)解。(2) 對偶性定理：若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，而且兩者的目 標(biāo)函數(shù)值相等。(3) 互補松弛性：原問題和對偶問題的松弛變量為Xs和Ys,它們的可行解X ,Y 為最優(yōu)解的充分必要條件是Y*Xs =0,YsX* =

21、0 (4)對偶問題的最優(yōu)解對應(yīng)于原問題最優(yōu)單純形表中，初始基變量的檢驗數(shù)的負(fù)值。若-Ys對應(yīng)于原問題決策變量x的檢驗數(shù)，則-Y對應(yīng)于原問題松弛變量Xs的檢驗生活不會辜負(fù)努力的人數(shù)。4 已知線性規(guī)劃問題maxZ = 4xi + X2 +2x3s.t.8x1 +3x2 +X3 <2 (第一種資源) 6x1 +X2 +X3 <8 (第二種資源) X1,X2,X3 >0求出該問題產(chǎn)值最大的最優(yōu)解和最優(yōu)值。(2)求出該問題的對偶問題的最優(yōu)解和最優(yōu)值。(3)給出兩種資源的影子價格，并說明其經(jīng)濟(jì)含義；第一種資源限量由2變?yōu)?,最優(yōu)解是否改變?(4) 代加工產(chǎn)品丁，每單位產(chǎn)品需消耗第一種資源

22、2單位，消耗第二種資源3單位，應(yīng)該如何定價?解：(1)標(biāo)準(zhǔn)化，并列出初始單純形表Cj41200QCbXbbX1X2X3X4X5"i0X42831102/80X58611018/6J412004X11/413/81/81/8020X513/265/41/43/412601/23/2-1/202X32831100X56-22011bj125020由最末單純性表可知，該問題的最優(yōu)解為：X* =(O,O2O,6)T，即Xj =0,X2=0,X3 =2，生活不會辜負(fù)努力的人最優(yōu)值為Z =4 (2) 由原問題的最末單純形表可知，對偶問題的最優(yōu)解和最優(yōu)值為:yi =2,y2 =0,w = 4 .(

23、3) 兩種資源的影子價格分別為2、0,表示對產(chǎn)值貢獻(xiàn)的大?。坏谝环N資源限量由2變?yōu)?,最優(yōu)解不會改變。(4) 代加工產(chǎn)品丁的價格不低于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)品售價(元)14.52115.516.5(1)請構(gòu)造使該廠獲利潤最大的線性規(guī)劃模型，并用單純形法求解該問題(不計加工成本)。(2) 該廠若出租資源給另一個工廠，構(gòu)成原問題的對偶問題，列出對偶問題的數(shù)學(xué)模型，資源甲、乙、丙的影子價格是多

24、少？若工廠可在市場上買到原料丙，工廠是否應(yīng)該購進(jìn)該原料以擴大生產(chǎn)?(3) 原料丙可利用量在多大范圍內(nèi)變化，原最優(yōu)生產(chǎn)方案中生產(chǎn)產(chǎn)品的品種不變(即最優(yōu)基不變)？(4) 若產(chǎn)品B的價格下降了 0.5元，生產(chǎn)計劃是否需要調(diào)整?解：(1)設(shè)Xi,X2,X3,X4分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量，建立線性規(guī)劃模型max Z = x1 中 5x2 + 3x3 + 4x42x4 +3x2 +X3 +2X4 <8005為 + 4x2 + 3x3 + 4x4 < 1200 s.t. «3% + 4X2 + 5X3 + 3X4 <1000Xi >0,i =123,4初始單純形表Cj

25、1534000CBXbbX1X2X3X4X5X6X70X58002312100800/30X6120054340101200/40X7100034530011000/4bj1534000最末單純形表Cj1534000aCBXbbX1X2X3X4X5X6X760X51001/40-13/4011/4-14X420020-2101-15X2100-3/4111/400-3/41J-13/40-11/400-1/4-1解得最優(yōu)解為：X* =(0,100,0,200,100)T，最優(yōu)值 Z =1300 .(2) 原問題的對偶問題的數(shù)學(xué)模型為mi M=80(yi +120 02 +100 032y5y3

26、y1 3y4y4y5 s.t. « yr3y5y12y1 +4y2 訕3 >4.y1, y2, y 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)的工藝路線如圖2 1所示，試統(tǒng)計單位產(chǎn)品的設(shè)備工時消耗，填入表 2 7。又已知材料、設(shè)備C和設(shè)備D等資源的單位成本和擁有量如表27所示。表27資源消耗與資源成本表產(chǎn)品資源資源消耗資源成本資源

27、擁有量甲乙元/單位資源材料(公斤)60502004200設(shè)備C (小時)3040103000設(shè)備D (小時)6050204500據(jù)市場分析，甲、乙產(chǎn)品銷售價格分別為13700元和11640元，試確定獲利最大的產(chǎn)品生產(chǎn)計劃。(1) 設(shè)產(chǎn)品甲的計劃生產(chǎn)量為xi，產(chǎn)品乙的計劃生產(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)取值分別為X1 =20,X2 =60,X3 =0,X4 =0,X5 =300，則產(chǎn)品的最優(yōu)生產(chǎn)計劃方案是什么？并

28、解釋X3 =0,X4 =0, X5 =300 的經(jīng)濟(jì)意乂。(3) 利用LINDO軟件對價值系數(shù)進(jìn)行敏感性分析，結(jié)果如下:Obj Coefficie nt Ran gesVariableCurre nt CoefAllowable In creaseAllowable DecreaseX12008820X224026.6773.33試問如果生產(chǎn)計劃執(zhí)行過程中，甲產(chǎn)品售價上升到13800元，或者乙產(chǎn)品售價降低 60元，所制定的生產(chǎn)計劃是否需要進(jìn)行調(diào)整?(4) 利用LINDO軟件對資源向量進(jìn)行敏感性分析，結(jié)果如下:Right hand Side Ran gesResourceCurre nt Rhs

29、Allowable In creaseAllowable Decrease材料4200300450設(shè)備C3000360900設(shè)備D4500Infinity300試問非緊缺資源最多可以減少到多少，而緊缺資源最多可以增加到多少?解：(1)建立的線性規(guī)劃模型為max Z =200x1 +240x260X4 +50x2 <420030兀 +40x2 <3000 s.t. 60x<H 50x2 < 4500x1 ,X2 3 0將其標(biāo)準(zhǔn)化max Z =200xi +240x260x1 +50X2 +X3 =420030x1 +40x2 +X4 =3000s.t. <160X1

30、 +50X2 +X5 =4500x 二0,i =1,2,5(2)甲生產(chǎn)20件，乙生產(chǎn)60件，材料和設(shè)備C充分利用，設(shè)備D剩余600單位。(3)甲上升到13800需要調(diào)整，乙下降60不用調(diào)整。生活不會辜負(fù)努力的人(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ī)劃也沒有可行解。(2)

31、定界過程。對于極大化的整數(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ù)條件的變量 Xi作為分枝變量，若Xi的值是bi*，構(gòu)造兩個新的 約束條件：Xi <bi*或Xi >b； +1，分別并入相

32、應(yīng)的數(shù)學(xué)模型中，構(gòu)成兩個子問題。對 任一個子問題，轉(zhuǎn)步驟(1).3試用分枝定界法求如下線性規(guī)劃:x251J1 1SL1S19捲 ±7x疣WM0X70、沁max = 40x1 +J90131F界:07X1女冷2二0gXI = 5. J2 = 1.74礙377上界i 349 卜界：d屛最優(yōu)整數(shù)解為：Xj =4, X2 =2,Z =340 .4.有4名職工，由于各人的能力不同，每個人做各項工作所用的時間不同，所花費時間如表37所示。、時間任務(wù)人員'ABCD甲15182124乙19232218丙26171619丁19212317表37 （單位：分鐘）問指派哪個人去完成哪項工作，可使總

33、的消耗時間最少?解：設(shè)Xiji0，任二不人人元完成7為個人i對于任務(wù)j的時間耗費矩陣，則建立整數(shù)規(guī)劃模型為:44min Z = S 送 xij tijirn jT4£ Xjj 二1i =14s.t.Z： Xij =1uXij =0或 1,i,j =1,234解得：Xi2 =1,X211, X33 =1,X44 =1，其余均為零，Z = 70，即任務(wù)A由乙元成，任務(wù)B由甲完成，任務(wù)C由丙完成，任務(wù)D由丁完成。5某部門一周中每天需要不同數(shù)目的雇員：周一到周四每天至少需要50人，周五至少需要80人，周六周日每天至少需要90人，先規(guī)定應(yīng)聘者需連續(xù)工作 5天，試確定聘用方案，即周一到周日每天聘

34、用多少人，使在滿足需要的條件下聘用總?cè)藬?shù)最少。解：設(shè)Xi表示在第i天應(yīng)聘的雇員人數(shù)(i=1,2,3,4,5,6,7)。數(shù)學(xué)模型為min Z =Xi +X2 +X3 +X4 + X5 + X6 +X7X1+ X4+ X5+ X6+ X7>50X1+ X2+ X5+ X6+ X7>50X1+ X2+ X3+ X6+ X7>50X1+ X2+ X3+ X4+ X7>50X1+ X2+ X3+ X4+ X5>80X2+ X3+ X4+ X5+ X6>90X3+ X4+ X5+ X6+ X7>90Xi>0,i= 1,2,7s.t. *Xi取整數(shù)，i =1,

35、2,7解得：x1 = 0, X2 = 4, X3 = 32, X4 = 10, X5 = 34, Xq = 10, X7 = 4, Z = 94 .第4章 目標(biāo)規(guī)劃(復(fù)習(xí)思考題)1.某計算機公司生產(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)能力，避免開工不足;

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

37、此裝配線目標(biāo)約束為min di 5X, +8X2 +12X3 +!-*+ = 1700(2)銷售目標(biāo)優(yōu)先滿足老客戶的需求，并根據(jù)三種電腦的純利潤分配不同的權(quán)因子， 三種型號的電腦每小時的利潤是罟，譽詈，因此，老客戶的銷售目標(biāo)約束為min 20d廠+ 18d3 + 21d4Xdr-d = 50X2 +d3-d3+ =50X3 +d廠-d4+ = 80再考慮一般銷售。類似上面的討論，得到min 20d + 18d + 21d7Xdr-d = 120X3 +d7-d?十= 100(3)加班限制首先是限制裝配線加班時間，不允許超過200小時，因此得到5旨 +8X2 +12x3+d8-d8+ = 190

38、0其次裝配線的加班時間盡可能少，即min d/ 5x1 +8X2 +12x3 +!-*+ = 1700寫出目標(biāo)規(guī)劃的數(shù)學(xué)模型min G =Rd1+ F2（20d廠+ 18d3 + 21d4J + P3d/+F4（20d+ 18d+ 21dT） + RdJs.t.5x1 +8X2 + 12x3+ = 1700+ dr-d =50+ dr-d=50+d4-dj = 80+ dr-d/ = 100+ dr-d=120+df-d/ = 100XiX2X3XiX2X35x8x2 +12x3 +d廠-*中=1900Xj >0,i =1,2 dr,d/>0,l =1,2,8經(jīng)過LINGO軟件計算

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

40、需求量必須全部滿足;表43工廠產(chǎn)量一用戶需求量及運費單價（單位：元）第二目標(biāo)第三目標(biāo)供應(yīng)用戶1的產(chǎn)品中，工廠3的產(chǎn)品不少于100個單位; 每個用戶的滿足率不低于 80%;第四目標(biāo)應(yīng)盡量滿足各用戶的需求;第五目標(biāo)第六目標(biāo)新方案的總運費不超過原運輸問題 （線性規(guī)劃模型）的調(diào)度方案的10%;因道路限制，工廠 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元，運輸方案如下表所示。1234/ f * -、廠.生產(chǎn)量1100200300220020032501504004100100需求量(單位)200i00450250(2)下面按照目標(biāo)的重要性的等級列出目標(biāo)規(guī)劃的約束和目標(biāo)函數(shù)。設(shè)Xij表示“工廠i (