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

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

2、51510表表3-26解：表解：表3-26產(chǎn)地個(gè)數(shù)產(chǎn)地個(gè)數(shù)m=3，銷地個(gè)數(shù)，銷地個(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í)的基可行解。可作為表上作業(yè)法時(shí)的基可行解。2021-10-253銷地產(chǎn)地b1b2b3b4b5產(chǎn)量a1a2a3a4a515090200210300250250805020400500300300100銷量24041055033070表表3-27解：表解：表3-27產(chǎn)地個(gè)數(shù)產(chǎn)地個(gè)數(shù)m=5，銷地個(gè)數(shù)，銷地個(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í)的基可行解。2021-10-2543.3 試對給出運(yùn)輸問題初始基可行解的最小元素法和試對給出運(yùn)輸問題初始基可行解的最小元素法和vogel法進(jìn)行比較，分析給出的解之質(zhì)量不同的原因。法進(jìn)行比較，分析給出的解之質(zhì)量不同的原因。解：解： 對于任意給出運(yùn)輸問題初始基可行解的最小元素對于任意給出運(yùn)輸問題初始基可行解的最小元素法和法和vogel法進(jìn)行比較，分析給出的兩種不同的方法求出法進(jìn)行比較，分析給出的兩種不同的方法求出的解確有不同的原因。初看起來，最小元素法十分合理的解確有不同的原因。初看起來，最

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)很高的其他供銷點(diǎn)時(shí)，從，卻可能導(dǎo)致不得不采用運(yùn)費(fèi)很高的其他供銷點(diǎn)時(shí)，從而使整個(gè)運(yùn)輸費(fèi)用增加。我們稱各銷售地或供應(yīng)地的單而使整個(gè)運(yùn)輸費(fèi)用增加。我們稱各銷售地或供應(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à)安2021-10-255銷地產(chǎn)地b1b2b3b4產(chǎn)量a141468a212508a337514銷量656320排運(yùn)輸。這就是最小元素法和沃格爾法質(zhì)量不同的原因。排運(yùn)輸。這就是最小元素法和沃格爾法質(zhì)量不同的原因。3.7 表表3-28和表和表3-29分別給出了各產(chǎn)地和各銷地的產(chǎn)量分別給出了各產(chǎn)地和各銷地的產(chǎn)量和銷量，以及各產(chǎn)地至各銷地的單位運(yùn)價(jià)，試用表上作業(yè)和銷量，以及各產(chǎn)地至各銷地的單位運(yùn)價(jià)，試用表上作業(yè)法求最優(yōu)解。法求最優(yōu)解。表3-282021-10-256銷地產(chǎn)地b1b2b3b4產(chǎn)量a137645a2243

6、22a343856銷量3332表3-29解：（解：（1）表）表3-28用三種方法計(jì)算，用閉回路法檢驗(yàn)。用三種方法計(jì)算，用閉回路法檢驗(yàn)。用最小元素法計(jì)算如下表所示用最小元素法計(jì)算如下表所示銷地產(chǎn)地b1b2b3b4產(chǎn)量a137645a224322a343856銷量3332銷地產(chǎn)地b1b2b3b4產(chǎn)量a137645a224322a343856銷量33322021-10-257銷地產(chǎn)地b1b2b3b4產(chǎn)量a14 5 13 468a25 1253 08a31 373 5 1 4銷量656320 最小元素法求解如下：最小元素法求解如下：從上表計(jì)算知：從上表計(jì)算知：x12=5，x13=3，x21=5，x24

7、=3，x31=1，x33=3?？傎M(fèi)用?？傎M(fèi)用=513451301335=402021-10-258銷地產(chǎn)地b1b2b3b4產(chǎn)量a1 6 4 2 1468a21 3 25 5 08a3 371 5 3 1 4銷量656320西北解法計(jì)算如下：西北解法計(jì)算如下：從上表計(jì)算知：從上表計(jì)算知：x11=6，x12=2，x22=3，x23=5，x33=1，x34=3?？傎M(fèi)用?？傎M(fèi)用=642132551531=652021-10-259銷地產(chǎn)地b1b2b3b4產(chǎn)量ui1234a14 51 3468302a231225308115a337 15 1 4224銷量6563 用沃格爾法求解如下：用沃格爾法求解如下

8、：列罰數(shù)vj121112211311412021-10-2510從上表計(jì)算知：從上表計(jì)算知：x12=5，x13=3，x21=3，x23=2，x24=3，x33=1?？傎M(fèi)用。總費(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)如下：2021-10-2511產(chǎn)地銷地b1b2b3b4產(chǎn)量a1 45 13 4 68a23 1 2 2 53 08a3 3 71 5 14銷量6563第一個(gè)閉回路第

9、一個(gè)閉回路11，走，走4154線路線路11=4-1+5-4=42021-10-2512產(chǎn)地銷地b1b2b3b4產(chǎn)量a1 45 13 4 68a23 1 2 2 53 08a3 3 71 5 14銷量6563第二閉回路第二閉回路14，走，走6054線路線路14=6-0+5-4=72021-10-2513產(chǎn)地銷地b1b2b3b4產(chǎn)量a1 45 13 4 68a23 1 2 2 53 08a3 3 71 5 14銷量6563第三個(gè)閉回路第三個(gè)閉回路22，走，走2145線路線路22=2-1+4-5=02021-10-2514產(chǎn)地銷地b1b2b3b4產(chǎn)量a1 45 13 4 68a23 1 2 2 53

10、 08a3 3 71 5 14銷量6563第四個(gè)閉回路31，走3155線路31=3-1+5-5=22021-10-2515產(chǎn)地銷地b1b2b3b4產(chǎn)量a1 45 13 4 68a23 1 2 2 53 08a3 3 71 5 14銷量6563第五個(gè)閉回路32，走7145線路32=7-1+4-5=22021-10-2516產(chǎn)地銷地b1b2b3b4產(chǎn)量a1 45 13 4 68a23 1 2 2 53 08a3 3 71 5 14銷量6563第六個(gè)閉回路第六個(gè)閉回路34，走，走1550線路線路34=1-5+5-0=1，至此，六個(gè)閉回路全部計(jì)算完，至此，六個(gè)閉回路全部計(jì)算完，11=4，14=2，22

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

12、645a224322a343856銷量3322表3-292021-10-2518銷地產(chǎn)地b1b2b3b4b5產(chǎn)量a11 3761 43 05a22 243202a343 32 81 506銷量33223 最小元素法求解：最小元素法求解：x11=1，x14=1，x15=3，x21=2，x32=3，x33=2，x34=1，總費(fèi)，總費(fèi)用用=13143022332815412021-10-2519銷地產(chǎn)地b1b2b3b4b5產(chǎn)量a13 32 76405a221 41 3202a3431 82 53 06銷量33223 西北角法求解：西北角法求解：x11=3，x12=2，x22=1，x23=1，x33=

13、2，x34=2，x35=2，總費(fèi)，總費(fèi)用用=33271413182530482021-10-2520銷地產(chǎn)地b1b2b3b4b5產(chǎn)量行罰數(shù)ui1234a1237643053111a2242320220a31433 0 825063111銷量33223 沃格爾法求解：沃格爾法求解：列罰數(shù)vj111320211323142141212021-10-2521x11=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)用=5

14、6，因此用沃格爾法計(jì)算所，因此用沃格爾法計(jì)算所需費(fèi)用需費(fèi)用=35是最小的，但不知是否最優(yōu)，還要用對偶變是最小的，但不知是否最優(yōu)，還要用對偶變量法（位勢法）加以檢驗(yàn)。如表量法（位勢法）加以檢驗(yàn)。如表3-30所示：所示：產(chǎn)地銷地b1b2b3b4b5uia1230a22a31302vj表3-30位勢法檢驗(yàn)表3-30位勢法檢驗(yàn)表3-30位勢法檢驗(yàn)表3-30位勢法檢驗(yàn)表3-30位勢法檢驗(yàn)表3-30位勢法檢驗(yàn)2021-10-2522產(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-1表表3-30 位勢法檢驗(yàn)位勢法檢驗(yàn)由13=-1，故知z=35還不是最優(yōu)