運輸問題表上作業(yè)法課件

關于運輸問題表上作業(yè)法第1頁，講稿共35頁，2023年5月2日，星期三

確定初始方案(初始基本可行解)

改進調(diào)整（換基迭代）否

判定是否最優(yōu)？是結(jié)束最優(yōu)方案圖1運輸問題求解思路圖第2頁，講稿共35頁，2023年5月2日，星期三

二、初始基本可行解的確定

例2：甲、乙兩個煤礦供應A、B、C三個城市用煤，各煤礦產(chǎn)量及各城市需煤量、各煤礦到各城市的運輸單價見表所示，求使總運輸費用最少的調(diào)運方案。第3頁，講稿共35頁，2023年5月2日，星期三例題有關信息表450200150100

日銷量（需求量）250756580

乙200100

7090

甲

日產(chǎn)量（供應量）CBA運距城市煤礦第4頁，講稿共35頁，2023年5月2日，星期三例題數(shù)學模型第5頁，講稿共35頁，2023年5月2日，星期三

（1）最小元素法：從運價最小的格開始，在格內(nèi)的標上允許取得的最大數(shù)。然后按運價從小到大順序填數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進行下去，直至得到一個基本可行解。第6頁，講稿共35頁，2023年5月2日，星期三調(diào)銷地運量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450

用最小元素法確定初始調(diào)運方案

150100100100100100100第7頁，講稿共35頁，2023年5月2日，星期三

得到初始調(diào)運方案為：

x11=100，x13=100，x22=150，x23=100

第8頁，講稿共35頁，2023年5月2日，星期三（2）西北角法不是優(yōu)先考慮具有最小單位運價的供銷業(yè)務，而是優(yōu)先滿足運輸表中西北角（左上角）上空格的供銷要求第9頁，講稿共35頁，2023年5月2日，星期三調(diào)銷地運量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X21

65

X2275

X23250

銷量

100

150

200

450

用西北角法確定初始調(diào)運方案

100100100

5050200200第10頁，講稿共35頁，2023年5月2日，星期三

得到初始調(diào)運方案為：

x11=100，x12=100，x22=50，x23=200

第11頁，講稿共35頁，2023年5月2日，星期三三、最優(yōu)性檢驗根據(jù)最小元素法或西北角法求得運輸問題的初始基可行解之后，按照表上作業(yè)法的第二步，下面需對這個解進行最優(yōu)性判別，看它是否為本運輸問題的最優(yōu)解.第12頁，講稿共35頁，2023年5月2日，星期三１、閉回路法思路：要判定運輸問題的初始基可行解是否為最優(yōu)解，可仿照一般單純形法，檢驗這個解的各非基變量（對應于運輸表中的空格）的檢驗數(shù)。檢驗數(shù)：運輸問題中非基變量（對應于空格）的檢驗數(shù)定義為給某空格增加單位運量導致總費用的增加量。如果有某空格（Ａi、Bj）的檢驗數(shù)為負，說明將Xij變?yōu)榛兞繉⑹惯\輸費用減少，故當前這個解不是最優(yōu)解。若所有空格的檢驗數(shù)全為非負，則不管怎樣變換，均不能使運輸費用降低，即目標函數(shù)值已無法改進，這個解就是最優(yōu)解。第13頁，講稿共35頁，2023年5月2日，星期三閉回路：在給出的調(diào)運方案的運輸表上，從一個空格（非基變量）出發(fā)，沿水平或垂直方向前進，只有碰到代表基變量的數(shù)字格才能向左或向右轉(zhuǎn)90°繼續(xù)前進，直至最終回到初始空格而形成的一條回路。從每一空格出發(fā)，一定可以找到一條且只存在唯一一條閉回路。第14頁，講稿共35頁，2023年5月2日，星期三以xij空格為第一個奇數(shù)頂點，沿閉回路的順（或逆）時針方向前進，對閉回路上的每個折點依次編號；非基變量xij的檢驗數(shù)：現(xiàn)在，在用最小元素法確定例2初始調(diào)運方案的基礎上，計算非基變量X12的檢驗數(shù)：=（閉回路上奇數(shù)次頂點運距或運價之和）-（閉回路上偶數(shù)次頂點運距或運價之和）第15頁，講稿共35頁，2023年5月2日，星期三調(diào)銷地運量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450100100100150初始調(diào)運方案中以X12(X21)為起點的閉回路第16頁，講稿共35頁，2023年5月2日，星期三非基變量X12的檢驗數(shù)：非基變量X21的檢驗數(shù)：

=（c12+c23）-（c13+c22）

=70+75-（100+65）=-20，=（c21+c13）-（c11+c23）=80+100-（90+75）=15。經(jīng)濟含義：在保持產(chǎn)銷平衡的條件下，該非基變量增加一個單位運量而成為基變量時目標函數(shù)值的變化量。第17頁，講稿共35頁，2023年5月2日，星期三2、對偶變量法（位勢法）檢驗數(shù)公式：

分別表示前m個約束等式對應的對偶變量；分別表示后n個約束等式對應的對偶變量。第18頁，講稿共35頁，2023年5月2日，星期三初始調(diào)運方案對偶變量對應表

調(diào)銷地運量產(chǎn)地

B1B2B3產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450對偶變量vjv1v2v3100100100150對偶變量

uiu1u2第19頁，講稿共35頁，2023年5月2日，星期三

以初始調(diào)運方案為例，設置對偶變量和，然后構造下面的方程組：第20頁，講稿共35頁，2023年5月2日，星期三

在式中，令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與前面用閉回路法求得的結(jié)果相同。第21頁，講稿共35頁，2023年5月2日，星期三方程組的特點：方程個數(shù)是m+n-1=2+3-1=4個，對偶變量共有m+n=2+3=5。初始方案的每一個基變量xij對應一個方程——-—所在行和列對應的對偶變量之和等于該基變量對應的運距（或運價）：ui+vj=cij；

方程組恰有一個自由變量，可以證明方程組中任意一個變量均可取作自由變量。這個時候方程的解可以稱為位勢。第22頁，講稿共35頁，2023年5月2日，星期三

在式中，令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與前面用閉回路法求得的結(jié)果相同。第23頁，講稿共35頁，2023年5月2日，星期三位勢法計算非基變量xij檢驗數(shù)的公式σij=cij-（ui+vj）=（閉回路上奇數(shù)次頂點運距或運價之和）-（閉回路上偶數(shù)次頂點運距或運價之和）閉回路法計算非基變量xij檢驗數(shù)的公式：復習比較檢驗數(shù)計算的兩種方法思考：試解釋位勢變量的含義（提示：寫出運輸問題的對偶問題）第24頁，講稿共35頁，2023年5月2日，星期三四、解的改進如檢驗出初始解不是最優(yōu)解，即某非基變量檢驗數(shù)為負，說明將這個非基變量變?yōu)榛兞繒r運費會下降。根據(jù)表上作業(yè)法的第三步，需對初始方案進行改進。第25頁，講稿共35頁，2023年5月2日，星期三（一）解改進的步驟為：1．（如存在多個非基變量的檢驗數(shù)為負時，以最小負檢驗數(shù)所在空格對應的變量）為換入變量，找出它在運輸表中的閉回路；2．以這個空格為第一個奇數(shù)頂點，沿閉回路的順（或逆）時針方向前進，對閉回路上的每個折點依次編號；第26頁，講稿共35頁，2023年5月2日，星期三解的改進步驟續(xù)：3．在閉回路的所有偶數(shù)折點中，找出運輸量最小的一個折點，以該格中的變量為換出變量；4．將閉回路上所有奇數(shù)折點的運輸量都增加這一換出變量值，所有偶數(shù)折點處的運輸量都減去這一數(shù)值，最終得出一個新的運輸方案。對得出的新方案再進行最優(yōu)性檢驗，如不是最優(yōu)解，就重復以上步驟繼續(xù)進行調(diào)整，一直到得出最優(yōu)解為止。第27頁，講稿共35頁，2023年5月2日，星期三調(diào)銷地運量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450100100100150++--因σ12=-20，畫出以x12為起始變量的閉回路020050100第28頁，講稿共35頁，2023年5月2日，星期三

計算調(diào)整量：ε=Min（100，150）=100。按照下面的方法調(diào)整調(diào)運量：閉回路上，奇數(shù)次頂點的調(diào)運量加上ε，偶數(shù)次頂點的調(diào)運量減去ε；閉回路之外的變量調(diào)運量不變。得到新的調(diào)運方案：第29頁，講稿共35頁，2023年5月2日，星期三調(diào)銷地運量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

45034250100100200

50重復上面的步驟，直至求出最優(yōu)調(diào)運方案：第30頁，講稿共35頁，2023年5月2日，星期三調(diào)銷地運量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165