2019-2020年整理管理運籌學(xué)第二版課后習(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ù)項 h芝0, 決策變量滿足非負(fù)性.如果參加的這個非負(fù)變量取值為非零的話,那么說明該約束限定沒有約束力,對企業(yè)來說不是緊缺資源,所以稱為松弛變量；剩余變量取值為非零的話,那么說明

3、“況約束的左邊取值大丁右邊規(guī)劃值,出現(xiàn)剩余量.4. 試述線性規(guī)劃問題的可行解、根底解、基可行解、最優(yōu)解的概念及其相互關(guān)系.答：可行解：滿足約束條件 AX =b, X芝0的解,稱為可行解.基可行解：滿足非負(fù)性約束的基解,稱為基可行解可行基：對應(yīng)丁基可行解的基,稱為可行基.最優(yōu)解：使目標(biāo)函數(shù)最優(yōu)的可行解,稱為最優(yōu)解.最優(yōu)基：最優(yōu)解對應(yīng)的基矩陣,稱為最優(yōu)基.它們的相互關(guān)系如右圖所示：5. 用表格單純形法求解如下線性規(guī)劃.maxZ =4x1 x2 2x3_8x1 3x2 - x3 _ 2s.t. < 6x1 +x2 +x3 <8解：標(biāo)準(zhǔn)化 m a更=4x1 x2 - 2x3列出單純形表s.

4、t.8xi6x+ 3x2 十 x31 +x2 +x3X,x2,x3,十x4+ 乂5 乂4,乂5 N 0=2=8cj41200C BXbbxix2x3x4x0x42831102/80x58611018/6j412004xi1/413/81/81/80(1/4)/(1/8)0*513/265/41/4-3/41(13/2)/(1/4)01/23/2-1/202x32831100x56-2-20-11一12-50-20故最優(yōu)解為X* =(0,0,2,0,6)T ,即x1 =0,x2= 0,x3 =2 ,此時最優(yōu)值為Z(X*) =4 .6. 表115中給出了求極大化問題的單純形表,問表中 a!,a2,

5、Ci,C2,d為何值及變量屆丁哪一類型時有：1表中解為唯一最優(yōu)解；2表中解為無窮多最優(yōu)解之一；3 下一步迭代將以xi代替基變量x5; 4該線性規(guī)劃問題具有無界解；5該線性規(guī)劃問題無可行解.表1 15某極大化問題的單純形表CjGc2000QiCbXbbxix2x3x4x50*3d4a1000x42-1-50100x53a2-3001cc2000解：(1) d 芝0, g < 0,C2 <0 ;(2) d芝0,g苴0,c2 <0 (q,c2中至少有一個為零)；(3) c1?0,a2 >0, d a 3 ;4 a2(4) c2 >0,& £0;(5)

6、*為人工變量,且G為包含M的大丁零的數(shù),;或者X2為人工變量,4 a2且c2為包含M的大丁零的數(shù),ai A0,d?0.7. 用大M法求解如下線性規(guī)劃.maxZ = 5x1 3x2 6x3x1 +2x2 +x3 <182x1 +x2 +3x3 <16 s.t.x x2 x3 =10x,x2, x3 -0解：參加人工變量,進(jìn)行人造基后的數(shù)學(xué)模型如下:maxZ = 5x1 3x2 6x3 0x4 0x5 - Mx6x1 +2x2 +x3 +x4 =182x1 x2 3x3 x5 =16 s.t.x x2 x3 x6 = 10.xi -0 (i =1,2, ,6)列出單純形表Cj53600

7、-Me：CbXbbX1X2X3X4X5X610X41812110018/10X51621301016/3-MX61011100110/15+M3+M6+M0000X438/31/35/3011/3038/56X316/32/31/3101/3016-MX614/31/32/3001/3114/2%11 + M 13+ -M3001 2M300X411/20011/25/2一6X331/20101/21/263X271/21001/23/214a. j1/20003/235M20X4400111-35Xi610201-13X2401-10-12j00-10-2-1- M故最優(yōu)解為X*= (6,4

8、,0,4,0,0)T ,即x = 6, X2=4, X3=0,此時最優(yōu)值為Z(X*) =42.8A , B, C二個城市每年需分別供給電力320,250和350單位,由I：II兩個電站提供,它們的最大可供電量分別為 400單位和450單位,單位費用如表1 16所示.由丁需要量大-于可供量,決定城巾A的供給量可減少030單位,城市B的供給量不變,城市C的供給量不能少丁 270單位.試建立線性規(guī)劃模型,求將可供電量用完的最 低總費用分配方案.表1 16單位電力輸電費(單位：元)ABCI151822II212516解：設(shè)Xj為“第i電站向第j城市分配的電量 (i=1,2; j=1,2,3),建立模型

9、如下:maxZ =15xii 18x1222x13 21x2125x22 16x23X11 - x2 為3 = 400x21 x22x23 = 450x1 x21 _290s.t. «x1 x21 £320x2 , x22 250x3 x23 二 270x3 ' x23 350Xj 芝0,i =1,2;j =1,2,39. 某公司在3年的方案期內(nèi),有4個建設(shè)工程可以投資：工程I從第一年到第三 年年初都可以投資.預(yù)計每年年初投資,年末可收回本利120%,每年乂可以重新將所獲本利納入投資方案；工程II需要在第一年初投資,經(jīng)過兩年可收回本利150%, 乂可以重新將所獲本利

10、納入投資方案,但用丁該工程的最大投資不得超過20萬元；工程III需要在第二年年初投資,經(jīng)過兩年可收回本利160%,但用丁該工程的最大投資不得超過15萬元；工程IV需要在第三年年初投資,年末可收回本利 140%,但用丁該工程的 最大投資不得超過10萬元.在這個方案期內(nèi),該公司第一年可供投資的資金有 30萬元. 問怎樣的投資方案,才能使該公司在這個方案期獲得最大利潤？解：設(shè)x(1)表示第一次投資工程i,設(shè)x(2)表示第二次投資工程i,設(shè)x表示第三次投資工程i, (i=1,2,3,4),那么建立的線性規(guī)劃模型為 maxZ =1.2x1 1.6x31)1.4x41x1(1) + x21)苴 30x；2

11、) +x31)"2x1 +30f(1) -x21)xi(3) +xf =1公1(2) +1.5x21)+1.2x1(1) +30*-x21) -xi(2) -x31)s.t.,x21) 主 20x31W15x41) <10Lxi(1),xi(2),xi(3) Z0,i =1,2,3,4通過 LINGO 軟件計算得：妒) =10,x21) =20,x31) =0,xi=12,為(2) =44.10. 某家具制造廠生產(chǎn)五種不同規(guī)格的家具.每種家具都要經(jīng)過機(jī)械成型、打磨、 上漆幾道重要工序.每種家具的每道工序所用的時間、每道工序的可用時間、每種家具 的利潤由表1 17給出.問工廠應(yīng)如

12、何安排生產(chǎn),使總利潤最大？表1 17家具生廣工藝耗時和利潤表生產(chǎn)工序所需時間小時每道工序可用 時間小時12345成型346233600打磨435643950上漆233432800利潤白元2.734.52.53解：設(shè)x表示第i種規(guī)格的家具的生產(chǎn)量i=1,2,5,那么maxZ =2.7x1 3x2 4.5x3 2.5x4 3x53x1 +4x2 +6x3 +2x4 +3x5 壬 36004x1 +3x2 +5x3 +6x4 +4x5 3950 s.t.2x1 3x2 3x3 4x4 3x5 £ 2800為0,i =1,2, ,5通過 LINGO 軟件計算得：x1 =0,x2 =38,x3

13、 =254, x4 =0,x5 =642,Z =3181.11. 某廠生產(chǎn)甲、乙、丙三種產(chǎn)品,分別經(jīng)過A , B, C三種設(shè)備加工.生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時數(shù)、設(shè)備的現(xiàn)有加工水平及每件產(chǎn)品的利潤如表2 10所小表1 18產(chǎn)品生產(chǎn)工藝消耗系數(shù)甲乙丙設(shè)備水平A 小時111100B 小時1045600C 小時226300單位產(chǎn)品利潤元10641建立線性規(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的變化范圍

14、5如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品丙,試確定最優(yōu)方案的變化.解：1設(shè)X1,X2,X 3分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量,建立線性規(guī)劃模型max Z = 10x1 6x2 4x3x1 十 x2 +x3 壬10010x1 +4x2 +5x3 壬 600 s.t.2x1 2x2 6x3 三 300x,x2,x3 0標(biāo)準(zhǔn)化得maxZ =10x1 6x2 4x3 0x4 0x5 0x6x1 +x2 +x3 +x4 =10010x1 +4x2 +5x3 +x5 =600 s.t.2x1 2x2 6x3 x6 = 300= 732.入法2法3,乂4,乂5,乂6 0列出單純形表cj10640006iCBXbbx

15、ix2x3x4x5x60x41001111001000x6001045010600x300226001150a. j10640000x44003/51/211/100200/310xi6012/51/201/1001500x18006/5501/51150j02-10-106x2200/3015/65/31/6010xi100/3101/62/31/600x100004-201a :j008/310/32/30故最優(yōu)解為xi =100/3,x2 =200/3,x3 =0 , 乂由丁 xi,x2,x3取整數(shù),故四舍五入可得最優(yōu)解為 x1 =33, x2 =67,x3 =0,Zmax(2)產(chǎn)品丙的

16、利潤C(jī)3變化的單純形法迭代表如下:Cj106C30006iCBXbbxx2x3x4x5x66x2200/3015/65/31/6010x100/3101/62/31/600x100004-20100C3 20/310/32/30要使原最優(yōu)方案保持不變,只要.3 = C3 - 20 < 0,即C3苴62整6.67 .故當(dāng)產(chǎn)品丙每33件的利潤增加到大丁 6.67時,才值得安排生產(chǎn).如產(chǎn)品丙每件的利潤增加到6時,此時6<6.67,故原最優(yōu)方案不變.(3)由最末單純形表計算出,1C2 c1Ccr3 =1 c1 壬0,.4=一10+ C1 <0,cr5=1G 至0636解得6、ci,5

17、,即當(dāng)產(chǎn)品甲的利潤C(jī)i在6,15范圍內(nèi)變化時,原最優(yōu)方案保持不變"5/3-1/6 0、(4)由最末單純形表找出最優(yōu)基的逆為 8 = ；-2/3 1/6 0 ,新的最優(yōu)解為一20b5/3X； =Bb'= -2/3 2-1/61/60,'100+10q '、.600 I、300 J200 50q-100 -20q3(100 -20q)解得-4壬q苴5 ,故要保持原最優(yōu)基不變的q的變化范圍為,5.(5) 如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品丙,那么線性規(guī)劃模型變成maxZ =10x1 6x2 4x3x1 +x2 +x3?100 10x1 +4x2 +5x3 <60

18、0 s.t. <2x1+2x2+6x3300x3 芝 10xzx -0通過 LINGO 軟件計算得到：為=32,x2 =58,x3 =10,Z = 708.第2章 對偶規(guī)劃(復(fù)習(xí)思考題)1. 對偶問題和對偶向量(即影子價值)的經(jīng)濟(jì)意義是什么？答：原問題和對偶問題從不同的角度來分析同一個問題,前者從產(chǎn)品產(chǎn)量的角度來 考察利潤,后者那么從形成產(chǎn)品本身所需要的各種資源的角度來考察利潤,即利潤是產(chǎn)品 生產(chǎn)帶來的,同時乂是資源消耗帶來的.對偶變量的值表示第i種資源的邊際價值,稱為影子價值.可以把對偶問題的解Y定義為每增加一個單位的資源引起的目標(biāo)函數(shù)值的增量.2. 什么是資源的影子價格？它與相應(yīng)的市

19、場價格有什么區(qū)別？答：假設(shè)以產(chǎn)值為目標(biāo),那么yi是增加單位資源i對產(chǎn)值的奉獻(xiàn),稱為資源的影子價格(Shadow Price).即有“影子價格=資源本錢+影子利潤.由于它并不是資源的實際價 格,而是企業(yè)內(nèi)部資源的配比價格,是由企業(yè)內(nèi)部資源的配置狀況來決定的,并不是由 市場來決定,所以叫影子價格.可以將資源的市場價格與影子價格進(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分別

20、為原問題和對偶問題的可行解,且 cX = bTY, 那么X,Y分別為各自的最優(yōu)解.(2) 對偶性定理：假設(shè)原問題有最優(yōu)解,那么對偶問題也有最優(yōu)解,而且兩者的目 標(biāo)函數(shù)值相等.(3) 互補(bǔ)松弛性：原I可題和對偶I可題的松弛變量為 Xs和Ys,它們的可行解X ,Y 為最優(yōu)解的充分必要條件是 Y*Xs =0,YsX* = 0 .(4) 對偶問題的最優(yōu)解對應(yīng)丁原問題最優(yōu)單純形表中,初始基變量的檢驗數(shù)的負(fù)值.假設(shè)-Ys對應(yīng)丁原問題決策變量x的檢驗數(shù),那么-丫對應(yīng)丁原問題松弛變量Xs的檢驗4. 線性規(guī)劃問題maxZ =4x1 x2 2x3"8x1 +3x2 + x3壬2 (第一種資源)s.t.

21、< 6x1 +x2 +x3 菱8 (第二種資源)xi, x2, x3 芝 0(1) 求出該問題產(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)品需消耗第一種資源2單位,消耗第二種資源3單位,應(yīng)該如何定價？解：(1)標(biāo)準(zhǔn)化,并歹0出初始單純形表cj41200CbXbbxix2x3x4x50x42831102/80x8611018/6a. j412004xi1/413/81/81/8020x513/265/41/43/4126j01/23/2-1

22、/202x32831100x6-2-20-116 j一12-50-20由最末單純性表可知,該問題的最優(yōu)解為：X* = (0,0,2,0,6)T,即x1 = 0, x2 = 0,x3 = 2 , 最優(yōu)值為Z = 4 .(2) 由原問題的最末單純形表可知,對偶問題的最優(yōu)解和最優(yōu)值為:y = 2, y2 = 0,w = 4 -(3) 兩種資源的影子價格分別為2、0,表示對產(chǎn)值奉獻(xiàn)的大??；第一種資源限量 由2變?yōu)?,最優(yōu)解不會改變.(4) 代加工產(chǎn)品丁的價格不低丁 2x2+0x3 = 4.5. 某廠生產(chǎn)A , B, C, D4種產(chǎn)品,有關(guān)資料如表2-6所示.表26資源消耗資源產(chǎn)品資源供給量(公斤)原料

23、本錢(元/公斤)ABCD甲23128002.0乙543412001.0丙345310001.5單位產(chǎn)品售價(元)14.52115.516.5(1) 請構(gòu)造使該廠獲利潤最大的線性規(guī)劃模型,并用單純形法求解該問題(不計 加工本錢).(2) 該廠假設(shè)出租資源給另一個工廠,構(gòu)成原問題的對偶問題,列出對偶問題的數(shù) 學(xué)模型,資源甲、乙、丙的影子價格是多少？假設(shè)工廠可在市場上買到原料丙,工廠是否 應(yīng)該購進(jìn)該原料以擴(kuò)大生產(chǎn)？(3) 原料丙可利用量在多大范圍內(nèi)變化,原最優(yōu)生產(chǎn)方案中生產(chǎn)產(chǎn)品的品種不變 (即最優(yōu)基不變)？(4) 假設(shè)產(chǎn)品B的價格下降了 0.5元,生產(chǎn)方案是否需要調(diào)整？解：(1)設(shè)Xi,X2,X3,

24、X4分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量,建立線性規(guī)劃模型max Z = x1 5x2 3x3 4x42x1 +3x2 +x3 +2x4?8005x1 +4x2 +3x3 +4x4 9200 s.t.3x1 4x2 5x3 3x4 £1000xi -0,i =1,2,3,4初始單純形表Cj1534000eCbXbbX1X2X3X4X5X6X7u i0X58002312100800/30X6120054340101200/40X7100034530011000/41534000最末單純形表cj1534000ACBXbbXiX2X3X4X5X6X7°i0X51001/40-13/40

25、11/4-14X420020-2101-15X2100-3/4111/400-3/41CT . j-13/40-11/400-1/4-1解得最優(yōu)解為：X =(0,100,0,200,100)T ,最優(yōu)值 Z =1300 .(2) 原問題的對偶問題的數(shù)學(xué)模型為min w = 800y1 1200y2 1000y32y +5y2 +3y3 芝13y +4y2 +4y3 芝 5s.t. « y1 +3y2 +5y3 芝12y +4y2 +3y3 芝 4y,y2, y3 -0解得影子價格分另U為2、1.25、2.5.比照市場價格和影子價格,當(dāng)市場價低丁影子 價格時購進(jìn).(3) 原料丙可利用量

26、在900,1100范圍內(nèi)變化,原最優(yōu)生產(chǎn)方案中生產(chǎn)產(chǎn)品的品種 不變(即最優(yōu)基不變).(4) 假設(shè)產(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所小.表2-7資源消耗與資源本錢表產(chǎn)品資源資源消耗資源本錢資源擁有量甲乙元/單位資源材料(公斤)60502004200設(shè)備C (小時)3040103000設(shè)備D (小時)6050204500據(jù)市場分析,甲、乙產(chǎn)品銷售價格分別為 13700元和11640元,試確定獲利最大的 產(chǎn)品生產(chǎn)方

27、案.(1) 設(shè)產(chǎn)品甲的方案生產(chǎn)量為 ,產(chǎn)品乙的方案生產(chǎn)量為X2,試建立其線性規(guī)劃 的數(shù)學(xué)模型；假設(shè)將材料約束加上松弛變量 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* =0,X4 =0,X5 =300 ,那么產(chǎn)品的最優(yōu)生產(chǎn)方案方案是什么？并解釋 x3 =0, x4 =0, x5 =300 的經(jīng)濟(jì)意義.(3) 利用LINDO軟件對價值系數(shù)進(jìn)行敏感性分析,結(jié)果如下：Obj Coefficient RangesVariableCurrent CoefAllo

28、wable IncreaseAllowable DecreaseXi2008820X224026.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試問非緊缺資源最多可以減少到多少,而緊缺資源最多可以增加到多少?解：

29、(1)建立的線性規(guī)劃模型為maxZ =200x1 240x260x1+50X2420030x1+40X23000 s.t.60xi 50x2 三 4500xi,x2 -0將其標(biāo)準(zhǔn)化maxZ =200x1 240x2"60xi +50x2 +x3 =420030x1 +40x2 +x4 =3000 s.t.60x150x2 x5 =4500為 _0,i =1,2,5(2) 甲生產(chǎn)20件,乙生產(chǎn)60件,材料和設(shè)備C充分利用,設(shè)備D剩余600單位(3) 甲上升到13800需要調(diào)整,乙下降60不用調(diào)整.(4) 非緊缺資源設(shè)備D最多可以減少到300,而緊缺資源一材料最多可以增加到300,緊缺資

30、源一設(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ī)劃問題.假設(shè)相應(yīng)的線性 規(guī)劃問題沒有可行解,停止計算,這時原整數(shù)規(guī)劃也沒有可行解.(2) 定界過程.對丁極大化的整數(shù)規(guī)劃問題,當(dāng)前所有未分枝子問題中最大的目 標(biāo)函數(shù)值為整數(shù)規(guī)劃問題上界；在滿足整數(shù)約束的子問題的解中,最大的目標(biāo)函數(shù)值為 整數(shù)規(guī)劃問題的下界.當(dāng)上下界相同時,那么已得最優(yōu)解；否那么,轉(zhuǎn)入剪枝過程.(3) 剪枝過程.在下述情況下剪除這些分枝：假設(shè)某一子問題相應(yīng)的線性

31、規(guī)劃問 題無可行解；在分枝過程中,求解某一線性規(guī)劃所得到的目標(biāo)函數(shù)值 Z不優(yōu)丁現(xiàn)有下 界.(4) 分枝過程.當(dāng)有多個待求分枝時,應(yīng)先選取目標(biāo)函數(shù)值最優(yōu)的分枝繼續(xù)進(jìn)行分枝.選取一個不符合整數(shù)條件的變重 x作為分枝變重,右Xi的值是bi ,構(gòu)造兩個新的約束條件：Xi <bi成為芝bi+1,分力U并入相應(yīng)的數(shù)學(xué)模型中,構(gòu)成兩個子I可題.對任一個子問題,轉(zhuǎn)步驟(1).3. 試用分枝定界法求如下線性規(guī)劃:maxZ = 40x1 90x29x1 +7x2 壬 567X1 +20X2 壬70 s.t.x,x2 0x1, x2取整數(shù)解：xl = 4. jci = 2.z 340最優(yōu)整數(shù)解為：x1 =上界

32、：349h.界:340 卜界：妃4. 有4名職工,由丁各人的水平不同,每個人做各項工作所用的時間不同,所花費時間如表37所小表3-7 單位：分鐘間壬務(wù)ABCD甲：5：82：24乙：92322：8丙26：7：6：9丁：92：23：7問指派哪個人去完成哪項工作,可使總的消耗時間最少？解：設(shè)x =0 "*%炊3成 *為個人1對于任務(wù)j的時間消耗矩陣,那么建立整數(shù)規(guī)劃模型為：44min Z _ xij tij'4£ xij =1id：4s.t. < Z xij =：jmXij =0或：,i, j =：,2,3,4解得：X：2 =：,X2： =：,X33 =：,X44

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

34、2 +x3 +x4 +x7 芝50s.t.x1 +x2 +x3 +x4 +x5 芝80x2 +x3 +x4 +x5 +x6 芝 90x3 +x4 +x5 +x6 +x7 芝 90為芝 0,i =1,2,7xi取整數(shù),i =1,2,7解得：x1= 0, x2 = 4, x3= 32, x4= 10, x5= 34, x6= 10,x7= 4, Z = 94.第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)時間是每月170

35、0小時,公司營業(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ù)三種電腦三種電腦的純利潤分配不同的加權(quán)系數(shù)；第三目標(biāo)：限制裝配線加班時間,最好不超過200小時；第四目標(biāo)：滿足各種型號電腦的銷售目標(biāo),A , B, C三種型號分別為100臺、120臺、100臺,再根據(jù)三種電腦的純利潤分配不同的加權(quán)系數(shù)；第五目標(biāo)：裝配線加班時間盡可能少.請

36、列出相應(yīng)的目標(biāo)規(guī)劃模型,并用 LING.軟件求解.解：建立目標(biāo)約束.(1) 裝配線正常生產(chǎn)設(shè)生產(chǎn)A, B, C型號的電腦為*,X2,X3 (臺),d為裝配線正常生產(chǎn)時間未利用數(shù),d為裝配線加班時間,希望裝配線正常生產(chǎn),防止開工缺乏,因此裝配線目標(biāo)約束為mind5x1 8x2 12x3 df-d； =1700(2) 銷售目標(biāo)優(yōu)先滿足老客戶的需求,并根據(jù)三種電腦的純利潤分配不同的權(quán)因子,A , B , C三種型號的電腦每小時的利潤是 ,1440,2520,因此,老客戶的銷售目標(biāo)約束為 5812min20d2一 18df 21d4xi df-d =50x2 d3-d3 =50x3 d-d4 =80再

37、考慮一般銷售.類似上面的討論,得到min20d5 18d6一 21d7"Xi dr-ds =100x2 d-d =120x3 d7-d7 =1003加班限制首先是限制裝配線加班時間,不允許超過 200小時,因此得到mind85xi 8x2 12x3 dr-d8 =1900其次裝配線的加班時間盡可能少,即mind1 5x1 8x2 12x3 d-d=1700寫出目標(biāo)規(guī)劃的數(shù)學(xué)模型minG = Rd+ P2 (20d2+18d+ 21dQ + Rd：+R (20d廠+ 18d廠 + 21dD + Rd,5x +8x2 +12x3 +d-dr = 1700x +d2-d； = 50x2 +

38、d3-d3+ = 50x3 +d-d： = 80x % +d5d5+=100s.t. <+x2 +d6-d6 =120x3 扣7一2十=1005x +8x2 +12x3 +d7+ = 1900為芝0,i =1,2d,di 0,l =1,2, ,8經(jīng)過LINGO軟件計算,得到x =100,x2 =55或=80,裝配線生產(chǎn)時間為1900小時,滿足裝配線加班不超過200小時的要求.能夠滿足老客戶的需求,但未能到達(dá)銷售 目標(biāo).銷售總利潤為 100X1000+55X1440+80X2520=380800 元.2.3個工廠生產(chǎn)的產(chǎn)品供給給 4個客戶,各工廠生產(chǎn)量、用戶需求量及從各 工廠到用戶的單位產(chǎn)

39、品的運輸費用如表 4-3所示.由丁總生產(chǎn)量小丁總需求量,上級 部門經(jīng)研究后,制定了調(diào)配方案的 8個目標(biāo),并規(guī)定了重要性的次序.表4-3工廠產(chǎn)量一用戶需求量及運費單價單位：元目戶1234生廣里152672354634523需求量(單位)200100450250第一目標(biāo)：用戶4為重要部門,需求量必須全部滿足；第二目標(biāo)：供給用戶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ī)劃模型,并用 LING.軟件求解.解：假設(shè)三個工廠對應(yīng)的生產(chǎn)量分別為300, 200, 400.(1)求解原運輸問題由丁總生產(chǎn)量小丁總需求量,虛設(shè)工廠 4,生產(chǎn)量為100個單位,到各個用戶間的 運費單價為0.用LINGO軟件求解,得到總運費是2950元,運輸方