第04章運(yùn)輸問(wèn)題-運(yùn)籌學(xué)課件

1第4章

運(yùn)輸問(wèn)題

1第4章2運(yùn)輸問(wèn)題與有關(guān)概念運(yùn)輸問(wèn)題的求解—表上作業(yè)法運(yùn)輸問(wèn)題應(yīng)用—建模本章內(nèi)容重點(diǎn)2運(yùn)輸問(wèn)題與有關(guān)概念本章內(nèi)容重點(diǎn)34.1運(yùn)輸問(wèn)題模型及有關(guān)概念

4.1.1問(wèn)題的提出

一般的運(yùn)輸問(wèn)題就是要解決把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地，在每個(gè)產(chǎn)地的供應(yīng)量與每個(gè)銷地的需求量已知，并知道各地之間的運(yùn)輸單價(jià)的前提下，如何確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案。34.1運(yùn)輸問(wèn)題模型及有關(guān)概念4.1.1問(wèn)題的提出44.1運(yùn)輸問(wèn)題模型及有關(guān)概念

例4.1:某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？44.1運(yùn)輸問(wèn)題模型及有關(guān)概念例4.1:某公司從5解：產(chǎn)銷平衡問(wèn)題：總產(chǎn)量=總銷量

設(shè)xij

為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：4.1運(yùn)輸問(wèn)題模型及有關(guān)概念5解：產(chǎn)銷平衡問(wèn)題：4.1運(yùn)輸問(wèn)題模型及有關(guān)概念6

Min

f=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）4.1運(yùn)輸問(wèn)題模型及有關(guān)概念6Minf=6x11+4x12+6x13+6x21+7

111000

000111100100

010010

001001系數(shù)矩陣4.1運(yùn)輸問(wèn)題模型及有關(guān)概念7系數(shù)矩陣4.1運(yùn)輸問(wèn)題模型及有關(guān)概念8

模型系數(shù)矩陣特征

1.共有m+n行，分別表示各產(chǎn)地和銷地；mn列，分別表示各決策變量；

2.每列只有兩個(gè)1，其余為0，分別表示只有一個(gè)產(chǎn)地和一個(gè)銷地被使用。4.1運(yùn)輸問(wèn)題模型及有關(guān)概念8模型系數(shù)矩陣特征4.1運(yùn)輸問(wèn)題模型及有關(guān)概念9一般運(yùn)輸問(wèn)題的提法：假設(shè)A1,A2,…,Am

表示某物資的m個(gè)產(chǎn)地；B1,B2,…,Bn

表示某物資的n個(gè)銷地；si表示產(chǎn)地Ai

的產(chǎn)量；dj

表示銷地Bj

的銷量；cij

表示把物資從產(chǎn)地Ai

運(yùn)往銷地Bj

的單位運(yùn)價(jià)（表4-3）。如果

s1+s2+…+sm

=d1+d2+…+dn則稱為產(chǎn)銷平衡問(wèn)題；否則，稱產(chǎn)銷不平衡。首先討論產(chǎn)銷平衡問(wèn)題。4.1.2一般運(yùn)輸問(wèn)題的線性規(guī)劃模型及求解思路9一般運(yùn)輸問(wèn)題的提法：4.1.2一般運(yùn)輸問(wèn)題的線性規(guī)劃模型10表4-3運(yùn)輸問(wèn)題數(shù)據(jù)表4.1運(yùn)輸問(wèn)題模型及有關(guān)概念

銷地產(chǎn)地B1B2…Bn產(chǎn)量A1A2┇

Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmns1s2┇

sm銷量d1d2…dn

設(shè)xij

為從產(chǎn)地Ai

運(yùn)往銷地Bj

的運(yùn)輸量，根據(jù)這個(gè)運(yùn)輸問(wèn)題的要求，可以建立運(yùn)輸變量表（表4-4）。10表4-3運(yùn)輸問(wèn)題數(shù)據(jù)表4.1運(yùn)輸問(wèn)題模型及有關(guān)概念11表4-4運(yùn)輸問(wèn)題變量表4.1運(yùn)輸問(wèn)題模型及有關(guān)概念

銷地產(chǎn)地B1B2…Bn產(chǎn)量A1A2

┇Amx11x12…x1nx21x22…x2n┇┇┇xm1xm2…xmns1s2

┇sm銷量d1d2…dn

11表4-4運(yùn)輸問(wèn)題變量表4.1運(yùn)輸問(wèn)題模型及有關(guān)概念

mn

Minf=cijxiji=1j=1

n

s.t.xij=si

i=1,2,…,m

(4-5)

j=1

m

xij=dj

j=1,2,…,n

(4-6)

i=1xij≥0(i=1,2,…,m;j=1,2,…,n)4.1運(yùn)輸問(wèn)題模型及有關(guān)概念

對(duì)于產(chǎn)銷平衡問(wèn)題，可得到下列運(yùn)輸問(wèn)題的模型：mn4.1運(yùn)輸問(wèn)題13運(yùn)輸問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題，在求解時(shí)依然可以采用單純形法的思路，如圖4-1所示。由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計(jì)算，則無(wú)法利用這些有利條件。人們?cè)诜治鲞\(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對(duì)運(yùn)輸問(wèn)題的表上作業(yè)法。下面主要討論基本可行解、檢驗(yàn)數(shù)以及基的轉(zhuǎn)換等問(wèn)題。產(chǎn)銷平衡運(yùn)輸模型求解13運(yùn)輸問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題，在求解時(shí)依然可以采用14產(chǎn)銷平衡運(yùn)輸模型求解過(guò)程基本可行解是否最優(yōu)解結(jié)束換基是否圖4-1運(yùn)輸問(wèn)題的求解思路返回14產(chǎn)銷平衡運(yùn)輸模型求解過(guò)程基本是否結(jié)束換基是否圖4-1運(yùn)15

運(yùn)輸問(wèn)題求解的有關(guān)概念考慮產(chǎn)銷平衡問(wèn)題，由于我們關(guān)心的量均在表4-3與表4-4中，因此考慮把表4-3與表4-4合成一個(gè)表,如下表4-5

表4-5運(yùn)輸問(wèn)題求解作業(yè)數(shù)據(jù)表(下頁(yè)）15運(yùn)輸問(wèn)題求解的有關(guān)概念16產(chǎn)銷平衡運(yùn)輸模型數(shù)據(jù)表

銷地產(chǎn)地B1B2…Bn產(chǎn)量A1c11

x11c12

x12…c1n

x1na1A2c21

x21c22

x22…c2n

x2na2┇┇┇┇┇Amcm1

xm1cm2

xm2…cmnxmnam銷量b1b2…bn

16產(chǎn)銷平衡運(yùn)輸模型數(shù)據(jù)表銷地B1B2…Bn產(chǎn)量A117

運(yùn)輸問(wèn)題的基變量共有m+n-1個(gè)，系數(shù)矩陣A的秩為m+n-1。運(yùn)輸問(wèn)題的m+n-1個(gè)變量構(gòu)成基變量的充分必要條件是不含閉回路。閉回路、閉回路的頂點(diǎn)運(yùn)輸模型的基變量17運(yùn)輸問(wèn)題的基變量共有m+n-1個(gè)，系數(shù)矩陣18

定義4.1在表4-5的決策變量格中，凡是能夠排列成下列形式的

xab,xac,xdc,xde,…,xst,xsb(4-7)

或xab,xcb,xcd,xed,…,xst,xat(4-8)

其中，a,d,…,s

各不相同；b,c,…,t

各不相同，我們稱之為變量集合的一個(gè)閉回路，并將式（4-7）、式（4-8）中的變量稱為這個(gè)閉回路的頂點(diǎn)。

為了說(shuō)明這個(gè)特征，我們不加證明的給出一些概念和結(jié)論。下面的討論建立在表4-5中決策變量格的基礎(chǔ)上。4.1運(yùn)輸問(wèn)題模型及有關(guān)概念18定義4.1在表4-5的決策變量格中，凡是19例如，x13,x16,x36,x34,x24,x23

；

x23,x53,x55,x45,x41,x21

；

x11,x14,x34,x31等都是閉回路。若把閉回路的各變量格看作節(jié)點(diǎn)，在表中可以畫出如下形式的閉回路：4.1運(yùn)輸問(wèn)題模型及有關(guān)概念

閉回路示意圖19例如，x13,x16,x36,x34,x24,20

根據(jù)定義可以看出閉回路的一些明顯特點(diǎn)：

(1)閉回路均為一封閉折線，它的每一條邊，或?yàn)樗降模驗(yàn)榇怪钡模?/p>

(2)閉回路的每一條邊（水平的或垂直的）均有且僅有兩個(gè)閉回路的頂點(diǎn)（變量格）。4.1運(yùn)輸問(wèn)題模型及有關(guān)概念20根據(jù)定義可以看出閉回路的一些明顯特點(diǎn)：4.1運(yùn)21

(1)設(shè)xab,xac,xdc,xde,…,xst,xsb

是一個(gè)閉回路，那么該閉回路中變量所對(duì)應(yīng)的系數(shù)列向量pab,pac,

pdc,pde,…,pst,psb

線性相關(guān)；

(2)若變量組xab,xcd,xef,…,xst

中包含一個(gè)部分組構(gòu)成閉回路，那么該變量組所對(duì)應(yīng)的系數(shù)列向量pab,pcd,

pef,…,pst

線性相關(guān)。根據(jù)上述結(jié)論以及線性規(guī)劃基變量的特點(diǎn)，可以得到下面重要定理及其推論。關(guān)于閉回路有如下的一些重要結(jié)論21(1)設(shè)xab,xac,xdc,x定理4.1

變量組xab,xcd,xef,…,xst

所對(duì)應(yīng)的系數(shù)列向量pab,pcd,pef,…,pst

線性無(wú)關(guān)的充分必要條件是這個(gè)變量組中不包含閉回路。推論產(chǎn)銷平衡運(yùn)輸問(wèn)題的m+n-1個(gè)變量構(gòu)成基變量的充分必要條件是它不含閉回路。這個(gè)推論給出了運(yùn)輸問(wèn)題基本解的重要性質(zhì)，也為尋求基本可行解提供了依據(jù)。4.1運(yùn)輸問(wèn)題模型及有關(guān)概念定理4.1變量組xab,xcd,xef,…4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

表上作業(yè)法求解運(yùn)輸問(wèn)題的思想和單純形法完全類似：確定一個(gè)初始基本可行解——

根據(jù)最優(yōu)性判別準(zhǔn)則來(lái)檢查這個(gè)基本可行解是不是最優(yōu)的？如果是，則計(jì)算結(jié)束；如果不是，則進(jìn)行換基。

——

直至求出最優(yōu)解為止。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法表上作業(yè)法求解運(yùn)輸問(wèn)244.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

一、初始基本可行解的確定根據(jù)上面的討論，要求得運(yùn)輸問(wèn)題的初始基本可行解，必須保證找到m+n–1個(gè)不構(gòu)成閉回路的基變量。一般的方法步驟如下：

244.2運(yùn)輸問(wèn)題求解—表上作業(yè)法一、初始基本可行解的確定254.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

(1)在運(yùn)輸問(wèn)題求解作業(yè)數(shù)據(jù)表中任選一個(gè)單元格

xij(Ai

行Bj

列交叉位置上的格),令

xij

=min{ai,bj

}

即從Ai

向Bj

運(yùn)最大量(使行或列在允許的范圍內(nèi)盡量飽和，即使一個(gè)約束方程得以滿足),填入xij

的相應(yīng)位置；254.2運(yùn)輸問(wèn)題求解—表上作業(yè)法(1)在運(yùn)輸問(wèn)題求解作業(yè)26運(yùn)輸問(wèn)題求解—表上作業(yè)法(2)從ai

和bj

中分別減去xij

的值，修正為新的ai

和bj即調(diào)整Ai

的擁有量及Bj

的需求量；(3)若ai=0，則劃去對(duì)應(yīng)的行（已經(jīng)把擁有的量全部運(yùn)走），若bj=0則劃去對(duì)應(yīng)的列（已經(jīng)把需要的量全部運(yùn)來(lái)），且每次只劃去一行或一列（即每次要去掉且只去掉一個(gè)約束）；26運(yùn)輸問(wèn)題求解—表上作業(yè)法(2)從ai和bj27運(yùn)輸問(wèn)題求解—表上作業(yè)法(4)當(dāng)最終的運(yùn)輸量選定時(shí)，其所在行、列同時(shí)滿足，此時(shí)要同時(shí)劃去一行和一列。這樣，運(yùn)輸平衡表中所有的行與列均被劃去，則得到了一個(gè)初始基本可行解。否則在剩下的運(yùn)輸平衡表中選下一個(gè)變量，返回(1)。27運(yùn)輸問(wèn)題求解—表上作業(yè)法(4)當(dāng)最終的運(yùn)輸量選定時(shí)，其28上述計(jì)算過(guò)程可用流程圖描述如下（圖4-2）取未劃去的單元格xij,令xij=min{ai,bj}ai’=ai-xijbj’=bj-xijai’=0?劃去第i行劃去第j列是否

bj’=0否所有行列是否均被劃去是找到初始基本可行解圖4-2求運(yùn)輸問(wèn)題的初始基本可行解過(guò)程注：為了方便，這里總記剩余的產(chǎn)量和銷量為ai,bj28上述計(jì)算過(guò)程可用流程圖描述如下（圖4-2）取未劃去的單元294.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

按照上述方法所產(chǎn)生的一組變量的取值將滿足下面條件：

(1)所得的變量均為非負(fù)，且變量總數(shù)恰好為m+n–1個(gè)；

(2)所有的約束條件均得到滿足；

(3)所得的變量不構(gòu)成閉回路。294.2運(yùn)輸問(wèn)題求解—表上作業(yè)法按照上述方法所產(chǎn)生的一304.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

在上面的方法中，xij

的選取方法并沒有給予限制，若采取不同的規(guī)則來(lái)選取xij

，則得到不同的方法，較常用的方法有西北角法和最小元素法。下面分別舉例予以說(shuō)明。304.2運(yùn)輸問(wèn)題求解—表上作業(yè)法在上面314.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

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

（1）西北角法：從西北角（左上角）格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按行（列）標(biāo)下一格的數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。314.2運(yùn)輸問(wèn)題求解—表上作業(yè)法1、初始基本可行32

（2）最小元素法：從運(yùn)價(jià)最小的格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按運(yùn)價(jià)從小到大順序填數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法32（2）最小元素法：從運(yùn)價(jià)最小的格開始，在格內(nèi)的右33

注:應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只劃去一行或一列，只有最后一個(gè)元例外（同時(shí)劃去一行和一列）。當(dāng)填上一個(gè)數(shù)后行、列同時(shí)飽和時(shí)，也應(yīng)任意劃去一行（列），在保留的列（行）中沒被劃去的格內(nèi)標(biāo)一個(gè)0。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法33注:應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法354.2運(yùn)輸問(wèn)題求解—表上作業(yè)法354.2運(yùn)輸問(wèn)題求解—表上作業(yè)法364.2運(yùn)輸問(wèn)題求解—表上作業(yè)法364.2運(yùn)輸問(wèn)題求解—表上作業(yè)法37

最優(yōu)性檢驗(yàn)就是檢查所得到的方案是不是最優(yōu)方案。檢查的方法與單純形方法中的原理相同，即計(jì)算檢驗(yàn)數(shù)。由于目標(biāo)要求極小，因此，當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案；否則就不是最優(yōu)，需要進(jìn)行調(diào)整。下面介紹兩種求檢驗(yàn)數(shù)的方法:閉回路法和位勢(shì)法二、基本可行解的最優(yōu)性檢驗(yàn)

4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法37最優(yōu)性檢驗(yàn)就是檢查所得到的方案是不是最優(yōu)方案。381、閉回路法為了方便，我們以表1給出的初始基本可行解方案為例，考察初始方案的任意一個(gè)非基變量，比如x24。根據(jù)初始方案，產(chǎn)地A2的產(chǎn)品是不運(yùn)往銷地B4的。如果現(xiàn)在改變初始方案，把A2的產(chǎn)品運(yùn)送1個(gè)單位給B4

，那么為了保持產(chǎn)銷平衡，就必須使x14

或x34

減少1個(gè)單位；而如果x14

減少1個(gè)單位，第1行的運(yùn)輸量就必須增加1個(gè)單位，例如x13

增加1個(gè)單位，那么為了保持產(chǎn)銷平衡，就必須使x23

減少1個(gè)單位。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法381、閉回路法4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法39

這個(gè)過(guò)程就是尋找一個(gè)以非基變量x24為起始頂點(diǎn)的閉回路—{x24，x14，x13，x23}，這個(gè)閉回路的其他頂點(diǎn)均為基變量(對(duì)應(yīng)著填上數(shù)字的格)。容易計(jì)算出上述調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為8–10+3–2＝-1，即總的運(yùn)費(fèi)減少1個(gè)單位，這就說(shuō)明原始方案不是最優(yōu)方案，可以進(jìn)行調(diào)整以得到更好的方案。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法39這個(gè)過(guò)程就是尋找一個(gè)以非基變量x24為起始頂點(diǎn)40

可以證明，如果對(duì)閉回路的方向不加區(qū)別（即只要起點(diǎn)及其他所有頂點(diǎn)完全相同，而不區(qū)別行進(jìn)方向），那么以每一個(gè)非基量為起始頂點(diǎn)的閉回路就存在而且唯一。因此，對(duì)每一個(gè)非基變量可以找到而且只能找到唯一的一個(gè)閉回路。表4-10中用虛線畫出以非基變量x22

為起始頂點(diǎn)的閉回路。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法40可以證明，如果對(duì)閉回路的方向不加區(qū)別（即41表4-10以非基變量x22

為起始頂點(diǎn)的閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量3[]11[]341037139[]218[]47[]4610[]539銷量365620(產(chǎn)銷平衡)A1A2A341表4-10以非基變量x22為起始頂點(diǎn)的閉回路銷地B42

可以計(jì)算出以非基變量x22

為起始頂點(diǎn)的閉回路調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為

9–2+3–10+5–4＝1

即總的運(yùn)費(fèi)增加1個(gè)單位，這就說(shuō)明這個(gè)調(diào)整不能改善目標(biāo)值。從上面的討論可以看出，當(dāng)某個(gè)非基變量增加一個(gè)單位時(shí)，有若干個(gè)基變量的取值受其影響。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法42可以計(jì)算出以非基變量x22為起始頂點(diǎn)的閉43

這樣，利用單位產(chǎn)品變化（運(yùn)輸?shù)膯挝毁M(fèi)用）可計(jì)算出它們對(duì)目標(biāo)函數(shù)的綜合影響，其作用與線性規(guī)劃單純形方法中的檢驗(yàn)數(shù)完全相同。故也稱這個(gè)綜合影響為該非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)。上面計(jì)算的兩個(gè)非基變量的檢驗(yàn)數(shù)為24=-1，22=1。閉回路方法原理就是通過(guò)尋找閉回路來(lái)找到非基變量的檢驗(yàn)數(shù)。

4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法43這樣，利用單位產(chǎn)品變化（運(yùn)輸?shù)膯挝毁M(fèi)用）可計(jì)44

如果規(guī)定作為起始頂點(diǎn)的非基變量為第1個(gè)頂點(diǎn)，閉回路的其他頂點(diǎn)依次為第2個(gè)頂點(diǎn)、第3個(gè)頂點(diǎn)……那么就有

ij=(閉回路上的奇數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和)-(閉回路上的偶數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和)

其中ij為非基變量的下角指標(biāo)。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法44如果規(guī)定作為起始頂點(diǎn)的非基變量為第1個(gè)頂45

按上述作法，可計(jì)算出表1的所有非基變量的檢驗(yàn)數(shù)，把它們填入相應(yīng)位置的方括號(hào)內(nèi)，如圖4-11所示。

銷地產(chǎn)地B1B2B3B4產(chǎn)量A13[1]11[2]341037A2139[1]218[-1]4A37[10]4610[12]539銷量365620(產(chǎn)銷平衡)表4-11初始基本可行解及檢驗(yàn)數(shù)45按上述作法，可計(jì)算出表1的所有非基變量的檢驗(yàn)46

顯然，當(dāng)所有非基變量的檢驗(yàn)數(shù)均大于或等于零時(shí)，現(xiàn)行的調(diào)運(yùn)方案就是最優(yōu)方案，因?yàn)榇藭r(shí)對(duì)現(xiàn)行方案作任何調(diào)整都將導(dǎo)致總的運(yùn)輸費(fèi)用增加。閉回路法的主要缺點(diǎn)是：當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路以及計(jì)算兩方面都會(huì)產(chǎn)生困難。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法46顯然，當(dāng)所有非基變量的檢驗(yàn)數(shù)均大于或等于零時(shí)

2.位勢(shì)法

位勢(shì)：設(shè)對(duì)應(yīng)基變量xij

的m+n-1個(gè)ij

，存在ui,vj

滿足

ui+vj=cij

，i=1,2…,m;j=1,2…,n.

稱這些ui,vj

為該基本可行解對(duì)應(yīng)的位勢(shì)。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法2.位勢(shì)法4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法48由于有m+n

個(gè)變量（ui,vj

），

m+n-1個(gè)方程（基變量個(gè)數(shù)），故有一個(gè)自由變量，位勢(shì)不唯一。

利用位勢(shì)求檢驗(yàn)數(shù)：

ij=cij-ui-vj

i=1,…,m;j=1,…,n4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法48由于有m+n個(gè)變量（ui,vj），49前例，位勢(shì)法求檢驗(yàn)數(shù)：step1

從任意基變量對(duì)應(yīng)的cij

開始,任取

ui

或vj

，然后利用cij=ui+vj公式依次找出m+n

個(gè)ui

、vj,我們從c14=10開始step2

計(jì)算非基變量的檢驗(yàn)數(shù)

ij=cij-ui-vj

；填入圓圈內(nèi)4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法49前例，位勢(shì)法求檢驗(yàn)數(shù)：4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法504.2運(yùn)輸問(wèn)題求解—表上作業(yè)法504.2運(yùn)輸問(wèn)題求解—表上作業(yè)法51

當(dāng)非基變量的檢驗(yàn)數(shù)出現(xiàn)負(fù)值時(shí)，則表明當(dāng)前的基本可行解不是最優(yōu)解。在這種情況下，應(yīng)該對(duì)基本可行解進(jìn)行調(diào)整，即找到一個(gè)新的基本可行解使目標(biāo)函數(shù)值下降，這一過(guò)程通常稱為換基(或主元變換)過(guò)程。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法三、求新的基本可行解51當(dāng)非基變量的檢驗(yàn)數(shù)出現(xiàn)負(fù)值時(shí)，則表明當(dāng)前的基52

（1）選負(fù)檢驗(yàn)數(shù)中最小者rk，那么xrk

為主元，作為進(jìn)基變量（上頁(yè)圖中x24）;

（2）以xrk

為起點(diǎn)找一條閉回路，除xrk

外其余頂點(diǎn)必須為基變量格（上頁(yè)圖中的回路）;4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

在運(yùn)輸問(wèn)題的表上作業(yè)法中，換基的過(guò)程是如下進(jìn)行：52（1）選負(fù)檢驗(yàn)數(shù)中最小者rk，那么xrk53（3）為閉回路的每一個(gè)頂點(diǎn)標(biāo)號(hào)，xrk

為1，沿一個(gè)方向（順時(shí)針或逆時(shí)針）依次給各頂點(diǎn)標(biāo)號(hào)；（4）求=Min{xijxij對(duì)應(yīng)閉回路上的偶數(shù)標(biāo)號(hào)格}=xpq那么確定xpq為出基變量，為調(diào)整量；4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法53（3）為閉回路的每一個(gè)頂點(diǎn)標(biāo)號(hào)，xrk為1，沿一個(gè)54（5）對(duì)閉回路的各奇標(biāo)號(hào)頂點(diǎn)調(diào)整為：xij+，對(duì)各偶標(biāo)號(hào)頂點(diǎn)調(diào)整為：xij-，特別

xpq-=0，xpq變?yōu)榉腔兞?。重?fù)(2)、(3)步，直到所有檢驗(yàn)數(shù)均非負(fù)，得到最優(yōu)解。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法54（5）對(duì)閉回路的各奇標(biāo)號(hào)頂點(diǎn)調(diào)整為：xij+，對(duì)各554.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

ij≥0，得到最優(yōu)解

x13=5,x14=2,x21=3,x24=1,

x32=6,x34=3,其余xij=0;

最優(yōu)值：

f*=3×5+10×2+1×3+8×1+4×6+5×3=85554.2運(yùn)輸問(wèn)題求解—表上作業(yè)法ij≥056例題求解過(guò)程總結(jié)：

初始基本可行解56例題求解過(guò)程總結(jié)：

初始基本可行解位勢(shì)法求檢驗(yàn)數(shù)：位勢(shì)法求檢驗(yàn)數(shù)：58

選擇負(fù)檢驗(yàn)數(shù)，找出閉回路，確定調(diào)整運(yùn)輸量58選擇負(fù)檢驗(yàn)數(shù)，找出閉回路，確定調(diào)整運(yùn)輸量59

計(jì)算新的基本可行解，重新計(jì)算，檢驗(yàn)數(shù)均為非負(fù)，即得到最優(yōu)解：

；最優(yōu)值為8559計(jì)算新的基本可行解，重新計(jì)算，檢驗(yàn)數(shù)均為60產(chǎn)銷不平衡問(wèn)題的處理

實(shí)踐中的運(yùn)輸問(wèn)題常常非產(chǎn)銷平衡，為下列的一般運(yùn)輸問(wèn)題模型60產(chǎn)銷不平衡問(wèn)題的處理實(shí)踐中的運(yùn)輸問(wèn)題常常611.產(chǎn)量大于銷量的情況考慮si

>dj

情況，得到的數(shù)學(xué)模型為611.產(chǎn)量大于銷量的情況考慮si>dj情況，得62

我們只須在模型中的產(chǎn)量限制約束(前m個(gè)不等式約束)中引入m個(gè)松弛變量xin+1

i=1,2,…,m即可，變?yōu)椋簒ij+xin+1=si

i=1,2,…,m

然后，需設(shè)一個(gè)銷地Bn+1,它的銷量為：dn+1=si-

dj由于實(shí)際不運(yùn)送,它們的運(yùn)費(fèi)為cin+1=0i=1,2,…,m。于是，這個(gè)運(yùn)輸問(wèn)題就轉(zhuǎn)化成了一個(gè)產(chǎn)銷平衡的問(wèn)題62我們只須在模型中的產(chǎn)量限制約束(前m個(gè)63例4.3某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？63例4.3某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B164

解：增加一個(gè)虛設(shè)的銷地運(yùn)輸費(fèi)用為064解：增加一個(gè)虛設(shè)的銷地運(yùn)輸費(fèi)用為0652.銷量大于產(chǎn)量的情況考慮si

<dj

情況，得到的數(shù)學(xué)模型為652.銷量大于產(chǎn)量的情況考慮si<dj情況，得66

我們只須在模型中的銷量限制約束(后n個(gè)不等式約束)中引入n個(gè)松弛變量xm+1j

j=1,2,…,n即可，變?yōu)椋簒ij+xm+1j

=dj

j=1,2,…,n然后，需設(shè)一個(gè)銷地BAm+1,它的c產(chǎn)量為：dm+1=dj-

si由于實(shí)際不運(yùn)送,它們的運(yùn)費(fèi)為cm+1j=0j=1,2,…,n。于是，這個(gè)運(yùn)輸問(wèn)題就轉(zhuǎn)化成了一個(gè)產(chǎn)銷平衡的問(wèn)題66我們只須在模型中的銷量限制約束(后n個(gè)67

某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？例4.467某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、68解：增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為068解：增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為04.3運(yùn)輸問(wèn)題的應(yīng)用例4.5:某研究院有三個(gè)區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩處煤礦供應(yīng)，價(jià)格、質(zhì)量相同。供應(yīng)能力分別為1500、4000噸，運(yùn)價(jià)如下表。由于需求大于供給，經(jīng)研究提出，1區(qū)供應(yīng)量可減少0—300噸，2區(qū)必須滿足需求量，3區(qū)供應(yīng)量不少于1700噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。4.3運(yùn)輸問(wèn)題的應(yīng)用例4.5:某研究院有三個(gè)區(qū)。每70

解:根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價(jià)表：取M

代表一個(gè)很大的正數(shù)，其作用是強(qiáng)迫相應(yīng)的x31、x33、x34取值為0。

70解:根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價(jià)表：取M71例4.6:設(shè)有A、B、C三個(gè)化肥廠供應(yīng)1、2、3、4四個(gè)地區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表。試求總費(fèi)用為最低的化肥調(diào)撥方案。71例4.6:設(shè)有A、B、C三個(gè)化肥廠供應(yīng)1、2、3、4四個(gè)72首先，作出產(chǎn)銷平衡運(yùn)價(jià)表:最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為M；最高要求與最低要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為0。對(duì)應(yīng)4”的銷量50是考慮問(wèn)題本身適當(dāng)取的數(shù)據(jù)，根據(jù)產(chǎn)銷平衡要求確定D的產(chǎn)量為50。解：72首先，作出產(chǎn)銷平衡運(yùn)價(jià)表:最低要求必須滿足，因此把相應(yīng)生產(chǎn)與儲(chǔ)存問(wèn)題例4.7:某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表。如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用0.15萬(wàn)元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案生產(chǎn)與儲(chǔ)存問(wèn)題例4.7:某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分交貨：

生產(chǎn)：x11=10x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35

x13+x23+x33=25x33+x34≤30

x14+x24+x34+x44=20x44≤10解：設(shè)xij

為第i

季度生產(chǎn)的第j季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足把第i季度生產(chǎn)的柴油機(jī)數(shù)目看作第i

個(gè)生產(chǎn)廠的產(chǎn)量；把第j

季度交貨的柴油機(jī)數(shù)目看作第j

個(gè)銷售點(diǎn)的銷量；成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)。交貨：生產(chǎn)：解：設(shè)xij可構(gòu)造下列產(chǎn)銷平衡問(wèn)題：

目標(biāo)函數(shù)：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44

可構(gòu)造下列產(chǎn)銷平衡問(wèn)題：

目標(biāo)函數(shù)：Minf=10.76轉(zhuǎn)運(yùn)問(wèn)題:

實(shí)踐中，還會(huì)有轉(zhuǎn)運(yùn)站，那么常出現(xiàn)的運(yùn)輸方式就會(huì)有：產(chǎn)地轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)站銷地、產(chǎn)地產(chǎn)地、產(chǎn)地銷地、銷地轉(zhuǎn)運(yùn)站、銷地產(chǎn)地等。

為此，可把有輸出時(shí)稱發(fā)點(diǎn)、有輸入時(shí)稱收點(diǎn)。此時(shí)，產(chǎn)地、銷地與轉(zhuǎn)運(yùn)站均可視為既是發(fā)點(diǎn)又是收點(diǎn)，于是有如下關(guān)系產(chǎn)地：輸出量-輸入量=產(chǎn)量轉(zhuǎn)運(yùn)站：輸入量-輸出量=0

銷地：輸入量-輸出量=銷量76轉(zhuǎn)運(yùn)問(wèn)題:實(shí)踐中，還會(huì)有轉(zhuǎn)運(yùn)站，那么常出現(xiàn)的運(yùn)輸方式就77例4.7:

某儀器公司在大連和廣州有兩個(gè)分廠生產(chǎn)同一種儀器，大連分廠每月生產(chǎn)450臺(tái),廣州分廠每月生產(chǎn)600臺(tái)。該公司在上海和天津有兩個(gè)銷售公司負(fù)責(zé)對(duì)南京、濟(jì)南、南昌、青島四個(gè)城市的儀器供應(yīng)。另外因?yàn)榇筮B距離青島較近，公司同意大連分廠向青島直接供貨，運(yùn)輸費(fèi)用如下圖，單位是百元。問(wèn)應(yīng)該如何調(diào)運(yùn)儀器，可使總運(yùn)輸費(fèi)用最低？77例4.7:某儀器公司在大連和廣州有兩個(gè)分廠78圖中

1廣州、2大連、3上海、4天津、5南京、6濟(jì)南、7南昌、8青島78圖中1廣州、2大連、3上海、4天津、5南京、79

設(shè)xij

為從i

到j(luò)的運(yùn)輸量，可得到有下列特點(diǎn)的線性規(guī)劃模型：目標(biāo)函數(shù)：Minf=所有可能的運(yùn)輸費(fèi)用（運(yùn)輸單價(jià)與運(yùn)輸量乘積之和）約束條件：產(chǎn)地、銷地與轉(zhuǎn)運(yùn)站的運(yùn)輸限制產(chǎn)地i

：輸出量-輸入量=產(chǎn)量轉(zhuǎn)運(yùn)站：輸入量-輸出量=0

銷地j

：輸入量-輸出量=銷量解：79設(shè)xij為從i到j(luò)的運(yùn)輸量，80s.t.x13+x14≤600(廣州分廠供應(yīng)量限制）

x23+x24+x28≤450(大連分廠供應(yīng)量限制）

-x13-x23+x35+x36+x37+x38=0

（上海銷售公司，轉(zhuǎn)運(yùn)站）

-x14-x24+x45+x46+x47+x48=0

（天津銷售公司，轉(zhuǎn)運(yùn)站）Minf=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48

模型目標(biāo)函數(shù)：約束條件：80s.t.x13+x14≤60081模型（續(xù)）

x35+x45=200（南京的銷量）

x36+x46=150（濟(jì)南的銷量）

x37+x47=350（南昌的銷量）

x38+x48+x28=300（南京的銷量）

xij

≥0,i,j=1,2,3,4,5,6,7,8可求得結(jié)果：

x13=550,x14=0x23=0,x24=150,x28=300x35=200,x36=0,x37=350,x38=0x45=0,x46=150,x47=0,x48=081模型（續(xù)）

x35+x45=20082在實(shí)際問(wèn)題建模時(shí)，還會(huì)出現(xiàn)如下一些變化：（1）有時(shí)目標(biāo)函數(shù)求最大，如求利潤(rùn)最大或營(yíng)業(yè)額最大等；（2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，模型中可直接加入等式或不等式約束。運(yùn)輸問(wèn)題模型的其他情況82在實(shí)際問(wèn)題建模時(shí)，還會(huì)出現(xiàn)如下一些變化：運(yùn)輸問(wèn)題83第4章

運(yùn)輸問(wèn)題

1第4章84運(yùn)輸問(wèn)題與有關(guān)概念運(yùn)輸問(wèn)題的求解—表上作業(yè)法運(yùn)輸問(wèn)題應(yīng)用—建模本章內(nèi)容重點(diǎn)2運(yùn)輸問(wèn)題與有關(guān)概念本章內(nèi)容重點(diǎn)854.1運(yùn)輸問(wèn)題模型及有關(guān)概念

4.1.1問(wèn)題的提出

一般的運(yùn)輸問(wèn)題就是要解決把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地，在每個(gè)產(chǎn)地的供應(yīng)量與每個(gè)銷地的需求量已知，并知道各地之間的運(yùn)輸單價(jià)的前提下，如何確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案。34.1運(yùn)輸問(wèn)題模型及有關(guān)概念4.1.1問(wèn)題的提出864.1運(yùn)輸問(wèn)題模型及有關(guān)概念

例4.1:某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？44.1運(yùn)輸問(wèn)題模型及有關(guān)概念例4.1:某公司從87解：產(chǎn)銷平衡問(wèn)題：總產(chǎn)量=總銷量

設(shè)xij

為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：4.1運(yùn)輸問(wèn)題模型及有關(guān)概念5解：產(chǎn)銷平衡問(wèn)題：4.1運(yùn)輸問(wèn)題模型及有關(guān)概念88

Min

f=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）4.1運(yùn)輸問(wèn)題模型及有關(guān)概念6Minf=6x11+4x12+6x13+6x21+89

111000

000111100100

010010

001001系數(shù)矩陣4.1運(yùn)輸問(wèn)題模型及有關(guān)概念7系數(shù)矩陣4.1運(yùn)輸問(wèn)題模型及有關(guān)概念90

模型系數(shù)矩陣特征

1.共有m+n行，分別表示各產(chǎn)地和銷地；mn列，分別表示各決策變量；

2.每列只有兩個(gè)1，其余為0，分別表示只有一個(gè)產(chǎn)地和一個(gè)銷地被使用。4.1運(yùn)輸問(wèn)題模型及有關(guān)概念8模型系數(shù)矩陣特征4.1運(yùn)輸問(wèn)題模型及有關(guān)概念91一般運(yùn)輸問(wèn)題的提法：假設(shè)A1,A2,…,Am

表示某物資的m個(gè)產(chǎn)地；B1,B2,…,Bn

表示某物資的n個(gè)銷地；si表示產(chǎn)地Ai

的產(chǎn)量；dj

表示銷地Bj

的銷量；cij

表示把物資從產(chǎn)地Ai

運(yùn)往銷地Bj

的單位運(yùn)價(jià)（表4-3）。如果

s1+s2+…+sm

=d1+d2+…+dn則稱為產(chǎn)銷平衡問(wèn)題；否則，稱產(chǎn)銷不平衡。首先討論產(chǎn)銷平衡問(wèn)題。4.1.2一般運(yùn)輸問(wèn)題的線性規(guī)劃模型及求解思路9一般運(yùn)輸問(wèn)題的提法：4.1.2一般運(yùn)輸問(wèn)題的線性規(guī)劃模型92表4-3運(yùn)輸問(wèn)題數(shù)據(jù)表4.1運(yùn)輸問(wèn)題模型及有關(guān)概念

銷地產(chǎn)地B1B2…Bn產(chǎn)量A1A2┇

Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmns1s2┇

sm銷量d1d2…dn

設(shè)xij

為從產(chǎn)地Ai

運(yùn)往銷地Bj

的運(yùn)輸量，根據(jù)這個(gè)運(yùn)輸問(wèn)題的要求，可以建立運(yùn)輸變量表（表4-4）。10表4-3運(yùn)輸問(wèn)題數(shù)據(jù)表4.1運(yùn)輸問(wèn)題模型及有關(guān)概念93表4-4運(yùn)輸問(wèn)題變量表4.1運(yùn)輸問(wèn)題模型及有關(guān)概念

銷地產(chǎn)地B1B2…Bn產(chǎn)量A1A2

┇Amx11x12…x1nx21x22…x2n┇┇┇xm1xm2…xmns1s2

┇sm銷量d1d2…dn

11表4-4運(yùn)輸問(wèn)題變量表4.1運(yùn)輸問(wèn)題模型及有關(guān)概念

mn

Minf=cijxiji=1j=1

n

s.t.xij=si

i=1,2,…,m

(4-5)

j=1

m

xij=dj

j=1,2,…,n

(4-6)

i=1xij≥0(i=1,2,…,m;j=1,2,…,n)4.1運(yùn)輸問(wèn)題模型及有關(guān)概念

對(duì)于產(chǎn)銷平衡問(wèn)題，可得到下列運(yùn)輸問(wèn)題的模型：mn4.1運(yùn)輸問(wèn)題95運(yùn)輸問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題，在求解時(shí)依然可以采用單純形法的思路，如圖4-1所示。由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計(jì)算，則無(wú)法利用這些有利條件。人們?cè)诜治鲞\(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對(duì)運(yùn)輸問(wèn)題的表上作業(yè)法。下面主要討論基本可行解、檢驗(yàn)數(shù)以及基的轉(zhuǎn)換等問(wèn)題。產(chǎn)銷平衡運(yùn)輸模型求解13運(yùn)輸問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題，在求解時(shí)依然可以采用96產(chǎn)銷平衡運(yùn)輸模型求解過(guò)程基本可行解是否最優(yōu)解結(jié)束換基是否圖4-1運(yùn)輸問(wèn)題的求解思路返回14產(chǎn)銷平衡運(yùn)輸模型求解過(guò)程基本是否結(jié)束換基是否圖4-1運(yùn)97

運(yùn)輸問(wèn)題求解的有關(guān)概念考慮產(chǎn)銷平衡問(wèn)題，由于我們關(guān)心的量均在表4-3與表4-4中，因此考慮把表4-3與表4-4合成一個(gè)表,如下表4-5

表4-5運(yùn)輸問(wèn)題求解作業(yè)數(shù)據(jù)表(下頁(yè)）15運(yùn)輸問(wèn)題求解的有關(guān)概念98產(chǎn)銷平衡運(yùn)輸模型數(shù)據(jù)表

銷地產(chǎn)地B1B2…Bn產(chǎn)量A1c11

x11c12

x12…c1n

x1na1A2c21

x21c22

x22…c2n

x2na2┇┇┇┇┇Amcm1

xm1cm2

xm2…cmnxmnam銷量b1b2…bn

16產(chǎn)銷平衡運(yùn)輸模型數(shù)據(jù)表銷地B1B2…Bn產(chǎn)量A199

運(yùn)輸問(wèn)題的基變量共有m+n-1個(gè)，系數(shù)矩陣A的秩為m+n-1。運(yùn)輸問(wèn)題的m+n-1個(gè)變量構(gòu)成基變量的充分必要條件是不含閉回路。閉回路、閉回路的頂點(diǎn)運(yùn)輸模型的基變量17運(yùn)輸問(wèn)題的基變量共有m+n-1個(gè)，系數(shù)矩陣100

定義4.1在表4-5的決策變量格中，凡是能夠排列成下列形式的

xab,xac,xdc,xde,…,xst,xsb(4-7)

或xab,xcb,xcd,xed,…,xst,xat(4-8)

其中，a,d,…,s

各不相同；b,c,…,t

各不相同，我們稱之為變量集合的一個(gè)閉回路，并將式（4-7）、式（4-8）中的變量稱為這個(gè)閉回路的頂點(diǎn)。

為了說(shuō)明這個(gè)特征，我們不加證明的給出一些概念和結(jié)論。下面的討論建立在表4-5中決策變量格的基礎(chǔ)上。4.1運(yùn)輸問(wèn)題模型及有關(guān)概念18定義4.1在表4-5的決策變量格中，凡是101例如，x13,x16,x36,x34,x24,x23

；

x23,x53,x55,x45,x41,x21

；

x11,x14,x34,x31等都是閉回路。若把閉回路的各變量格看作節(jié)點(diǎn)，在表中可以畫出如下形式的閉回路：4.1運(yùn)輸問(wèn)題模型及有關(guān)概念

閉回路示意圖19例如，x13,x16,x36,x34,x24,102

根據(jù)定義可以看出閉回路的一些明顯特點(diǎn)：

(1)閉回路均為一封閉折線，它的每一條邊，或?yàn)樗降?，或?yàn)榇怪钡模?/p>

(2)閉回路的每一條邊（水平的或垂直的）均有且僅有兩個(gè)閉回路的頂點(diǎn)（變量格）。4.1運(yùn)輸問(wèn)題模型及有關(guān)概念20根據(jù)定義可以看出閉回路的一些明顯特點(diǎn)：4.1運(yùn)103

(1)設(shè)xab,xac,xdc,xde,…,xst,xsb

是一個(gè)閉回路，那么該閉回路中變量所對(duì)應(yīng)的系數(shù)列向量pab,pac,

pdc,pde,…,pst,psb

線性相關(guān)；

(2)若變量組xab,xcd,xef,…,xst

中包含一個(gè)部分組構(gòu)成閉回路，那么該變量組所對(duì)應(yīng)的系數(shù)列向量pab,pcd,

pef,…,pst

線性相關(guān)。根據(jù)上述結(jié)論以及線性規(guī)劃基變量的特點(diǎn)，可以得到下面重要定理及其推論。關(guān)于閉回路有如下的一些重要結(jié)論21(1)設(shè)xab,xac,xdc,x定理4.1

變量組xab,xcd,xef,…,xst

所對(duì)應(yīng)的系數(shù)列向量pab,pcd,pef,…,pst

線性無(wú)關(guān)的充分必要條件是這個(gè)變量組中不包含閉回路。推論產(chǎn)銷平衡運(yùn)輸問(wèn)題的m+n-1個(gè)變量構(gòu)成基變量的充分必要條件是它不含閉回路。這個(gè)推論給出了運(yùn)輸問(wèn)題基本解的重要性質(zhì)，也為尋求基本可行解提供了依據(jù)。4.1運(yùn)輸問(wèn)題模型及有關(guān)概念定理4.1變量組xab,xcd,xef,…4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

表上作業(yè)法求解運(yùn)輸問(wèn)題的思想和單純形法完全類似：確定一個(gè)初始基本可行解——

根據(jù)最優(yōu)性判別準(zhǔn)則來(lái)檢查這個(gè)基本可行解是不是最優(yōu)的？如果是，則計(jì)算結(jié)束；如果不是，則進(jìn)行換基。

——

直至求出最優(yōu)解為止。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法表上作業(yè)法求解運(yùn)輸問(wèn)1064.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

一、初始基本可行解的確定根據(jù)上面的討論，要求得運(yùn)輸問(wèn)題的初始基本可行解，必須保證找到m+n–1個(gè)不構(gòu)成閉回路的基變量。一般的方法步驟如下：

244.2運(yùn)輸問(wèn)題求解—表上作業(yè)法一、初始基本可行解的確定1074.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

(1)在運(yùn)輸問(wèn)題求解作業(yè)數(shù)據(jù)表中任選一個(gè)單元格

xij(Ai

行Bj

列交叉位置上的格),令

xij

=min{ai,bj

}

即從Ai

向Bj

運(yùn)最大量(使行或列在允許的范圍內(nèi)盡量飽和，即使一個(gè)約束方程得以滿足),填入xij

的相應(yīng)位置；254.2運(yùn)輸問(wèn)題求解—表上作業(yè)法(1)在運(yùn)輸問(wèn)題求解作業(yè)108運(yùn)輸問(wèn)題求解—表上作業(yè)法(2)從ai

和bj

中分別減去xij

的值，修正為新的ai

和bj即調(diào)整Ai

的擁有量及Bj

的需求量；(3)若ai=0，則劃去對(duì)應(yīng)的行（已經(jīng)把擁有的量全部運(yùn)走），若bj=0則劃去對(duì)應(yīng)的列（已經(jīng)把需要的量全部運(yùn)來(lái)），且每次只劃去一行或一列（即每次要去掉且只去掉一個(gè)約束）；26運(yùn)輸問(wèn)題求解—表上作業(yè)法(2)從ai和bj109運(yùn)輸問(wèn)題求解—表上作業(yè)法(4)當(dāng)最終的運(yùn)輸量選定時(shí)，其所在行、列同時(shí)滿足，此時(shí)要同時(shí)劃去一行和一列。這樣，運(yùn)輸平衡表中所有的行與列均被劃去，則得到了一個(gè)初始基本可行解。否則在剩下的運(yùn)輸平衡表中選下一個(gè)變量，返回(1)。27運(yùn)輸問(wèn)題求解—表上作業(yè)法(4)當(dāng)最終的運(yùn)輸量選定時(shí)，其110上述計(jì)算過(guò)程可用流程圖描述如下（圖4-2）取未劃去的單元格xij,令xij=min{ai,bj}ai’=ai-xijbj’=bj-xijai’=0?劃去第i行劃去第j列是否

bj’=0否所有行列是否均被劃去是找到初始基本可行解圖4-2求運(yùn)輸問(wèn)題的初始基本可行解過(guò)程注：為了方便，這里總記剩余的產(chǎn)量和銷量為ai,bj28上述計(jì)算過(guò)程可用流程圖描述如下（圖4-2）取未劃去的單元1114.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

按照上述方法所產(chǎn)生的一組變量的取值將滿足下面條件：

(1)所得的變量均為非負(fù)，且變量總數(shù)恰好為m+n–1個(gè)；

(2)所有的約束條件均得到滿足；

(3)所得的變量不構(gòu)成閉回路。294.2運(yùn)輸問(wèn)題求解—表上作業(yè)法按照上述方法所產(chǎn)生的一1124.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

在上面的方法中，xij

的選取方法并沒有給予限制，若采取不同的規(guī)則來(lái)選取xij

，則得到不同的方法，較常用的方法有西北角法和最小元素法。下面分別舉例予以說(shuō)明。304.2運(yùn)輸問(wèn)題求解—表上作業(yè)法在上面1134.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

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

（1）西北角法：從西北角（左上角）格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按行（列）標(biāo)下一格的數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。314.2運(yùn)輸問(wèn)題求解—表上作業(yè)法1、初始基本可行114

（2）最小元素法：從運(yùn)價(jià)最小的格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按運(yùn)價(jià)從小到大順序填數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法32（2）最小元素法：從運(yùn)價(jià)最小的格開始，在格內(nèi)的右115

注:應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只劃去一行或一列，只有最后一個(gè)元例外（同時(shí)劃去一行和一列）。當(dāng)填上一個(gè)數(shù)后行、列同時(shí)飽和時(shí)，也應(yīng)任意劃去一行（列），在保留的列（行）中沒被劃去的格內(nèi)標(biāo)一個(gè)0。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法33注:應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法1174.2運(yùn)輸問(wèn)題求解—表上作業(yè)法354.2運(yùn)輸問(wèn)題求解—表上作業(yè)法1184.2運(yùn)輸問(wèn)題求解—表上作業(yè)法364.2運(yùn)輸問(wèn)題求解—表上作業(yè)法119

最優(yōu)性檢驗(yàn)就是檢查所得到的方案是不是最優(yōu)方案。檢查的方法與單純形方法中的原理相同，即計(jì)算檢驗(yàn)數(shù)。由于目標(biāo)要求極小，因此，當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案；否則就不是最優(yōu)，需要進(jìn)行調(diào)整。下面介紹兩種求檢驗(yàn)數(shù)的方法:閉回路法和位勢(shì)法二、基本可行解的最優(yōu)性檢驗(yàn)

4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法37最優(yōu)性檢驗(yàn)就是檢查所得到的方案是不是最優(yōu)方案。1201、閉回路法為了方便，我們以表1給出的初始基本可行解方案為例，考察初始方案的任意一個(gè)非基變量，比如x24。根據(jù)初始方案，產(chǎn)地A2的產(chǎn)品是不運(yùn)往銷地B4的。如果現(xiàn)在改變初始方案，把A2的產(chǎn)品運(yùn)送1個(gè)單位給B4

，那么為了保持產(chǎn)銷平衡，就必須使x14

或x34

減少1個(gè)單位；而如果x14

減少1個(gè)單位，第1行的運(yùn)輸量就必須增加1個(gè)單位，例如x13

增加1個(gè)單位，那么為了保持產(chǎn)銷平衡，就必須使x23

減少1個(gè)單位。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法381、閉回路法4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法121

這個(gè)過(guò)程就是尋找一個(gè)以非基變量x24為起始頂點(diǎn)的閉回路—{x24，x14，x13，x23}，這個(gè)閉回路的其他頂點(diǎn)均為基變量(對(duì)應(yīng)著填上數(shù)字的格)。容易計(jì)算出上述調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為8–10+3–2＝-1，即總的運(yùn)費(fèi)減少1個(gè)單位，這就說(shuō)明原始方案不是最優(yōu)方案，可以進(jìn)行調(diào)整以得到更好的方案。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法39這個(gè)過(guò)程就是尋找一個(gè)以非基變量x24為起始頂點(diǎn)122

可以證明，如果對(duì)閉回路的方向不加區(qū)別（即只要起點(diǎn)及其他所有頂點(diǎn)完全相同，而不區(qū)別行進(jìn)方向），那么以每一個(gè)非基量為起始頂點(diǎn)的閉回路就存在而且唯一。因此，對(duì)每一個(gè)非基變量可以找到而且只能找到唯一的一個(gè)閉回路。表4-10中用虛線畫出以非基變量x22

為起始頂點(diǎn)的閉回路。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法40可以證明，如果對(duì)閉回路的方向不加區(qū)別（即123表4-10以非基變量x22

為起始頂點(diǎn)的閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量3[]11[]341037139[]218[]47[]4610[]539銷量365620(產(chǎn)銷平衡)A1A2A341表4-10以非基變量x22為起始頂點(diǎn)的閉回路銷地B124

可以計(jì)算出以非基變量x22

為起始頂點(diǎn)的閉回路調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為

9–2+3–10+5–4＝1

即總的運(yùn)費(fèi)增加1個(gè)單位，這就說(shuō)明這個(gè)調(diào)整不能改善目標(biāo)值。從上面的討論可以看出，當(dāng)某個(gè)非基變量增加一個(gè)單位時(shí)，有若干個(gè)基變量的取值受其影響。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法42可以計(jì)算出以非基變量x22為起始頂點(diǎn)的閉125

這樣，利用單位產(chǎn)品變化（運(yùn)輸?shù)膯挝毁M(fèi)用）可計(jì)算出它們對(duì)目標(biāo)函數(shù)的綜合影響，其作用與線性規(guī)劃單純形方法中的檢驗(yàn)數(shù)完全相同。故也稱這個(gè)綜合影響為該非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)。上面計(jì)算的兩個(gè)非基變量的檢驗(yàn)數(shù)為24=-1，22=1。閉回路方法原理就是通過(guò)尋找閉回路來(lái)找到非基變量的檢驗(yàn)數(shù)。

4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法43這樣，利用單位產(chǎn)品變化（運(yùn)輸?shù)膯挝毁M(fèi)用）可計(jì)126

如果規(guī)定作為起始頂點(diǎn)的非基變量為第1個(gè)頂點(diǎn)，閉回路的其他頂點(diǎn)依次為第2個(gè)頂點(diǎn)、第3個(gè)頂點(diǎn)……那么就有

ij=(閉回路上的奇數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和)-(閉回路上的偶數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和)

其中ij為非基變量的下角指標(biāo)。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法44如果規(guī)定作為起始頂點(diǎn)的非基變量為第1個(gè)頂127

按上述作法，可計(jì)算出表1的所有非基變量的檢驗(yàn)數(shù)，把它們填入相應(yīng)位置的方括號(hào)內(nèi)，如圖4-11所示。

銷地產(chǎn)地B1B2B3B4產(chǎn)量A13[1]11[2]341037A2139[1]218[-1]4A37[10]4610[12]539銷量365620(產(chǎn)銷平衡)表4-11初始基本可行解及檢驗(yàn)數(shù)45按上述作法，可計(jì)算出表1的所有非基變量的檢驗(yàn)128

顯然，當(dāng)所有非基變量的檢驗(yàn)數(shù)均大于或等于零時(shí)，現(xiàn)行的調(diào)運(yùn)方案就是最優(yōu)方案，因?yàn)榇藭r(shí)對(duì)現(xiàn)行方案作任何調(diào)整都將導(dǎo)致總的運(yùn)輸費(fèi)用增加。閉回路法的主要缺點(diǎn)是：當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路以及計(jì)算兩方面都會(huì)產(chǎn)生困難。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法46顯然，當(dāng)所有非基變量的檢驗(yàn)數(shù)均大于或等于零時(shí)

2.位勢(shì)法

位勢(shì)：設(shè)對(duì)應(yīng)基變量xij

的m+n-1個(gè)ij

，存在ui,vj

滿足

ui+vj=cij

，i=1,2…,m;j=1,2…,n.

稱這些ui,vj

為該基本可行解對(duì)應(yīng)的位勢(shì)。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法2.位勢(shì)法4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法130由于有m+n

個(gè)變量（ui,vj

），

m+n-1個(gè)方程（基變量個(gè)數(shù)），故有一個(gè)自由變量，位勢(shì)不唯一。

利用位勢(shì)求檢驗(yàn)數(shù)：

ij=cij-ui-vj

i=1,…,m;j=1,…,n4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法48由于有m+n個(gè)變量（ui,vj），131前例，位勢(shì)法求檢驗(yàn)數(shù)：step1

從任意基變量對(duì)應(yīng)的cij

開始,任取

ui

或vj

，然后利用cij=ui+vj公式依次找出m+n

個(gè)ui

、vj,我們從c14=10開始step2

計(jì)算非基變量的檢驗(yàn)數(shù)

ij=cij-ui-vj

；填入圓圈內(nèi)4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法49前例，位勢(shì)法求檢驗(yàn)數(shù)：4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法1324.2運(yùn)輸問(wèn)題求解—表上作業(yè)法504.2運(yùn)輸問(wèn)題求解—表上作業(yè)法133

當(dāng)非基變量的檢驗(yàn)數(shù)出現(xiàn)負(fù)值時(shí)，則表明當(dāng)前的基本可行解不是最優(yōu)解。在這種情況下，應(yīng)該對(duì)基本可行解進(jìn)行調(diào)整，即找到一個(gè)新的基本可行解使目標(biāo)函數(shù)值下降，這一過(guò)程通常稱為換基(或主元變換)過(guò)程。4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法三、求新的基本可行解51當(dāng)非基變量的檢驗(yàn)數(shù)出現(xiàn)負(fù)值時(shí)，則表明當(dāng)前的基134

（1）選負(fù)檢驗(yàn)數(shù)中最小者rk，那么xrk

為主元，作為進(jìn)基變量（上頁(yè)圖中x24）;

（2）以xrk

為起點(diǎn)找一條閉回路，除xrk

外其余頂點(diǎn)必須為基變量格（上頁(yè)圖中的回路）;4.2運(yùn)輸問(wèn)題求解—表上作業(yè)法

在運(yùn)輸問(wèn)題的表上作業(yè)法中，換基的過(guò)程是如下進(jìn)行：52（1）選負(fù)檢驗(yàn)數(shù)中最小者rk，那么xrk135（3）為閉回路的每一個(gè)頂點(diǎn)標(biāo)號(hào)，xrk

為1