《運輸問題表上作業法》由會員分享，可在線閱讀，更多相關《運輸問題表上作業法(35頁珍藏版)》請在人人文庫網上搜索。

1、7.4 表上作業法,一、表上作業法迭代步驟 1按某種規則找出一個初始基可行解； 2對現行解作最優性判斷，即求各非基變量的檢驗數，判別是否達到最優解，如已是最優解，則停止計算，如不是最優解，則進行下一步驟； 3在表上對初始方案進行改進，找出新的基可行解，再按第二步進行判別，直至找出最優解。,圖 1運輸問題求解思路圖,二、初始基本可行解的確定,例2：甲、乙兩個煤礦供應A、B、C三個城市用煤，各煤礦產量及各城市需煤量、各煤礦到各城市的運輸單價見表所示，求使總運輸費用最少的調運方案。,例題有關信息表,例題 數學模型,(1)最小元素法：從運價最小的格開始，在格內的標上允許取得的最大數。然后按運價從小到大。

2、順序填數。若某行(列)的產量(銷量)已滿足，則把該行(列)的其他格劃去。如此進行下去，直至得到一個基本可行解。,用最小元素法確定初始調運方案,150,100,100,100,100,100,100,得到初始調運方案為： x11=100，x13=100，x22=150，x23=100,(2)西北角法 不是優先考慮具有最小單位運價的供銷業務，而是優先滿足運輸表中西北角(左上角)上空格的供銷要求,用西北角法確定初始調運方案,100,100,100,50,50,200,200,得到初始調運方案為： x11=100，x12=100，x22=50，x23=200,三、最優性檢驗,根據最小元素法或西北角法求。

3、得運輸問題的初始基可行解之后，按照表上作業法的第二步，下面需對這個解進行最優性判別，看它是否為本運輸問題的最優解.,、閉回路法,思路：要判定運輸問題的初始基可行解是否為最優解，可仿照一般單純形法，檢驗這個解的各非基變量(對應于運輸表中的空格)的檢驗數。 檢驗數：運輸問題中非基變量(對應于空格)的檢驗數定義為給某空格增加單位運量導致總費用的增加量。 如果有某空格(i、Bj)的檢驗數為負，說明將Xij變為基變量將使運輸費用減少，故當前這個解不是最優解。若所有空格的檢驗數全為非負，則不管怎樣變換，均不能使運輸費用降低，即目標函數值已無法改進，這個解就是最優解。,閉回路：在給出的調運方案的運輸表上，從。

4、一個空格(非基變量)出發，沿水平或垂直方向前進，只有碰到代表基變量的數字格才能向左或向右轉90繼續前進，直至最終回到初始空格而形成的一條回路。 從每一空格出發，一定可以找到一條且只存在唯一一條閉回路 。,以xij空格為第一個奇數頂點，沿閉回路的順(或逆)時針方向前進，對閉回路上的每個折點依次編號； 非基變量 xij 的檢驗數：,現在，在用最小元素法確定例2初始調運方案的基礎上，計算非基變量X12的檢驗數 ：,初始調運方案中以X12(X21)為起點的閉回路,非基變量X12的檢驗數：,非基變量X21的檢驗數：,=(c12+c23)-(c13+c22) =70+75-(100+65)=-20，,=(。

5、c21+c13)-(c11+c23) =80+100-(90+75)=15。,經濟含義：在保持產銷平衡的條件下，該非基變量增加一個單位運量而成為基變量時目標函數值的變化量。,2、對偶變量法(位勢法),檢驗數公式： 分別表示前m個約束等式對應的對偶變量； 分別表示后n個約束等式對應的對偶變量。,初始調運方案對偶變量對應表,以初始調運方案為例，設置對偶變量 和 ， 然后構造下面的方程組：,在式中，令u1=0，則可解得v1=90，v3=100，u2=-25，v2=90，于是 12=c12-(u1+v2)=70-(0+90)=-20 21=c21-(u2+v1)=80-(-25+90)=15 與前面用。

6、閉回路法求得的結果相同。,方程組的特點： 方程個數是m+n-1=2+3-1=4個，對偶變量共有m+n=2+3=5。 初始方案的每一個基變量xij對應一個方程-所在行和列對應的對偶變量之和等于該基變量對應的運距(或運價)：ui+vj=cij； 方程組恰有一個自由變量，可以證明方程組中任意一個變量均可取作自由變量。 這個時候方程的解可以稱為位勢。,在式中，令u1=0，則可解得v1=90，v3=100，u2=-25，v2=90，于是 12=c12-(u1+v2)=70-(0+90)=-20 21=c21-(u2+v1)=80-(-25+90)=15 與前面用閉回路法求得的結果相同。,位勢法計算非基變。

7、量xij檢驗數的公式 ij=cij-(ui+vj),復習比較檢驗數計算的兩種方法,思考：試解釋位勢變量的含義(提示：寫出運輸問題的對偶問題),四、解的改進,如檢驗出初始解不是最優解，即某非基變量檢驗數為負，說明將這個非基變量變為基變量時運費會下降。根據表上作業法的第三步，需對初始方案進行改進。,(一)解改進的步驟為：,1(如存在多個非基變量的檢驗數為負時，以最小負檢驗數所在空格對應的變量)為換入變量，找出它在運輸表中的閉回路； 2以這個空格為第一個奇數頂點，沿閉回路的順(或逆)時針方向前進，對閉回路上的每個折點依次編號；,解的改進步驟續：,3在閉回路的所有偶數折點中，找出運輸量最小的一個折點，。

8、以該格中的變量為換出變量； 4將閉回路上所有奇數折點的運輸量都增加這一換出變量值，所有偶數折點處的運輸量都減去這一數值，最終得出一個新的運輸方案。 對得出的新方案再進行最優性檢驗，如不是最優解，就重復以上步驟繼續進行調整，一直到得出最優解為止。,因12=-20 ，畫出以x12為起始變量的閉回路,0,200,50,100,計算調整量：=Min(100，150)=100。 按照下面的方法調整調運量： 閉回路上，奇數次頂點的調運量加上，偶數次頂點的調運量減去；閉回路之外的變量調運量不變。,得到新的調運方案：,重復上面的步驟，直至求出最優調運方案：,結 果 最優調運方案是： x11=50，x12=15。

9、0，x21=50，x23=200 相應的最小總運輸費用為： Zmin=9050+70150+8050+75200 =34000,課堂練習：,五、幾點說明,(1)、若運輸問題的某一基可行解有多個非基變量的檢驗數為負，在繼續迭代中。通常取 中最小者對應的變量為換入變量； (2)、當迭代到運輸問題的最優解時，如果有某非基變量的檢驗數等于0，則說明該運輸問題有多重最優解；,(3)當運輸問題某部分產地的產量和，與某部分銷地的銷量和相等時，在迭代過程中間有可能有某個格填入一個運量時需同時劃去運輸表的一行和一列，這時就出現了退化。為了使表上作業法的迭代工作能順利進行下去，退化時應在同時劃去的一行或一列中的某個格中填入0，表示這個格中的變量是取值為0的基變量，使迭代過程中基變量個數恰好為(m+n-1)個。

總結

以上是生活随笔為你收集整理的c语言实现运输问题表上作业法,运输问题表上作业法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。