清華大學出版社《運籌學教程》（第三版）運籌學基礎胡運權主編教材

諸如這類有多個不同的生產、消費者，如何合理不同的生產者和消費者之間的分配關系，達到最小費用的問題也運籌學最重要的問題之一。我們把這種分派問題稱為運輸問題。

在運籌學中，運輸問題是一個廣義的“運輸”，即許多其它問題也可以通過適當的手段，把它們轉化為運輸問題加以解決。這部分也是我們這學期主要學習內容之一。運輸問題某種物品先存放在兩個倉庫A1相A2中，再運往三個使用地B1，B2和B3，其間的距離(或單位運價)如下表小方格中的數據所示，各倉庫的存量和使用地的需用量也都示于下表中，試建立控總運輸量(或總運費)最小的運輸問題數學模型。設：xij——

從Ai地運往Bj地的貨物數量運價min

z=3x11+4x12+2x13+

3x21+5x22+3x23x11+x12+x13=10約束條件st.x21+x22+x23=4x11+x21=3x12+x22=5x13+x23=6xij

≥0運輸問題的特點x11+x12+x13=10x21+x22+x23=4x11+x21=3x12+x22=5x13+x23=6111101114113115116

1）運輸問題有有限最優解2）運輸問題系數矩陣非常特殊3）運輸問題約束都是等式約束5）一般運輸問題都是產銷平衡的（不平衡問題要化為平衡問題）4）一般運輸問題約束有一個多余的約束6）一般產m、銷n有（m*n）個變量和（m+n）個約束（沒有去掉多余）7）產m、銷n運輸問題最多有（m+n-1）個值為非零的變量因為有一個約束多余，既R（A）=m+n-1運輸問題求解方法：表上作業法例三

B1B2B3B4產量A116A210A322銷量8141214484124112103985116最小元素法82101486

B1B2B3B4產量A116A210A322銷量81412144841241121039851168864814西北角法運價：246運價：372例三

B1B2B3B4產量A116A210A322銷量8141214484850402103985116最小元素法821486108864814運價：880運價：456

B1B2B3B4產量A116A210A322銷量8141214484850402103985116西北角法有沒有搞錯！！！例三

B1B2B3B4產量A116A210A322銷量8141214484850402103985116最小元素法8214問題就在這里！！！沃格爾提出一種新的解決問題的方法思路例三

B1B2B3B4產量A116A210A322銷量814121448412411210398511614運價：244列罰數12345行罰數8124282513011213012212011276200運價：246（最小元素法）運價：372（西北角法）怎樣的安排為最優呢？例三

B1B2B3B4產量A116A210A322銷量8141214484124112103985116abcd

B1B2B3B4產量A116A210A322銷量814121448afbcde

cbjiahgfed閉回路檢驗法例三

B1B2B3B4產量A116A210A322銷量8141214484124112103985116最小元素法82101486運價：246b例三

B1B2B3B4產量A116A210A322銷量8141214484124112103985116最小元素法82101486運價：246b0例三

B1B2B3B4產量A116A210A322銷量8141214484124112103985116最小元素法82101486運價：246b2例三

B1B2B3B4產量A116A210A322銷量8141214484124112103985116最小元素法82101484運價：246b2例三

B1B2B3B4產量A116A210A322銷量8141214484124112103985116最小元素法82121484運價：246b2例三

B1B2B3B4產量A116A210A322銷量8141214484124112103985116最小元素法80121484運價：246b2例三

B1B2B3B4產量A116A210A322銷量8141214484124112103985116最小元素法8121484運價：2462244例三

B1B2B3B4產量A116A210A322銷量814121448412411210398511680121484b

B1B2B3B4產量A116A210A322銷量81412144841241121039851169-11+4-3=-1-11102112

我們可以通過找出所有回路的方法來確定怎樣調整運輸計劃，逐步使總運價降低。這種逐步調整運輸計劃直至達到最優解為止的方法稱為閉合回路法。它的難點是每次找這些回路非常復雜。有更好的辦法嗎？運輸問題的數學模型（假定產銷平衡）目標函數：nmj=1i=1minZ=∑∑Cij

xijnj=1∑xij=aii=1,2,…m產量約束：銷量約束：mi=1∑xij=bjj=1,2,…nxij

≥0nmj=1i=1maxw=∑aiui＋∑bj

vjui+vj

≤cijui、vj無約束σ=C-CBB-1A=C-YAσij=cij-(u1,u2……um,v1,v2……vn)pij=cij-ui-vj運輸問題的數學模型（假定產銷平衡）由于基變量的檢驗數等于零，故對這組基變量可寫出方程組：現設已得到的運輸問題的一個基可行解，其基變量是：顯然，這個方程組有(m+n-1)個方程。運輸表中每個產地和每個銷地都對應原運輸問題的一個約束條件，從而也對應各自的一個對偶變量；由于運輸表中每行和每列都含有基變量，可知這樣構造的以上方程組中含有全部(m+n)個對偶變量。可以證明，以上方程組有解，且由于對偶變量比方程數多一個，故解不唯一。基變量對應的σ應該等于零n+m-1個等式,但有n+m個變量無窮多解解稱為位勢運輸問題的數學模型（假定產銷平衡）若由以上方程組解得的某組解滿足對偶問題約束條件，這時可以證明：若由上式解得的解不滿足約束條件式，即非基變量的檢驗數有負值存在，則上面得到的運輸問題的解不是最優解，需要進行解的調整。現仍用前面的例子說明用位勢法(對偶變量法)求檢驗數的方法和步驟。運輸問題的數學模型（假定產銷平衡）

(1)在上表上增加一位勢列ui和位勢行vi。

(2)計算位勢。可先建立方程組，并據此計算出運輸表各行和格列的位勢。在本例中，x13，x14，x21，x23，x32，x34這六個變量為基變量，故有：

B1B2B3B4產量A116A210A322銷量814121448412411210398511681014862運輸問題的數學模型（假定產銷平衡）在求解以上方程組時，為計算簡便，常任意指定某一位勢等于一個較小的整數或零。在此例求解時，任意指定u2=0，由此可算出：v1=2，v3=3，u1=1，v4=10，u3=-4，v2=9(3)計算檢驗數有了位勢ui和vj之后，即可計算各空格的檢驗數。本例算出各空格的檢驗數如下表：

B1B2B3B4產量A116A210A322銷量81412144841241121039851161121210-1運輸問題的數學模型（假定產銷平衡）三、解的改進對運輸問題的一個解來說，若最優性檢驗時某非基變量xij的檢驗數為負，說明將這個非基變量變為基變量時運費會更小，因而這個解不是最優解，還可以進一步改進。改進的方法是在運輸表中找出這個空格對應的閉回路，在滿足所有約束條件前提下，使xij盡量增大并相應調整此閉回路上其他頂點的運輸量，已得到另一個更好的基可行解。解改進的具體步驟為：(1)以xij為換入變量，找出它在運輸表中的閉回路；(2)以空格(Ai,Bj)為第一個奇數頂點，沿閉回路的順(或逆)時針方向前進，對閉回路上的頂點依次編號；(3)在閉回路上的所有偶數頂點中，找出運輸量最小的xij的頂點，以該格中的變量為換出變量;(4)以運輸量最小的xij為調整量，將該閉合回路上所有奇數頂點處的運輸量都增加這一數值，所有偶數頂點處的運輸量都減去這一數值，從而得出一新的運輸方案。該運輸方案的總費用比原運輸方案減少。然后再對得到的新解進行最優性檢驗。運輸問題的數學模型（假定產銷平衡）例：對上面用最小元素法得出的解進行改進。

B1B2B3B4產量A116A210A322銷量81412144841241121039851161121210-1

B1B2B3B4產量A116A210A322銷量814121448412411210398511682121484b2運價：246+2*（-1）=244運輸問題的數學模型（假定產銷平衡）再用位勢法或閉回路法求這個新解各非基變量的檢驗數，結果列于下表。由于所有非基變量的檢驗數全非負，故為最優解。

B1B2B3B4產量A116A210A322銷量81412144841241121039851160221291對這個解來說，因為

ij=0,若x11為換入變量可再得一解，它與上面最優解的目標函數值相等，故它也是一個最優解。幾點說明

1、若運輸問題的某一基可行解有多個非基變量的檢驗數為負，在繼續進行迭代時，取它們中的任一變量為換入變量可使目標函數值得到改善，但通常取最小者對應的變量為換入變量。

2、當迭代到運輸問題的最優解時，如果有某非基變量的檢驗數為0，則說明該運輸問題有多重最優解。

3、當運輸問題某部分產地的產量和與某一部分銷地的銷量和相等時，在迭代過程中有可能在某個格填入一個運量時需同時劃去運輸表的一行和一列，這時就出現了退化。在運輸問題中，退化解是時常發生的。為了使表上作業法的迭代工作能順利進行下去，退化時應在同時劃去的一行或一列中的某個格中填入數字0，表示這個格中的變量是取值為0的基變量。使迭代過程中基變量個數恰好為(m+n-1)個。運輸問題的進一步討論一、產銷不平衡的運輸問題前面講述的運輸問題的算法，是以總產量等于總銷量為前提的。實際上，在很多運輸問題中，總產量不等于總銷量。這時，為了使用前述表上作業法求解，就需將產銷不平衡問題化為產銷平衡運輸問題。如果總產量大于總銷量，即運輸問題的進一步討論為借助于產銷平衡時的表上作業法求解，可增加一個假想的銷地Bn+1，由于實際上它不存在，因而由產地Ai調運到這個假想銷地的物品數量xi,n+1，實際上是就地存儲在Ai的物品數量。就地存儲的物品不經過運輸，故可令其單位運價ci,n+1=0。

若令假想地的銷量為bn+1，且則模型變為：運輸問題的進一步討論

？例某市有三個造紙廠A1、A2和A3，其紙的產量分別為8個單位、5個單位和9個單位，有4個集中用戶B1、B2、B3和B4，其需用量分別為4個單位，3個單位，5個單位和6個單位