運(yùn)輸問(wèn)題表上作業(yè)法

關(guān)于運(yùn)輸問(wèn)題表上作業(yè)法

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

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

判定是否最優(yōu)？是結(jié)束最優(yōu)方案圖1運(yùn)輸問(wèn)題求解思路圖第2頁(yè),共35頁(yè)，2024年2月25日，星期天

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

例2：甲、乙兩個(gè)煤礦供應(yīng)A、B、C三個(gè)城市用煤，各煤礦產(chǎn)量及各城市需煤量、各煤礦到各城市的運(yùn)輸單價(jià)見(jiàn)表所示，求使總運(yùn)輸費(fèi)用最少的調(diào)運(yùn)方案。第3頁(yè),共35頁(yè)，2024年2月25日，星期天例題有關(guān)信息表450200150100

日銷量（需求量）250756580

乙200100

7090

甲

日產(chǎn)量（供應(yīng)量）CBA運(yùn)距城市煤礦第4頁(yè),共35頁(yè)，2024年2月25日，星期天例題數(shù)學(xué)模型第5頁(yè),共35頁(yè)，2024年2月25日，星期天

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

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450

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

150100100100100100100第7頁(yè),共35頁(yè)，2024年2月25日，星期天

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

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

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

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X21

65

X2275

X23250

銷量

100

150

200

450

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

100100100

5050200200第10頁(yè),共35頁(yè)，2024年2月25日，星期天

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

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

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

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450100100100150初始調(diào)運(yùn)方案中以X12(X21)為起點(diǎn)的閉回路第16頁(yè),共35頁(yè)，2024年2月25日，星期天非基變量X12的檢驗(yàn)數(shù)：非基變量X21的檢驗(yàn)數(shù)：

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

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

分別表示前m個(gè)約束等式對(duì)應(yīng)的對(duì)偶變量；分別表示后n個(gè)約束等式對(duì)應(yīng)的對(duì)偶變量。第18頁(yè),共35頁(yè)，2024年2月25日，星期天初始調(diào)運(yùn)方案對(duì)偶變量對(duì)應(yīng)表

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

B1B2B3產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450對(duì)偶變量vjv1v2v3100100100150對(duì)偶變量

uiu1u2第19頁(yè),共35頁(yè)，2024年2月25日，星期天

以初始調(diào)運(yùn)方案為例，設(shè)置對(duì)偶變量和，然后構(gòu)造下面的方程組：第20頁(yè),共35頁(yè)，2024年2月25日，星期天

在式中，令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頁(yè),共35頁(yè)，2024年2月25日，星期天方程組的特點(diǎn)：

方程個(gè)數(shù)是m+n-1=2+3-1=4個(gè)，對(duì)偶變量共有m+n=2+3=5。

初始方案的每一個(gè)基變量xij對(duì)應(yīng)一個(gè)方程——-—所在行和列對(duì)應(yīng)的對(duì)偶變量之和等于該基變量對(duì)應(yīng)的運(yùn)距（或運(yùn)價(jià)）：ui+vj=cij；

方程組恰有一個(gè)自由變量，可以證明方程組中任意一個(gè)變量均可取作自由變量。這個(gè)時(shí)候方程的解可以稱為位勢(shì)。第22頁(yè),共35頁(yè)，2024年2月25日，星期天

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

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450100100100150++--因σ12=-20，畫出以x12為起始變量的閉回路020050100第28頁(yè),共35頁(yè)，2024年2月25日，星期天

計(jì)算調(diào)整量：ε=Min（100，150）=100。

按照下面的方法調(diào)整調(diào)運(yùn)量：閉回路上，奇數(shù)次頂點(diǎn)的調(diào)運(yùn)量加上ε，偶數(shù)次頂點(diǎn)的調(diào)運(yùn)量減去ε；閉回路之外的變量調(diào)運(yùn)量不變。

得到新的調(diào)運(yùn)方案：第29頁(yè),共35頁(yè)，2024年2月25日，星期天調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

45034250100100200

50重復(fù)上面的步驟，直至求出最優(yōu)調(diào)運(yùn)方案：第30頁(yè),共35頁(yè)，2024年2月25日，星期天調(diào)銷地運(yùn)量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275