第十講運輸問題的表上作業(yè)法§1運輸問題事例§2運輸問題的一般形式§3表上作業(yè)法§1運輸問題事例（1）

已知，有4個產(chǎn)地（源點）生產(chǎn)的產(chǎn)品需銷售到4個需求地（目的地或匯點），其源點產(chǎn)量和目的地需求量見表1-5。表1-5運輸問題的需求量及產(chǎn)量目的地

需求量

源點

產(chǎn)量

1234總計

22281723901234總計

2418123690其源點到目的地的單位產(chǎn)品的運費價格見圖1-7。§1運輸問題事例（2）費目用的源點地12341③

⑨

⑤

⑥

2④

①

⑦

④3⑥⑧

②

⑤4⑤⑤④③2418123622281723圖1-7運輸費用矩陣表格旁邊數(shù)字為產(chǎn)量和需要求量§2運輸問題的一般形式ri——源i產(chǎn)量，aj——目的地j的需求量。

§3表上作業(yè)法

（1）與單純形表格法一樣，該法亦分兩步進行：·求出初始基礎可行解·求出最優(yōu)解

1．用最小元素法求出滿意的初始基礎可解其方法是，按照費用矩陣元素Cij增長順序逐個選擇引入基本解的變量xij，非退化情況下，每選擇1個，就必然排除1個源點或目的地，最后一步可一次排除1個源點和1個目的地，這樣便可得到一個初始基礎可行解?！?表上作業(yè)法

（2）以上例考察，觀察圖1-7。①∵min{cij}=c22=1。故優(yōu)先分配源2和目的地2之間的產(chǎn)品圖1-8最小元素法第1步

③⑨⑤⑥④18①⑦④⑥⑧②⑤⑤⑤④③2401222171023361828§3表上作業(yè)法

（3）②余下元素中，最小值為c32=2。

圖1-9最小元素法第2步

③依此類推，最后獲初始基礎可行解示如圖1-10中。③⑨⑤⑥④18①⑦④⑥⑧12②⑤⑤⑤④③240122217102336182805§3表上作業(yè)法

（4）

圖1-10初始基礎可行解

即基礎解為：x11=22，x12=18，x33=12，x42=8，x43=5，x44=23。此時總費用為225。22③2⑨⑤⑥④18①⑦⑤⑥⑧12②⑤⑤8⑤5④23③§3表上作業(yè)法

（5）

2．求出最優(yōu)解這有兩種方法：閉回路法和位勢法。①閉回路法，其思路是令表中空格（即非基礎解），對應的變量由0增加d單位，然后在保持產(chǎn)品供求平衡（即滿足約束條件）情況下，使基礎解參與變動，看其費有如何變化，若費用減少，則該非基變量可進入基，否則，加以排除，其思路與單純形法一致?，F(xiàn)繼上圖繼續(xù)改進基礎解，直至達優(yōu)。

i)

參見圖1-11，分析非基變量x32增加d單位以后，其它基礎解及費用變化?！?表上作業(yè)法

（6）

22③2⑨⑤⑥24④18①⑦④18⑥⑧+d12②-d⑤12⑤8⑤-d5④+d23③3622281723

2．求出最優(yōu)解圖1-11回路法原理§3表上作業(yè)法

（7）為使供求平衡，必須符合：x32+d→x42－d→x43+d→x33－d變動后，費用增加值為：8d－5d+4d－2d=5d，即費用增加，x32不能進基，為比較，把增加1個單位產(chǎn)品所引起的費用增加值填入相應的非基變量表格內(nèi)，這又稱檢驗值。注意，在用回路法求解每個非基變量檢驗值時，在根據(jù)供求平衡尋找閉合回路過程中，其回路轉折點必須是基礎解！例如，分析非基解x31↑→x11↓→x12↑→x42↓→x43↑→x33↓→x31?！?表上作業(yè)法

（8）

22③2⑨⑤⑥24④18①⑦④18⑥⑧12②⑤12⑤8⑤5④23③3622281723

9695-3745-1對每個非基變量計算后，將其檢驗值填入圖1-12中。

圖1-12

回路法計算結果

其中：

內(nèi)表示費用元素

內(nèi)表示檢驗值表內(nèi)其它值為基礎解。§3表上作業(yè)法

（9）ii)

觀察表格，或檢驗值全部≥0，已達最優(yōu)勝，結束。否則，選取最負的檢驗值所對的非基變量，令其進基。圖1-12中，x13的檢驗值為最負，故令x13進基，應使x13盡量大，但又必須使其它變量非負。觀察x13變化規(guī)律：x13↑→x12↓→x42↑→x43↓。應取下降變量中的最小值作為x13的值。此時min{x12

，x43}=min{2，5}=2。故令x13=2則x12=0，x42=10，x43=3。將圖1-12修正后，再求出當前非變量的檢驗值，示如圖1-13。非基礎解的檢驗數(shù)合為正，故獲最成解，總費用為249。§3表上作業(yè)法

（10）

22③⑨2⑤⑥24④18①⑦④18⑥⑧12②⑤12⑤10⑤3④23③3622281723

636357452圖1-13

回路法所得最優(yōu)表格

§3表上作業(yè)法

（11）②位勢法（簡捷法）該法對運輸費用矩陣表格每次可確定一組“行值”和“列值”。確定原則為使得每個基礎變量之費用cij等于相應得行、列值之和，根據(jù)該原則求出行列值之后，用這些值再去求解每個非基本變量的檢驗數(shù)。結合本例闡述該步驟：（見圖1-14）

§3表上作業(yè)法

（12）圖1-14

用位勢法求解實例

22③2⑨⑤⑥24④18①⑦④18⑥⑧12②⑤12⑤8⑤5④23③3622281723

969-35745-1S1S2S3S4

t1t2t3t4§3表上作業(yè)法

（13）i)

令si，tj分別為行值和列值求解方程：si+tj=cij

[xij

B基集]

從方程知，共有m+n－1個方程和m+n個未知量。由于我們感興趣的是相對值，故可令任一個行值或列值等于某個固定值，例如令t1=0，即可求出各行、列值，可見“行”“列”值不是唯一的。對于本例，令t1=0后，解聯(lián)立方程：

§3表上作業(yè)法

（14）

ii)根據(jù)已得的si，tj值求出非基礎的檢驗值（或成本變動值）

ij：

ij=cij－(si+tj)

例如：圖1-14中，

13=c13－(s1+t3)＝5－(3+5)=-3

若

13<0,則可進入基，根據(jù)此法求出所有非基本變量對應的檢驗值（成本變動值）后，選取min

ij(

ij<0)所對應的變量進入基礎解。圖1-14中得知，

13=-3為最小值，令x13進基，采用回路法找出應離開的基變量，重新調(diào)整后，仍按上述步驟反復運算，最后得出最優(yōu)解?，F(xiàn)在看位勢法的對偶解釋：結合本例，示如表1-6中?！?表上作業(yè)法

（15）表1-6位勢法的對偶解釋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=28x13+x23+x33+x43=17x14+x24+x34+x44=23(r1)s1(r2)s2(r3)s3(r4)s4(a1)t1(a2)t2(a3)t3(a4)t4c11c12c13c14………………..c44§3表上作業(yè)法

（16）

表1-6列出了本例的供求關系的8個約束方程。（由于，故只有7個獨立約束方程）。該規(guī)劃的對偶約束必為：§3表上作業(yè)法

（17）

顯然，si，