運籌學-運輸問題的表上作業(yè)法(名校講義)課件

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

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

需求量

源點

產量

1234總計

22281723901234總計

2418123690其源點到目的地的單位產品的運費價格見圖1-7。§1運輸問題事例（1）目的地需求量源點產量12§1運輸問題事例（2）費目用的源點地12341③

⑨

⑤

⑥

2④

①

⑦

④3⑥⑧

②

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

§2運輸問題的一般形式ri——源i產量，§3表上作業(yè)法

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

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

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

③⑨⑤⑥④18①⑦④⑥⑧②⑤⑤⑤④③2401222171023361828§3表上作業(yè)法（2）以上例考察，觀察圖1-7。圖1-8§3表上作業(yè)法

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

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

③依此類推，最后獲初始基礎可行解示如圖1-10中。③⑨⑤⑥④18①⑦④⑥⑧12②⑤⑤⑤④③240122217102336182805§3表上作業(yè)法（3）②余下元素中，最小值為c32=2?！?表上作業(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è)法（4）

圖1-10初始基礎可行解§3表上作業(yè)法

（5）

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

i)

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

2．求出最優(yōu)解§3表上作業(yè)法

（6）

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

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

22③2⑨⑤⑥24④18①⑦④1§3表上作業(yè)法

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

（8）

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

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

圖1-12

回路法計算結果

其中：內表示費用元素內表示檢驗值表內其它值為基礎解?！?表上作業(yè)法（8）

22③2⑨⑤⑥§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?！?表上作業(yè)法（9）ii)

觀察表格，§3表上作業(yè)法

（10）

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

636357452圖1-13

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

§3表上作業(yè)法（10）

22③⑨2⑤§3表上作業(yè)法

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

§3表上作業(yè)法（11）②位勢法（簡捷法）§3表上作業(yè)法

（12）圖1-14

用位勢法求解實例

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

969-35745-1S1S2S3S4

t1t2t3t4§3表上作業(yè)法（12）圖1-14用位勢法求解實例

§3表上作業(yè)法

（13）i)

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

[xijB基集]

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

§3表上作業(yè)法（13）i)

令si，tj分別為§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ù)此法求出所有非基本變量對應的檢驗值（成本變動值）后，選取minij(ij<0)所對應的變量進入基礎解。圖1-14中得知，13=-3為最小值，令x13進基，采用回路法找出應離開的基變量，重新調整后，仍按上述步驟反復運算，最后得出最優(yōu)解?，F(xiàn)在看位勢法的對偶解釋：結合本例，示如表1-6中?！?表上作業(yè)法（14）ii)根據(jù)已得的si，t§3表上作業(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è)法（15）表1-6位勢法的對偶解釋x1§3表上作業(yè)法

（16）

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

（17）

顯然，si，t