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

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

2、函數(shù)表達(dá)式 ， 有的目標(biāo)要實(shí)現(xiàn)極大值 ，有的則要求極小值 。2求解線(xiàn)性規(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)有可行解 ：線(xiàn)性規(guī)劃問(wèn)題的可行域是空集 。當(dāng)無(wú)界解和沒(méi)有可行解時(shí) ， 可能是建模時(shí)有錯(cuò) 。3什么是線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)型 ？ 松弛變量和剩余變量的管理含義是什么 ？ 答：線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)型是 ： 目標(biāo)函數(shù)極大化 ，約束條件為等式 ，右端常數(shù)項(xiàng) bi 0 ，決策變量滿(mǎn)足非負(fù)性 。如果加入的這個(gè)非負(fù)變量取值為非零的話(huà) ，則說(shuō)明該約束限定沒(méi)有

3、約束力 ，對(duì)企 業(yè)來(lái)說(shuō)不是緊缺資源 ，所以稱(chēng)為松弛變量 ；剩余變量取值為非零的話(huà) ，則說(shuō)明 “型”約 束的左邊取值大于右邊規(guī)劃值 ， 出現(xiàn)剩余量 。4試述線(xiàn)性規(guī)劃問(wèn)題的可行解 、基礎(chǔ)解、基可行解 、最優(yōu)解的概念及其相互關(guān)學(xué)習(xí)幫手 系。答：可行解 ：滿(mǎn)足約束條件 AX b，X 0的解，稱(chēng)為可行解 基可行解 ：滿(mǎn)足非負(fù)性約束的基解 ， 稱(chēng)為基可行解 。 可行基：對(duì)應(yīng)于基可行解的基 ，稱(chēng)為可行基 。最優(yōu)解 ：使目標(biāo)函數(shù)最優(yōu)的可行解 ， 稱(chēng)為最優(yōu)解 。最優(yōu)基 ：最優(yōu)解對(duì)應(yīng)的基矩陣 ，稱(chēng)為最優(yōu)基 。 它們的相互關(guān)系如右圖所示 ：5用表格單純形法求解如下線(xiàn)性規(guī)劃 。maxZ 4x1 x2 2x38x1 3

4、x2 x3 2s.t. 6x1 x2 x3 8x1,x2 ,x3 0解：標(biāo)準(zhǔn)化 maxZ 4x1 x2 2x38x1 3x2 x3 x4 2s.t. 6x1 x2 x3x5 8x1,x2 ,x3,x4,x5 0學(xué)習(xí)幫手j01/23/2-1/202x32831100x5622011j125020故最優(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 為何值及變量屬于哪一類(lèi)型時(shí)有 ：（1）表中解為唯一最優(yōu)解 ；（ 2）表中解為無(wú)窮多最優(yōu)解之 一；（3）下一步迭

5、代將以 x1代替基變量 x5；（4）該線(xiàn)性規(guī)劃問(wèn)題具有無(wú)界解 ；（ 5） 該線(xiàn)性規(guī)劃問(wèn)題無(wú)可行解 。表 1 15某極大化問(wèn)題的單純形表cjc1c2000iCBXBbx1x2x3x4x50x3d4a11000x42150100x53a23001jc1c2000解：（ 1） d 0,c10,c2 0 ；（2）d 0,c10,c20（c1,c2中至少有一個(gè)為零）（3）d3；c1 0,a2 0,4a2（4）c2 0,a10；（5） x1為人工變量 ，且c1為包含 M 的大于零的數(shù) ，d 3 ；或者 x2為人工變 4 a2量，且c2為包含 M 的大于零的數(shù) ， a1 0,d 0學(xué)習(xí)幫手7用大 M 法求解

6、如下線(xiàn)性規(guī)劃max Z 5x1 3x2 6x3x1 2x2 x3 182x1 x2 3x3 16 s.t.x1 x2 x3 10x1,x2,x3 0解：加入人工變量 ，進(jìn)行人造基后的數(shù)學(xué)模型如下 ：max Z 5x1 3x2 6x3 0x4 0x5 Mx6x1 2x2 x3 x4 182x1 x2 3x3 x5 16 s.t.x1 x2 x3 x6 10xi 0 (i 1,2, ,6)列出單純形表cj53600MiCBXBbx1x2x3x4x5x60x41812110018/10x51621301016/3Mx61011100110/1j5+M3+M6+M0000x438/31/35/3011

7、/3038/56x316/32/31/3101/3016Mx614/31/32/3001/3114/2j11M21M0012M03330x411/20011/25/26x331/20101/21/263x271/21001/23/214學(xué)習(xí)幫手j1/20003/23M20x440011135x161020113x24011012j001021M故 最 優(yōu) 解 為 X* (6,4,0,4,0,0)T ， 即 x1 6,x2 4,x3 0 ， 此 時(shí) 最 優(yōu) 值 為Z(X*) 42 8A，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 單位。試建立線(xiàn)性規(guī)劃模型 ，求將可供電量用完的最 低總費(fèi)用分配方案 。表 116單位電力輸電費(fèi) (單位 ：元)電站 城市ABCI151822II212516解：設(shè)xij為“第i電站向第 j城市分配的電量 ”(i=1,2; j=1,2,3)，建立模型如下 ：max Z 15x11 18x12 22x13 21x21 25x22 16x23x11x12x13 400x21x22x23 450x11x21290x

9、11x21320x12x22250x13x23270x13x23350s.t.xij 0,i 1,2; j 1,2,3學(xué)習(xí)幫手9某公司在 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)目 I

10、V 需要在第三年年初投資 ，年末可收回本利 140%，但用于該項(xiàng)目的 最大投資不得超過(guò) 10 萬(wàn)元 。在這個(gè)計(jì)劃期內(nèi) ，該公司第一年可供投資的資金有 30 萬(wàn) 元。問(wèn)怎樣的投資方案 ，才能使該公司在這個(gè)計(jì)劃期獲得最大利潤(rùn) ？解：設(shè) xi(1)表示第一次投資項(xiàng)目 i，設(shè) xi(2 )表示第二次投資項(xiàng)目 i，設(shè) xi(3)表示第三次 投資項(xiàng)目 i，( i=1,2,3,4 )，則建立的線(xiàn)性規(guī)劃模型為maxZ 1.2x1(3) 1.6x3(1) 1.4 x4(1)x1(1) x2(1) 30x1(2) x3(1) 1.2x1(1) 30 x1(1) x2(1)x1(3)x4(1)1.2x1(2)1.5

11、x2(1)1.2x1(1)30x1(1)x2(1)x1(2)x3(1)s.t.x2(1) 20x3(1) 15x4(1) 10xi(1),xi(2) ,xi(3) 0,i 1,2,3,4通過(guò) LINGO 軟件計(jì)算得 ： x1(1) 10,x2(1) 20,x3(1) 0, x1( 2) 12, x1(2) 4410 某家具制造廠(chǎng)生產(chǎn)五種不同規(guī)格的家具。每種家具都要經(jīng)過(guò)機(jī)械成型 、打磨、 上漆幾道重要工序 。每種家具的每道工序所用的時(shí)間 、每道工序的可用時(shí)間 、每 種家具的利潤(rùn)由表 1 17 給出。 問(wèn)工廠(chǎng)應(yīng)如何安排生產(chǎn) ，使總利潤(rùn)最大 ？表 1 17家具生產(chǎn)工藝耗時(shí)和利潤(rùn)表生產(chǎn)工序所需時(shí)間 (

12、小時(shí) )每道工序可用12345時(shí)間(小時(shí))學(xué)習(xí)幫手成型346233600打磨435643950上漆233432800利潤(rùn)（百元）2.734.52.53解：設(shè) xi表示第 i 種規(guī)格的家具的生產(chǎn)量 （i =1,2, ,5），則max Z 2.7x1 3x2 4.5x3 2.5x4 3x53x14x26x32x43x536004x13x25x36x44x53950s.t. 123452x13x23x34x43x52800xi0,i1,2,5通過(guò) LINGO 軟件計(jì)算得 ： x1 0,x2 38,x3 254, x4 0,x5 642,Z 318111某廠(chǎng)生產(chǎn)甲 、乙 、丙三種產(chǎn)品 ，分別經(jīng)過(guò) A，

13、B，C 三種設(shè)備加工 。已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)數(shù) 、設(shè)備的現(xiàn)有加工能力及每件產(chǎn)品的利潤(rùn)如表2 10 所示。表 1 18產(chǎn)品生產(chǎn)工藝消耗系數(shù)甲乙丙設(shè)備能力A（小時(shí)）111100B（小時(shí)）1045600C（小時(shí)）226300單位產(chǎn)品利潤(rùn)（元）10641）建立線(xiàn)性規(guī)劃模型 ，求該廠(chǎng)獲利最大的生產(chǎn)計(jì)劃 。2）產(chǎn)品丙每件的利潤(rùn)增加到多大時(shí)才值得安排生產(chǎn) ？如產(chǎn)品丙每件的利潤(rùn)增加到 6 ，求最優(yōu)生產(chǎn)計(jì)劃學(xué)習(xí)幫手3)產(chǎn)品甲的利潤(rùn)在多大范圍內(nèi)變化時(shí) ，原最優(yōu)計(jì)劃保持不變 ？4)設(shè)備 A 的能力如為 100+10 q， 確定保持原最優(yōu)基不變的 q 的變化范圍 。5)如合同規(guī)定該廠(chǎng)至少生產(chǎn) 10 件產(chǎn)品丙

14、 ，試確定最優(yōu)計(jì)劃的變化 。解：1)設(shè) x1,x2,x3分別表示甲 、乙、丙產(chǎn)品的生產(chǎn)量 ，建立線(xiàn)性規(guī)劃模型max Z 10x1 6x2 4x3x1 x2 x3 10010x1 4x2 5x3 600 s.t.2x1 2x2 6x3 300 x1,x2,x3 0標(biāo)準(zhǔn)化得max Z 10x1 6x2 4x3 0x4 0x5 0x6x1 x2 x3 x4 10010x1 4x2 5x3 x5 600 s.t.2x1 2x2 6x3 x6 300x1,x2,x3,x4,x5,x6 0cj1064000iiCBXBbx1x2x3x4x5x60x41001111001000x56001045010600

15、x6300226001150j10640000x44003/51/210200/31/1010x16012/51/201/1001500x618006/5501/51150列出單純形表學(xué)習(xí)幫手j0210106x2200/3015/65/31/6010x1100/3101/62/31/600x6100004201j008/310/32/30故最優(yōu)解為 x1 100/3,x2 200/3,x3 0，又由于 x1,x2,x3取整數(shù) ，故四舍五入可 得最優(yōu)解為 x1 33,x2 67,x3 0,Zmax 732 2）產(chǎn)品丙的利潤(rùn) c3 變化的單純形法迭代表如下 ：cj106c3000iCBXBbx1x

16、2x3x4x5x66x2200/3015/65/31/6010x1100/3101/62/31/600x6100004201j00c3 20/310/32/30要使原最優(yōu)計(jì)劃保持不變 ，只要 3 c3 230 0，即 c3 632 6.67 故當(dāng)產(chǎn)品丙每件的利潤(rùn)增加到大于 6.67 時(shí) ，才值得安排生產(chǎn) 。如產(chǎn)品丙每件的利潤(rùn)增加到 6 時(shí)， 此時(shí) 66.67 ，故原最優(yōu)計(jì)劃不變 。（3）由最末單純形表計(jì)算出1213 1 c1 0, 4 10 c1 0, 5 1 c1 0 ，636解得 6 c1 15 ，即當(dāng)產(chǎn)品甲的利潤(rùn) c1在6,15范圍內(nèi)變化時(shí) ，原最優(yōu)計(jì)劃保持不學(xué)習(xí)幫手1/60100 10

17、q13200 50q1/60600100 20q0013003(100 20q)5/3 1/6 0B 1 2/3 1/6 0 ，新的最優(yōu)解為2 0 15/3X B B 1b2/324）由最末單純形表找出最優(yōu)基的逆為解得 4 q 5 ，故要保持原最優(yōu)基不變的 q 的變化范圍為 4,5（5）如合同規(guī)定該廠(chǎng)至少生產(chǎn) 10 件產(chǎn)品丙 ，則線(xiàn)性規(guī)劃模型變成 max Z 10x1 6x2 4x3x1 x2 x3 10010x1 4x2 5x3 600s.t. 2x1 2x2 6x3 300x3 10x1, x2 , x3 0通過(guò) LINGO 軟件計(jì)算得到 ： x1 32,x2 58,x3 10,Z 708

18、第 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à)值 ，稱(chēng)為影子價(jià)值 ?？梢园褜?duì)偶問(wèn)題的解 Y 定義為每增加一個(gè)單位的資源引起的目標(biāo)函數(shù)值的增量 。2什么是資源的影子價(jià)格 ？它與相應(yīng)的市場(chǎng)價(jià)格有什么區(qū)別 ？答：若以產(chǎn)值為目標(biāo) ，則 yi是增加單位資源 i對(duì)產(chǎn)值的貢獻(xiàn) ，稱(chēng)為資源的影子價(jià)格 （Shadow Pr

19、ice）。即有“影子價(jià)格 =資源成本 +影子利潤(rùn) ”。因?yàn)樗⒉皇琴Y源的實(shí)際學(xué)習(xí)幫手 價(jià)格 ，而是企業(yè)內(nèi)部資源的配比價(jià)格 ，是由企業(yè)內(nèi)部資源的配置狀況來(lái)決定的 ，并不 是由市場(chǎng)來(lái)決定 ，所以叫影子價(jià)格 。 可以將資源的市場(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)題變量之間 、 解及檢 驗(yàn)數(shù)之間的關(guān)系 ？答：（1）最優(yōu)性定理：設(shè) X,Y 分別為原問(wèn)題和對(duì)偶問(wèn)題的可行解，且 CX bTY ，則 X,Y

20、 分別為各自的最優(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) 數(shù)。4已知線(xiàn)性規(guī)劃問(wèn)題maxZ 4x1 x2 2x38x1 3x2 x3 2 （第一種資源）s.t. 6x1 x2 x3 8 （第二種資源）x1, x2 , x3 0（ 1

21、）求出該問(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)解是否改變 ？學(xué)習(xí)幫手4）代加工產(chǎn)品丁 ，每單位產(chǎn)品需消耗第一種資源 2 單位，消耗第二種資源 3 單位 ，應(yīng)該如何定價(jià) ？解：（ 1）標(biāo)準(zhǔn)化 ，并列出初始單純形表cj41200iCBXBbx1x2x3x4x50x42831102/80x58611018/6j412004x11/413/81/81/8020x513/265/41/43/4126j01/23/2-1/202x32831100x5622011j125020由

22、 最 末 單 純 性 表 可 知 ， 該 問(wèn) 題 的 最 優(yōu) 解 為 ： X* （0,0,2,0,6）T ， 即x1 0,x2 0,x3 2 ，最優(yōu)值為 Z 4 （2）由原問(wèn)題的最末單純形表可知 ， 對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)值為 ：y1 2,y2 0,w 4 （3）兩種資源的影子價(jià)格分別為 2、0，表示對(duì)產(chǎn)值貢獻(xiàn)的大小 ；第一種資源限量 由 2 變?yōu)?4 ，最優(yōu)解不會(huì)改變 。（4）代加工產(chǎn)品丁的價(jià)格不低于 2 2 0 3 4 5某廠(chǎng)生產(chǎn) A，B，C，D4 種產(chǎn)品，有關(guān)資料如表 26 所示。表 2 6學(xué)習(xí)幫手資源消耗資源產(chǎn)品資源供應(yīng)量（公斤）原料成本（元/公斤）ABCD甲23128002.0乙54

23、3412001.0丙345310001.5單位產(chǎn)品售價(jià)（元）14.52115.516.51）請(qǐng)構(gòu)造使該廠(chǎng)獲利潤(rùn)最大的線(xiàn)性規(guī)劃模型 ，并用單純形法求解該問(wèn)題 （不計(jì)加工成本 ）。（2）該廠(chǎng)若出租資源給另一個(gè)工廠(chǎng) ，構(gòu)成原問(wèn)題的對(duì)偶問(wèn)題 ，列出對(duì)偶問(wèn)題的數(shù) 學(xué)模型，資源甲 、乙、丙的影子價(jià)格是多少 ？若工廠(chǎng)可在市場(chǎng)上買(mǎi)到原料丙 ，工廠(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è)x1,x2,x3,x4分別表示甲 、乙、丙產(chǎn)品的生產(chǎn)量

24、 ，建立線(xiàn)性規(guī)劃模型 max Z x1 5x2 3x3 4x42x1 3x2 x3 2x4 8005x1 4x2 3x3 4x4 1200s.t.3x1 4x2 5x3 3x4 1000xi 0,i 1,2,3,4初始單純形表c j 1 5 3 4 0 0 0學(xué)習(xí)幫手CBXBbx1x2x3x4x5x6x70x58002312100800/30x6120054340101200/40x7100034530011000/4j1534000最末單純形表cj1534000CBXBbx1x2x3x4x5x6x7i0x51001/40-13/4011/4-14x420020-2101-15x2100-3/

25、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）原問(wèn)題的對(duì)偶問(wèn)題的數(shù)學(xué)模型為min w 800y1 1200 y2 1000 y32y1 5y2 3y3 13y1 4y2 4y3 5s.t. y1 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)品

26、 B 的價(jià)格下降了 0.5 元，生產(chǎn)計(jì)劃不需要調(diào)整 。學(xué)習(xí)幫手6某企業(yè)生產(chǎn)甲 、乙兩種產(chǎn)品 ，產(chǎn)品生產(chǎn)的工藝路線(xiàn)如圖 2 1 所示，試統(tǒng)計(jì)單 位產(chǎn)品的設(shè)備工時(shí)消耗 ，填入表 27。又已知材料 、設(shè)備 C 和設(shè)備 D 等資源的單位成 本和擁有量如表 2 7 所示 。表 2 7 資源消耗與資源成本表產(chǎn)品資源資源消耗資源成本資源擁有量甲乙元/ 單位資源材料（公斤 ）60502004200設(shè)備 C（ 小時(shí)）3040103000設(shè)備 D （小時(shí)）6050204500據(jù)市場(chǎng)分析 ， 甲、乙產(chǎn)品銷(xiāo)售價(jià)格分別為 13700 元和 11640 元，試確定獲利最大 的產(chǎn)品生產(chǎn)計(jì)劃 。（1）設(shè)產(chǎn)品甲的計(jì)劃生產(chǎn)量為

27、x1，產(chǎn)品乙的計(jì)劃生產(chǎn)量為 x2 ，試建立其線(xiàn)性規(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)計(jì)劃方案是什么 ？并解釋 x3 0,x4 0,x5 300 的經(jīng)濟(jì)意義 。（3）利用 LINDO 軟件對(duì)價(jià)值系數(shù)進(jìn)行敏感性分析 ，結(jié)果如下 ：Obj Coefficient RangesVariableCurrentCoefAllowab

28、le IncreaseAllowable Decreasex12008820學(xué)習(xí)幫手x2240 26.67 73.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é)果如下 ：Right hand Side RangesResourceCurrent RhsAllowableIncreaseAllowableDecrease材料4200300450設(shè)備 C3000360900設(shè)備 D4500Infinity300試問(wèn)非緊缺資源最多可以減少到多少 ，而緊缺

29、資源最多可以增加到多少 ？解：（ 1）建立的線(xiàn)性規(guī)劃模型為max Z 200x1 240x260x1 50x2 420030x1 40x2 3000s.t.60x1 50x2 4500x1,x2 0將其標(biāo)準(zhǔn)化max Z 200x1 240x260x1 50x2 x3 420030x1 40x2 x4 3000s.t.60x1 50x2 x5 4500xi 0,i 1,2, ,5（2）甲生產(chǎn) 20 件，乙生產(chǎn) 60 件，材料和設(shè)備 C充分利用，設(shè)備 D 剩余 600 單 位。（3）甲上升到 13800 需要調(diào)整 ，乙下降 60 不用調(diào)整 。學(xué)習(xí)幫手4）非緊缺資源設(shè)備 D 最多可以減少到 300

30、，而緊缺資源 材料最多可以增加到300，緊缺資源設(shè)備 C最多可以增加到 360第 3 章 整數(shù)規(guī)劃（復(fù)習(xí)思考題 ）1整數(shù)規(guī)劃的類(lèi)型有哪些 ？答：純整數(shù)規(guī)劃 、0-1 規(guī)劃和混合整數(shù)規(guī)劃 。2試述整數(shù)規(guī)劃分枝定界法的思路 。答：（ 1）首先不考慮整數(shù)條件 ，求解整數(shù)規(guī)劃相應(yīng)的線(xiàn)性規(guī)劃問(wèn)題 。若相應(yīng)的線(xiàn) 性規(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ī)劃問(wèn)題上界 ；在滿(mǎn)足整數(shù)約束的子問(wèn)題的解中 ，最大的目標(biāo)函數(shù)值 為整數(shù)規(guī)劃問(wèn)題的下界 。當(dāng)上下界相同時(shí) ，則已得最優(yōu)解 ；否則 ，轉(zhuǎn)入剪

31、枝過(guò)程 。（3）剪枝過(guò)程 。在下述情況下剪除這些分枝 ： 若某一子問(wèn)題相應(yīng)的線(xiàn)性規(guī)劃問(wèn)題無(wú)可行解 ；在分枝過(guò)程中 ， 求解某一線(xiàn)性規(guī)劃所得到的目標(biāo)函數(shù)值 Z 不優(yōu)于現(xiàn)有下界學(xué)習(xí)幫手4）分枝過(guò)程 。當(dāng)有多個(gè)待求分枝時(shí) ，應(yīng)先選取目標(biāo)函數(shù)值最優(yōu)的分枝繼續(xù)進(jìn)行分枝。選取一個(gè)不符合整數(shù)條件的變量 xi作為分枝變量 ，若 xi的值是 bi* ，構(gòu)造兩個(gè)新的約束條件 ： xi bi*或xi bi* 1，分別并入相應(yīng)的數(shù)學(xué)模型中 ，構(gòu)成兩個(gè)子問(wèn)題 對(duì)任一個(gè)子問(wèn)題 ，轉(zhuǎn)步驟 （1）3試用分枝定界法求如下線(xiàn)性規(guī)劃 ：max Z 40x1 90x29x1 7x2 567x1 20x2 70s.t.x1,x2 0x

32、1,x2 取整數(shù)解：最優(yōu)整數(shù)解為 ： x1 4,x2 2,Z 340 4有 4 名職工 ，由于各人的能力不同 ，每個(gè)人做各項(xiàng)工作所用的時(shí)間不同，所花費(fèi)時(shí)間如表 3 7表 37（單位： 分鐘）學(xué)習(xí)幫手甲15182124乙19232218丙26171619丁19212317問(wèn)指派哪個(gè)人去完成哪項(xiàng)工作 ，可使總的消耗時(shí)間最少 ？解：設(shè)xij 1 ，任務(wù)i由人員j完成 ，tij 為個(gè)人 i對(duì)于任務(wù) j的時(shí)間耗費(fèi)矩陣 ，則 ij 0 ，任務(wù)i不由人員 j完成 ij建立整數(shù)規(guī)劃模型為 ：44min Zxij tiji1j14xij 1i14s.t.xij 1j1xij 0或1,i, j 1,2,3,4解得

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

34、x5x6x750x1x2x3x6x750x1x2x3x4x750s.t. x1x2x3x4x580x2x3x4x5x690x3x4x5x6x790xi 0,i 1,2, ,7 xi取整數(shù) ,i 1,2, ,7解得： x1 0,x2 4,x3 32,x4 10,x5 34,x6 10,x7 4,Z 94 學(xué)習(xí)幫手第 4 章 目標(biāo)規(guī)劃 （復(fù)習(xí)思考題 ）1某計(jì)算機(jī)公司生產(chǎn) A，B，C 三種型號(hào)的筆記本電腦 。這三種筆記本電腦需要在 復(fù)雜的裝配線(xiàn)上生產(chǎn) ，生產(chǎn)一臺(tái) A，B，C型號(hào)的筆記本電腦分別需要 5 小時(shí)、8 小時(shí)、 12 小時(shí) 。公司裝配線(xiàn)正常的生產(chǎn)時(shí)間是每月 1700 小時(shí)，公司營(yíng)業(yè)部門(mén)估計(jì)

35、A，B，C 三種筆記本電腦每臺(tái)的利潤(rùn)分別是 1000 元、1440 元 、2520 元 ，而且公司預(yù)測(cè)這個(gè)月 生產(chǎn)的筆記本電腦能夠全部售出 。公司經(jīng)理考慮以下目標(biāo) ：第一目標(biāo) ：充分利用正常的生產(chǎn)能力 ，避免開(kāi)工不足 ；第二目標(biāo) ：優(yōu)先滿(mǎn)足老客服的需求 ，A，B，C三種型號(hào)的電腦各為 50 臺(tái)、50 臺(tái)、80 臺(tái)， 同時(shí)根據(jù)三種電腦三種電腦的純利潤(rùn)分配不同的加權(quán)系數(shù) ；第三目標(biāo)：限制裝配線(xiàn)加班時(shí)間 ，最好不超過(guò) 200 小時(shí)；第四目標(biāo) ：滿(mǎn)足各種型號(hào)電腦的銷(xiā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) ：裝配線(xiàn)加

36、班時(shí)間盡可能少 。請(qǐng)列出相應(yīng)的目標(biāo)規(guī)劃模型 ，并用 LINGO 軟件求解 。解：建立目標(biāo)約束 。（1）裝配線(xiàn)正常生產(chǎn)設(shè)生產(chǎn) A，B，C 型號(hào)的電腦為 x1,x2,x3（臺(tái)）， d1 為裝配線(xiàn)正常生產(chǎn)時(shí)間未利用 數(shù)，d1 為裝配線(xiàn)加班時(shí)間 ，希望裝配線(xiàn)正常生產(chǎn) ，避免開(kāi)工不足 ，因此裝配線(xiàn)目標(biāo)約 束為min d1 學(xué)習(xí)幫手5x1 8x2 12x3 d1 d1 1700(2) 銷(xiāo)售目標(biāo)優(yōu)先滿(mǎn)足老客戶(hù)的需求 ，并根據(jù)三種電腦的純利潤(rùn)分配不同的權(quán)因子 ， A，B，C 三種型號(hào)的電腦每小時(shí)的利潤(rùn)是 1000 ,1440 , 2520 ，因此，老客戶(hù)的銷(xiāo)售目標(biāo)約束為5 8 12min 20d2 18d3

37、21d4 x1 d2 d2 50x2 d3 d3 50x3 d4 d4 80再考慮一般銷(xiāo)售 。類(lèi)似上面的討論 ，得到min 20d5 18d6 21d7 x1 d5 d5 100x2 d6 d6 120x3 d7 d7 100(3) 加班限制首先是限制裝配線(xiàn)加班時(shí)間 ，不允許超過(guò) 200 小時(shí) ，因此得到min d8 5x1 8x2 12x3 d8 d8 1900其次裝配線(xiàn)的加班時(shí)間盡可能少 ，即min d1 5x1 8x2 12x3 d1 d1 1700寫(xiě)出目標(biāo)規(guī)劃的數(shù)學(xué)模型min G P1d1 P2(20d2 18d3 21d4 ) P3d8 P4(20d5 18d6 21d7 ) P5d

38、1學(xué)習(xí)幫手5x1 8x2 12x3 d1 d1 1700 x1 d2 d2 50 x2 d3 d3 50 x3 d4 d4 80x1 d5 d5 100 s.t.x2 d6 d6 120x3 d7 d7 100 5x1 8x2 12x3 d1 d1 1900 xi 0,i 1,2dl ,dl 0,l 1,2, ,8經(jīng)過(guò) LINGO 軟件計(jì)算 ，得到 x1 100, x2 55,x3 80 ，裝配線(xiàn)生產(chǎn)時(shí)間為 1900 小 時(shí)，滿(mǎn)足裝配線(xiàn)加班不超過(guò) 200 小時(shí)的要求 。能夠滿(mǎn)足老客戶(hù)的需求 ，但未能達(dá)到銷(xiāo)售目標(biāo) 。銷(xiāo)售總利潤(rùn)為 1001000+551440+802520=380800（ 元）。

39、2已知 3 個(gè)工廠(chǎng)生產(chǎn)的產(chǎn)品供應(yīng)給 4 個(gè)客戶(hù) ，各工廠(chǎng)生產(chǎn)量 、用戶(hù)需求量及從各 工廠(chǎng)到用戶(hù)的單位產(chǎn)品的運(yùn)輸費(fèi)用如表 43 所示 。由于總生產(chǎn)量小于總需求量 ，上級(jí) 部門(mén)經(jīng)研究后 ，制定了調(diào)配方案的 8 個(gè)目標(biāo) ，并規(guī)定了重要性的次序 。表 43工廠(chǎng)產(chǎn)量 用戶(hù)需求量及運(yùn)費(fèi)單價(jià) （單位：元）工廠(chǎng) 用戶(hù)1234生產(chǎn)量152672354634523需求量（單位）200100450250第一目標(biāo)：用戶(hù) 4 為重要部門(mén) ，需求量必須全部滿(mǎn)足 ；第二目標(biāo) ：供應(yīng)用戶(hù) 1 的產(chǎn)品中 ，工廠(chǎng) 3 的產(chǎn)品不少于 100 個(gè)單位 ；第三目標(biāo) ：每個(gè)用戶(hù)的滿(mǎn)足率不低于 80%；第四目標(biāo) ：應(yīng)盡量滿(mǎn)足各用戶(hù)的需求

40、；學(xué)習(xí)幫手第五目標(biāo) ：新方案的總運(yùn)費(fèi)不超過(guò)原運(yùn)輸問(wèn)題 （ 線(xiàn)性規(guī)劃模型 ）的調(diào)度方案的 10%；第六目標(biāo)：因道路限制 ，工廠(chǎng) 2 到用戶(hù) 4 的路線(xiàn)應(yīng)盡量避免運(yùn)輸任務(wù) ；第七目標(biāo)：用戶(hù) 1 和用戶(hù) 3 的滿(mǎn)足率應(yīng)盡量保持平衡 ；第八目標(biāo) ：力求減少總運(yùn)費(fèi) 。請(qǐng)列出相應(yīng)的目標(biāo)規(guī)劃模型 ，并用 LINGO 軟件求解 。 解：假設(shè)三個(gè)工廠(chǎng)對(duì)應(yīng)的生產(chǎn)量分別為 300，200， 400（1）求解原運(yùn)輸問(wèn)題由于總生產(chǎn)量小于總需求量 ，虛設(shè)工廠(chǎng) 4，生產(chǎn)量為 100 個(gè)單位 ，到各個(gè)用戶(hù)間 的運(yùn)費(fèi)單價(jià)為 0。用LINGO 軟件求解，得到總運(yùn)費(fèi)是 2950 元，運(yùn)輸方案如下表所示 。工廠(chǎng) 用戶(hù)1234生產(chǎn)量1100200300220020032501504004100100需求量（單位）2001004502502）下面按照目標(biāo)的重要性的等級(jí)列出目標(biāo)規(guī)劃的約束和目標(biāo)函數(shù)設(shè) xij