運籌學第三章課后習題答案

1、2021-7-513.1 與一般線性規(guī)劃的數(shù)學模型相比，運輸問題的數(shù)學模型具有什么特征？答： 與一般線性規(guī)劃的數(shù)學模型相比，運輸問題的數(shù)學模型具有如下特征：1.運輸問題不象一般線性規(guī)劃問題那樣，線性規(guī)劃問題有可能有無窮多最優(yōu)解，運輸問題只有有限個最優(yōu)。2.運輸問題約束條件系數(shù)矩陣的元素等于0或1；且每一列有兩個非零元素。3.運輸問題的解的個數(shù)不可能大于(m+n-1)個。3.2 運輸問題的基可行解應滿足什么條件?試判斷形表3-26和表3-27中給出的調(diào)運方案是否作為表上作業(yè)法迭代時的基可行解?為什么?銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A30515151015255銷量51515102021-7

2、-52表表3-26解：表解：表3-26產(chǎn)地個數(shù)產(chǎn)地個數(shù)m=3，銷地個數(shù)，銷地個數(shù)n=4，m+n-1=3+4-1=6個，而表個，而表3-26中非零個數(shù)的分量為中非零個數(shù)的分量為5個個6個，所以表個，所以表3-26不不可作為表上作業(yè)法時的基可行解。可作為表上作業(yè)法時的基可行解。銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A1A2A3A4A515090200210300250250805020400500300300100銷量240410550330702021-7-53表表3-27解：表解：表3-27產(chǎn)地個數(shù)產(chǎn)地個數(shù)m=5，銷地個數(shù)，銷地個數(shù)n=5，m+n-1=5+5-1=9個，而表個，而表3-27中非零個數(shù)

3、的分量為中非零個數(shù)的分量為10個個9個，也不可作為表個，也不可作為表上作業(yè)法時的基可行解。上作業(yè)法時的基可行解。2021-7-543.3 試對給出運輸問題初始基可行解的最小元素法和試對給出運輸問題初始基可行解的最小元素法和Vogel法進行比較，分析給出的解之質量不同的原因。法進行比較，分析給出的解之質量不同的原因。解：解： 對于任意給出運輸問題初始基可行解的最小元素對于任意給出運輸問題初始基可行解的最小元素法和法和Vogel法進行比較，分析給出的兩種不同的方法求出法進行比較，分析給出的兩種不同的方法求出的解確有不同的原因。初看起來，最小元素法十分合理的解確有不同的原因。初看起來，最小元素法十分

4、合理。但是，有時按某一最小單位運價優(yōu)先安排物品調(diào)運時。但是，有時按某一最小單位運價優(yōu)先安排物品調(diào)運時，卻可能導致不得不采用運費很高的其他供銷點時，從，卻可能導致不得不采用運費很高的其他供銷點時，從而使整個運輸費用增加。我們稱各銷售地或供應地的單而使整個運輸費用增加。我們稱各銷售地或供應地的單位運價中找出的最小單位運價和次小單位運價之差為罰位運價中找出的最小單位運價和次小單位運價之差為罰數(shù)，若罰數(shù)的值不大，當不能按最小單位運價安排運輸數(shù)，若罰數(shù)的值不大，當不能按最小單位運價安排運輸時造成的運費損失不大；但如果罰數(shù)很大，不按最小運時造成的運費損失不大；但如果罰數(shù)很大，不按最小運價組織運輸就會造成很

5、大損失，故應盡量按最小運價安價組織運輸就會造成很大損失，故應盡量按最小運價安銷地產(chǎn)地B1B2B3B4產(chǎn)量A141468A212508A337514銷量6563202021-7-55排運輸。這就是最小元素法和沃格爾法質量不同的原因。排運輸。這就是最小元素法和沃格爾法質量不同的原因。3.7 表表3-28和表和表3-29分別給出了各產(chǎn)地和各銷地的產(chǎn)量分別給出了各產(chǎn)地和各銷地的產(chǎn)量和銷量，以及各產(chǎn)地至各銷地的單位運價，試用表上作業(yè)和銷量，以及各產(chǎn)地至各銷地的單位運價，試用表上作業(yè)法求最優(yōu)解。法求最優(yōu)解。表3-282021-7-56銷地產(chǎn)地B1B2B3B4產(chǎn)量A137645A224322A343856銷

6、量3332表3-29解：（解：（1）表）表3-28用三種方法計算，用閉回路法檢驗。用三種方法計算，用閉回路法檢驗。用最小元素法計算如下表所示用最小元素法計算如下表所示銷地產(chǎn)地B1B2B3B4產(chǎn)量A137645A224322A343856銷量3332銷地產(chǎn)地B1B2B3B4產(chǎn)量A137645A224322A343856銷量33322021-7-57銷地產(chǎn)地B1B2B3B4產(chǎn)量A14 5 13 468A25 1253 08A31 373 5 1 4銷量656320 最小元素法求解如下：最小元素法求解如下：從上表計算知：從上表計算知：x12=5，x13=3，x21=5，x24=3，x31=1，x33

7、=3?？傎M用?？傎M用=513451301335=402021-7-58銷地產(chǎn)地B1B2B3B4產(chǎn)量A1 6 4 2 1468A21 3 25 5 08A3 371 5 3 1 4銷量656320西北解法計算如下：西北解法計算如下：從上表計算知：從上表計算知：x11=6，x12=2，x22=3，x23=5，x33=1，x34=3?？傎M用?？傎M用=642132551531=652021-7-59銷地產(chǎn)地B1B2B3B4產(chǎn)量ui1234A14 51 3468302A231225308115A337 15 1 4224銷量6563 用沃格爾法求解如下：用沃格爾法求解如下：列罰數(shù)vj1211122113

8、11412021-7-510從上表計算知：從上表計算知：x12=5，x13=3，x21=3，x23=2，x24=3，x33=1?？傎M用?？傎M用=513431253015=35，在上述三種計算方法中，這種方法計算所需，在上述三種計算方法中，這種方法計算所需運輸費用是最省的。但還不知是否最優(yōu)?，F(xiàn)用閉回路法運輸費用是最省的。但還不知是否最優(yōu)?，F(xiàn)用閉回路法檢驗如下：檢驗如下：閉回路法檢驗如下：閉回路法檢驗如下：產(chǎn)地銷地B1B2B3B4產(chǎn)量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14銷量65632021-7-511第一個閉回路第一個閉回路11，走，走4154線路線路1

9、1=4-1+5-4=4產(chǎn)地銷地B1B2B3B4產(chǎn)量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14銷量65632021-7-512第二閉回路第二閉回路14，走，走6054線路線路14=6-0+5-4=7產(chǎn)地銷地B1B2B3B4產(chǎn)量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14銷量65632021-7-513第三個閉回路第三個閉回路22，走，走2145線路線路22=2-1+4-5=0產(chǎn)地銷地B1B2B3B4產(chǎn)量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14銷量65632021-7-514第四個閉回

10、路31，走3155線路31=3-1+5-5=2產(chǎn)地銷地B1B2B3B4產(chǎn)量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14銷量65632021-7-515第五個閉回路32，走7145線路32=7-1+4-5=2產(chǎn)地銷地B1B2B3B4產(chǎn)量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14銷量65632021-7-516第六個閉回路第六個閉回路34，走，走1550線路線路34=1-5+5-0=1，至此，六個閉回路全部計算完，至此，六個閉回路全部計算完，11=4，14=2，22=0，31=2，32=2，34=1，即全部檢驗數(shù)，即全部檢驗

11、數(shù)均大于或等于均大于或等于0。即用上述三種方法計算中，用沃格爾法。即用上述三種方法計算中，用沃格爾法計算所得結果計算所得結果z*=35為最優(yōu)解。為最優(yōu)解。2021-7-517解：（解：（2）表）表3-29用三種方法計算，用位勢法檢驗。因用三種方法計算，用位勢法檢驗。因為總產(chǎn)量為總產(chǎn)量=13，總銷量，總銷量=10，所以該題的總產(chǎn)量總銷，所以該題的總產(chǎn)量總銷量，所以該題是產(chǎn)銷不平衡的問題，故假設一銷地量，所以該題是產(chǎn)銷不平衡的問題，故假設一銷地B5用最小元素法計算如下表所示用最小元素法計算如下表所示銷地產(chǎn)地B1B2B3B4產(chǎn)量A137645A224322A343856銷量3322表3-29銷地產(chǎn)地

12、B1B2B3B4B5產(chǎn)量A11 3761 43 05A22 243202A343 32 81 506銷量33223 2021-7-518最小元素法求解：最小元素法求解：x11=1，x14=1，x15=3，x21=2，x32=3，x33=2，x34=1，總費，總費用用=1314302233281541銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A13 32 76405A221 41 3202A3431 82 53 06銷量33223 2021-7-519西北角法求解：西北角法求解：x11=3，x12=2，x22=1，x23=1，x33=2，x34=2，x35=2，總費，總費用用=33271413182530

13、48銷地產(chǎn)地B1B2B3B4B5產(chǎn)量行罰數(shù)ui1234A1237643053111A2242320220A31433 0 825063111銷量33223 2021-7-520沃格爾法求解：沃格爾法求解：列罰數(shù)vj111320211323142141212021-7-521x11=2，x15=3，x23=2，x31=1，x32=3，X33=0，x34=2，總費用，總費用=2306302314332535。在最小元素法中，總費用。在最小元素法中，總費用=41，在用，在用西北角法計算中，總費用西北角法計算中，總費用=56，因此用沃格爾法計算所，因此用沃格爾法計算所需費用需費用=35是最小的，但不知

14、是否最優(yōu)，還要用對偶變是最小的，但不知是否最優(yōu)，還要用對偶變量法（位勢法）加以檢驗。如表量法（位勢法）加以檢驗。如表3-30所示：所示：產(chǎn)地銷地B1B2B3B4B5UiA1230A22A31302vj表3-30位勢法檢驗表3-30位勢法檢驗表3-30位勢法檢驗表3-30位勢法檢驗表3-30位勢法檢驗表3-30位勢法檢驗產(chǎn)地銷地B1B2B3B4B5產(chǎn)量UiA12-1 3712=2 +1 613=-1414=03 050A2221=3422=2 2-1 3+1224=2025=52-4A31+14330 82-1 5 015=061銷量33223vj3274-12021-7-522表表3-30 位勢法檢驗位勢法檢驗由13=-1，故知z=35還不是最優(yōu)