運(yùn)籌學(xué)課件-運(yùn)輸問題

1第三章運(yùn)輸問題

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

問題的提出一般的運(yù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)用最小的方案。31.運(yù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)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？4

解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量設(shè)

xij

為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：

1.運(yùn)輸問題模型及有關(guān)概念5

MinZ

=6x11+4x12+6x13+6x21+5x22+5x23

s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1,2；j=1,2,3）1.運(yùn)輸問題模型及有關(guān)概念6

111000

000111100100

010010

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

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

1.共有m+n行，分別表示各產(chǎn)地和銷地；m

n列，分別表示各決策變量；

2.每列只有兩個(gè)1，其余為0，分別表示只有一個(gè)產(chǎn)地和一個(gè)銷地被使用。1.運(yùn)輸問題模型及有關(guān)概念8

一般運(yùn)輸問題的線性規(guī)劃模型及求解思路一般運(yùn)輸問題的提法：假設(shè)A1,A2,…,Am

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

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

的產(chǎn)量；bj

表示銷地Bj

的銷量；cij

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

運(yùn)往銷地Bj

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

a1+a2+…+am

=b1+b2+…+bn則稱該運(yùn)輸問題為產(chǎn)銷平衡問題；否則，稱產(chǎn)銷不平衡。首先討論產(chǎn)銷平衡問題。1.運(yùn)輸問題模型及有關(guān)概念9表4-3運(yùn)輸問題數(shù)據(jù)表1.運(yùn)輸問題模型及有關(guān)概念

銷地產(chǎn)地B1B2

…

Bn產(chǎn)量A1A2┇

Amc11c12

…c1nc21c22

…c2n┇┇┇┇cm1cm2

…

cmna1a2┇

am銷量b1b2

…

bn

設(shè)xij

為從產(chǎn)地Ai

運(yùn)往銷地Bj

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

銷地產(chǎn)地B1B2

…

Bn產(chǎn)量A1A2

┇Amx11x12

…x1nx21x22

…x2n┇┇┇┇xm1xm2

…

xmna1a2

┇am銷量b1b2

…

bn

11

m

nMinZ=

cijxij

（4-1）

i=1j=1

n

s.t.

xij

ai

i=1,2,…,m

（4-2）

j=1

m

xij

(=,

)bj

j=1,2,…,n

（4-3）

i=1

xij

0(i=1,2,…,m;j=1,2,…,n)（4-4）1.運(yùn)輸問題模型及有關(guān)概念

于是得到下列一般運(yùn)輸問題的模型：

在模型（4-1）—（4-4）中，式（4-2）為m個(gè)產(chǎn)地的產(chǎn)量約束；式（4-3）為n

個(gè)銷地的銷量約束。

12

mn

MinZ=

cijxij

i=1j=1

n

s.t.

xij=ai

i=1,2,…,m

(4-5)

j=1

m

xij

=bj

j=1,2,…,n(4-6)

i=1

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

對于產(chǎn)銷平衡問題，可得到下列運(yùn)輸問題的模型：13

在產(chǎn)銷平衡問題中，仔細(xì)觀察式（4-2）、

（4-3）分別變?yōu)椋?-5）、（4-6），約束條件成為等式。在實(shí)際問題建模時(shí)，還會出現(xiàn)如下一些變化：（1）有時(shí)目標(biāo)函數(shù)求最大，如求利潤最大或營業(yè)額最大等；（2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，模型中可直接加入（等式或不等式）約束；1.運(yùn)輸問題模型及有關(guān)概念14

(3)產(chǎn)銷不平衡的情況。當(dāng)銷量大于產(chǎn)量時(shí)可加入一個(gè)虛設(shè)的產(chǎn)地去生產(chǎn)不足的物資，這相當(dāng)于在式（4-2）每一式中加上1個(gè)松弛變量，共m

個(gè)；當(dāng)產(chǎn)量大于銷量時(shí)可加入一個(gè)虛設(shè)的銷地去消化多余的物資，這相當(dāng)于在式（4-3）每一式中加上1個(gè)松弛變量，共n個(gè)。1.運(yùn)輸問題模型及有關(guān)概念15

運(yùn)輸問題是一種特殊的線性規(guī)劃問題，在求解時(shí)依然可以采用單純形法的思路，如圖4-1所示。由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計(jì)算，則無法利用這些有利條件。人們在分析運(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對運(yùn)輸問題的表上作業(yè)法。在這里需要討論基本可行解、檢驗(yàn)數(shù)以及基的轉(zhuǎn)換等問題。1.運(yùn)輸問題模型及有關(guān)概念161.運(yùn)輸問題模型及有關(guān)概念基本可行解是否最優(yōu)解結(jié)束換基是否圖4-1運(yùn)輸問題的求解思路17

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

表4-5運(yùn)輸問題求解作業(yè)數(shù)據(jù)表(下頁）1.運(yùn)輸問題模型及有關(guān)概念181.運(yùn)輸問題模型及有關(guān)概念

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

x11c12

x12…c1n

x1na1A2c21

x21c22

x22…c2n

x2na2┇┇┇┇┇┇Amcm1

xm1cm2

xm2…cmn

xmnam銷量b1b2…bn

19中任意m+n階子式等于零，取第一行到m+n－1行與對應(yīng)的列（共m+n-1列）組成的m+n－1階子式20故r(A)=m+n－1所以運(yùn)輸問題有m+n－1個(gè)基變量。21

運(yùn)輸問題的基變量共有m+n-1個(gè)，A的秩為m+n-1。運(yùn)輸問題的m+n-1個(gè)變量構(gòu)成基變量的充分必要條件是不含閉回路。重要概念:

閉回路、閉回路的頂點(diǎn)特點(diǎn)

運(yùn)輸問題基變量的1.運(yùn)輸問題模型及有關(guān)概念22

定義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)。

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

；

x23,x53,x55,x45,x41,x21

；

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

閉回路示意圖24

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

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

(2)閉回路的每一條邊（水平的或垂直的）均有且僅有兩個(gè)閉回路的頂點(diǎn)（變量格）。1.運(yùn)輸問題模型及有關(guān)概念25

x23

B1B2B3B4B5A1

A2

A3

x35A4

x43

x11x12

x25x31

x42表3－3表3－3中閉回路的變量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8個(gè)頂點(diǎn)，這8個(gè)頂點(diǎn)間用水平或垂直線段連接起來，組成一條封閉的回路。

26x11x12x32x33x41

B1B2B3A1

A2

A3

A4

x43表3－4

一條回路中的頂點(diǎn)數(shù)一定是偶數(shù)，回路遇到頂點(diǎn)必須轉(zhuǎn)90度與另一頂點(diǎn)連接，表3－3中的變量x32及x33不是回閉路的頂點(diǎn)，只是連線的交點(diǎn)。表3－4中閉回路是例如變量組A不能組成一條閉回路，但A中包含有閉回路B的變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路；27C是一條閉回路，若把C重新寫成就不難看出C仍是一條閉回路?！径ɡ?】

若變量組B

包含有閉回路，則B中的變量對應(yīng)的例向量線性相關(guān)。【證】由線性代數(shù)知，向量組中部分向量組線性相關(guān)則該向量組線性相關(guān)，顯然，將C中列向量分別乘以正負(fù)號線性組合后等于零，即因而C中的列向量線性相關(guān)，所以B中列向量線性相關(guān)?！径ɡ?】若變量組中包含一個(gè)部分組構(gòu)成閉回路，那么該變量組所對應(yīng)的系數(shù)列向量線性相關(guān)。28

定理3變量組xab

,xcd

,xef

,…,xst

所對應(yīng)的系數(shù)列向量pab

,pcd

,pef

,…,pst

線性無關(guān)的充分必要條件是這個(gè)變量組中不包含閉回路。

推論產(chǎn)銷平衡運(yùn)輸問題的m+n-1個(gè)變量構(gòu)成基變量的充分必要條件是它不含閉回路。這個(gè)推論給出了運(yùn)輸問題基本解的重要性質(zhì)，也為尋求基本可行解提供了依據(jù)。這個(gè)推論告訴了一個(gè)求基變量的簡單方法，同時(shí)也可以判斷一組變量是否可以作為某個(gè)運(yùn)輸問題的基變量。這種方法是直接在運(yùn)價(jià)表中進(jìn)行的，不需要在系數(shù)矩陣A中去尋找，從而給運(yùn)輸問題求初始基可行解帶來極大的方便。29例如，m=3,n=4，在運(yùn)價(jià)表Cij的格子的右上方填上相應(yīng)的xij，如表3-5所示。表3－5

BjAiB1B2B3B4aiA1

x11

x12

x13

x14

a1C11C12C13C14A2

x21

x22

x23

x24a2C21C22C23C24A3

x31

x32

x2

x34a3C31C32C33C34bjb1b2b3b4

30這個(gè)運(yùn)輸問題的基變量數(shù)目是3+4－1=6。變量組中有7個(gè)變量，顯然不能構(gòu)成一組基變量，又如中有6個(gè)變量，但包含有一條閉回路故不能構(gòu)成一組基變量。變量組有6個(gè)變量且不含有任何閉回路，故可以構(gòu)成此問題的一組基變量。312.運(yùn)輸問題求解

—表上作業(yè)法

上一節(jié)已經(jīng)分析了，對于產(chǎn)銷平衡問題，我們關(guān)心的量均可以表示在表4-5中。因此可以建立基于表4-5的求解運(yùn)輸問題的方法——表上作業(yè)法。這里求解運(yùn)輸問題的思想和單純形法完全類似，即首先確定一個(gè)初始基本可行解，然后根據(jù)最優(yōu)性判別準(zhǔn)則來檢查這個(gè)基本可行解是不是最優(yōu)的。如果是則計(jì)算結(jié)束；如果不是，則進(jìn)行換基，直至求出最優(yōu)解為止。322.運(yùn)輸問題求解

—表上作業(yè)法

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

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

行Bj

列交叉位置上的格),令

xij

=min{ai,bj

}即從Ai

向Bj

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

的相應(yīng)位

置；332.運(yùn)輸問題求解

—表上作業(yè)法

(2)從ai

或bj

中分別減去

xij

的值，即調(diào)整Ai

的擁有量及Bj

的需求量；

(3)若ai=0，則劃去對應(yīng)的行（把擁有的量全部運(yùn)走），若bj=0則劃去對應(yīng)的列（把需要的量全部運(yùn)來），且每次只劃去一行或一列（即每次要去掉且只去掉一個(gè)約束）；

(4)若運(yùn)輸平衡表中所有的行與列均被劃去，則得到了一個(gè)初始基本可行解。否則在剩下的運(yùn)輸平衡表中選下一個(gè)變量，轉(zhuǎn)(4)。34上述計(jì)算過程可用流程圖描述如下（圖4-2）取未劃去的單元格xij

,令xij

=min{ai,bj

}ai’=ai-xijbj’=bj-xijai’=0?劃去第i行劃去第j列是否

bj’=0否所有行列是否均被劃去是找到初始基本可行解圖4-2求運(yùn)輸問題的初始基本可行解過程352.運(yùn)輸問題求解

—表上作業(yè)法

按照上述方法所產(chǎn)生的一組變量的取值將滿足下面條件：(1)所得的變量均為非負(fù)，且變量總數(shù)恰好為m+n–1個(gè)；(2)所有的約束條件均得到滿足；(3)所得的變量不構(gòu)成閉回路。因此，根據(jù)定理4.1及其推論，所得的解一定是運(yùn)輸問題的基本可行解。

在上面的方法中，xij

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

，則得到不同的方法，較常用的方法有西北角法和最小元素法。下面分別舉例予以說明。362.運(yùn)輸問題求解

—表上作業(yè)法

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

銷地

產(chǎn)地可供量(t)907095200806575230需求量(t)10015018038

銷地

產(chǎn)地可供量(t)90（100）70（100）95200（100）8065（50）75（180）230（180）需求量(t)100（0）150（50）180（0）第一次第二次第三次第四次392.運(yùn)輸問題求解

—表上作業(yè)法

（2）最小元素法：從運(yùn)價(jià)最小的格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按運(yùn)價(jià)從小到大順序填數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。最小元素法的思想是就近優(yōu)先運(yùn)送，即最小運(yùn)價(jià)Cij對應(yīng)的變量xij優(yōu)先賦值然后再在剩下的運(yùn)價(jià)中取最小運(yùn)價(jià)對應(yīng)的變量賦值并滿足約束，依次下去，直到最后一個(gè)初始基可行解。40【例2】求表3－6所示的運(yùn)輸問題的初始基可行解。表3－6

銷地產(chǎn)地B1B2B3產(chǎn)量A186730A243545A374825銷量60301010041B1B2B3可發(fā)量A186730A243545A374825未滿足量6030101000

00【解】301510252015452020000產(chǎn)地銷地42

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

—表上作業(yè)法

432.運(yùn)輸問題求解

—表上作業(yè)法

表1442.運(yùn)輸問題求解

—表上作業(yè)法

452.運(yùn)輸問題求解

—表上作業(yè)法

46

最優(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ù)的方法。

二、基本可行解的最優(yōu)性檢驗(yàn)2.運(yùn)輸問題求解

—表上作業(yè)法

47

1、閉回路法為了方便，我們以表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è)單位。2.運(yùn)輸問題求解

—表上作業(yè)法

48

這個(gè)過程就是尋找一個(gè)以非基變量x24

為起始頂點(diǎn)的閉回路——{x24

，x14

，x13

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

—表上作業(yè)法

49

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

為起始頂點(diǎn)的閉回路。2.運(yùn)輸問題求解

—表上作業(yè)法

50表4-10以非基變量x22

為起始頂點(diǎn)的閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量3[]11[]341037139[]218[]47[]4610[]539銷量365620(產(chǎn)銷平衡)A1A2A351

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

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

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

即總的運(yùn)費(fèi)增加1個(gè)單位，這就說明這個(gè)調(diào)整不能改善目標(biāo)值。從上面的討論可以看出，當(dāng)某個(gè)非基變量增加一個(gè)單位時(shí)，有若干個(gè)基變量的取值受其影響。2.運(yùn)輸問題求解

—表上作業(yè)法

52

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

24=-1，

22=1。閉回路方法原理就是通過尋找閉回路來找到非基變量的檢驗(yàn)數(shù)。2.運(yùn)輸問題求解

—表上作業(yè)法

53

如果規(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)。2.運(yùn)輸問題求解

—表上作業(yè)法

54

按上述作法，可計(jì)算出表1的所有非基變量的檢驗(yàn)數(shù)，把它們填入相應(yīng)位置的方括號內(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ù)55

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

—表上作業(yè)法

56【解】用最小元素法得到下列一組基本可行解【例4】求下列運(yùn)輸問題的一個(gè)初始基本可行解及其檢驗(yàn)數(shù)。矩陣中的元素為運(yùn)價(jià)Cij

，矩陣右邊的元素為產(chǎn)量ai

，下方的元素為銷量bj

。1060403057矩陣中打“×”的位置是非基變量，其余是基變量，這里只求非基變量的檢驗(yàn)數(shù)。求λ11，先找出x11的閉回路，對應(yīng)的運(yùn)價(jià)為再用正負(fù)號分別交替乘以運(yùn)價(jià)有直接求代數(shù)和得58同理可求出其它非基變量的檢驗(yàn)數(shù)：這里λ34<0，說明這組基本可行解不是最優(yōu)解。只要求得的基變量是正確的且數(shù)目為m+n－1，則某個(gè)非基變量的閉回路存在且唯一，因而檢驗(yàn)數(shù)唯一。59

2.位勢法根據(jù)單純形法中檢驗(yàn)數(shù)的定義，可以從約束條件中解出基變量（用非基變量表示基變量），然后代入目標(biāo)函數(shù)消去目標(biāo)中的基變量，得到的非基變量系數(shù)就是檢驗(yàn)數(shù)。這一過程可以用下列位勢法等價(jià)地加以實(shí)現(xiàn)。位勢：設(shè)對應(yīng)基變量xij

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

，存在ui,vj

滿足

ui+vj=cij

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

稱這些ui,vj

為該基本可行解對應(yīng)的位勢。

2.運(yùn)輸問題求解

—表上作業(yè)法

60位勢法求檢驗(yàn)數(shù)是根據(jù)對偶理論推導(dǎo)出來的一種方法。設(shè)平衡運(yùn)輸問題為設(shè)前m個(gè)約束對應(yīng)的對偶變量為ui,i=1,2,…,m，后n個(gè)約束對應(yīng)的對偶變量為vj,j=1,2,…,n則運(yùn)輸問題的對偶問題是61加入松馳變量λij將約束化為等式ui+vj+λij=cij記原問題基變量XB的下標(biāo)集合為I，由第二章對偶性質(zhì)知，原問題xij的檢驗(yàn)數(shù)是對偶問題的松弛變量λij當(dāng)（i，j）

時(shí)λij=0，因而有解上面第一個(gè)方程，將ui、vj代入第二個(gè)方程求出λij。62【例5】用位勢法求例4給出的初始基本可行解的檢驗(yàn)數(shù)。【解】第一步求位勢u1、u2、u3及v1、v2、v3、v4。10604030令u1=0得到位勢的解為63再由公式求出檢驗(yàn)數(shù)，其中Cij是非基變量對應(yīng)的運(yùn)價(jià)。計(jì)算結(jié)果與例4結(jié)果相同。642.運(yùn)輸問題求解

—表上作業(yè)法

前例3用位勢法求檢驗(yàn)數(shù)：65

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

—表上作業(yè)法

三、求新的基本可行解66

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

rk，那么xrk

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

（2）以xrk

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

外其余頂點(diǎn)必須為基變量格（上頁圖中的回路）;2.運(yùn)輸問題求解

—表上作業(yè)法

在運(yùn)輸問題的表上作業(yè)法中，換基的過程是如下進(jìn)行：

（3）為閉回路的每一個(gè)頂點(diǎn)標(biāo)號，為1，沿一個(gè)方向（順時(shí)針或逆時(shí)針）依次給各頂點(diǎn)標(biāo)號；67

（4）求

=Min{xij

xij對應(yīng)閉回路上的偶數(shù)標(biāo)號格}=xpq那么確定xpq為出基變量，

為調(diào)整量；2.運(yùn)輸問題求解

—表上作業(yè)法

（5）對閉回路的各奇標(biāo)號頂點(diǎn)調(diào)整為：xij+

，對各偶標(biāo)號頂點(diǎn)調(diào)整為：xij-

，特別

xpq-

=0，

xpq變?yōu)榉腔兞?。重?fù)(2)、(3)步，直到所有檢驗(yàn)數(shù)均非負(fù)，得到最優(yōu)解。68【例9】求下表所示的運(yùn)輸問題的最優(yōu)解。表3－6

B1B2B3產(chǎn)量A186730A243545A374825銷量603010100產(chǎn)地銷地69B1B2B3產(chǎn)量A186730A243545A374825銷量603010100【解】3015102520＋－＋－[-1]前面已得到此題的初始可行解，現(xiàn)在接著做下去。用閉回路法求檢驗(yàn)數(shù)如下：產(chǎn)地銷地70

B1B2B3產(chǎn)量A186730A243545A374825銷量60301010030151020[-1]＋－＋－[2]25產(chǎn)地銷地【解】前面已得到此題的初始可行解，現(xiàn)在接著做下去。用閉回路法求檢驗(yàn)數(shù)如下：71B1B2B3產(chǎn)量A186730A243545A374825銷量60301010030151020[-1][2]25＋－＋－[-2]產(chǎn)地銷地【解】前面已得到此題的初始可行解，現(xiàn)在接著做下去。用閉回路法求檢驗(yàn)數(shù)如下：72B1B2B3產(chǎn)量A186730A243545A374825銷量60301010030151020[-1][2]25＋－＋－[-2]產(chǎn)地銷地[2]【解】前面已得到此題的初始可行解，現(xiàn)在接著做下去。用閉回路法求檢驗(yàn)數(shù)如下：73B1B2B3A1867A2435A374830151020[-1][2]25[-2]產(chǎn)地銷地[０]

因?yàn)橛校矀€(gè)負(fù)檢驗(yàn)數(shù)，所以這組基本可行解不是最優(yōu)解。取非基變量x32進(jìn)基,用閉回路法調(diào)整如下閉回路如上圖，標(biāo)負(fù)號的運(yùn)量是：x31=25、x22=30，取其最小值25作為調(diào)整量，在閉回路上x21、x32分別加上25，x31、x22分別減去25，調(diào)整后得到一組新的基可行解。＋－＋25－

40

5

74B1B2B3產(chǎn)量A186730A243545A374825銷量603010100540102520[-1]

[2]＋－＋－

[2]再檢驗(yàn)（表中括號中的數(shù)字為檢驗(yàn)數(shù)）75B1B2B3產(chǎn)量A186730A243545A374825銷量603010100540102520[-1]

[2][4]＋－＋－

[2]＋－再檢驗(yàn)（表中括號中的數(shù)字為檢驗(yàn)數(shù)）76B1B2B3產(chǎn)量A186730A243545A374825銷量603010100540102520[-1]

[2][4]＋－

[2]＋－5

45

15檢驗(yàn)數(shù)l12=-1,方案需調(diào)整，下面用閉回路法調(diào)整77B1B2B3產(chǎn)量A186730A243545A374825銷量60301010025451015再計(jì)算一次檢驗(yàn)數(shù)（表中括號中的數(shù)字）產(chǎn)地銷地5

[2]

[1]

[1]

[3]檢驗(yàn)數(shù)已全非負(fù)，故表中的解已為最優(yōu)解，最小運(yùn)費(fèi)為500元。782.表上作業(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=8579

四、產(chǎn)銷不平衡問題的處理在實(shí)際中遇到的運(yùn)輸問題常常不是產(chǎn)銷平衡的，而是下列的一般運(yùn)輸問題模型

m

nMinf=

cij

xij

（4-1）

i=1j=1

n

s.t.

xij

si

i=1,2,…,m

（4-2）

j=1

m

xij

(=,

)dj

j=1,2,…,n(4-3）

i=1

xij

0(i=1,2,…,m;j=1,2,…,n)（4-4）2.運(yùn)輸問題求解

—表上作業(yè)法

80

我們已經(jīng)介紹過，可以通過增加虛設(shè)產(chǎn)地或銷地（加、減松弛變量）把問題轉(zhuǎn)換成產(chǎn)銷平衡問題，下面分別來討論。

1.產(chǎn)量大于銷量的情況

m

n

考慮

si

>dj

的運(yùn)輸問題，得到的數(shù)學(xué)模

i=1

j=1型為2.運(yùn)輸問題求解

—表上作業(yè)法812.運(yùn)輸問題求解

—表上作業(yè)法

mn

Minf=

cijxij

i=1j=1

n

s.t.

xij

si

i=1,2,…,m

j=1

m

xij

=dj

j=1,2,…,n

i=1

xij≥0(i=1,2,…,m;j=1,2,…,n)82

只要在模型中的產(chǎn)量限制約束（前m個(gè)不等式約束）中引入m個(gè)松弛變量xin+1i=1,2,…,m即可，變?yōu)椋?/p>

n

xij+xin+1=si

i=1,2,…mj=1然后，需設(shè)一個(gè)銷地Bn+1,它的銷量為：

mn

bn+1=si-dj

i=1j=1

2.運(yùn)輸問題求解

—表上作業(yè)法

83

這里，松弛變量xin+1

可以視為從產(chǎn)地Ai

運(yùn)往銷地B

n+1

的運(yùn)輸量，由于實(shí)際并不運(yùn)送，它們的運(yùn)費(fèi)為cin+1=0i=1,2,…,m。于是，這個(gè)運(yùn)輸問題就轉(zhuǎn)化成了一個(gè)產(chǎn)銷平衡的問題。2.運(yùn)輸問題求解

—表上作業(yè)法

84

例4.2:某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？2.運(yùn)輸問題求解

—表上作業(yè)法

85

解：增加一個(gè)虛設(shè)的銷地運(yùn)輸費(fèi)用為02.運(yùn)輸問題求解

—表上作業(yè)法

86

2.銷量大于產(chǎn)量的情況

mn

考慮

si<dj的運(yùn)輸問題，得到的數(shù)學(xué)模型為

i=1

j=12.運(yùn)輸問題求解

—表上作業(yè)法

mn

Minf=

cijxij

i=1j=1

n

s.t.

xij

=si

i=1,2,…,m

j=1

m

xij

dj

j=1,2,…,n

i=1

xij≥0(i=1,2,…,m;j=1,2,…,n)87

只要在模型中的產(chǎn)量限制約束（后n個(gè)不等式約束）中引入n個(gè)松弛變量xm+1j

j=1,2,…,n即可，變?yōu)椋?/p>

m

xij+xm+1j=dj

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

nmam+1=dj

-si

j=1i=1

2.運(yùn)輸問題求解

—表上作業(yè)法

88

這里，松弛變量xm+1j

可以視為從產(chǎn)地Am+1

運(yùn)往銷地Bj

的運(yùn)輸量，由于實(shí)際并不運(yùn)送，它們的運(yùn)費(fèi)為cm+1j=0j=1,2,…,n。于是，這個(gè)運(yùn)輸問題就轉(zhuǎn)化成了一個(gè)產(chǎn)銷平衡的問題。2.運(yùn)輸問題求解

—表上作業(yè)法

89

例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)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？2.運(yùn)輸問題求解

—表上作業(yè)法

90

解：增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為02.運(yùn)輸問題求解

—表上作業(yè)法

91

例4.4:石家莊北方研究院有一、二、三，三個(gè)區(qū)。每年分別需要用煤3000、1000、2000t，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價(jià)格、質(zhì)量相同。供應(yīng)能力分別為1500、4000t，運(yùn)價(jià)如下表。由于需大于供，經(jīng)院研究決定一區(qū)供應(yīng)量可減少0—300t，二區(qū)必須滿足需求量，三區(qū)供應(yīng)量不少于1700t，試求總費(fèi)用為最低的調(diào)運(yùn)方案。3.運(yùn)輸問題的應(yīng)用92

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

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

3.運(yùn)輸問題的應(yīng)用93

例4.5:設(shè)有A、B、C三個(gè)化肥廠供應(yīng)1、2、3、4四個(gè)地區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表。試求總費(fèi)用為最低的化肥調(diào)撥方案。3.運(yùn)輸問題的應(yīng)用94

解：根據(jù)題意，作出產(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。對應(yīng)4”的銷量50是考慮問題本身適當(dāng)取的數(shù)據(jù)，根據(jù)產(chǎn)銷平衡要求確定D的產(chǎn)量為50。3.運(yùn)輸問題的應(yīng)用95

生產(chǎn)與儲存問題例4.6:某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、15、25、20臺同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如右表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺每積壓一個(gè)季度需儲存、維護(hù)等費(fèi)用0.15萬元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。3.運(yùn)輸問題的應(yīng)用96

交貨：生產(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)滿足：

3.運(yùn)輸問題的應(yīng)用97把第i季度生產(chǎn)的柴油機(jī)數(shù)目看作第i

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

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

個(gè)銷售點(diǎn)的銷量；成本加儲存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)?？蓸?gòu)造下列產(chǎ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

3.運(yùn)輸問題的應(yīng)用98

生產(chǎn)與儲存問題例4.7:光明儀器廠生產(chǎn)電腦繡花機(jī)是以產(chǎn)定銷的。已知1至6月份各月的生產(chǎn)能力、合同銷量和單臺電腦繡花機(jī)平均生產(chǎn)費(fèi)用見下表：

3.運(yùn)輸問題的應(yīng)用99

已知上年末庫存103臺繡花機(jī)，如果當(dāng)月生產(chǎn)出來的機(jī)器當(dāng)月不交貨，則需要運(yùn)到分廠庫房，每臺增加運(yùn)輸成本0.1萬元,每臺機(jī)器每月的平均倉儲費(fèi)、維護(hù)費(fèi)為0.2萬元。在7--8月份銷售淡季，全廠停產(chǎn)1個(gè)月，因此在6月份完成銷售合同后還要留出庫存80臺。加班生產(chǎn)機(jī)器每臺增加成本1萬元。問應(yīng)如何安排1--6月份的生產(chǎn)，可使總的生產(chǎn)費(fèi)用（包括運(yùn)輸、倉儲、維護(hù)）最少？運(yùn)輸問題（7）§3運(yùn)輸問題的應(yīng)用100

解：這個(gè)生產(chǎn)存儲問題可化為運(yùn)輸問題來做。考慮：各月生產(chǎn)與交貨分別視為產(chǎn)地和銷地。

1）1-6月份合計(jì)生產(chǎn)能力（包括上年末