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

2、njax1(3) ),1,( (4) 11minjjiarri源i產(chǎn)量，aj目的地j的需求量。 與單純形表格法一樣，該法亦分兩步進行：求出初始基礎(chǔ)可行解求出最優(yōu)解 1 用最小元素法求出滿意的初始基礎(chǔ)可解其方法是，按照費用矩陣元素Cij增長順序逐個選擇引入基本解的變量xij，非退化情況下，每選擇1個，就必然排除1個源點或目的地，最后一步可一次排除1個源點和1個目的地，這樣便可得到一個初始基礎(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。此時總費用為225。22218128523 2求出最優(yōu)解這有兩種方法：閉回路法和位勢法。 閉回路法，其思路是令表中空格（即非基礎(chǔ)解），對應(yīng)的變量由0增加d單位，然后在保持產(chǎn)品供求平衡（即滿足約束條件）情況下，使基礎(chǔ)解參與變動，看其費有如何變化，若費用減少，則該非基變量可進入基，否則，加以排除，其思路與單純形法一致。現(xiàn)繼上圖繼續(xù)改進基礎(chǔ)解，直至達優(yōu)。

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

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

6、2=10，x43=3。將圖1-12修正后，再求出當前非變量的檢驗值，示如圖1-13。非基礎(chǔ)解的檢驗數(shù)合為正，故獲最成解，總費用為249。 22 2 24 18 18 12 12 10 3 23 3622281723 636357452圖1-13 回路法所得最優(yōu)表格 位勢法（簡捷法） 該法對運輸費用矩陣表格每次可確定一組“行值”和“列值”。確定原則為使得每個基礎(chǔ)變量之費用cij等于相應(yīng)得行、列值之和，根據(jù)該原則求出行列值之后，用這些值再去求解每個非基本變量的檢驗數(shù)。 結(jié)合本例闡述該步驟：（見圖1-14） 圖1-14 用位勢法求解實例 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個方程和m+n個未知量。由于我們感興趣的是相對值，故可令任一個行值或列值等于某個固定值，例如令t1=0，即可求出各行、列值，可見“行”“列”值不是唯一的。 對于本例，令t1=0后，解聯(lián)立方程： 1 3 5 3 93432112211111ssssctscts ii)根據(jù)已得的si，tj值求出非基礎(chǔ)的檢驗值（或成本變動值）ij： ij =cij(si+tj) 例如：圖1-14中，13=c13(s1+t3)5(3+5)=-3

8、若130,則可進入基，根據(jù)此法求出所有非基本變量對應(yīng)的檢驗值（成本變動值）后，選取minij (ij 0)所對應(yīng)的變量進入基礎(chǔ)解。圖1-14中得知，13=-3為最小值，令x13進基，采用回路法找出應(yīng)離開的基變量，重新調(diào)整后，仍按上述步驟反復運算，最后得出最優(yōu)解。 現(xiàn)在看位勢法的對偶解釋： 結(jié)合本例，示如表1-6中。表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 =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個約束方程。 （由于 ，故只有7個獨立約束方程）。 該規(guī)劃的對偶約束必為：jiar444412211111 ctsctscts 顯然，si，tj即是對偶問題的對偶變量y。共8個對偶變量， 每次送代時有7個基礎(chǔ)解變量，可寫出7平衡方程式