運(yùn)籌學(xué) 復(fù)習(xí)練習(xí)題

1、串講練習(xí)題1. 某公司生產(chǎn)的產(chǎn)品A，B，C和D都要經(jīng)過(guò)下列工序：刨、立銑、鉆孔和裝配。已知每單位產(chǎn)品所需工時(shí)及本月四道工序可用生產(chǎn)時(shí)間如下表所示：刨立銑鉆孔裝配A0.52.00.53.0B1.01.0.0.51.0.C1.01.01.02.0D0.51.01.03.0可用生產(chǎn)時(shí)間（小時(shí)）1800280030006000又知四種產(chǎn)品對(duì)利潤(rùn)貢獻(xiàn)及本月最少銷售需要單位如下：產(chǎn)品最少銷售需要單位元/單位A1002B6003C5001D4004問(wèn)該公司該如何安排生產(chǎn)使利潤(rùn)收入為最大？（建立模型）2已知線性規(guī)劃問(wèn)題 min z=2x1-x2+2x3 -x1+x2+x3=4 -x1+x2-x36 x10,x

2、20,x3無(wú)約束（1） 寫出其對(duì)偶問(wèn)題并化為標(biāo)準(zhǔn)型式。（2） 用單純形法求出原問(wèn)題的最優(yōu)解。3應(yīng)用對(duì)偶問(wèn)題性質(zhì)，求出下面問(wèn)題的最優(yōu)解。4.某混合飼料場(chǎng)為某種動(dòng)物配置飼料。已知此動(dòng)物的生長(zhǎng)速度與飼料中的三種營(yíng)養(yǎng)成分甲、乙、丙有關(guān)，且每頭動(dòng)物每天需要營(yíng)養(yǎng)甲85g、乙5g、丙15g?，F(xiàn)有五種飼料中都含有這三種營(yíng)養(yǎng)成分，每種飼料每公斤所含營(yíng)養(yǎng)成分及每種飼料成本如下表所示。求既滿足動(dòng)物生長(zhǎng)需要又使成本最低的飼料配方。飼料營(yíng)養(yǎng)甲/g營(yíng)養(yǎng)乙/g營(yíng)養(yǎng)丙/g成本/元10.500.100.08222.000.060.70633.000.040.35541.500.150.25450.800.200.0235.京成

3、畜產(chǎn)品公司計(jì)劃在市區(qū)的東西南北四區(qū)建立銷售門市部，擬議中有10個(gè)位置可供選擇，考慮到各地區(qū)居民的生活水平及居民居住密集度，規(guī)定：在東區(qū)由三個(gè)點(diǎn)至多選擇兩個(gè)；在西區(qū)由兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)由兩個(gè)點(diǎn)中至少選一個(gè)；在北區(qū)由三個(gè)點(diǎn)中至少選兩個(gè)。各點(diǎn)的設(shè)備投資及每年可獲利潤(rùn)由于地點(diǎn)不同都是不一樣的，預(yù)測(cè)情況如下表。但投資總額不能超過(guò)720萬(wàn)元，問(wèn)應(yīng)選擇哪幾個(gè)銷售點(diǎn)可使年利潤(rùn)為最大。投資額10012015080709080140160180利潤(rùn)364050222030254858616已知下表為求解某線性規(guī)劃問(wèn)題的最終單純形表，表中為松弛變量，問(wèn)題的約束條件為形式。5/201/211/205/21-1

4、/20-1/61/30-40-4-2（1） 寫出原線性規(guī)劃問(wèn)題的數(shù)學(xué)模型；（2） 寫出原問(wèn)題的對(duì)偶問(wèn)題；（3） 直接由上表寫出對(duì)偶問(wèn)題的最優(yōu)解。7已知線性規(guī)劃問(wèn)題 max z=2x1+x2 5x215 6x1+2x224x1+x2 5 x1,x20（1）寫出其對(duì)偶問(wèn)題并化為標(biāo)準(zhǔn)型式； （2）用單純形法求出原問(wèn)題的最優(yōu)解；唯一最優(yōu)解（3）根據(jù)最終單純形表寫出其對(duì)偶問(wèn)題的最優(yōu)解，三種資源的影子價(jià)格各為多少并說(shuō)明其涵義；（4）若第三種資源增加3單位，問(wèn)最優(yōu)解有何變化，資源的影子價(jià)格變?yōu)槎嗌佟?運(yùn)輸問(wèn)題課后習(xí)題3.3（1）（2）9指派問(wèn)題 課后習(xí)題5.710最小樹(shù)問(wèn)題 課后習(xí)題10.4，10.511最

5、短路問(wèn)題 課后習(xí)題10.6 10.712.最大流問(wèn)題：10.12,10.13部分答案：2解：（1）其對(duì)偶問(wèn)題為： 化成標(biāo)準(zhǔn)型式為：（2）原問(wèn)題的準(zhǔn)標(biāo)準(zhǔn)型為： 用大M法求解 Cj-2 -1 2 -2 M 0 cBxBb x2 x4 x5 x6 x7 M0X6x7461 1 1 -1 1 0 1 1 -1 1 0 1 46檢驗(yàn)數(shù)-2-M 1-M 2-M M-2 0 0-20X7421 1 1 -1 1 0 0 0 -2 2 -1 1-1檢驗(yàn)數(shù)0 1 0 -4 M+2 0-2-2X5511 1 0 0 1/2 1/2 0 0 -1 1 -1/2 1/2 檢驗(yàn)數(shù)0 1 0 0 M 2所以，原問(wèn)題的最優(yōu)

6、解為：4解：設(shè)為每千克混合飼料中所含5種飼料的重量 目標(biāo)函數(shù)為： 約束條件有：6解：（1）首先設(shè)a、b、c表示對(duì)應(yīng)原模型的價(jià)值系數(shù)，則由檢驗(yàn)數(shù)的計(jì)算公式，得解此方程組，得：a=6，b=-2，c=10再由單純形表與原模型標(biāo)準(zhǔn)型的特點(diǎn)，得有這兩個(gè)關(guān)系式，可得：所以：愿問(wèn)題的模型為：（2）由原問(wèn)題的模型，得到其對(duì)偶問(wèn)題模型： （3）由對(duì)偶理論，從原問(wèn)題的最終單純形表中，直接得到對(duì)偶問(wèn)題的最優(yōu)解：7（2）唯一最優(yōu)解 （3）其對(duì)偶問(wèn)題的最優(yōu)解為： 第一種資源影子價(jià)格為0，第二種資源為1/4，第三種資源為1/2 其含義為：每增加一個(gè)單位的第一種資源，最優(yōu)值不會(huì)增加，每增加一個(gè)單位的第二種資源，最優(yōu)值增加1/4，每增加一個(gè)單位的第三種資源，最優(yōu)值會(huì)增加1/2。所以要想增加最優(yōu)值，可以增加第二和第三種資源。 （4）第三種資源增加三個(gè)單位，= 新最優(yōu)解為：13有七個(gè)城市V1,V2,，V7其公路網(wǎng)如下圖所示，弧旁數(shù)字為該段公路的長(zhǎng)度，有一批貨物要從V1運(yùn)到V7，試用迪克斯特拉算法或雙標(biāo)號(hào)法求出走那條路距離最短。 用狄克斯特拉算法或雙標(biāo)號(hào)法標(biāo)號(hào) （7分）得到最短路路徑：V1V3V4V5V7（2分）最短路路權(quán)：10（1分）14.幾個(gè)工地之間建立一個(gè)局域網(wǎng)，由于條件不同，各工地間相連的費(fèi)用不同，如下圖所示，求A,B,C,D,E間