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

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ù)項，決策變量滿足非負(fù)性。如果加入的這個非負(fù)變量取值為非零的話，則說明該約束限定沒有約束力，對企業(yè)來說不是緊缺資源，所以稱為松弛變量；剩余變量取值為非零的話，則說明“”型約束的左邊取值大于右邊規(guī)劃值，出現(xiàn)剩余量。4試述線性規(guī)

3、劃問題的可行解、基礎(chǔ)解、基可行解、最優(yōu)解的概念及其相互關(guān)系。答：可行解：滿足約束條件的解，稱為可行解?；尚薪猓簼M足非負(fù)性約束的基解，稱為基可行解?？尚谢簩?yīng)于基可行解的基，稱為可行基。最優(yōu)解：使目標(biāo)函數(shù)最優(yōu)的可行解，稱為最優(yōu)解。最優(yōu)基：最優(yōu)解對應(yīng)的基矩陣，稱為最優(yōu)基。 它們的相互關(guān)系如右圖所示：5用表格單純形法求解如下線性規(guī)劃。s.t. 解：標(biāo)準(zhǔn)化 s.t. 列出單純形表41200b02831102/808611018/64120041/413/81/81/80(1/4)/(1/8)013/265/41/43/41(13/2)/(1/4)01/23/2-1/2022831100622011

4、125020故最優(yōu)解為，即，此時最優(yōu)值為6表115中給出了求極大化問題的單純形表，問表中為何值及變量屬于哪一類型時有：（1）表中解為唯一最優(yōu)解；（2）表中解為無窮多最優(yōu)解之一；（3）下一步迭代將以代替基變量；（4）該線性規(guī)劃問題具有無界解；（5）該線性規(guī)劃問題無可行解。表115 某極大化問題的單純形表000b0d41000215010033001000解：（1）；（2）；（3）；（4）；（5）為人工變量，且為包含M的大于零的數(shù)，；或者為人工變量，且為包含M的大于零的數(shù)，7用大M法求解如下線性規(guī)劃。s.t. 解：加入人工變量，進(jìn)行人造基后的數(shù)學(xué)模型如下：s.t. 列出單純形表53600Mb018

5、12110018/101621301016/3M1011100110/15+M3+M6+M000038/31/35/3011/3038/5616/32/31/3101/3016M14/31/32/3001/3114/2000011/20011/25/2631/20101/21/26371/21001/23/2141/20003/2040011135610201134011012001021M故最優(yōu)解為，即，此時最優(yōu)值為8A，B，C三個城市每年需分別供應(yīng)電力320，250和350單位，由I，II兩個電站提供，它們的最大可供電量分別為400單位和450單位，單位費用如表116所示。由于需要量大于可

6、供量，決定城市A的供應(yīng)量可減少030單位，城市B的供應(yīng)量不變，城市C的供應(yīng)量不能少于270單位。試建立線性規(guī)劃模型，求將可供電量用完的最低總費用分配方案。表116 單位電力輸電費（單位：元）電站 城市ABCI151822II212516解：設(shè)為“第i電站向第j城市分配的電量”（i=1,2; j=1,2,3），建立模型如下：s.t. 9某公司在3年的計劃期內(nèi)，有4個建設(shè)項目可以投資：項目I從第一年到第三年年初都可以投資。預(yù)計每年年初投資，年末可收回本利120%，每年又可以重新將所獲本利納入投資計劃；項目II需要在第一年初投資，經(jīng)過兩年可收回本利150%，又可以重新將所獲本利納入投資計劃，但用于該

7、項目的最大投資不得超過20萬元；項目III需要在第二年年初投資，經(jīng)過兩年可收回本利160%，但用于該項目的最大投資不得超過15萬元；項目IV需要在第三年年初投資，年末可收回本利140%，但用于該項目的最大投資不得超過10萬元。在這個計劃期內(nèi)，該公司第一年可供投資的資金有30萬元。問怎樣的投資方案，才能使該公司在這個計劃期獲得最大利潤？解：設(shè)表示第一次投資項目i，設(shè)表示第二次投資項目i，設(shè)表示第三次投資項目i，（i=1,2,3,4），則建立的線性規(guī)劃模型為s.t. 通過LINGO軟件計算得：10某家具制造廠生產(chǎn)五種不同規(guī)格的家具。每種家具都要經(jīng)過機(jī)械成型、打磨、上漆幾道重要工序。每種家具的每道工

8、序所用的時間、每道工序的可用時間、每種家具的利潤由表117給出。問工廠應(yīng)如何安排生產(chǎn)，使總利潤最大？表117 家具生產(chǎn)工藝耗時和利潤表生產(chǎn)工序所需時間（小時）每道工序可用時間（小時）12345成型346233600打磨435643950上漆233432800利潤（百元）2.734.52.53解：設(shè)表示第i種規(guī)格的家具的生產(chǎn)量（i=1,2,5），則s.t. 通過LINGO軟件計算得：11某廠生產(chǎn)甲、乙、丙三種產(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（小時）111100B

9、（小時）1045600C（小時）226300單位產(chǎn)品利潤（元）1064 （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è)分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量，建立線性規(guī)劃模型s.t. 標(biāo)準(zhǔn)化得s.t. 列出單純形表1064000b010011110010006001045010600300226001

10、150106400004003/51/211/100200/3106012/51/201/100150018006/5501/511500210106200/3015/65/31/6010100/3101/62/31/600100004201008/310/32/30故最優(yōu)解為，又由于取整數(shù)，故四舍五入可得最優(yōu)解為,（2）產(chǎn)品丙的利潤變化的單純形法迭代表如下：106000b6200/3015/65/31/6010100/3101/62/31/6001000042010020/310/32/30要使原最優(yōu)計劃保持不變，只要，即故當(dāng)產(chǎn)品丙每件的利潤增加到大于6.67時，才值得安排生產(chǎn)。如產(chǎn)品丙每件

11、的利潤增加到6時，此時6<6.67，故原最優(yōu)計劃不變。（3）由最末單純形表計算出，解得，即當(dāng)產(chǎn)品甲的利潤在范圍內(nèi)變化時，原最優(yōu)計劃保持不變。（4）由最末單純形表找出最優(yōu)基的逆為，新的最優(yōu)解為解得，故要保持原最優(yōu)基不變的q的變化范圍為（5）如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品丙，則線性規(guī)劃模型變成s.t. 通過LINGO軟件計算得到：第2章 對偶規(guī)劃（復(fù)習(xí)思考題）1對偶問題和對偶向量（即影子價值）的經(jīng)濟(jì)意義是什么？答：原問題和對偶問題從不同的角度來分析同一個問題，前者從產(chǎn)品產(chǎn)量的角度來考察利潤，后者則從形成產(chǎn)品本身所需要的各種資源的角度來考察利潤，即利潤是產(chǎn)品生產(chǎn)帶來的，同時又是資源消耗帶來的

12、。對偶變量的值表示第i種資源的邊際價值，稱為影子價值?？梢园褜ε紗栴}的解Y定義為每增加一個單位的資源引起的目標(biāo)函數(shù)值的增量。 2什么是資源的影子價格它與相應(yīng)的市場價格有什么區(qū)別答：若以產(chǎn)值為目標(biāo)，則是增加單位資源i對產(chǎn)值的貢獻(xiàn)，稱為資源的影子價格（Shadow Price）。即有“影子價格=資源成本+影子利潤”。因為它并不是資源的實際價格，而是企業(yè)內(nèi)部資源的配比價格，是由企業(yè)內(nèi)部資源的配置狀況來決定的，并不是由市場來決定，所以叫影子價格?？梢詫①Y源的市場價格與影子價格進(jìn)行比較，當(dāng)市場價格小于影子價格時，企業(yè)可以購進(jìn)相應(yīng)資源，儲備或者投入生產(chǎn)；當(dāng)市場價格大于影子價格時，企業(yè)可以考慮暫不購進(jìn)資源，

13、減少不必要的損失。3如何根據(jù)原問題和對偶問題之間的對應(yīng)關(guān)系，找出兩個問題變量之間、解及檢驗數(shù)之間的關(guān)系？答：（1）最優(yōu)性定理：設(shè)分別為原問題和對偶問題的可行解，且，則分別為各自的最優(yōu)解。（2）對偶性定理：若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，而且兩者的目標(biāo)函數(shù)值相等。（3）互補(bǔ)松弛性：原問題和對偶問題的松弛變量為和，它們的可行解為最優(yōu)解的充分必要條件是（4）對偶問題的最優(yōu)解對應(yīng)于原問題最優(yōu)單純形表中，初始基變量的檢驗數(shù)的負(fù)值。若對應(yīng)于原問題決策變量x的檢驗數(shù)，則對應(yīng)于原問題松弛變量的檢驗數(shù)。4已知線性規(guī)劃問題s.t. （1）求出該問題產(chǎn)值最大的最優(yōu)解和最優(yōu)值。（2）求出該問題的對偶問題的最

14、優(yōu)解和最優(yōu)值。（3）給出兩種資源的影子價格，并說明其經(jīng)濟(jì)含義；第一種資源限量由2變?yōu)?，最優(yōu)解是否改變？（4）代加工產(chǎn)品丁，每單位產(chǎn)品需消耗第一種資源2單位，消耗第二種資源3單位，應(yīng)該如何定價？解：（1）標(biāo)準(zhǔn)化，并列出初始單純形表41200b02831102/808611018/64120041/413/81/81/802013/265/41/43/412601/23/2-1/2022831100622011125020由最末單純性表可知，該問題的最優(yōu)解為：，即，最優(yōu)值為（2）由原問題的最末單純形表可知，對偶問題的最優(yōu)解和最優(yōu)值為：（3）兩種資源的影子價格分別為2、0，表示對產(chǎn)值貢獻(xiàn)的大??；第

15、一種資源限量由2變?yōu)?，最優(yōu)解不會改變。（4）代加工產(chǎn)品丁的價格不低于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é)模型，資源甲、乙、丙的影子價格是多少若工廠可在市場上買到原料丙，工廠是否應(yīng)該購進(jìn)該原料以擴(kuò)大生產(chǎn)（3）原料丙可利用量在多大范圍內(nèi)變化

16、，原最優(yōu)生產(chǎn)方案中生產(chǎn)產(chǎn)品的品種不變（即最優(yōu)基不變）（4）若產(chǎn)品B的價格下降了0.5元，生產(chǎn)計劃是否需要調(diào)整？解：（1）設(shè)分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量，建立線性規(guī)劃模型s.t. 初始單純形表1534000b08002312100800/30120054340101200/40100034530011000/41534000最末單純形表1534000b01001/40-13/4011/4-1420020-2101-15100-3/4111/400-3/41-13/40-11/400-1/4-1解得最優(yōu)解為：，最優(yōu)值（2）原問題的對偶問題的數(shù)學(xué)模型為 s.t.解得影子價格分別為2、1.25、2.

17、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)品資源 資源消耗資源成本資源擁有量甲乙元/單位資源材料（公斤）60502004200設(shè)備C（小時）3040103000設(shè)備D（小時）6050204500據(jù)市場分析，甲、乙產(chǎn)品銷售價格分

18、別為13700元和11640元，試確定獲利最大的產(chǎn)品生產(chǎn)計劃。（1）設(shè)產(chǎn)品甲的計劃生產(chǎn)量為，產(chǎn)品乙的計劃生產(chǎn)量為，試建立其線性規(guī)劃的數(shù)學(xué)模型；若將材料約束加上松弛變量，設(shè)備C約束加上松弛變量，設(shè)備D約束加上松弛變量，試化成標(biāo)準(zhǔn)型。（2）利用LINDO軟件求得：最優(yōu)目標(biāo)函數(shù)值為18400，變量的最優(yōu)取值分別為，則產(chǎn)品的最優(yōu)生產(chǎn)計劃方案是什么？并解釋的經(jīng)濟(jì)意義。（3）利用LINDO軟件對價值系數(shù)進(jìn)行敏感性分析，結(jié)果如下：Obj Coefficient RangesVariableCurrent CoefAllowable IncreaseAllowable Decrease200882024026

19、.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 RangesResourceCurrent RhsAllowable IncreaseAllowable Decrease材料4200300450設(shè)備C3000360900設(shè)備D4500Infinity300試問非緊缺資源最多可以減少到多少，而緊缺資源最多可以增加到多少？解：（1）建立的線性規(guī)劃模型為s.t. 將其標(biāo)準(zhǔn)化s.t. （2）甲生產(chǎn)20件，乙生產(chǎn)60件，材料和設(shè)

20、備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ī)劃也沒有可行解。（2）定界過程。對于極大化的整數(shù)規(guī)劃問題，當(dāng)前所有未分枝子問題中最大的目標(biāo)函數(shù)值為整數(shù)規(guī)劃問題上界；在滿足整數(shù)約束的子問題的解中，最

21、大的目標(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ù)條件的變量作為分枝變量，若的值是，構(gòu)造兩個新的約束條件：或，分別并入相應(yīng)的數(shù)學(xué)模型中，構(gòu)成兩個子問題。對任一個子問題，轉(zhuǎn)步驟（1）3試用分枝定界法求如下線性規(guī)劃：s.t.解：最優(yōu)整數(shù)解為：4有4名職工，由于各人的能力不同，每個人做各項工作所用的時間不同，所花費時間如表

22、37所示。表37（單位：分鐘）時間 任務(wù)人員ABCD甲15182124乙19232218丙26171619丁19212317問指派哪個人去完成哪項工作，可使總的消耗時間最少？解：設(shè)，為個人i對于任務(wù)j的時間耗費矩陣，則建立整數(shù)規(guī)劃模型為：s.t. 解得：，其余均為零，即任務(wù)A由乙完成，任務(wù)B由甲完成，任務(wù)C由丙完成，任務(wù)D由丁完成。5某部門一周中每天需要不同數(shù)目的雇員：周一到周四每天至少需要50人，周五至少需要80人，周六周日每天至少需要90人，先規(guī)定應(yīng)聘者需連續(xù)工作5天，試確定聘用方案，即周一到周日每天聘用多少人，使在滿足需要的條件下聘用總?cè)藬?shù)最少。解：設(shè)表示在第i天應(yīng)聘的雇員人數(shù)（i=1,

23、2,3,4,5,6,7）。數(shù)學(xué)模型為s.t.解得：第4章 目標(biāo)規(guī)劃（復(fù)習(xí)思考題）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ù)三種電腦三種電

24、腦的純利潤分配不同的加權(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型號的電腦為（臺），為裝配線正常生產(chǎn)時間未利用數(shù)，為裝配線加班時間，希望裝配線正常生產(chǎn)，避免開工不足，因此裝配線目標(biāo)約束為（2）銷售目標(biāo)優(yōu)先滿足老客戶的需求，并根據(jù)三種電腦的純利潤分配不同的權(quán)因子，A，B，C三種型號的電腦每小時的利潤是，因此，老

25、客戶的銷售目標(biāo)約束為再考慮一般銷售。類似上面的討論，得到（3）加班限制首先是限制裝配線加班時間，不允許超過200小時，因此得到其次裝配線的加班時間盡可能少，即寫出目標(biāo)規(guī)劃的數(shù)學(xué)模型s.t.經(jīng)過LINGO軟件計算，得到，裝配線生產(chǎn)時間為1900小時，滿足裝配線加班不超過200小時的要求。能夠滿足老客戶的需求，但未能達(dá)到銷售目標(biāo)。銷售總利潤為100×1000+55×1440+80×2520=380800（元）。2已知3個工廠生產(chǎn)的產(chǎn)品供應(yīng)給4個客戶，各工廠生產(chǎn)量、用戶需求量及從各工廠到用戶的單位產(chǎn)品的運輸費用如表43所示。由于總生產(chǎn)量小于總需求量，上級部門經(jīng)研究后，制

26、定了調(diào)配方案的8個目標(biāo)，并規(guī)定了重要性的次序。表43 工廠產(chǎn)量用戶需求量及運費單價（單位：元）工廠 用戶1234生產(chǎn)量152672354634523需求量（單位）200100450250第一目標(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，