運(yùn)籌學(xué)第三章課后習(xí)題答案

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

2、3-282表表3-26解：表解：表3-26產(chǎn)地個(gè)數(shù)產(chǎn)地個(gè)數(shù)m=3，銷(xiāo)地個(gè)數(shù)，銷(xiāo)地個(gè)數(shù)n=4，m+n-1=3+4-1=6個(gè)，而表個(gè)，而表3-26中非零個(gè)數(shù)的分量為中非零個(gè)數(shù)的分量為5個(gè)個(gè)6個(gè)，所以表個(gè)，所以表3-26不不可作為表上作業(yè)法時(shí)的基可行解?？勺鳛楸砩献鳂I(yè)法時(shí)的基可行解。銷(xiāo)地產(chǎn)地B1B2B3B4B5產(chǎn)量A1A2A3A4A515090200210300250250805020400500300300100銷(xiāo)量240410550330702022-3-283表表3-27解：表解：表3-27產(chǎn)地個(gè)數(shù)產(chǎn)地個(gè)數(shù)m=5，銷(xiāo)地個(gè)數(shù)，銷(xiāo)地個(gè)數(shù)n=5，m+n-1=5+5-1=9個(gè)，而表個(gè)，而表3-27中非

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

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

5、會(huì)造成很大損失，故應(yīng)盡量按最小運(yùn)價(jià)安價(jià)組織運(yùn)輸就會(huì)造成很大損失，故應(yīng)盡量按最小運(yùn)價(jià)安銷(xiāo)地產(chǎn)地B1B2B3B4產(chǎn)量A141468A212508A337514銷(xiāo)量6563202022-3-285排運(yùn)輸。這就是最小元素法和沃格爾法質(zhì)量不同的原因。排運(yùn)輸。這就是最小元素法和沃格爾法質(zhì)量不同的原因。3.7 表表3-28和表和表3-29分別給出了各產(chǎn)地和各銷(xiāo)地的產(chǎn)量分別給出了各產(chǎn)地和各銷(xiāo)地的產(chǎn)量和銷(xiāo)量，以及各產(chǎn)地至各銷(xiāo)地的單位運(yùn)價(jià)，試用表上作業(yè)和銷(xiāo)量，以及各產(chǎn)地至各銷(xiāo)地的單位運(yùn)價(jià)，試用表上作業(yè)法求最優(yōu)解。法求最優(yōu)解。表3-282022-3-286銷(xiāo)地產(chǎn)地B1B2B3B4產(chǎn)量A137645A224322A3

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

7、1=1，x33=3?？傎M(fèi)用。總費(fèi)用=513451301335=402022-3-288銷(xiāo)地產(chǎn)地B1B2B3B4產(chǎn)量A1 6 4 2 1468A21 3 25 5 08A3 371 5 3 1 4銷(xiāo)量656320西北解法計(jì)算如下：西北解法計(jì)算如下：從上表計(jì)算知：從上表計(jì)算知：x11=6，x12=2，x22=3，x23=5，x33=1，x34=3?？傎M(fèi)用?？傎M(fèi)用=642132551531=652022-3-289銷(xiāo)地產(chǎn)地B1B2B3B4產(chǎn)量ui1234A14 51 3468302A231225308115A337 15 1 4224銷(xiāo)量6563 用沃格爾法求解如下：用沃格爾法求解如下：列罰數(shù)vj1

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

9、，走4154線路線路11=4-1+5-4=4產(chǎn)地銷(xiāo)地B1B2B3B4產(chǎn)量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14銷(xiāo)量65632022-3-2812第二閉回路第二閉回路14，走，走6054線路線路14=6-0+5-4=7產(chǎn)地銷(xiāo)地B1B2B3B4產(chǎn)量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14銷(xiāo)量65632022-3-2813第三個(gè)閉回路第三個(gè)閉回路22，走，走2145線路線路22=2-1+4-5=0產(chǎn)地銷(xiāo)地B1B2B3B4產(chǎn)量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14銷(xiāo)量656320

10、22-3-2814第四個(gè)閉回路31，走3155線路31=3-1+5-5=2產(chǎn)地銷(xiāo)地B1B2B3B4產(chǎn)量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14銷(xiāo)量65632022-3-2815第五個(gè)閉回路32，走7145線路32=7-1+4-5=2產(chǎn)地銷(xiāo)地B1B2B3B4產(chǎn)量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14銷(xiāo)量65632022-3-2816第六個(gè)閉回路第六個(gè)閉回路34，走，走1550線路線路34=1-5+5-0=1，至此，六個(gè)閉回路全部計(jì)算完，至此，六個(gè)閉回路全部計(jì)算完，11=4，14=2，22=0，31=2，32=2，3

11、4=1，即全部檢驗(yàn)數(shù)，即全部檢驗(yàn)數(shù)均大于或等于均大于或等于0。即用上述三種方法計(jì)算中，用沃格爾法。即用上述三種方法計(jì)算中，用沃格爾法計(jì)算所得結(jié)果計(jì)算所得結(jié)果z*=35為最優(yōu)解。為最優(yōu)解。2022-3-2817解：（解：（2）表）表3-29用三種方法計(jì)算，用位勢(shì)法檢驗(yàn)。因用三種方法計(jì)算，用位勢(shì)法檢驗(yàn)。因?yàn)榭偖a(chǎn)量為總產(chǎn)量=13，總銷(xiāo)量，總銷(xiāo)量=10，所以該題的總產(chǎn)量總銷(xiāo)，所以該題的總產(chǎn)量總銷(xiāo)量，所以該題是產(chǎn)銷(xiāo)不平衡的問(wèn)題，故假設(shè)一銷(xiāo)地量，所以該題是產(chǎn)銷(xiāo)不平衡的問(wèn)題，故假設(shè)一銷(xiāo)地B5用最小元素法計(jì)算如下表所示用最小元素法計(jì)算如下表所示銷(xiāo)地產(chǎn)地B1B2B3B4產(chǎn)量A137645A224322A3438

12、56銷(xiāo)量3322表3-29銷(xiāo)地產(chǎn)地B1B2B3B4B5產(chǎn)量A11 3761 43 05A22 243202A343 32 81 506銷(xiāo)量33223 2022-3-2818最小元素法求解：最小元素法求解：x11=1，x14=1，x15=3，x21=2，x32=3，x33=2，x34=1，總費(fèi)，總費(fèi)用用=1314302233281541銷(xiāo)地產(chǎn)地B1B2B3B4B5產(chǎn)量A13 32 76405A221 41 3202A3431 82 53 06銷(xiāo)量33223 2022-3-2819西北角法求解：西北角法求解：x11=3，x12=2，x22=1，x23=1，x33=2，x34=2，x35=2，總費(fèi)，

13、總費(fèi)用用=3327141318253048銷(xiāo)地產(chǎn)地B1B2B3B4B5產(chǎn)量行罰數(shù)ui1234A1237643053111A2242320220A31433 0 825063111銷(xiāo)量33223 2022-3-2820沃格爾法求解：沃格爾法求解：列罰數(shù)vj111320211323142141212022-3-2821x11=2，x15=3，x23=2，x31=1，x32=3，X33=0，x34=2，總費(fèi)用，總費(fèi)用=2306302314332535。在最小元素法中，總費(fèi)用。在最小元素法中，總費(fèi)用=41，在用，在用西北角法計(jì)算中，總費(fèi)用西北角法計(jì)算中，總費(fèi)用=56，因此用沃格爾法計(jì)算所，因此用沃格爾

14、法計(jì)算所需費(fèi)用需費(fèi)用=35是最小的，但不知是否最優(yōu)，還要用對(duì)偶變是最小的，但不知是否最優(yōu)，還要用對(duì)偶變量法（位勢(shì)法）加以檢驗(yàn)。如表量法（位勢(shì)法）加以檢驗(yàn)。如表3-30所示：所示：產(chǎn)地銷(xiāo)地B1B2B3B4B5UiA1230A22A31302vj表3-30位勢(shì)法檢驗(yàn)表3-30位勢(shì)法檢驗(yàn)表3-30位勢(shì)法檢驗(yàn)表3-30位勢(shì)法檢驗(yàn)表3-30位勢(shì)法檢驗(yàn)表3-30位勢(shì)法檢驗(yàn)產(chǎn)地銷(xiāo)地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銷(xiāo)量33223vj3274-12022-3-2822表表3-30 位勢(shì)法檢驗(yàn)位勢(shì)法檢驗(yàn)由13=-1，故知z=35還不是最優(yōu)