2022年規(guī)劃數(shù)學(xué)第三版課后習(xí)題答案習(xí)題

1、習(xí) 題 1 1 用圖解法求解下列線性規(guī)劃問題，并指出問題具有唯一最優(yōu)解、無(wú)窮最優(yōu)解、 無(wú)界解還是無(wú)可行解。0 xx42x4x66x4x3x2xminz)a(21212121，0 x,x124x3x2x2x2x3xmaxz)b(212121218x310 x512010 x6xxxmaxz)c(2121210 x,x23x2x2x2x6x5xmaxz)d(21212121答案：(a)唯一解3*,)5.0,75.0(*zxt); (b) 無(wú)可行解 ; (c)唯一解16*,)6,10(*zxt); (d)無(wú)界解）2 用單純形法求解下列線性規(guī)劃問題。0 x,x82x5x94x3x5x10 xmaxz)

2、a(212121210 x,x5xx242x6x155xx2xmaxz)b(212121221答案：(a)唯一解5.17*,)5.1 , 1(*zxt)， 對(duì)偶問題5.17*,)786.1 ,357.0(*wyt; (b)唯一解5.8*,)5. 1, 5. 3(*zxt） ，5.8*,)5.0,25.0, 0(*wyt3 用大 m 法和兩階段法求解下列線性規(guī)劃問題，并指出屬于哪一類解。0 xxx0 x2x2x2x6xxx2xx2xmaxz)a(3,2,132313213210 x,x,x62x3x82x4xxx3x2xminz)b(32121321321答案：(a)無(wú)界解； (b)唯一解8*,

3、)0, 8. 1, 8. 0(*zxt)，對(duì)偶問題8*,)0, 1(*wyt4 已知線性規(guī)劃問題的初始單純形表（如表1-54 所示）和用單純形法迭代后得到的表（如表 1-55 所示）如下，試求括弧中未知數(shù)al 的值。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁(yè)，共 10 頁(yè) - - - - - - - - -表 1-54 初始單純形表b x1 x2 x3 x4 x5x4 6 (b) (c) (d) 1 0 x5 1 -1 3 (e) 0 1 cj-zj (a) -1 2 0 0 表 1-55 單純形法迭代后的表b x1 x2 x3 x4 x

4、5x1 (f) (g) 2 -1 1/2 0 x5 4 (h) (i) 1 1/2 1 cj-zj 0 -7 (j) (k) (l) 表 1-55 基變量 x1列向量011p，所以 g=1,h=0 （2）初始表,jpb某步表jpbbb11,有已知表查出12/102/11b, 341612/102/141fffbb201112/102/10111bbpb5,42312/102/1221icicipb2,21112/102/11131ededpb（ 3）初始表主元行（-主元檢驗(yàn)數(shù) /主元）加到檢驗(yàn)數(shù)行得下一步表的檢驗(yàn)數(shù)行。表 1-54 第一行系數(shù)（-a/b）+表 1-54 檢驗(yàn)數(shù)行 =表 1-54

5、 檢驗(yàn)數(shù)行即：0,21,2,712lakjaa故：0,23, 5, 3lkja。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁(yè)，共 10 頁(yè) - - - - - - - - -5 某廠生產(chǎn)、三種產(chǎn)品，都分別經(jīng)a、b 兩道工序加工。設(shè)a 工序可分別在設(shè)備a1或 a2上完成，有b1、b2、b3三種設(shè)備可用于完成b 工序。已知產(chǎn)品可在a、b 任何一種設(shè)備上加工；產(chǎn)品可在任何規(guī)格的a 設(shè)備上加工，但完成b 工序時(shí)，只能在b1設(shè)備上加工； 產(chǎn)品只能在a2與 b2設(shè)備上加工。 加工單位產(chǎn)品所需工序時(shí)間及其他各項(xiàng)數(shù)據(jù)見下表 1-56，試安排最優(yōu)生產(chǎn)計(jì)劃，使

6、該廠獲利最大。表 1-56 產(chǎn)品的有關(guān)數(shù)據(jù)表設(shè)備產(chǎn)品設(shè)備有效臺(tái)時(shí)設(shè)備加工費(fèi)（元 /小時(shí)）a1a2b1b2b35 7 6 4 7 10 9 812 116 000 10 000 4 000 7 000 4 000 0.05 0.03 0.06 0.11 0.05 原料費(fèi)（元 /件）售價(jià)（元 /件）0.25 1.25 0.35 2.00 0.50 2.80 6 一家糖果商店出售三種不同品牌的果仁糖，每個(gè)品牌含有不同比例的杏仁、核桃仁、 胡桃仁。為了維護(hù)商店的質(zhì)量信譽(yù)，每個(gè)品牌中所含有的果仁的最大、最小比例是必須滿足的，如下表 1-57 所示：表 1-57 每個(gè)品牌中所含有的果仁的比例表品牌含量需求

7、每磅售價(jià)（美元）普通腰果仁不超過(guò)20% 胡桃仁不低于40% 核桃仁不超過(guò)25% 杏仁沒有限制0.89 豪華腰果仁不超過(guò)35% 杏仁不低于40% 核桃仁、胡桃仁沒有限制1.10 藍(lán)帶腰果仁含量位于30%50%之間杏仁不低于30% 核桃仁、胡桃仁沒有限制1.80 表 1-58 列出了商店從供應(yīng)商每周能夠得到的每類果仁的最大數(shù)量和每磅的價(jià)格：表 1-58 每類果仁的最大數(shù)量和每磅的價(jià)表果仁類型每磅價(jià)格（美元）每周最大供應(yīng)量（磅）杏仁0.45 2000 核桃仁0.55 4000 腰果仁0.70 5000 胡桃仁0.50 3000 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - -

8、- - - - 第 3 頁(yè)，共 10 頁(yè) - - - - - - - - -商店希望確定每周購(gòu)進(jìn)杏仁、核桃仁、腰果仁、胡桃仁的數(shù)量，使周利潤(rùn)最大。建立數(shù)學(xué)模型，幫助該商店管理人員解決果仁混合的問題。7 寫出下列線性規(guī)劃問題的對(duì)偶問題。無(wú)約束321321321321321x0,x,x53x4xx33xx2x24x3xx4x2x2xminz)a()n, 1nj (x)nn, 1j (0 x)m, 1mi (bxa)mm, 1i (bxaxcmaxz)b(1j1j1in1jjij1in1jjijn1jjj無(wú)約束答案：（a）無(wú)約束321321321321321x0,x,x43x3y4y24yy3y2y

9、2yy5y3y2ymax（b）)m, 1i (v)n, 1i (0u)n,.,1nj (cvaua)nn, 1j (cvauavbubmin1i1i1jm1im1miiijiij1jm1im1miiijiijm1miiim1iii111111mm無(wú)約束精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁(yè)，共 10 頁(yè) - - - - - - - - -8 已知線性規(guī)劃問題：0 xxx1xx2x2xxxxxmaxz32132132121，試應(yīng)用對(duì)偶理論證明上述線性規(guī)劃問題最優(yōu)解為無(wú)界。答案：顯然t(0,0,0)x為該問題的可行解，其對(duì)偶問題為：0yy

10、0yy1yy12yyyy2min2121212121，顯然第一個(gè)約束與變量非負(fù)要求矛盾，故對(duì)偶問題無(wú)可行解。由無(wú)界性該問題最優(yōu)解為無(wú)界。9 已知線性規(guī)劃問題：)4, 1j (0 x)4(9xxx)3(6xxx)2(6x2x) 1(8x3xxxx4x2xmaxzj321432214214321要求： （1）寫出其對(duì)偶問題； （2）已知原問題最優(yōu)解為x*=(2,2,4,0)t，試根據(jù)對(duì)偶理論求出對(duì)偶問題最優(yōu)解。答案：對(duì)偶問題精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁(yè)，共 10 頁(yè) - - - - - - - - -)4, 1j (0y(4)1

11、yy(3)1yy(2)4yyy3y(1)2y2yy9yy66y8yminj314343214214321設(shè)對(duì)偶問題的最優(yōu)解為),(*4*3*2*1*yyyyy將 x*=(2,2,4,0)t代入原問題，約束（4）為嚴(yán)格不等式（即x*s1，x*s2，x*s3）0） ，由互補(bǔ)松弛性， y*4=0。又因?yàn)閤*1=2,x*2=2,x*3 =4 都大于 0，由互補(bǔ)松弛性，對(duì)偶問題對(duì)應(yīng)（1）-（3）約束為等式， （即 y*s1= y*s2 =y*s3=0）故有(3)1y(2)4yy3y(1)22yy*1*2*3321，解得 對(duì)偶問題的最優(yōu)解為)0, 1 , 5/3,5/4(*yy。10 已知線性規(guī)劃問題：0

12、 x,x,x42xx6xxxxx2xmaxz32121321321先用單純形法求出最優(yōu)解，再分析在下列條件單獨(dú)變化的情況最優(yōu)解的變化。（1）目標(biāo)函數(shù)變?yōu)?21x3x2xmaxz；（2）約束右端項(xiàng)由46變?yōu)?3；（3）增添一個(gè)新的約束條件：22xx31。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 6 頁(yè)，共 10 頁(yè) - - - - - - - - -答案：最終表cj 2 -1 1 0 0 b cb xb x1 x2 x3 x4 x5 2 x10 x51 1 1 1 0 0 3 1 1 1 6 10 j0 -3 -1 -2 0 該問題的最優(yōu)解tx)

13、10,0, 0,0,6(*，最優(yōu)值1262* z對(duì)偶問題的最優(yōu)解)2, 1 , 3,0,2(*y，最優(yōu)值1226*（1）目標(biāo)函數(shù)中非基變量2x的系數(shù)2c由 -1 變?yōu)?3 重新計(jì)算2x的檢驗(yàn)數(shù)20131)02(322jbpcc最優(yōu)解發(fā)生變化，將2x的檢驗(yàn)數(shù)12，系數(shù)3c2代入最終表，用單純形法求解之，見下表cj 2 3 1 0 0 b cb xb x1 x2 x3 x4 x5 2 x10 x51 1 1 1 0 0 3 1 1 1 6 10* j0 （1）-1 -2 0 2 x13 x21 0 2/3 2/3 -1/3 0 1 1/3 1/3 1/3 8/3 10/3 j0 0 -4/3 -7

14、/3 -1/3 該問題的最優(yōu)解tx)0,0 ,0 ,3/10,3/8(*，最優(yōu)值3463103382* z對(duì)偶問題的最優(yōu)解) 3/4, 0,0, 3/1 , 3/7(*y,最優(yōu)值346314376*（2）0373243313131321bb，故最優(yōu)基不變精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 7 頁(yè)，共 10 頁(yè) - - - - - - - - -最優(yōu)解為tx)0 ,0, 0, 3/7 ,3/2(*，最優(yōu)值325373322*z（3）最優(yōu)解tx)10, 0,0 ,0 ,6(*不滿足新加的約束將約束化為等式，選松弛變量作為基變量得-2x2xx6

15、31將其添加到最終表得過(guò)渡表，然后將第一行乘-1 加到第三行將基變量x1的系數(shù)列向量化為單位向量cj 2 -1 1 0 0 0 b cb xb x1 x2 x3 x4 x5 x6 2 x10 x5 0 x61 1 1 1 0 0 0 3 1 1 1 0 1 0 -2 0 0 1 6 10 -2 2 x10 x5 0 x61 1 1 1 0 0 0 3 1 1 1 0 0 -1 -3 -1 0 1 6 10 （-8）j0 -3 -1* -2 0 0 2 x10 x5 1 x31 2/3 0 2/3 0 1/3 0 8/3 0 2/3 1 1/3 0 1/3 1 1/3 0 -1/3 10/3 2

16、2/3 8/3 j0 -8/3 0 -5/3 0 -1/3 新的最優(yōu)解tx)3/22,0, 3/8 ,0 , 3/10(*，最優(yōu)值328383102*z11 用分支定界法求解下列整數(shù)規(guī)劃問題：(1) ，且為整數(shù)，0 xx369x4x357x5x3x2xmaxz21212121(2) 且為整數(shù),0 x,x305x6x165x2xxxmaxz2121212112 用隱枚舉法求解下列0-1 規(guī)劃問題：)5 , 1j (10 x35x3x6x11x83x4x-3x7x4x2xxx x3x2x5x2x3xmaxzj542154315432154321或xj=0 或 1，j = 1，2，3，4， 5 13

17、 某航運(yùn)公司承擔(dān)六個(gè)港口城市a、b、c、d、e、f 的四條固定航線的物資運(yùn)輸任務(wù)已知各條航線的起點(diǎn)、終點(diǎn)城市及每天航班數(shù)見表1-59。假定各條航線使用相同型號(hào)的船只，精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 8 頁(yè)，共 10 頁(yè) - - - - - - - - -又各城市之間的航程天數(shù)見表1-60。又知每條船只每次裝卸貨物的時(shí)間各需1 天，則該航運(yùn)公司至少應(yīng)配備多少條船,才能滿足所有航線的運(yùn)貨需求? 建立模型并用軟件求解。表 1-59 各條航線的起點(diǎn)、終點(diǎn)城市及每天航班數(shù)表航線起點(diǎn)終點(diǎn)每天航班1 2 3 4 e b a d d c f b 3

18、2 1 1 表 1-60 各城市之間的航程天數(shù)表終點(diǎn)起點(diǎn)a b c d e f a b c d e f 0 1 2 14 7 7 1 0 3 13 8 8 2 3 0 15 5 5 14 13 15 0 17 20 7 8 5 17 0 3 7 8 5 20 3 0 14 設(shè)某公司有五個(gè)人可以完成五項(xiàng)工作，每人做每項(xiàng)工作的用時(shí)如表1-61 所示。每人僅做一項(xiàng)工作，每項(xiàng)工作僅一人做。如何安排是用時(shí)最少？建立數(shù)學(xué)模型并用軟件求解表 1-61 每人完成任務(wù)的用時(shí)表單位：天工作人員a b c d e 人員甲12 7 9 7 9 人員乙8 9 6 6 6 人員丙7 17 12 14 9 人員丁15 14

19、 6 6 10 人員戊4 10 7 10 9 15 思考題（1）線性規(guī)劃問題在數(shù)學(xué)模型的形式、可行域的組成和最優(yōu)點(diǎn)的位置等方面與非線性規(guī)劃問題有什么不同？（2）如何理解線性規(guī)劃問題的求解其實(shí)就是可行域頂點(diǎn)的轉(zhuǎn)換方法？（3）線性規(guī)劃的基解、基可行解和最優(yōu)解之間有什么關(guān)系？（4）在解得轉(zhuǎn)換中，如何保證從一個(gè)基可行解轉(zhuǎn)換得到的仍然是一個(gè)基可行解？（5）在解的轉(zhuǎn)換中，如何保證目標(biāo)函數(shù)的值不僅下降，而且下降得最多？（6）在單純形算法中，如何選擇主元？主元可以是負(fù)的嗎？（7）線性規(guī)劃問題的約束條件是等式約束時(shí)，如何通過(guò)建立輔助規(guī)劃問題的一個(gè)初始基本可行解？（9） 簡(jiǎn)述對(duì)偶單純形法的優(yōu)點(diǎn)、適用條件和求解步驟。(10) 試從經(jīng)濟(jì)上解釋對(duì)偶問題和對(duì)偶變量的含義。（11）分支定界法求解極大化問題時(shí)，任何一個(gè)可行解的目標(biāo)函數(shù)是否都是該問題目標(biāo)函數(shù)精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 9 頁(yè)，共 10 頁(yè) - - - - - - - - -值的下界？16 案例練習(xí)題目 ：木材的儲(chǔ)存和收購(gòu)售出最優(yōu)化問題問題背景 ：在實(shí)際的銷售模型中，往往會(huì)碰到一類由于每個(gè)時(shí)期的需求和供給量不同，而需要囤積貨物在后期高價(jià)出售的