運(yùn)籌學(xué)-運(yùn)輸問題的表上作業(yè)法(名校講義)

1、1 運(yùn)輸問題事例2 運(yùn)輸問題的一般形式 3 表上作業(yè)法 已知，有4個(gè)產(chǎn)地（源點(diǎn)）生產(chǎn)的產(chǎn)品需銷售到4個(gè)需求地（目的地或匯點(diǎn)），其源點(diǎn)產(chǎn)量和目的地需求量見表1-5。表1-5 運(yùn)輸問題的需求量及產(chǎn)量目的地 需求量 源點(diǎn) 產(chǎn)量 1234總計(jì) 2228172390 1234總計(jì) 2418123690 其源點(diǎn)到目的地的單位產(chǎn)品的運(yùn)費(fèi)價(jià)格見圖1-7。費(fèi) 目 用 的源點(diǎn) 地12341 2 3 424181236 22 28 17 23圖1-7 運(yùn)輸費(fèi)用矩陣 表格旁邊數(shù)字為產(chǎn)量和需要求量njijijminmxc11(1) )( z min個(gè)目的地個(gè)源點(diǎn)，)2( ), 1( 1njiijmirx約束：mijij

2、njax1(3) ),1,( (4) 11minjjiarri源i產(chǎn)量，aj目的地j的需求量。 與單純形表格法一樣，該法亦分兩步進(jìn)行：求出初始基礎(chǔ)可行解求出最優(yōu)解 1 用最小元素法求出滿意的初始基礎(chǔ)可解其方法是，按照費(fèi)用矩陣元素Cij增長(zhǎng)順序逐個(gè)選擇引入基本解的變量xij，非退化情況下，每選擇1個(gè)，就必然排除1個(gè)源點(diǎn)或目的地，最后一步可一次排除1個(gè)源點(diǎn)和1個(gè)目的地，這樣便可得到一個(gè)初始基礎(chǔ)可行解。以上例考察，觀察圖1-7。mincij=c22=1。故優(yōu)先分配源2和目的地2之間的產(chǎn)品圖1-8 最小元素法第1步 18 24 01222171023361828余下元素中，最小值為c32=2。 圖1-

3、9 最小元素法第2步 依此類推，最后獲初始基礎(chǔ)可行解示如圖1-10中。18 12 24 0122217102336182805 圖1-10 初始基礎(chǔ)可行解 即基礎(chǔ)解為：x11=22，x12=18，x33=12，x42=8，x43=5，x44=23。此時(shí)總費(fèi)用為225。22218128523 2求出最優(yōu)解這有兩種方法：閉回路法和位勢(shì)法。 閉回路法，其思路是令表中空格（即非基礎(chǔ)解），對(duì)應(yīng)的變量由0增加d單位，然后在保持產(chǎn)品供求平衡（即滿足約束條件）情況下，使基礎(chǔ)解參與變動(dòng)，看其費(fèi)有如何變化，若費(fèi)用減少，則該非基變量可進(jìn)入基，否則，加以排除，其思路與單純形法一致?，F(xiàn)繼上圖繼續(xù)改進(jìn)基礎(chǔ)解，直至達(dá)優(yōu)。

4、i) 參見圖1-11，分析非基變量x32增加d單位以后，其它基礎(chǔ)解及費(fèi)用變化。 222241818+d12-d128-d5+d233622281723 2求出最優(yōu)解圖1-11 回路法原理為使供求平衡，必須符合：x32+dx42dx43+dx33d變動(dòng)后，費(fèi)用增加值為：8d5d+4d2d=5d，即費(fèi)用增加，x32不能進(jìn)基，為比較，把增加1個(gè)單位產(chǎn)品所引起的費(fèi)用增加值填入相應(yīng)的非基變量表格內(nèi)，這又稱檢驗(yàn)值。注意，在用回路法求解每個(gè)非基變量檢驗(yàn)值時(shí)，在根據(jù)供求平衡尋找閉合回路過程中，其回路轉(zhuǎn)折點(diǎn)必須是基礎(chǔ)解！例如，分析非基解x31x11x12x42x43x33x31。 22 2 24 18 18 1

5、2 12 8 5 23 3622281723 9695-3745-1對(duì)每個(gè)非基變量計(jì)算后，將其檢驗(yàn)值填入圖1-12中。 圖1-12 回路法計(jì)算結(jié)果 其中： 內(nèi)表示費(fèi)用元素 內(nèi)表示檢驗(yàn)值 表內(nèi)其它值為基礎(chǔ)解。 ii) 觀察表格，或檢驗(yàn)值全部0，已達(dá)最優(yōu)勝，結(jié)束。否則，選取最負(fù)的檢驗(yàn)值所對(duì)的非基變量，令其進(jìn)基。圖1-12中，x13的檢驗(yàn)值為最負(fù)，故令x13進(jìn)基，應(yīng)使x13盡量大，但又 必 須 使 其 它 變 量 非 負(fù) 。 觀 察 x1 3變 化 規(guī) 律 ：x13x12x42x43。應(yīng)取下降變量中的最小值作為x13的值。此時(shí)minx12 ，x43=min2，5=2。故令x13=2則x12=0，x4

6、2=10，x43=3。將圖1-12修正后，再求出當(dāng)前非變量的檢驗(yàn)值，示如圖1-13。非基礎(chǔ)解的檢驗(yàn)數(shù)合為正，故獲最成解，總費(fèi)用為249。 22 2 24 18 18 12 12 10 3 23 3622281723 636357452圖1-13 回路法所得最優(yōu)表格 位勢(shì)法（簡(jiǎn)捷法） 該法對(duì)運(yùn)輸費(fèi)用矩陣表格每次可確定一組“行值”和“列值”。確定原則為使得每個(gè)基礎(chǔ)變量之費(fèi)用cij等于相應(yīng)得行、列值之和，根據(jù)該原則求出行列值之后，用這些值再去求解每個(gè)非基本變量的檢驗(yàn)數(shù)。 結(jié)合本例闡述該步驟：（見圖1-14） 圖1-14 用位勢(shì)法求解實(shí)例 22 2 24 18 18 12 12 8 5 23 3622

7、281723 969-35745-1S1S2S3S4 t1t2t3t4 i) 令si，tj分別為行值和列值 求解方程：si+tj=cij xijB基集 從方程知，共有m+n1個(gè)方程和m+n個(gè)未知量。由于我們感興趣的是相對(duì)值，故可令任一個(gè)行值或列值等于某個(gè)固定值，例如令t1=0，即可求出各行、列值，可見“行”“列”值不是唯一的。 對(duì)于本例，令t1=0后，解聯(lián)立方程： 1 3 5 3 93432112211111ssssctscts ii)根據(jù)已得的si，tj值求出非基礎(chǔ)的檢驗(yàn)值（或成本變動(dòng)值）ij： ij =cij(si+tj) 例如：圖1-14中，13=c13(s1+t3)5(3+5)=-3

8、若130,則可進(jìn)入基，根據(jù)此法求出所有非基本變量對(duì)應(yīng)的檢驗(yàn)值（成本變動(dòng)值）后，選取minij (ij 0)所對(duì)應(yīng)的變量進(jìn)入基礎(chǔ)解。圖1-14中得知，13=-3為最小值，令x13進(jìn)基，采用回路法找出應(yīng)離開的基變量，重新調(diào)整后，仍按上述步驟反復(fù)運(yùn)算，最后得出最優(yōu)解。 現(xiàn)在看位勢(shì)法的對(duì)偶解釋： 結(jié)合本例，示如表1-6中。表1-6 位勢(shì)法的對(duì)偶解釋x11+x12+x13+x14 =24 x21+x22+x23+x24 =18 x31+x32+x43+x44 =12 x41+x42+x43+x44 =36x11 +x21 + x31 + x41 =22 x12 +x22 +x32 +x42 =28 x13 +x23 +x33 +x43 =17 x14 +x24 +x34 +x44 =23 (r1)s1(r2)s2(r3)s3(r4)s4(a1)t1(a2)t2(a3)t3(a4)t4c11 c12 c13 c14 . c44 表1-6列出了本例的供求關(guān)系的8個(gè)約束方程。 （由于 ，故只有7個(gè)獨(dú)立約束方程）。 該規(guī)劃的對(duì)偶約束必為：jiar444412211111 ctsctscts 顯然，si，tj即是對(duì)偶問題的對(duì)偶變量y。共8個(gè)對(duì)偶變量， 每次送代時(shí)有7個(gè)基礎(chǔ)解變量，可寫出7平衡方程式