1、管理運籌學(第二版)課后習題答案管理運籌學其次版課后習題參考答案第1章線性規(guī)劃復習思索題1什么是線性規(guī)劃？線性規(guī)劃的三要素是什么？答：線性規(guī)劃linear programming，lp是運籌學中最成熟的一個分支，并且是應(yīng)用最廣泛的一個運籌學分支。線性規(guī)劃屬于規(guī)劃論中的靜態(tài)規(guī)劃，是一種重要的優(yōu)化工具，可以解決有限資源的最正確安排問題。建立線性規(guī)劃問題要具備三要素：決策變量、約束條件、目的函數(shù)。決策變量是決策問題待定的量值，取值一般為非負；約束條件是指決策變量取值時受到的各種資源條件的限制，保障決策方案的可行性；目的函數(shù)是決策者盼望實現(xiàn)的目的，為決策變量的線性函數(shù)表達式，有的目的要實現(xiàn)極大值，有的

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

3、現(xiàn)剩余量。4試述線性規(guī)劃問題的可行解、根底解、基可行解、最優(yōu)解的概念及其互相關(guān)系。答：可行解：滿足約束條件0bax，的解，稱為可行解。=x基可行解：滿足非負性約束的基解，稱為基可行解。可行基：對應(yīng)于基可行解的基，稱為可行基。最優(yōu)解：使目的函數(shù)最優(yōu)的可行解，稱為最優(yōu)解。最優(yōu)基：最優(yōu)解對應(yīng)的基矩陣，稱為最優(yōu)基。它們的互相關(guān)系如右圖所示：5用表格單純形法求解如下線性規(guī)劃。32124max x x x z +=s .t . ?+0,86238321321321x x x x x x x x x解：標準化 32124m a x x x x z +=s .t . ?=+=+0,86238543215321

4、4321x x x x x x x x x x x x x 列出單純形表故最優(yōu)解為t x )6,0,2,0,0(*=，即2,0,0321=x x x ，此時最優(yōu)值為4*)(=x z 6表115中給出了求極大化問題的單純形表，問表中d c c a a ,2121為何值及變量屬于哪一類型時有：1表中解為唯一最優(yōu)解；2表中解為無窮多最優(yōu)解之一；3下一步迭代將以1x 代替基變量5x ；4該線性規(guī)劃問題具有無界解；5該線性規(guī)劃問題無可行解。表115 某極大化問題的單純形表解：10,0,021>>； 40,012>a c ；51x 為人工變量，且1c 為包含m 的大于零的數(shù)，234a d

5、 >；或者2x 為人工變量，且2c 為包含m 的大于零的數(shù)，0,01>>d a 7用大m 法求解如下線性規(guī)劃。321635max x x x z +=s .t . ?=+0,101632182321321321321x x x x x x x x x x x x解：參加人工變量，進展人造基后的數(shù)學模型如下：65432100635max mx x x x x x z -+=s .t . ?=+=+=+)6,2,1(0101632182632153214321 i x x x x x x x x x x x x x i列出單純形表故最優(yōu)解為t x )0,0,4,0,4,6(*=，

6、即0,4,6321=x x x ，此時最優(yōu)值為42*)(=x z 8a ，b ，c 三個城市每年需分別供給電力320，250和350單位，由i ，ii 兩個電站供應(yīng)，它們的最大可供電量分別為400單位和450單位，單位費用如表116所示。由于需要量大于可供量，打算城市a 的供給量可削減030單位，城市b 的供給量不變，城市c 的供給量不能少于270單位。試建立線性規(guī)劃模型，求將可供電量用完的最低總費用安排方案。表116 單位電力輸電費單位：元解：設(shè)ij x 為“第i 電站向第j 城市安排的電量i =1,2; j =1,2,3，建立模型如下：232221131211162521221815max

7、 x x x x x x z += s .t . ?=+=+=+=+3,2,1;2,1,035027025032029045040023132313221221112111232221131211j i x x x x x x x x x x x x x x x x x ij9某公司在3年的方案期內(nèi)，有4個建立工程可以投資：工程i 從第一年到第三年年初都可以投資。估計每年年初投資，年末可收回本利120%，每年又可以重新將所獲本利納入投資方案；工程ii 需要在第一年初投資，經(jīng)過兩年可收回本利150%，又可以重新將所獲本利納入投資方案，但用于該工程的最大投資不得超過20萬元；工程iii 需要在其次

8、年年初投資，經(jīng)過兩年可收回本利160%，但用于該工程的最大投資不得超過15萬元；工程iv 需要在第三年年初投資，年末可收回本利140%，但用于該工程的最大投資不得超過10萬元。在這個方案期內(nèi)，該公司第一年可供投資的資金有30萬元。問怎樣的投資方案，才能使該公司在這個方案期獲得最大利潤？解：設(shè))1(i x 表示第一次投資工程i ，設(shè))2(i x 表示其次次投資工程i ，設(shè))3(i x 表示第三次投資工程i ，i =1,2,3,4，那么建立的線性規(guī)劃模型為)1(4)1(3)3(14.16.12.1max x x x z += s .t . ?=-+=+-+4,3,2,1,0,101520302.1

9、5.12.1302.130)3()2()1()1(4)1(3)1(2)1(3)2(1)1(2)1(1)1(1)1(2)2(1)1(4)3(1)1(2)1(1)1(1)1(3)2(1)1(2)1(1i x x x x x x x x x x x x x x x x x x x x x x i i i 通過lingo 軟件計算得：44,12,0,20,10)2(1)2(1)1(3)1(2)1(1=x x x x x 10某家具制造廠生產(chǎn)五種不同規(guī)格的家具。每種家具都要經(jīng)過機械成型、打磨、上漆幾道重要工序。每種家具的每道工序所用的時間、每道工序的可用時間、每種家具的利潤由表117給出。問工廠應(yīng)如何支

10、配生產(chǎn)，使總利潤最大？表117 家具生產(chǎn)工藝耗時和利潤表解：設(shè)i x 表示第i 種規(guī)格的家具的生產(chǎn)量i =1,2,5，那么5432135.25.437.2max x x x x x z +=s .t . ?=+5,2,1,0280034332395046534360032643543215432154321 i x x x x x x x x x x x x x x x x i通過lingo 軟件計算得：3181,642,0,254,38,054321=z x x x x x 11某廠生產(chǎn)甲、乙、丙三種產(chǎn)品，分別經(jīng)過a ，b ，c 三種設(shè)備加工。已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時數(shù)、設(shè)備的現(xiàn)有加工

11、力量及每件產(chǎn)品的利潤如表210所示。表118 產(chǎn)品生產(chǎn)工藝消耗系數(shù) 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如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品丙，試確定最優(yōu)方案的改變。解：1設(shè)321,x x x 分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量，建立線性規(guī)劃模型3214610max x x x z +=s .t . ?+0,3006226005410100321321321321x x

12、x x x x x x x x x x標準化得6543210004610max x x x x x x z +=s .t . ?=+=+=+0,3006226005410100654321632153214321x x x x x x x x x x x x x x x x x x列出單純形表故最優(yōu)解為0,3/200,3/100321=x x x ，又由于321,x x x 取整數(shù)，故四舍五入可得最優(yōu)解為0,67,33321=x x x ,732max =z 2產(chǎn)品丙的利潤3c 改變的單純形法迭代表如下：要使原最優(yōu)方案保持不變，只要0333-=c ，即67.6363c 故當產(chǎn)品丙每件的利潤增加

13、到大于6.67時，才值得支配生產(chǎn)。如產(chǎn)品丙每件的利潤增加到6時，此時6<6.67，故原最優(yōu)方案不變。 3由最末單純形表計算出0611,03210,0611151413-=+-=-=c c c ，解得1561c ，即當產(chǎn)品甲的利潤1c 在15,6范圍內(nèi)改變時，原最優(yōu)方案保持不變。4由最末單純形表找出最優(yōu)基的逆為?-=-10206/13/206/13/51b ，新的最優(yōu)解為 0)20100(32010050200313006001010010206/13/206/13/51? ?-+=? ?+? ?-='='-q q q q b b x b解得54-q ，故要保持原最優(yōu)基不變

14、的q 的改變范圍為5,4-5如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品丙，那么線性規(guī)劃模型變成3214610max x x x z +=s .t . ?+0,1030062260054101003213321321321x x x x x x x x x x x x x通過lingo 軟件計算得到：708,10,58,32321=z x x x 第2章 對偶規(guī)劃復習思索題1對偶問題和對偶向量即影子價值的經(jīng)濟意義是什么？答：原問題和對偶問題從不同的角度來分析同一個問題，前者從產(chǎn)品產(chǎn)量的角度來考察利潤，后者那么從形成產(chǎn)品本身所需要的各種資源的角度來考察利潤，即利潤是產(chǎn)品生產(chǎn)帶來的，同時又是資源消耗帶來的。對

15、偶變量的值i y 表示第i 種資源的邊際價值，稱為影子價值。可以把對偶問題的解y 定義為每增加一個單位的資源引起的目的函數(shù)值的增量。2什么是資源的影子價格？它與相應(yīng)的市場價格有什么區(qū)分？答：假設(shè)以產(chǎn)值為目的，那么i y 是增加單位資源i 對產(chǎn)值的奉獻，稱為資源的影子價格shadow price 。即有“影子價格=資源本錢+影子利潤。因為它并不是資源的實際價格，而是企業(yè)內(nèi)部資源的配比價格，是由企業(yè)內(nèi)部資源的配置情況來打算的，并不是由市場來打算，所以叫影子價格。可以將資源的市場價格與影子價格進展比擬，當市場價格小于影子價格時，企業(yè)可以購進相應(yīng)資源，儲藏或者投入生產(chǎn)；當市場價格大于影子價格時，企業(yè)可以考慮暫不購進資源，削減不必要的損失。3如何依據(jù)原問題和對偶問題之間的對應(yīng)關(guān)系，找出兩個問題變量之間、解及檢驗數(shù)之間的關(guān)系？答：1最優(yōu)性定理：設(shè)y x ,分別為