運籌學(xué)教程黃皮版答案(第三章)[1]

1、 3.1 與一般線性規(guī)劃的數(shù)學(xué)模型相比，運輸問題與一般線性規(guī)劃的數(shù)學(xué)模型相比，運輸問題的數(shù)學(xué)模型具有什么特征的數(shù)學(xué)模型具有什么特征? 答：答： 1、運輸問題一定有有限最優(yōu)解。、運輸問題一定有有限最優(yōu)解。 2、約束系數(shù)只取、約束系數(shù)只取0或或1。 3、約束系數(shù)矩陣的每列有兩個、約束系數(shù)矩陣的每列有兩個1， 而且只有兩個而且只有兩個1。前。前m行中有一個行中有一個1，或，或n行中有一個行中有一個1。 4、對于產(chǎn)銷平衡的運輸問題，所有的約束都取、對于產(chǎn)銷平衡的運輸問題，所有的約束都取等式。等式。 3.2 運輸問題的基可行解應(yīng)滿足什么條件？將其運輸問題的基可行解應(yīng)滿足什么條件？將其填入運輸表中時有什么

2、體現(xiàn)？并說明在迭代計算過程填入運輸表中時有什么體現(xiàn)？并說明在迭代計算過程中對它的要求。中對它的要求。 解：運輸問題基可行解的要求是基變量的個數(shù)等解：運輸問題基可行解的要求是基變量的個數(shù)等于于m+n-1。填入表格時體現(xiàn)在數(shù)字格的個數(shù)也應(yīng)該等。填入表格時體現(xiàn)在數(shù)字格的個數(shù)也應(yīng)該等于于m+n-1。在迭代過程中，要始終保持數(shù)字格的個數(shù)。在迭代過程中，要始終保持數(shù)字格的個數(shù)不變。不變。 3.3 試對給出運輸問題初始基可行解的西北角法、試對給出運輸問題初始基可行解的西北角法、最小元素法和最小元素法和Vogel法進行比較，分析給出的解之質(zhì)量法進行比較，分析給出的解之質(zhì)量不同的原因。不同的原因。 解：用西北角

3、法可以快速得到初始解，但是由于解：用西北角法可以快速得到初始解，但是由于沒有考慮運輸價格，效果不好；最小元素法從最小的沒有考慮運輸價格，效果不好；最小元素法從最小的運輸價格入手，一開始效果很好，但是到了最后因選運輸價格入手，一開始效果很好，但是到了最后因選擇余地較少效果不好；擇余地較少效果不好； Vogel法從產(chǎn)地和銷地運價的法從產(chǎn)地和銷地運價的級差來考慮問題，總體效果很好，但是方法較復(fù)雜。級差來考慮問題，總體效果很好，但是方法較復(fù)雜。 3.4 詳細說明用位勢法詳細說明用位勢法(對偶變量法對偶變量法)求檢驗數(shù)的原求檢驗數(shù)的原理。理。 解：原問題的檢驗數(shù)也可以利用對偶變量來計解：原問題的檢驗數(shù)也

4、可以利用對偶變量來計算算 ：njmivucjiijij,2, 1;,2, 1)( 其中，其中，ui和和vj就是原問題約束對應(yīng)的對偶變量。由于就是原問題約束對應(yīng)的對偶變量。由于原問題的基變量的個數(shù)等于原問題的基變量的個數(shù)等于m+n-1。所以相應(yīng)的檢驗。所以相應(yīng)的檢驗數(shù)就應(yīng)該等于數(shù)就應(yīng)該等于0。即有：。即有：njmivucjiij,2, 1;,2, 10)( 由于方程有由于方程有m+n-1個，個， 而變量有而變量有m+n個。所以上個。所以上面的方程有無窮多個解。任意確定一個變量的值都可面的方程有無窮多個解。任意確定一個變量的值都可以通過方程求出一個解。然后再利用這個解就可以求以通過方程求出一個解。

5、然后再利用這個解就可以求出非基變量的檢驗數(shù)了。出非基變量的檢驗數(shù)了。 3.5 用表上作業(yè)法求解運輸問題時，在什么情況用表上作業(yè)法求解運輸問題時，在什么情況下會出現(xiàn)退化解？當(dāng)出現(xiàn)退化解時應(yīng)如何處理？下會出現(xiàn)退化解？當(dāng)出現(xiàn)退化解時應(yīng)如何處理？ 解：當(dāng)數(shù)字格的數(shù)量小于解：當(dāng)數(shù)字格的數(shù)量小于m+n-1時，相應(yīng)的解就時，相應(yīng)的解就是退化解。如果出現(xiàn)了退化解，首先找到同時劃去的是退化解。如果出現(xiàn)了退化解，首先找到同時劃去的行和列，然后在同時劃去的行和列中的某個空格中填行和列，然后在同時劃去的行和列中的某個空格中填入數(shù)字入數(shù)字0。只要數(shù)字格的數(shù)量保持在。只要數(shù)字格的數(shù)量保持在m+n-1個的水平即個的水平即可

6、?？?。 3.6 一般線性規(guī)劃問題具備什么特征才能將其轉(zhuǎn)一般線性規(guī)劃問題具備什么特征才能將其轉(zhuǎn)化為運輸問題求解，請舉例說明?；癁檫\輸問題求解，請舉例說明。 解：如果線性規(guī)劃問題有解：如果線性規(guī)劃問題有“供供”和和“需需”的關(guān)系，的關(guān)系，并且有相應(yīng)的并且有相應(yīng)的“費用費用”，就可以考慮將線性規(guī)劃問題，就可以考慮將線性規(guī)劃問題轉(zhuǎn)成運輸問題求解。例如，生產(chǎn)滿足需求的問題。轉(zhuǎn)成運輸問題求解。例如，生產(chǎn)滿足需求的問題。 3.7 試判斷表試判斷表3-30和表和表3-31中給出的調(diào)運方案可中給出的調(diào)運方案可否作為表上作業(yè)法迭代時的基可行解否作為表上作業(yè)法迭代時的基可行解?為什么為什么? 答：都不是。數(shù)字格的數(shù)

7、量不等于答：都不是。數(shù)字格的數(shù)量不等于m+n-1。表表3-30銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1015 15A2 151025A35 5銷量銷量5151510 表表3-31銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4B5產(chǎn)量產(chǎn)量A1150 250 400A2 200300 500A3 250 50300A490210 300A5 8020100銷量銷量24041055033070 3.8 表表3-32和表和表3-33分別給出了各產(chǎn)地和各銷地分別給出了各產(chǎn)地和各銷地的產(chǎn)量和銷量，以及各產(chǎn)地至各銷地的單位運價，試的產(chǎn)量和銷量，以及各產(chǎn)地至各銷地的單位運價，試用表上作業(yè)法求最優(yōu)解。用表上作業(yè)法求最優(yōu)解

8、。表表3-32銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量A145 13 468A26 1252 08A3373 51 14銷量銷量656320表表3-33銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量A193 3873A21 492 453A35765 25銷量銷量132511 3.9 試求出表試求出表3-34給出的產(chǎn)銷不平衡運輸問題的給出的產(chǎn)銷不平衡運輸問題的最優(yōu)解。最優(yōu)解。 表表3-34銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量A137645A224322A343856銷量銷量3322 習(xí)題習(xí)題3.9的解答的解答銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4B5產(chǎn)量A13 3762 405A2242 3202A343 385

9、3 06銷量銷量33223 3.10 某市有三個面粉廠，它們供給三個面食加工某市有三個面粉廠，它們供給三個面食加工廠所需的面粉。各面粉廠的產(chǎn)量、各面食加工廠加工廠所需的面粉。各面粉廠的產(chǎn)量、各面食加工廠加工面粉的能力、各面食加工廠和各面粉廠之間的單位運面粉的能力、各面食加工廠和各面粉廠之間的單位運價，均表示于表價，均表示于表3-35中。假定在第中。假定在第1，2和和3面食加工廠面食加工廠制作單位面粉食品的利潤分別為制作單位面粉食品的利潤分別為12元、元、16元和元和11元，元，試確定使總效益最大的面粉分配計劃試確定使總效益最大的面粉分配計劃(假定面粉廠和面假定面粉廠和面食加工廠都屬于同一個主管

10、單位食加工廠都屬于同一個主管單位)。 表表3-35食品廠食品廠面粉廠面粉廠123產(chǎn)量產(chǎn)量310220411830811420銷量銷量152520 習(xí)題習(xí)題3.10的解答的解答食品廠食品廠面粉廠面粉廠1234產(chǎn)量31020 202015 45 11810 030820 114020銷量銷量15252010 3.11 表表3-36示出一個運輸問題及它的一個解：示出一個運輸問題及它的一個解：表表3-36銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量A145 13 468A2 8 1262 110A317351 14銷量銷量8 56322 試問：試問： (1)表中給出的解是否為最優(yōu)解？請用位勢法進行表中給出的解

11、是否為最優(yōu)解？請用位勢法進行檢驗。檢驗。 答：是最優(yōu)解。答：是最優(yōu)解。 (2)如價值系數(shù)如價值系數(shù)c24由由1變?yōu)樽優(yōu)?，所給的解是否仍為最，所給的解是否仍為最優(yōu)解？若不是，請求出最優(yōu)解。優(yōu)解？若不是，請求出最優(yōu)解。 答：原來的解不是最優(yōu)解。新的最優(yōu)解是：答：原來的解不是最優(yōu)解。新的最優(yōu)解是： x12=3,x13=5,x21=8,x22=2,x33=1,x34=3， 其他變量為其他變量為0 。 (3)若所有價值系數(shù)均增加若所有價值系數(shù)均增加1，最優(yōu)解是否改變？，最優(yōu)解是否改變？為什么為什么? 答：不會改變。因為檢驗數(shù)不變。答：不會改變。因為檢驗數(shù)不變。 (4)若所有價值系數(shù)均乘以若所有價值系數(shù)

12、均乘以2，最優(yōu)解是否改變？，最優(yōu)解是否改變？為什么為什么? 答：最優(yōu)解不變。因為檢驗數(shù)不變。答：最優(yōu)解不變。因為檢驗數(shù)不變。 (5)寫出該運輸問題的對偶問題，并給出其對偶問寫出該運輸問題的對偶問題，并給出其對偶問題的最優(yōu)解。題的最優(yōu)解。1,5,2, 1,0,0, 1,2, 1;,2, 1,2, 1;,2, 1max432132111vvvvuuunjmivunjmicvuvbuaZjiijjinjjjmiii最優(yōu)解是：無約束解：對偶問題如下： 3.12 1，2，3三個城市每年需分別供應(yīng)電力三個城市每年需分別供應(yīng)電力320，250和和350單位，由單位，由I，兩個電站提供，它們的最大供兩個電站提

13、供，它們的最大供電量分別為電量分別為400個單位和個單位和450個單位，單位費用如表個單位，單位費用如表337所示。由于需要量大于可供量，決定城市所示。由于需要量大于可供量，決定城市1的供應(yīng)量的供應(yīng)量可減少可減少030單位，城市單位，城市2的供應(yīng)量不變，城市的供應(yīng)量不變，城市3的供應(yīng)的供應(yīng)量不能少于量不能少于270單位，試求總費用最低的分配方案單位，試求總費用最低的分配方案(將將可供電量用完可供電量用完)。表表3-37 城市城市電站電站123151822212516 習(xí)題習(xí)題3.123.12的解答的解答 城市城市電站電站城市城市1-11-1城市城市1-21-2城市城市2 2城市城市3-13-1

14、城市城市3-23-2產(chǎn)量產(chǎn)量150 1515250 182222400140 212125270 1640 16450M30 0MM40 070銷量銷量2903025027080 3.13 試寫出本章例試寫出本章例5轉(zhuǎn)運問題的數(shù)學(xué)模型。轉(zhuǎn)運問題的數(shù)學(xué)模型。 解：已知解：已知 a a1 11010，a a2 24040，a a3 3 = a= a4 4 = a= a5 5 = 0= 0 b b1 1= b= b2 2= b= b3 30 0，b b4 43030，b b5 520 Q20 Q5050 下面就是相應(yīng)的模型：下面就是相應(yīng)的模型： MIN Z= 4 X(1,1)+ 5 X(1,2)+

15、3 X(1,3)+ 2 X(1,4)+ 100X(1, 5) + 5 X(2,1)+ X(2,2)+2 X(2,3)+100 X(2,4) + 4 X(2, 5) + 3 X(3,1)+2X(3,2)+3 X(3,3)+5 X(3, 4) + 5 X( 3, 5) + 2 X(4,1)+100X(4,2)+5 X(4,3)+ 3 X(4,4)+6 X( 4, 5) + 100X(5,1)+4X(5,2)+5X(5,3)+6 X( 5, 4) +5 X( 5, 5) 2-X(1,1) + X(1,2) + X(1,3) + X(1,4) + X(1,5) = 10 3 X(2,1) - X(2,2) + X(2,3) + X(2,4) + X(2,5) = 40 4 X(3,1) + X(3,2) - X(3,3) + X(3,4) + X(3,5) = 0 5 X(4,1) + X(4,2) + X(4,3) - X(4,4) + X(4,5) = 0 6 X(5,1) + X(5,2) + X(5,3) + X(5,4) - X(5,5) = 0