運輸問題-下載課件

2022/12/211一、運輸問題的數(shù)學(xué)模型例：某運輸問題的資料如下：單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)量A1291029A213425A384257銷量38462022/12/211一、運輸問題的數(shù)學(xué)模型例：某運輸問題的2022/12/2122022/12/212某種物品有m個產(chǎn)地A1,A2,…,Am，各產(chǎn)地的產(chǎn)量分別是a1,a2,…,am；有n個銷地B1,B2,…,Bn，各銷地的銷量分別為b1,b2,…,bn。假設(shè)從產(chǎn)地Ai(i=1,2,…,m)向銷地Bj(j=1,2,…,n)運輸單位物品的運價是cij，怎樣調(diào)運這些物品才能使總運費最??？運輸問題-下載課件運輸問題的數(shù)學(xué)模型運輸問題的數(shù)學(xué)模型2022/12/215運輸問題數(shù)學(xué)模型的特點1.運輸問題有有限個最優(yōu)解2.運輸問題約束條件的特點：運輸問題的數(shù)學(xué)模型包含m×n個變量，(m+n)個約束方程，其系數(shù)矩陣的結(jié)構(gòu)比較松散且特殊。2022/12/215運輸問題數(shù)學(xué)模型的特點1.運輸問題有有2022/12/216運輸問題的解運輸問題也是一個線性規(guī)劃問題，其求解時仍然可以先找一個基可行解，進行解的最優(yōu)性檢驗，若不是最優(yōu)，就進行迭代，繼續(xù)檢驗和調(diào)整直到最優(yōu)，因此要求每步得到的解都是基可行解，需滿足(1)滿足所有約束條件；(2)基變量對應(yīng)的系數(shù)列向量線性無關(guān)；(3)解中非零變量的個數(shù)不能大于m+n-1個，原因是運輸問題中雖有m+n個約束條件，但由于總產(chǎn)量等于總銷量，故只有m+n-1個約束條件是線性獨立的；(4)保持基變量的個數(shù)在迭代過程中為m+n-1個。2022/12/216運輸問題的解運輸問題也是一個線性規(guī)劃問2022/12/217二、表上作業(yè)法表上作業(yè)法是單純形法在求解運輸問題時的一種簡化方法，其實質(zhì)是單純形法,但具體計算和術(shù)語有所不同，其步驟可歸納為：(1)找出初始基可行解：即在(m×n)產(chǎn)銷平衡表上用最小元素法或西北角法給出m+n-1個數(shù)字，稱為數(shù)字格，它們就是初始基變量的取值。(2)求各非基變量的檢驗數(shù)，即在表上計算空格的檢驗數(shù)，判別是否達到最優(yōu)解。如已是最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一步。(3)確定換入變量和換出變量，找出新的基可行解。在表上用閉回路法調(diào)整。(4)重復(fù)(2)，(3)直到得到最優(yōu)解為止。2022/12/217二、表上作業(yè)法表上作業(yè)法是單純形法在求

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

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

判定是否最優(yōu)？是結(jié)束最優(yōu)方案運輸問題求解思路圖確定初始方案改進調(diào)整否判定是否是結(jié)束最優(yōu)方

（一）初始基本可行解的確定

例2：甲、乙兩個煤礦供應(yīng)A、B、C三個城市用煤，各煤礦產(chǎn)量及各城市需煤量、各煤礦到各城市的運輸單價見表所示，求使總運輸費用最少的調(diào)運方案。

（一）初始基本可行解的確定例2：甲、乙兩個煤礦供應(yīng)例題有關(guān)信息表450200150100

日銷量（需求量）250756580

乙200100

7090

甲

日產(chǎn)量（供應(yīng)量）CBA運距城市煤礦例題有關(guān)信息表日銷量日產(chǎn)量運距城市例題數(shù)學(xué)模型例題數(shù)學(xué)模型

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

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450

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

150100100100100100100調(diào)銷地90

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

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

得到初始調(diào)運方案為：2022/12/2115練習(xí)單位銷地運價產(chǎn)地產(chǎn)量311310719284741059銷量3656產(chǎn)銷平衡例：某食品公司下屬的A1、A2、A3，3個廠生產(chǎn)方便食品，要運輸?shù)紹1、B2、B3、B4，4個銷售點，數(shù)據(jù)如下：用表上作業(yè)法求最初運輸方案。2022/12/2115練習(xí)單位銷地產(chǎn)量31132022/12/2116B1B2B3B4產(chǎn)量A17,3,0A2

4,1,0A39銷量3,06,05,1,06,3,0311310192741058341633總的運輸費用＝（3×1）＋（6×4）＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元2022/12/2116B1B2B3B4產(chǎn)量A17,3,0A（2）西北角法不是優(yōu)先考慮具有最小單位運價的供銷業(yè)務(wù)，而是優(yōu)先滿足運輸表中西北角（左上角）上空格的供銷要求（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調(diào)銷地90

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

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

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

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450100100100150初始調(diào)運方案中以X12(X21)為起點的閉回路調(diào)銷地90非基變量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)銷平衡的條件下，該非基變量增加一個單位運量而成為基變量時目標(biāo)函數(shù)值的變化量。非基變量X12的檢驗數(shù)：非基變量X21的檢驗數(shù)：2、對偶變量法（位勢法）檢驗數(shù)公式：

分別表示前m個約束等式對應(yīng)的對偶變量；分別表示后n個約束等式對應(yīng)的對偶變量。2、對偶變量法（位勢法）檢驗數(shù)公式：初始調(diào)運方案對偶變量對應(yīng)表

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

B1B2B3產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450對偶變量vjv1v2v3100100100150對偶變量

uiu1u2初始調(diào)運方案對偶變量對應(yīng)表調(diào)銷地

以初始調(diào)運方案為例，設(shè)置對偶變量和，然后構(gòu)造下面的方程組：以初始調(diào)運方案為例，設(shè)置對偶變量和

在式中，令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é)果相同。在式中，令u1=0，則可解得v1=90，v3=100方程組的特點：方程個數(shù)是m+n-1=2+3-1=4個，對偶變量共有m+n=2+3=5。初始方案的每一個基變量xij對應(yīng)一個方程——-—所在行和列對應(yīng)的對偶變量之和等于該基變量對應(yīng)的運距（或運價）：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與前面用閉回路法求得的結(jié)果相同。在式中，令u1=0，則可解得v1=90，v3=100位勢法計算非基變量xij檢驗數(shù)的公式σij=cij-（ui+vj）=（閉回路上奇數(shù)次頂點運距或運價之和）-（閉回路上偶數(shù)次頂點運距或運價之和）閉回路法計算非基變量xij檢驗數(shù)的公式：復(fù)習(xí)比較檢驗數(shù)計算的兩種方法位勢法計算非基變量xij檢驗數(shù)的公式σi2022/12/2133練習(xí)2022/12/2133練習(xí)2022/12/21342022/12/2134（三）解的改進——閉回路調(diào)整法如檢驗出初始解不是最優(yōu)解，即某非基變量檢驗數(shù)為負，說明將這個非基變量變?yōu)榛兞繒r運費會下降。根據(jù)表上作業(yè)法的第三步，需對初始方案進行改進。（三）解的改進——閉回路調(diào)整法如檢驗出初始解不是最優(yōu)解，即某解改進的步驟1．（如存在多個非基變量的檢驗數(shù)為負時，以最小負檢驗數(shù)所在空格對應(yīng)的變量）為換入變量，找出它在運輸表中的閉回路；2．以這個空格為第一個奇數(shù)頂點，沿閉回路的順（或逆）時針方向前進，對閉回路上的每個折點依次編號；3．在閉回路的所有偶數(shù)折點中，找出運輸量最小的一個折點，以該格中的變量為換出變量；4．將閉回路上所有奇數(shù)折點的運輸量都增加這一換出變量值，所有偶數(shù)折點處的運輸量都減去這一數(shù)值，最終得出一個新的運輸方案。對得出的新方案再進行最優(yōu)性檢驗，如不是最優(yōu)解，就重復(fù)以上步驟繼續(xù)進行調(diào)整，一直到得出最優(yōu)解為止。解改進的步驟1．（如存在多個非基變量的檢驗數(shù)為負時，以最小負調(diào)銷地運量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450100100100150++--因σ12=-20，畫出以x12為起始變量的閉回路020050100調(diào)銷地90

計算調(diào)整量：ε=Min（100，150）=100。按照下面的方法調(diào)整調(diào)運量：閉回路上，奇數(shù)次頂點的調(diào)運量加上ε，偶數(shù)次頂點的調(diào)運量減去ε；閉回路之外的變量調(diào)運量不變。得到新的調(diào)運方案：計算調(diào)整量：ε=Min（100，150）=100。得到調(diào)銷地運量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

45034250100100200

50重復(fù)上面的步驟，直至求出最優(yōu)調(diào)運方案：調(diào)銷地90調(diào)銷地運量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450150

50200

50調(diào)銷地90

結(jié)果

最優(yōu)調(diào)運方案是：

x11=50，x12=150，x21=50，x23=200

相應(yīng)的最小總運輸費用為：

Zmin=90×50+70×150+80×50+75×200=34000結(jié)2022/12/2142練習(xí)2022/12/2142練習(xí)練習(xí)

銷產(chǎn)B1B2B3B4產(chǎn)量A241241116A22103910A38511622銷量814121448練習(xí)銷B1B2B3B4產(chǎn)量A241241116A222022/12/2144（四）產(chǎn)銷不平衡的運輸問題

前面所講表上作業(yè)法，都是以產(chǎn)銷平衡為前提條件的，但是實際問題中產(chǎn)銷往往是不平衡的，這就需要設(shè)法把產(chǎn)銷不平衡的問題化成產(chǎn)銷平衡的問題。1、總產(chǎn)量大于總銷量即此時，運輸問題的數(shù)學(xué)模型可寫為2022/12/2144（四）產(chǎn)銷不平衡的運輸問題2022/12/2145要求解此問題，需要先將原問題變成平衡問題，可以假設(shè)一個銷地Bn+1(即實際問題中考慮產(chǎn)地的存量)，即：2022/12/2145要求解此問題，需要先將原問題變成平衡2022/12/2146單位運價表中的單位運價2、銷大于產(chǎn)：同樣假設(shè)一個產(chǎn)地即可，變化同上。2022/12/2146單位運價表中的單位運價B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5

A121134070A210359050A378120702030406040例題：B1B2B3B4A12113470A21035950A378（五）需要說明的幾個問題⑴無窮多最優(yōu)解：產(chǎn)銷平衡的運輸問題必定存在最優(yōu)解。如果非基變量的σij＝0，則該問題有無窮多最優(yōu)解。

⑵退化：表格中一般要有(m+n-1)個數(shù)字格。但有時，在分配運量時則需要同時劃去一行和一列，這時需要補一個0，以保證有(m+n-1)個數(shù)字格。一般可在劃去的行和列的任意空格處加一個0即可。在用閉回路法調(diào)整時，在閉回路上出現(xiàn)兩個或兩個以上的具有(-)標(biāo)記的相等的最小值。這時只能選擇其中一個作為調(diào)入格。而經(jīng)調(diào)整后，得到退化解。這時另一個數(shù)字格必須填入一個0，表明它是基變量。當(dāng)出現(xiàn)退化解后，并作改進調(diào)整時，可能在某閉回路上有標(biāo)記為(-)的取值為0的數(shù)字格，這時應(yīng)取調(diào)整量θ=0。（五）需要說明的幾個問題⑴無窮多最優(yōu)解：產(chǎn)銷平衡的運輸問題三、具有特殊調(diào)度約束的運輸問題供給量約束比如，某個供應(yīng)商給某個需求方的供應(yīng)量不超過百分之幾。中轉(zhuǎn)運輸問題增加幾個配送中心（或者物流網(wǎng)點），但是限制其吞吐能力。三、具有特殊調(diào)度約束的運輸問題供給量約束運輸問題-下載課件運輸問題-下載課件運輸問題-下載課件運輸問題-下載課件運輸問題-下載課件運輸問題-下載課件運輸問題-下載課件運輸問題-下載課件運輸問題-下載課件2222222222練習(xí)：某公司從三個供應(yīng)商（A1，A2，A3）購進某種物資來滿足四個銷售商（B1，B2，B3，B4）的生產(chǎn)需求，生產(chǎn)商的供給量、銷售商的需求量以及供需點之間的運輸距離如表所示。由于供不應(yīng)求和產(chǎn)品質(zhì)量原因，公司決定B2，B3的需求必須保證，B4不能從A3進貨，求最佳物資調(diào)運方案。B1B2B3B4供給量A116132217500A214131915600A319202310400需求量500700300200練習(xí)：某公司從三個供應(yīng)商（A1，A2，A3）購進某種物資來滿2022/12/2163B1B2B3B4產(chǎn)量A1500500A2400200600400A3100300400A40200200銷量500100700200300200170016132217141319192023M15M+1412230MM0M-4M-191235002022/12/2163B1B2B3B4產(chǎn)量12/2164單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)量A1291029A213425A384257銷量384621練習(xí)：某公司從三個供應(yīng)商（A1，A2，A3）購進某種物資來滿足四個銷售商的生產(chǎn)需求，生產(chǎn)商的供給量、銷售商廠的需求量以及供需點之間的運輸距離如表所示。假設(shè)供應(yīng)商之間可以互相轉(zhuǎn)運，銷售商之間也可以相互轉(zhuǎn)運。求最佳物資調(diào)運方案。2022/12/2164單位銷地B1B2B3B4A1A2A3A1013A210MA33M0B1B2B3B4B10142B21021B34203B42130A1A2A3A1013A210MA33M0B1B2B3B4B2022/12/2166B1B2B3B4產(chǎn)量A13693A23252A33473銷量384621291021348425233-56862022/12/2166B1B2B3B4產(chǎn)量A1369A22022/12/2167B1B2B3B4產(chǎn)量A1369A2055A3347銷量3846212910213484252835631532022/12/2167B1B2B3B4產(chǎn)量A1369A2閱讀推薦1、《物流工程》，齊二石，方慶琯.機械工業(yè)出版社，2006。2、《運籌學(xué)》閱讀推薦1、《物流工程》，齊二石，方慶琯.機械工業(yè)出版社，22022/12/2169一、運輸問題的數(shù)學(xué)模型例：某運輸問題的資料如下：單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)量A1291029A213425A384257銷量38462022/12/211一、運輸問題的數(shù)學(xué)模型例：某運輸問題的2022/12/21702022/12/212某種物品有m個產(chǎn)地A1,A2,…,Am，各產(chǎn)地的產(chǎn)量分別是a1,a2,…,am；有n個銷地B1,B2,…,Bn，各銷地的銷量分別為b1,b2,…,bn。假設(shè)從產(chǎn)地Ai(i=1,2,…,m)向銷地Bj(j=1,2,…,n)運輸單位物品的運價是cij，怎樣調(diào)運這些物品才能使總運費最小？運輸問題-下載課件運輸問題的數(shù)學(xué)模型運輸問題的數(shù)學(xué)模型2022/12/2173運輸問題數(shù)學(xué)模型的特點1.運輸問題有有限個最優(yōu)解2.運輸問題約束條件的特點：運輸問題的數(shù)學(xué)模型包含m×n個變量，(m+n)個約束方程，其系數(shù)矩陣的結(jié)構(gòu)比較松散且特殊。2022/12/215運輸問題數(shù)學(xué)模型的特點1.運輸問題有有2022/12/2174運輸問題的解運輸問題也是一個線性規(guī)劃問題，其求解時仍然可以先找一個基可行解，進行解的最優(yōu)性檢驗，若不是最優(yōu)，就進行迭代，繼續(xù)檢驗和調(diào)整直到最優(yōu)，因此要求每步得到的解都是基可行解，需滿足(1)滿足所有約束條件；(2)基變量對應(yīng)的系數(shù)列向量線性無關(guān)；(3)解中非零變量的個數(shù)不能大于m+n-1個，原因是運輸問題中雖有m+n個約束條件，但由于總產(chǎn)量等于總銷量，故只有m+n-1個約束條件是線性獨立的；(4)保持基變量的個數(shù)在迭代過程中為m+n-1個。2022/12/216運輸問題的解運輸問題也是一個線性規(guī)劃問2022/12/2175二、表上作業(yè)法表上作業(yè)法是單純形法在求解運輸問題時的一種簡化方法，其實質(zhì)是單純形法,但具體計算和術(shù)語有所不同，其步驟可歸納為：(1)找出初始基可行解：即在(m×n)產(chǎn)銷平衡表上用最小元素法或西北角法給出m+n-1個數(shù)字，稱為數(shù)字格，它們就是初始基變量的取值。(2)求各非基變量的檢驗數(shù)，即在表上計算空格的檢驗數(shù)，判別是否達到最優(yōu)解。如已是最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一步。(3)確定換入變量和換出變量，找出新的基可行解。在表上用閉回路法調(diào)整。(4)重復(fù)(2)，(3)直到得到最優(yōu)解為止。2022/12/217二、表上作業(yè)法表上作業(yè)法是單純形法在求

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

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

判定是否最優(yōu)？是結(jié)束最優(yōu)方案運輸問題求解思路圖確定初始方案改進調(diào)整否判定是否是結(jié)束最優(yōu)方

（一）初始基本可行解的確定

例2：甲、乙兩個煤礦供應(yīng)A、B、C三個城市用煤，各煤礦產(chǎn)量及各城市需煤量、各煤礦到各城市的運輸單價見表所示，求使總運輸費用最少的調(diào)運方案。

（一）初始基本可行解的確定例2：甲、乙兩個煤礦供應(yīng)例題有關(guān)信息表450200150100

日銷量（需求量）250756580

乙200100

7090

甲

日產(chǎn)量（供應(yīng)量）CBA運距城市煤礦例題有關(guān)信息表日銷量日產(chǎn)量運距城市例題數(shù)學(xué)模型例題數(shù)學(xué)模型

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

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450

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

150100100100100100100調(diào)銷地90

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

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

得到初始調(diào)運方案為：2022/12/2183練習(xí)單位銷地運價產(chǎn)地產(chǎn)量311310719284741059銷量3656產(chǎn)銷平衡例：某食品公司下屬的A1、A2、A3，3個廠生產(chǎn)方便食品，要運輸?shù)紹1、B2、B3、B4，4個銷售點，數(shù)據(jù)如下：用表上作業(yè)法求最初運輸方案。2022/12/2115練習(xí)單位銷地產(chǎn)量31132022/12/2184B1B2B3B4產(chǎn)量A17,3,0A2

4,1,0A39銷量3,06,05,1,06,3,0311310192741058341633總的運輸費用＝（3×1）＋（6×4）＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元2022/12/2116B1B2B3B4產(chǎn)量A17,3,0A（2）西北角法不是優(yōu)先考慮具有最小單位運價的供銷業(yè)務(wù)，而是優(yōu)先滿足運輸表中西北角（左上角）上空格的供銷要求（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調(diào)銷地90

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

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

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

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450100100100150初始調(diào)運方案中以X12(X21)為起點的閉回路調(diào)銷地90非基變量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)銷平衡的條件下，該非基變量增加一個單位運量而成為基變量時目標(biāo)函數(shù)值的變化量。非基變量X12的檢驗數(shù)：非基變量X21的檢驗數(shù)：2、對偶變量法（位勢法）檢驗數(shù)公式：

分別表示前m個約束等式對應(yīng)的對偶變量；分別表示后n個約束等式對應(yīng)的對偶變量。2、對偶變量法（位勢法）檢驗數(shù)公式：初始調(diào)運方案對偶變量對應(yīng)表

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

B1B2B3產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450對偶變量vjv1v2v3100100100150對偶變量

uiu1u2初始調(diào)運方案對偶變量對應(yīng)表調(diào)銷地

以初始調(diào)運方案為例，設(shè)置對偶變量和，然后構(gòu)造下面的方程組：以初始調(diào)運方案為例，設(shè)置對偶變量和

在式中，令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é)果相同。在式中，令u1=0，則可解得v1=90，v3=100方程組的特點：方程個數(shù)是m+n-1=2+3-1=4個，對偶變量共有m+n=2+3=5。初始方案的每一個基變量xij對應(yīng)一個方程——-—所在行和列對應(yīng)的對偶變量之和等于該基變量對應(yīng)的運距（或運價）：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與前面用閉回路法求得的結(jié)果相同。在式中，令u1=0，則可解得v1=90，v3=100位勢法計算非基變量xij檢驗數(shù)的公式σij=cij-（ui+vj）=（閉回路上奇數(shù)次頂點運距或運價之和）-（閉回路上偶數(shù)次頂點運距或運價之和）閉回路法計算非基變量xij檢驗數(shù)的公式：復(fù)習(xí)比較檢驗數(shù)計算的兩種方法位勢法計算非基變量xij檢驗數(shù)的公式σi2022/12/21101練習(xí)2022/12/2133練習(xí)2022/12/211022022/12/2134（三）解的改進——閉回路調(diào)整法如檢驗出初始解不是最優(yōu)解，即某非基變量檢驗數(shù)為負，說明將這個非基變量變?yōu)榛兞繒r運費會下降。根據(jù)表上作業(yè)法的第三步，需對初始方案進行改進。（三）解的改進——閉回路調(diào)整法如檢驗出初始解不是最優(yōu)解，即某解改進的步驟1．（如存在多個非基變量的檢驗數(shù)為負時，以最小負檢驗數(shù)所在空格對應(yīng)的變量）為換入變量，找出它在運輸表中的閉回路；2．以這個空格為第一個奇數(shù)頂點，沿閉回路的順（或逆）時針方向前進，對閉回路上的每個折點依次編號；3．在閉回路的所有偶數(shù)折點中，找出運輸量最小的一個折點，以該格中的變量為換出變量；4．將閉回路上所有奇數(shù)折點的運輸量都增加這一換出變量值，所有偶數(shù)折點處的運輸量都減去這一數(shù)值，最終得出一個新的運輸方案。對得出的新方案再進行最優(yōu)性檢驗，如不是最優(yōu)解，就重復(fù)以上步驟繼續(xù)進行調(diào)整，一直到得出最優(yōu)解為止。解改進的步驟1．（如存在多個非基變量的檢驗數(shù)為負時，以最小負調(diào)銷地運量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450100100100150++--因σ12=-20，畫出以x12為起始變量的閉回路020050100調(diào)銷地90

計算調(diào)整量：ε=Min（100，150）=100。按照下面的方法調(diào)整調(diào)運量：閉回路上，奇數(shù)次頂點的調(diào)運量加上ε，偶數(shù)次頂點的調(diào)運量減去ε；閉回路之外的變量調(diào)運量不變。得到新的調(diào)運方案：計算調(diào)整量：ε=Min（100，150）=100。得到調(diào)銷地運量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

45034250100100200

50重復(fù)上面的步驟，直至求出最優(yōu)調(diào)運方案：調(diào)銷地90調(diào)銷地運量產(chǎn)地

B1B2B3

產(chǎn)量A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250

銷量

100

150

200

450150

50200

50調(diào)銷地90

結(jié)果

最優(yōu)調(diào)運方案是：

x11=50，x12=150，x21=50，x23=200

相應(yīng)的最小總運輸費用為：

Zmin=90×50+70×150+80×50+75×200=34000結(jié)2022/12/21110練習(xí)2022/12/2142練習(xí)練習(xí)

銷產(chǎn)B1B2B3B4產(chǎn)量A241241116A22103910A38511622銷量814121448練習(xí)銷B1B2B3B4產(chǎn)量A241241116A222022/12/21112（四）產(chǎn)銷不平衡的運輸問題

前面所講表上作業(yè)法，都是以產(chǎn)銷平衡為前提條件的，但是實際問題中產(chǎn)銷往往是不平衡的，這就需要設(shè)法把產(chǎn)銷不平衡的問題化成產(chǎn)銷平衡的問題。1、總產(chǎn)量大于總銷量即此時，運輸問題的數(shù)學(xué)模型可寫為2022/12/2144（四）產(chǎn)銷不平衡的運輸問題2022/12/21113要求解此問題，需要先將原問題變成平衡問題，可以假設(shè)一個銷地Bn+1(即實際問題中考慮產(chǎn)地的存量)，即：2022/12/2145要求解此問題，需要先將原問題變成平衡2022/12/21114單位運價表中的單位運價2、銷大于產(chǎn)：同樣假設(shè)一個產(chǎn)