運(yùn)籌學(xué)3運(yùn)輸問(wèn)題

1、運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型表上作業(yè)法表上作業(yè)法運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用 例例3.1 某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地將物品運(yùn)往三個(gè)銷地B1, B2, B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。啃。緽1B2B3產(chǎn)量產(chǎn)量A1646200A2655300銷量銷量150150200解：產(chǎn)銷平衡問(wèn)題：總產(chǎn)量解：產(chǎn)銷平衡問(wèn)題：總產(chǎn)量 = 總銷量總銷量500 設(shè)設(shè) xij 為從產(chǎn)地為從產(chǎn)地A

2、i運(yùn)往銷地運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量的運(yùn)輸量，得到下列運(yùn)輸量表：表：B1B2B3產(chǎn)量產(chǎn)量A1x11x12x13200A2x21x22x23300銷量銷量150150200Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）運(yùn)輸問(wèn)題的一般形式：產(chǎn)銷平衡運(yùn)輸問(wèn)題的一般形式：產(chǎn)銷平衡A1、 A2、 Am 表示某物資的表

3、示某物資的m個(gè)產(chǎn)地；個(gè)產(chǎn)地； B1、B2、Bn 表示表示某物質(zhì)的某物質(zhì)的n個(gè)銷地；個(gè)銷地；ai 表示產(chǎn)地表示產(chǎn)地Ai的產(chǎn)量；的產(chǎn)量； bj 表示銷地表示銷地Bj 的銷量；的銷量； cij 表示把物資從產(chǎn)地表示把物資從產(chǎn)地Ai運(yùn)往銷地運(yùn)往銷地Bj的單位運(yùn)價(jià)。設(shè)的單位運(yùn)價(jià)。設(shè) xij 為從產(chǎn)地為從產(chǎn)地Ai運(yùn)往銷地運(yùn)往銷地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問(wèn)題的模型：的運(yùn)輸量，得到下列一般運(yùn)輸量問(wèn)題的模型： minjijijxcz11min111,.1,0,1,;1,nijijmijjiijxaims txbjnxim jnLLLL 已知資料如下：已知資料如下： 銷銷產(chǎn)產(chǎn) 地地 地地產(chǎn)產(chǎn) 量量1nB

4、BL1mA AM1ma aM1nb bL1 111nmm nc c c cLMMLnijjm1iiba產(chǎn)銷平衡產(chǎn)銷平衡銷銷 量量運(yùn)價(jià)運(yùn)價(jià)的單位運(yùn)價(jià)到為ijijijBAc ) ( 0min11ijjijijiijminjijijxbabxaxxcZ當(dāng)當(dāng)產(chǎn)銷平衡產(chǎn)銷平衡時(shí)，其模型如下：時(shí)，其模型如下：當(dāng)當(dāng)產(chǎn)大于銷產(chǎn)大于銷時(shí)，其模型如下：時(shí)，其模型如下： ) ( 0min11ijjijijiijminjijijxbabxaxxcZ當(dāng)當(dāng)產(chǎn)小于銷產(chǎn)小于銷時(shí)，其模型如下：時(shí)，其模型如下：0, 0, 0)(0min ijjijjiijjijiijijijcbabaxbxaxxcZ并假設(shè)：并假設(shè)： 特征：特征

5、： 1、平衡運(yùn)輸問(wèn)題必有可行解，也必有最優(yōu)解；、平衡運(yùn)輸問(wèn)題必有可行解，也必有最優(yōu)解； 2、運(yùn)輸問(wèn)題的基本可行解中應(yīng)包括、運(yùn)輸問(wèn)題的基本可行解中應(yīng)包括 m+n1 個(gè)基變量。個(gè)基變量。運(yùn)輸問(wèn)題約束條件的系數(shù)矩陣運(yùn)輸問(wèn)題約束條件的系數(shù)矩陣111111111111111111 L LL LO OL LO OO OO OO Onnmmm nxxxxxxxxx111212122212L LL LL LL Lmn銷銷 產(chǎn)產(chǎn) B1 B2 Bn 產(chǎn)產(chǎn)量量 c11 c12 c1n A1 x11 x12 x1n a1 c21 c22 c2n A2 x21 x22 x2n a2 cm1 cm2 cmn Am xm1

6、 xm2 xmn am 銷銷量量 b1 b1 bn 平平衡衡表表、運(yùn)運(yùn)價(jià)價(jià)表表合合二二為為一一：基本可行解是否最優(yōu)解結(jié)束換基是否 運(yùn)輸問(wèn)題的求解思路 計(jì)算步驟：計(jì)算步驟：(1) 找出初始調(diào)運(yùn)方案。即在找出初始調(diào)運(yùn)方案。即在(mn)產(chǎn)銷平衡表上給出產(chǎn)銷平衡表上給出m+n-1個(gè)數(shù)字格。個(gè)數(shù)字格。(最小元素法、西北角法或伏格爾法）最小元素法、西北角法或伏格爾法）(2) 求檢驗(yàn)數(shù)。（閉回路法或位勢(shì)法）求檢驗(yàn)數(shù)。（閉回路法或位勢(shì)法） 判別是否達(dá)到最優(yōu)判別是否達(dá)到最優(yōu)解。如已是最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)到下一步。解。如已是最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)到下一步。(3) 對(duì)方案進(jìn)行改善，找出新的調(diào)運(yùn)方案。（表上

7、閉回對(duì)方案進(jìn)行改善，找出新的調(diào)運(yùn)方案。（表上閉回路法調(diào)整）路法調(diào)整）確定確定m+n-1個(gè)基變量個(gè)基變量 (4) 重復(fù)（重復(fù)（2）、（）、（3），直到求得最優(yōu)調(diào)運(yùn)方案。），直到求得最優(yōu)調(diào)運(yùn)方案?？崭窨崭穸?、表上作業(yè)法二、表上作業(yè)法表上作業(yè)法是一種求解運(yùn)輸問(wèn)題的特殊方法，其表上作業(yè)法是一種求解運(yùn)輸問(wèn)題的特殊方法，其實(shí)質(zhì)是單純實(shí)質(zhì)是單純形法。形法。步驟步驟描述描述方法方法第一步第一步求初始基行可行解（初始調(diào)運(yùn)方案）求初始基行可行解（初始調(diào)運(yùn)方案）最小元素法、最小元素法、西北角法、西北角法、伏格爾法伏格爾法第二步第二步求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的檢驗(yàn)

8、數(shù)檢驗(yàn)數(shù) i j i j全都非負(fù)全都非負(fù)( (求求min)min)時(shí)得到最優(yōu)解，若時(shí)得到最優(yōu)解，若存在檢驗(yàn)數(shù)存在檢驗(yàn)數(shù) i j i j 00，說(shuō)明還沒(méi)有達(dá)到最優(yōu)，轉(zhuǎn)，說(shuō)明還沒(méi)有達(dá)到最優(yōu)，轉(zhuǎn)第三步。第三步。閉回路法和位閉回路法和位勢(shì)法勢(shì)法第三步第三步調(diào)整運(yùn)量，即換基，選一個(gè)變量出基，對(duì)原運(yùn)調(diào)整運(yùn)量，即換基，選一個(gè)變量出基，對(duì)原運(yùn)量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步例例3.2 3.2 某運(yùn)輸資料如下表所示：某運(yùn)輸資料如下表所示：?jiǎn)挝粏挝?銷地銷地 運(yùn)價(jià)運(yùn)價(jià) 產(chǎn)地產(chǎn)地產(chǎn)量產(chǎn)量3 311113 310107 71 19 92 28 84 47 74 410105

9、 59 9銷量銷量3 36 65 56 64321 BBBB321AAA問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？1 1、求初始方案：、求初始方案：最小元素法、西北角法、伏格爾法最小元素法、西北角法、伏格爾法 基本思想是就近供應(yīng)，即從運(yùn)價(jià)最小的地方開始供應(yīng)（調(diào)基本思想是就近供應(yīng)，即從運(yùn)價(jià)最小的地方開始供應(yīng)（調(diào)運(yùn)），然后次小，直到最后供完為止。運(yùn)），然后次小，直到最后供完為止。B1B2B3B4產(chǎn)量產(chǎn)量A17A2 4A39銷量銷量3656311310192741058總的運(yùn)輸費(fèi)總的運(yùn)輸費(fèi)(31)+(64) +(43) +(12)+(310)+(35)=86元元方法方法1：

10、最小元素法：最小元素法341633練習(xí)練習(xí) 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1675314A2842727A35910619銷量銷量221312131213131912 （2）西北角法（或左上角法）西北角法（或左上角法）此法是純粹的人為的規(guī)定，沒(méi)有理論依據(jù)和實(shí)際背景，但此法是純粹的人為的規(guī)定，沒(méi)有理論依據(jù)和實(shí)際背景，但它易操作，特別適合在計(jì)算機(jī)上編程計(jì)算，因而受歡迎。它易操作，特別適合在計(jì)算機(jī)上編程計(jì)算，因而受歡迎。方法如下：方法如下：3 6 5 63 6 5 67 7 4 4 9 93 34 4 4 4 9 90 6 5 60 6 5 64 40 0 4 4 9 90 2 5 60

11、 2 5 62 20 0 2 2 9 90 0 5 60 0 5 62 20 0 0 0 9 90 0 3 60 0 3 63 63 60 0 0 00 0 0 00 0 0 0 0 03 4 0 03 4 0 00 2 2 00 2 2 00 0 3 60 0 3 6在滿足約束條件下盡可能的給最左上角的變量最大值在滿足約束條件下盡可能的給最左上角的變量最大值. 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A141241116A22103910A38511622銷量銷量8141214488864814所以，初始基可行解為：所以，初始基可行解為：(8,8,4,8,14)目標(biāo)函數(shù)值目標(biāo)函數(shù)值Z372例

12、例3.3 3.3 某運(yùn)輸資料如下表所示：某運(yùn)輸資料如下表所示：練習(xí)練習(xí) 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1675314A2842727A35910619銷量銷量22131213813131466 最小元素法的最小元素法的缺點(diǎn)缺點(diǎn)是：為了節(jié)省一處的費(fèi)用，有時(shí)造成在其他處是：為了節(jié)省一處的費(fèi)用，有時(shí)造成在其他處要多花幾倍的運(yùn)費(fèi)。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最要多花幾倍的運(yùn)費(fèi)。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有一個(gè)差額。差額越大，小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有一個(gè)差額。差額越大，說(shuō)明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多。因而對(duì)差額

13、最大處，說(shuō)明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多。因而對(duì)差額最大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)。就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)。例如下面兩種運(yùn)輸方案。例如下面兩種運(yùn)輸方案。 最小元素法：最小元素法：15152012105815510總運(yùn)費(fèi)是總運(yùn)費(fèi)是z=108+52+151=10515152012105851510另一種方法：另一種方法：總運(yùn)費(fèi)總運(yùn)費(fèi)z=105+152+51=85方法方法2：Vogel法法1）從運(yùn)價(jià)表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)）從運(yùn)價(jià)表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行。費(fèi)的差額，并填入該表的最右列和最下行。B1B2B3B4產(chǎn)量產(chǎn)量A

14、17A2 4A39銷量銷量365631131019274105810-3=72-1=15-4=13-1=29-4=53-2=18-5=32）再?gòu)牟钪底畲蟮男谢蛄兄姓页鲎钚∵\(yùn)價(jià)確定供需關(guān)系和）再?gòu)牟钪底畲蟮男谢蛄兄姓页鲎钚∵\(yùn)價(jià)確定供需關(guān)系和供需數(shù)量。當(dāng)產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足供需數(shù)量。當(dāng)產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足時(shí)，劃去運(yùn)價(jià)表中對(duì)應(yīng)的行或列。時(shí)，劃去運(yùn)價(jià)表中對(duì)應(yīng)的行或列。重復(fù)重復(fù)1)和和2)，直到找出初始解為至。，直到找出初始解為至。B1B2B3B4產(chǎn)量產(chǎn)量A17A2 4A3 9銷量銷量3656311310192741058單位單位 銷地銷地 運(yùn)價(jià)運(yùn)價(jià) 產(chǎn)地產(chǎn)地產(chǎn)量

15、產(chǎn)量行差額行差額311310719284741059銷量銷量3656列差額列差額4321 BBBB321AAA71352753單位單位 銷地銷地 運(yùn)價(jià)運(yùn)價(jià) 產(chǎn)地產(chǎn)地產(chǎn)量產(chǎn)量行差額行差額311310719284741059銷量銷量3656列差額列差額4321 BBBB321AAA11351536312該方案的總運(yùn)費(fèi)該方案的總運(yùn)費(fèi):(13)(46)(35)(210)(18)(35)85元元 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量行差額行差額A1412411160A221039101A385116221銷量銷量814121448列差額列差額251314所以，初始基可行解為：目標(biāo)函數(shù)值Z244例例3

16、.4 3.4 某運(yùn)輸資料如下表所示：某運(yùn)輸資料如下表所示： 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量行差額行差額A1412411160A221039101A385116221銷量銷量814121448列差額列差額21314所以，初始基可行解為：目標(biāo)函數(shù)值Z2448例例3.4 3.4 某運(yùn)輸資料如下表所示：某運(yùn)輸資料如下表所示： 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量行差額行差額A1412411160A221039101A385116221銷量銷量814121448列差額列差額21314所以，初始基可行解為：目標(biāo)函數(shù)值Z24488例例3.4 3.4 某運(yùn)輸資料如下表所示：某運(yùn)輸資料如下表所示：

17、 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量行差額行差額A1412411160A221039101A38511622銷量銷量814121448列差額列差額1314所以，初始基可行解為：目標(biāo)函數(shù)值Z24488例例3.4 3.4 某運(yùn)輸資料如下表所示：某運(yùn)輸資料如下表所示：12 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量行差額行差額A1412411160A221039101A38511622銷量銷量814121448列差額列差額314所以，初始基可行解為：目標(biāo)函數(shù)值Z24488例例3.4 3.4 某運(yùn)輸資料如下表所示：某運(yùn)輸資料如下表所示：1224練習(xí)練習(xí) 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1

18、675314A2842727A35910619銷量銷量2213121312131213192、 最優(yōu)解的判別（檢驗(yàn)數(shù)的求法）最優(yōu)解的判別（檢驗(yàn)數(shù)的求法）求檢驗(yàn)數(shù)的方法有兩種：求檢驗(yàn)數(shù)的方法有兩種： 閉回路法閉回路法 對(duì)偶變量法（位勢(shì)法）對(duì)偶變量法（位勢(shì)法） （1 1）閉合回路法：）閉合回路法： ij ij0 0 （因?yàn)槟繕?biāo)函數(shù)要求最小化）（因?yàn)槟繕?biāo)函數(shù)要求最小化） 表格中有調(diào)運(yùn)量的地方為基變量，空格處為非基變量。表格中有調(diào)運(yùn)量的地方為基變量，空格處為非基變量。基變量的檢驗(yàn)數(shù)基變量的檢驗(yàn)數(shù) ij ij0 0，非基變量的檢驗(yàn)數(shù)，非基變量的檢驗(yàn)數(shù) ij ij00。 ij ij 0 0 0 表示運(yùn)費(fèi)增

19、加。表示運(yùn)費(fèi)增加。 閉回路：從空格出發(fā)順時(shí)針閉回路：從空格出發(fā)順時(shí)針( (或逆時(shí)針或逆時(shí)針) )畫水平畫水平( (或垂直或垂直) )直線，遇到填有運(yùn)量的方格可轉(zhuǎn)直線，遇到填有運(yùn)量的方格可轉(zhuǎn)9090，然后繼續(xù)前進(jìn)，直到，然后繼續(xù)前進(jìn)，直到到達(dá)出發(fā)的空格所形成的閉合回路。到達(dá)出發(fā)的空格所形成的閉合回路。調(diào)運(yùn)方案的任意空格存在唯一閉回路。調(diào)運(yùn)方案的任意空格存在唯一閉回路。注：注：1.1.每一空格有且僅有一條閉回路；每一空格有且僅有一條閉回路； 2.2.如果某數(shù)字格有閉回路，則此解不是可行解。如果某數(shù)字格有閉回路，則此解不是可行解。mnmnzzxxxx0111112122121 L Lm nxxxzz

20、11121101,0 L L若令則運(yùn)費(fèi)的增量運(yùn)費(fèi)的增量分析：分析：以最小元素法的初始解為例。假設(shè)產(chǎn)地以最小元素法的初始解為例。假設(shè)產(chǎn)地A1供應(yīng)供應(yīng)1個(gè)單位的個(gè)單位的物品給銷地物品給銷地B1。則解的變化和目標(biāo)函數(shù)的變化如何。則解的變化和目標(biāo)函數(shù)的變化如何。 銷地銷地產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量A141241116106A2210391082A38511622148銷量銷量814121448要保證產(chǎn)銷平衡，則要保證產(chǎn)銷平衡，則1, 12344110zz111121231311xxxx 稱為閉回路 21231311xxxx 銷地銷地產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量A141241116106A

21、2210391082A38511622148銷量銷量8141214481 銷地銷地產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量A141241116106A2210391082A38511622148銷量銷量81412144812561112122 銷地銷地產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量A141241116106A2210391082A38511622148銷量銷量81412144811561143102221 銷地銷地產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量A141241116106A2210391082A38511622148銷量銷量8141214481031823411610 211 銷地銷地產(chǎn)地產(chǎn)地

22、 B1B2B3B4產(chǎn)量產(chǎn)量A141241116106A2210391082A38511622148銷量銷量81412144813311411612 211210 銷地銷地產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量A141241116106A2210391082A38511622148銷量銷量814121448124934111 21-11210檢驗(yàn)數(shù)中有檢驗(yàn)數(shù)中有負(fù)數(shù)負(fù)數(shù)，說(shuō)明原方案不是最優(yōu)解。，說(shuō)明原方案不是最優(yōu)解。練習(xí)練習(xí) 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A167531414A28427278136A35910619613銷量銷量221312135579-3-11 uivjm個(gè)個(gè) n個(gè)個(gè)（

23、2 2）對(duì)偶變量法（位勢(shì)法）對(duì)偶變量法（位勢(shì)法）設(shè)其對(duì)偶變量為：設(shè)其對(duì)偶變量為：mnYu uuv vv1212(,.,.,) uivj無(wú)約束無(wú)約束 （i=1,2, ,m;j=1,2, ,n)標(biāo)準(zhǔn)型運(yùn)輸問(wèn)題的對(duì)偶問(wèn)題模型為：標(biāo)準(zhǔn)型運(yùn)輸問(wèn)題的對(duì)偶問(wèn)題模型為：1maxnijjjmiiivbuaw=+=ijjicvu則運(yùn)輸問(wèn)題變量則運(yùn)輸問(wèn)題變量xij的檢驗(yàn)數(shù)為：的檢驗(yàn)數(shù)為：ijijijijijijmnijijijczcYPcuuuvvvPcuv1212(, ., .,)() 用位勢(shì)法對(duì)初始方案進(jìn)行最優(yōu)性檢驗(yàn)的方法：用位勢(shì)法對(duì)初始方案進(jìn)行最優(yōu)性檢驗(yàn)的方法：1）在給定初始解的表上增加一行和一列，在列中填入

24、）在給定初始解的表上增加一行和一列，在列中填入ui，在，在行中填入行中填入vj。2）令）令u10，再按，再按cij-(ui+vj)=0（基變量的（基變量的cij求出其余的求出其余的ui與與vj。3）由）由 i j=Ci j -（ui+vj），求出非基變量的檢驗(yàn)數(shù)。），求出非基變量的檢驗(yàn)數(shù)。B1B2B3B4uiA1A2A3vj311310192741058注意：基變量的檢驗(yàn)數(shù)注意：基變量的檢驗(yàn)數(shù) i j=Ci j -（ui+vj）=0436313B1B2B3B4uiA1A2A3vj311310192741058令令u1=0u1+v3=3u1+ v4 =10u2+ v3=2u2+v1=1u3+v2

25、=4u3+ v4=543631321039vj-5A3-1A20A1uiB4B3B2B1436313當(dāng)存在非基變量的檢驗(yàn)數(shù)當(dāng)存在非基變量的檢驗(yàn)數(shù) ij 0，說(shuō)明現(xiàn)行方案，說(shuō)明現(xiàn)行方案為最優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。為最優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。注意：非基變量的檢驗(yàn)數(shù)注意：非基變量的檢驗(yàn)數(shù) i j=ci j -（ui+vj） 11=c11 -（u1+v1）=3-(0+2)=1 31=c31 -（u3+v1）=7-(2-5)=10 24=c24 -（u2+v4）=8-(10-1)=-1 22=c22 -（u2+v2）=9-(9-1)=1 12=c12 -（u1+v2）=11-

26、(0+9)=2 33=c33 -（u3+v3）=10-(3-5)=123113101927410583、 解的改進(jìn)解的改進(jìn) 閉合回路調(diào)整法（原理同單純形法一樣）閉合回路調(diào)整法（原理同單純形法一樣） 當(dāng)在表中空格處出現(xiàn)當(dāng)在表中空格處出現(xiàn)負(fù)檢驗(yàn)數(shù)負(fù)檢驗(yàn)數(shù)時(shí)，表明未得最優(yōu)解。時(shí)，表明未得最優(yōu)解。若有兩個(gè)或兩個(gè)以上的負(fù)檢驗(yàn)數(shù)時(shí)，一般選用其中最小的若有兩個(gè)或兩個(gè)以上的負(fù)檢驗(yàn)數(shù)時(shí)，一般選用其中最小的負(fù)檢驗(yàn)數(shù)，以它對(duì)應(yīng)的空格為調(diào)入格，即以它對(duì)應(yīng)的非基負(fù)檢驗(yàn)數(shù)，以它對(duì)應(yīng)的空格為調(diào)入格，即以它對(duì)應(yīng)的非基變量為換入變量。做一閉合回路。變量為換入變量。做一閉合回路。( 1 ) 確定換入基的變量：確定換入基的變量：當(dāng)

27、存在非基變量的檢驗(yàn)數(shù)當(dāng)存在非基變量的檢驗(yàn)數(shù) kl 0 且且 kl =min ij時(shí)，時(shí)，以以Xkl為換入變量，找出它在運(yùn)輸表中為換入變量，找出它在運(yùn)輸表中的閉合回路。的閉合回路。接上例：接上例：pqijj , i)(min 0Xpq=X24為換入變量為換入變量解的改進(jìn)的具體步驟：解的改進(jìn)的具體步驟：21039vj-5A3-1A20A1uiB4B3B2B1436313311310192741058( 2 ) 頂點(diǎn)編號(hào)：以空格頂點(diǎn)編號(hào)：以空格(Ak,Bl)(或進(jìn)基變量或進(jìn)基變量xik）為第一個(gè)）為第一個(gè)奇數(shù)頂點(diǎn)，沿閉回路的順（或逆）時(shí)針?lè)较蚯斑M(jìn)，對(duì)閉回奇數(shù)頂點(diǎn)，沿閉回路的順（或逆）時(shí)針?lè)较蚯斑M(jìn)，對(duì)

28、閉回路上的頂點(diǎn)依次編號(hào)。路上的頂點(diǎn)依次編號(hào)。132421039vj-5A3-1A20A1uiB4B3B2B1436313311310192741058( 2 ) 頂點(diǎn)編號(hào)：以空格頂點(diǎn)編號(hào)：以空格(Ak,Bl)(或進(jìn)基變量或進(jìn)基變量xik）為第一個(gè)）為第一個(gè)奇數(shù)頂點(diǎn)，沿閉回路的順（或逆）時(shí)針?lè)较蚯斑M(jìn)，對(duì)閉回奇數(shù)頂點(diǎn)，沿閉回路的順（或逆）時(shí)針?lè)较蚯斑M(jìn)，對(duì)閉回路上的頂點(diǎn)依次編號(hào)。路上的頂點(diǎn)依次編號(hào)。1324換出變量換出變量X23 13 , 1minmin14,23 xx( 3 ) 確定換出基的變量：在該閉回路上，從所有偶數(shù)號(hào)格確定換出基的變量：在該閉回路上，從所有偶數(shù)號(hào)格點(diǎn)的調(diào)運(yùn)量中選出最小值點(diǎn)的調(diào)

29、運(yùn)量中選出最小值 的頂點(diǎn)（格子），的頂點(diǎn)（格子），以該格子中的變量為換出變量。以該格子中的變量為換出變量。ijxmin ( 4 ) 確定新的運(yùn)輸方案：確定新的運(yùn)輸方案：以換出變量的運(yùn)輸量為調(diào)整量以換出變量的運(yùn)輸量為調(diào)整量 ，將該閉回路上將該閉回路上所有奇數(shù)號(hào)格的調(diào)運(yùn)量加上調(diào)整量所有奇數(shù)號(hào)格的調(diào)運(yùn)量加上調(diào)整量 ，所有偶，所有偶數(shù)號(hào)格的調(diào)運(yùn)量減去數(shù)號(hào)格的調(diào)運(yùn)量減去 ，其余的不變，這樣就得到一個(gè)新的，其余的不變，這樣就得到一個(gè)新的調(diào)運(yùn)方案調(diào)運(yùn)方案。該運(yùn)輸方案的總運(yùn)費(fèi)比原運(yùn)輸方案減少，改變量。該運(yùn)輸方案的總運(yùn)費(fèi)比原運(yùn)輸方案減少，改變量等于換出變量的檢驗(yàn)數(shù)。等于換出變量的檢驗(yàn)數(shù)。( 5 )然后，再對(duì)得到

30、的新解進(jìn)行最優(yōu)性檢驗(yàn)，加不是最優(yōu)解，然后，再對(duì)得到的新解進(jìn)行最優(yōu)性檢驗(yàn)，加不是最優(yōu)解，就重復(fù)以上步驟繼續(xù)進(jìn)行調(diào)整，一直到得出最優(yōu)解為止。就重復(fù)以上步驟繼續(xù)進(jìn)行調(diào)整，一直到得出最優(yōu)解為止。21039vj-5A3-1A20A1uiB4B3B2B136313113101927410584331039vj-5A3-2A20A1uiB4B3B2B1536312311310192741058重新求所有非基變量的檢驗(yàn)數(shù)：重新求所有非基變量的檢驗(yàn)數(shù)：31039vj-5A3-2A20A1uiB4B3B2B1536312當(dāng)所有非基變量的檢驗(yàn)數(shù)均非負(fù)時(shí)，則當(dāng)前調(diào)運(yùn)方案即為最當(dāng)所有非基變量的檢驗(yàn)數(shù)均非負(fù)時(shí)，則當(dāng)前調(diào)運(yùn)

31、方案即為最優(yōu)方案，如表此時(shí)最小總運(yùn)費(fèi)：優(yōu)方案，如表此時(shí)最小總運(yùn)費(fèi)：Z =(13)(46)(35)(210)(18)(35)85元元311310192741058表上作業(yè)法的計(jì)算步驟：表上作業(yè)法的計(jì)算步驟：分析實(shí)際問(wèn)題列出產(chǎn)銷平分析實(shí)際問(wèn)題列出產(chǎn)銷平衡表及單位運(yùn)價(jià)表衡表及單位運(yùn)價(jià)表確定初始調(diào)運(yùn)方案（最小確定初始調(diào)運(yùn)方案（最小元素法或元素法或Vogel法）法）求檢驗(yàn)數(shù)（位勢(shì)法）求檢驗(yàn)數(shù)（位勢(shì)法）所有檢驗(yàn)數(shù)所有檢驗(yàn)數(shù)0找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)，用閉合找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)，用閉合回路調(diào)整，得到新的調(diào)運(yùn)方案回路調(diào)整，得到新的調(diào)運(yùn)方案得到最優(yōu)方案，得到最優(yōu)方案，算出總運(yùn)價(jià)算出總運(yùn)價(jià)（1）若運(yùn)輸問(wèn)題的某

32、一基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)）若運(yùn)輸問(wèn)題的某一基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)為負(fù)，在繼續(xù)迭代時(shí)，取它們中任一變量為換入變量均可使為負(fù)，在繼續(xù)迭代時(shí)，取它們中任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取目標(biāo)函數(shù)值得到改善，但通常取ij0中最小者對(duì)應(yīng)的變量為中最小者對(duì)應(yīng)的變量為換入變量。換入變量。（2）無(wú)窮多最優(yōu)解）無(wú)窮多最優(yōu)解產(chǎn)銷平衡的運(yùn)輸問(wèn)題必定存最優(yōu)解。如果非基變量的產(chǎn)銷平衡的運(yùn)輸問(wèn)題必定存最優(yōu)解。如果非基變量的ij0，則該問(wèn)題有無(wú)窮多最優(yōu)解。，則該問(wèn)題有無(wú)窮多最優(yōu)解。如上例：如上例： 11的檢驗(yàn)數(shù)是的檢驗(yàn)數(shù)是 0，經(jīng)過(guò)調(diào)整，可得到另一個(gè)最，經(jīng)過(guò)調(diào)整，可得到另一個(gè)最優(yōu)解。優(yōu)解。

33、退化解：退化解： 表格中一般要有表格中一般要有(m+n-1)個(gè)數(shù)字格。但有時(shí)在分配運(yùn)量個(gè)數(shù)字格。但有時(shí)在分配運(yùn)量時(shí)則需要同時(shí)劃去一行和一列，這時(shí)需要補(bǔ)一個(gè)時(shí)則需要同時(shí)劃去一行和一列，這時(shí)需要補(bǔ)一個(gè)0，以保證，以保證有有(m+n-1)個(gè)數(shù)字格作為基變量。一般可在劃去的行和列的個(gè)數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個(gè)任意空格處加一個(gè)0即可。即可。 利用進(jìn)基變量的閉回路對(duì)解進(jìn)行調(diào)整時(shí)，標(biāo)有負(fù)號(hào)的利用進(jìn)基變量的閉回路對(duì)解進(jìn)行調(diào)整時(shí)，標(biāo)有負(fù)號(hào)的最小運(yùn)量（超過(guò)最小運(yùn)量（超過(guò)2個(gè)最小值）作為調(diào)整量個(gè)最小值）作為調(diào)整量，選擇任意一個(gè)最，選擇任意一個(gè)最小運(yùn)量對(duì)應(yīng)的基變量作為出基變量，并打上小運(yùn)

34、量對(duì)應(yīng)的基變量作為出基變量，并打上“”以示作為以示作為非基變量。非基變量。 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A116A210A322銷量銷量81412141241148310295116(0)(2)(9)(2)(1)(12)如下例中如下例中11檢驗(yàn)數(shù)是檢驗(yàn)數(shù)是 0，經(jīng)過(guò)調(diào)整，可得到另一個(gè)最優(yōu)解。，經(jīng)過(guò)調(diào)整，可得到另一個(gè)最優(yōu)解。 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷量銷量365620114431377821060在在x12、x22、x33、x34中任選一個(gè)變量作為基變量，例如選中任選一個(gè)變量作為基變量，例如選x34例：用最小元素法求初始可行解例：用最小元素法求初始

35、可行解當(dāng)總產(chǎn)量與總銷量不相等時(shí)當(dāng)總產(chǎn)量與總銷量不相等時(shí),稱為不平衡運(yùn)輸問(wèn)題稱為不平衡運(yùn)輸問(wèn)題.這類這類運(yùn)輸問(wèn)題在實(shí)際中常常碰到運(yùn)輸問(wèn)題在實(shí)際中常常碰到,它的求解方法是將不平衡問(wèn)題它的求解方法是將不平衡問(wèn)題化為平衡問(wèn)題再按平衡問(wèn)題求解?；癁槠胶鈫?wèn)題再按平衡問(wèn)題求解。 當(dāng)產(chǎn)大于銷時(shí)，即：當(dāng)產(chǎn)大于銷時(shí)，即： minjjiba11數(shù)學(xué)模型為：數(shù)學(xué)模型為： minjijijxcZ11minnijijmijjiijxaimxbjnximjn111, 2,1, 2,01, 2,;1, 2, L LL LL LL L，由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運(yùn)送完，由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的

36、產(chǎn)量不能全部運(yùn)送完，必須就地庫(kù)存，即每個(gè)產(chǎn)地設(shè)一個(gè)倉(cāng)庫(kù)，假設(shè)該倉(cāng)庫(kù)為一個(gè)虛擬必須就地庫(kù)存，即每個(gè)產(chǎn)地設(shè)一個(gè)倉(cāng)庫(kù)，假設(shè)該倉(cāng)庫(kù)為一個(gè)虛擬銷地銷地Bn+1， bn+1作為一個(gè)虛設(shè)銷地作為一個(gè)虛設(shè)銷地Bn+1的銷量的銷量(即庫(kù)存量即庫(kù)存量)。各產(chǎn)地。各產(chǎn)地Ai到到Bn+1的運(yùn)價(jià)為零，即的運(yùn)價(jià)為零，即Ci,n+1=0,（i=1，m）。則平衡問(wèn)題的）。則平衡問(wèn)題的數(shù)學(xué)模型為：數(shù)學(xué)模型為： minjijijxcZ11min , 2 , 1, 2 , 1, 01, 2 , 1, 2 , 1111jmixnjbxmiaxijmijijnjiij；具體求解時(shí)具體求解時(shí), ,只只在運(yùn)價(jià)表右端在運(yùn)價(jià)表右端增加一列增加

37、一列B Bn n+1+1，運(yùn)價(jià)為零運(yùn)價(jià)為零, ,銷量銷量為為b bn n+1+1即可即可 當(dāng)銷大于產(chǎn)時(shí)，即：當(dāng)銷大于產(chǎn)時(shí)，即： minjjiba11 minjijijxCZ11minnijijmijjiijxaimxbjnxim j111,2,1,2,0,1,2,;1,2, L LL LL LL L數(shù)學(xué)模型為：數(shù)學(xué)模型為：由于總銷量大于總由于總銷量大于總產(chǎn)量產(chǎn)量, ,故一定有些需故一定有些需求地不完全滿足求地不完全滿足, ,這這時(shí)虛設(shè)一個(gè)產(chǎn)地時(shí)虛設(shè)一個(gè)產(chǎn)地Am+1Am+1，產(chǎn)量為：，產(chǎn)量為：nmjijiba11 銷大于產(chǎn)化為平衡問(wèn)題的數(shù)學(xué)模型為銷大于產(chǎn)化為平衡問(wèn)題的數(shù)學(xué)模型為 ： minjij

38、ijxcZ11minni jijmijjiijxaimxbjnximjn1111,2,11,2,0,1,2,11,2, L LL LL LL L；具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行Am+1，運(yùn)價(jià)為零。產(chǎn)，運(yùn)價(jià)為零。產(chǎn)量為量為am+1即可。即可。 例例3.4 求下列表中極小化運(yùn)輸問(wèn)題的最優(yōu)解。求下列表中極小化運(yùn)輸問(wèn)題的最優(yōu)解。 B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20603545180160 4141160180ijjiba因?yàn)橛校阂驗(yàn)橛校核允且粋€(gè)產(chǎn)大于銷的運(yùn)輸問(wèn)題。表中所以是一個(gè)產(chǎn)大于銷的運(yùn)輸問(wèn)題。表中

39、A2不可達(dá)不可達(dá)B1，用一個(gè)，用一個(gè)很大的正數(shù)很大的正數(shù)M表示運(yùn)價(jià)表示運(yùn)價(jià)C21。虛設(shè)一個(gè)銷量為。虛設(shè)一個(gè)銷量為b5=180-160=20，Ci5=0，i=1,2,3,4，表的右邊增添一列，表的右邊增添一列 ，得到新的運(yùn)價(jià)表。，得到新的運(yùn)價(jià)表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180下表為計(jì)算結(jié)果。可看出：產(chǎn)地下表為計(jì)算結(jié)果?？煽闯觯寒a(chǎn)地A4還有還有20個(gè)單位沒(méi)有運(yùn)出。個(gè)單位沒(méi)有運(yùn)出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180用前

40、面的方法求運(yùn)輸方案：用前面的方法求運(yùn)輸方案：例例3.5 某市有三個(gè)造紙廠某市有三個(gè)造紙廠A1，A2，A3，其紙的產(chǎn)量分別為，其紙的產(chǎn)量分別為8，5和和9個(gè)單位，有個(gè)單位，有4個(gè)集中用戶個(gè)集中用戶B1，B2，B3，B4，其需用量分，其需用量分別為別為4，3，5和和6個(gè)單位。由各造紙廠到各用戶的單位運(yùn)價(jià)個(gè)單位。由各造紙廠到各用戶的單位運(yùn)價(jià)如表如表314所示，請(qǐng)確定總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。所示，請(qǐng)確定總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4 產(chǎn)量產(chǎn)量A1312348A2112595A367159銷量銷量4356解：由于總產(chǎn)量解：由于總產(chǎn)量22大于總銷量大于總銷量18，故本問(wèn)題是個(gè)產(chǎn)銷不

41、平，故本問(wèn)題是個(gè)產(chǎn)銷不平衡運(yùn)輸問(wèn)題。增加一假想銷地衡運(yùn)輸問(wèn)題。增加一假想銷地B5，用表上作業(yè)法求解。，用表上作業(yè)法求解。 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4B5(貯存貯存)產(chǎn)量產(chǎn)量A13123408A21125905A3671509銷量銷量43564 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4B5(貯存貯存)產(chǎn)量產(chǎn)量A13123408418634A211259050302-8A3671509-2954-4銷量銷量43564例例3.5 由由n個(gè)地區(qū)需要某種物資，需要量分別不少于個(gè)地區(qū)需要某種物資，需要量分別不少于bj（j=1,n）。這些物資均由某公司分設(shè)在）。這些物資均由某公司分設(shè)在m個(gè)地區(qū)的工廠供個(gè)地區(qū)的

42、工廠供應(yīng)，各工廠的產(chǎn)量分別不大于應(yīng)，各工廠的產(chǎn)量分別不大于ai（i=1,m）,已知從第已知從第i個(gè)地個(gè)地區(qū)至第區(qū)至第j個(gè)需求地區(qū)單位物資的運(yùn)價(jià)為個(gè)需求地區(qū)單位物資的運(yùn)價(jià)為cij，又，又 ，試，試寫出其對(duì)偶問(wèn)題，并解釋對(duì)偶變量的經(jīng)濟(jì)意義。寫出其對(duì)偶問(wèn)題，并解釋對(duì)偶變量的經(jīng)濟(jì)意義。 由于在變量相等的情況下，表上作業(yè)法的計(jì)算遠(yuǎn)比單由于在變量相等的情況下，表上作業(yè)法的計(jì)算遠(yuǎn)比單純形法簡(jiǎn)單得多。所以在解決實(shí)際問(wèn)題時(shí)，人們常常盡可純形法簡(jiǎn)單得多。所以在解決實(shí)際問(wèn)題時(shí)，人們常常盡可能把某些線性規(guī)劃的問(wèn)題化為運(yùn)輸問(wèn)題的數(shù)學(xué)模型。能把某些線性規(guī)劃的問(wèn)題化為運(yùn)輸問(wèn)題的數(shù)學(xué)模型。mnijijab11 解：由題給出的條件，數(shù)學(xué)模型可寫為解：由題給出的條件，數(shù)學(xué)模型可寫為:mnijijijzc x11min nijijmijjiijxa im stxb jn x 11(1,).(1,)0 L LL L對(duì)偶問(wèn)題可寫為對(duì)偶問(wèn)