運(yùn)籌學(xué)(第三章)

第三章運(yùn)輸問題.主要內(nèi)容：第一節(jié)運(yùn)輸問題及數(shù)學(xué)模型第二節(jié)用表上作業(yè)法求解運(yùn)輸問題第三節(jié)運(yùn)輸問題的進(jìn)一步討論第四節(jié)運(yùn)輸問題的應(yīng)用舉例.第一節(jié)運(yùn)輸問題及其數(shù)學(xué)模型.一、運(yùn)輸問題的一般提法

運(yùn)輸問題是一種應(yīng)用廣泛的網(wǎng)絡(luò)最優(yōu)化模型，其主要目的是為物資調(diào)

運(yùn)、車輛調(diào)度選擇最經(jīng)濟(jì)的運(yùn)輸路線。有些問題，比如有m臺(tái)機(jī)床加工n種零件的問題，工廠的合理布局問題等,雖要求與提法不同,當(dāng)變化也可以使用本模型求得最優(yōu)解。

運(yùn)輸問題的一般提法是：

某種物資有m個(gè)產(chǎn)地iA，產(chǎn)量分別為),...,2,1(miai=，有n個(gè)銷

地jB，銷量（需求最）分別為),...,2,1(njbj=,已知iA到j(luò)B價(jià)為),...,2,1;,...,2,1(nnmicij==，又假設(shè)產(chǎn)銷是平衡的，即：

??===njjmiiba11，問應(yīng)如何安排運(yùn)輸可使總運(yùn)費(fèi)最??？

但經(jīng)過適的單位運(yùn).二、運(yùn)輸問題的數(shù)學(xué)模型假定ijx表示由iA到j(luò)B的運(yùn)輸量，則平衡條件下的運(yùn)輸問題可寫出如下的線性規(guī)劃模型：

ijminjijxcz??===11Mins.t),...,2,1(1miaxinjij==?=),...,2,1(1njbxjmiij==?=03ijx.約束方程即為：.三、運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)1.平衡條件下的運(yùn)輸問題一定有最優(yōu)解。2.運(yùn)輸問題的系數(shù)矩陣.系數(shù)矩陣的特點(diǎn)：（1）約束條件系數(shù)矩陣的元素為0或1；（2）約束條件系數(shù)矩陣的每一列有兩個(gè)1元素，對(duì)于變量xij在第i個(gè)約束方程中出現(xiàn)一次，在第m+j個(gè)方程中出現(xiàn)第二次；（3）系數(shù)矩陣的秩為m+n-1。.第二節(jié)用表上作業(yè)法求解運(yùn)輸問題.基本思路：（1）找出基本可行解；（2）檢驗(yàn)是否為最優(yōu)解。是，則停止，否，轉(zhuǎn)入（3）；（3）解的調(diào)整。得到一個(gè)新的基本可行解，重新回到步驟二。所有步驟都在表上進(jìn)行操作.運(yùn)輸表.例子：

某部門有3個(gè)生產(chǎn)同類產(chǎn)品的工廠，生產(chǎn)的產(chǎn)品由4個(gè)銷售點(diǎn)出售，各工廠的生產(chǎn)量、各銷售點(diǎn)的銷售量（假定單位均為噸）以及各工廠到各銷售點(diǎn)的單位運(yùn)價(jià)（元/噸）如下表，要求研究產(chǎn)品如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最小。.一、找出初始基可行解1.西北角法2.最小元素法3.沃格爾法（差值法）較差較好更好.8①8②6③4④8⑤14⑥⑥8×4+8×12+6×10+4×3+8×11+14×6=372（元）西北角法——每次找最左上角對(duì)應(yīng)的元素.①⑥④②③14⑤⑥8210868×2+14×5+10×4+2×3+6×11+8×6=246（元）最小元素法——每次找最小元素.14821288×2+14×5+12×4+4×11+2×9+8×6=244（元）行罰數(shù)列罰數(shù)25130110122212764沃格爾法——每次找行罰數(shù)和列罰數(shù)中最大值所對(duì)應(yīng)的行或列中最小的元素.二、解的最優(yōu)性檢驗(yàn)1.閉回路法2.對(duì)偶變量法（位勢(shì)法）.（14）（8）（2）（10）（8）（6）閉回路法：.（14）（8）（2）（10）（8）（6）11-121012存在小于0的檢驗(yàn)數(shù)，故此基可行解不是最優(yōu)解。.在運(yùn)輸問題中通常目標(biāo)函數(shù)是求最小值，所以當(dāng)所有的檢驗(yàn)數(shù)為正值時(shí)，得到最優(yōu)解。注意：對(duì)于每一個(gè)非基變量，在運(yùn)輸表中唯一對(duì)應(yīng)一條這樣的閉回路。.對(duì)偶變量法（位勢(shì)法）：ijminjijxcz??===11Min.基變量的檢驗(yàn)數(shù)為0，得到m+n-1個(gè)方程，這些方程中共包含m+n個(gè)對(duì)偶變量，因此解的個(gè)數(shù)不唯一。把用這m+n-1個(gè)方程求得的對(duì)偶變量的解帶入到其它m*n-(m+n-1)個(gè)式子中，求出非基變量的檢驗(yàn)數(shù)。當(dāng)所有的檢驗(yàn)數(shù)都≥0時(shí)，得到最優(yōu)解。.（14）（8）（2）（10）（8）（6）11-121012uivju1v4v3v2v1u2u3(4)(11)(0)(-5)(-1)(3)(10)……存在小于0的檢驗(yàn)數(shù)，故此基可行解不是最優(yōu)解。.三、解的改進(jìn)閉回路法（14）（8）（2）（10）（8）（6）+2+2-2-2.（14）（8）（12）（8）（4）（2）.四、重新進(jìn)行最優(yōu)性檢驗(yàn)（14）（8）（12）（8）（4）02（2）29121不存在小于0的檢驗(yàn)數(shù)，故此基可行解是最優(yōu)解，得到最優(yōu)運(yùn)輸方案。(存在無窮多最優(yōu)調(diào)運(yùn)方案).第三節(jié)運(yùn)輸問題的進(jìn)一步討論.一、產(chǎn)銷不平衡的運(yùn)輸問題表上作業(yè)法是以產(chǎn)銷平衡為前提的。當(dāng)實(shí)際問題是產(chǎn)銷不平衡的問題時(shí)，需要轉(zhuǎn)化為產(chǎn)銷平衡的運(yùn)輸問題。.ijminjijxcz??===11Mins.t),...,2,1(1miaxinjij=≤?=),...,2,1(1njbxjmiij==?=03ijx1、產(chǎn)大于銷，即.

此時(shí)增加一個(gè)假想的銷地n+1，該銷地的銷量為，而各產(chǎn)地到假想銷地的單位運(yùn)價(jià)定為0，就轉(zhuǎn)化成產(chǎn)銷平衡的運(yùn)輸問題。.2、銷大于產(chǎn)，即ijminjijxcz??===11Mins.t),...,2,1(1miaxinjij==?=),...,2,1(1njbxjmiij=≤?=03ijx.此時(shí)增加一個(gè)假想的產(chǎn)地m+1，該產(chǎn)地的產(chǎn)量為，而假想產(chǎn)地到各銷地的單位運(yùn)價(jià)定為0，就轉(zhuǎn)化成產(chǎn)銷平衡的運(yùn)輸問題。.例1：

某市有三個(gè)造紙廠A1,A2和A3，其紙的產(chǎn)量分別為8，5和9個(gè)單位。由各造紙廠到各用戶的單位運(yùn)價(jià)如表所示，請(qǐng)確定總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。....例2：有三個(gè)產(chǎn)地A1,A2,A3，生產(chǎn)同一種物品，使用者分別為B1,B2,B3，各產(chǎn)地到各使用者的單位運(yùn)價(jià)示與下表。這三個(gè)使用者的需求量分別為10、4和6個(gè)單位。由于銷售需要和客觀條件的限制，產(chǎn)地A1至少要發(fā)出6個(gè)單位的產(chǎn)品，但它最多只能生產(chǎn)11個(gè)單位的產(chǎn)品；A2必須發(fā)出7個(gè)單位的產(chǎn)品；A3至少要發(fā)出4個(gè)單位的產(chǎn)品。試根據(jù)以上條件用表上作業(yè)法求解該運(yùn)輸問題的最優(yōu)運(yùn)輸方案。.A3最多可能送出的產(chǎn)品數(shù)量：(10+4+6)-(6+7)=7...在以上討論中，假定物品由產(chǎn)地直接運(yùn)送到銷售目的地，不經(jīng)中間轉(zhuǎn)運(yùn)。但是，常常會(huì)遇到這種情形：需先將物品由產(chǎn)地運(yùn)列某個(gè)中間轉(zhuǎn)運(yùn)站(可能是另外的產(chǎn)地、銷地或中間轉(zhuǎn)運(yùn)倉庫)，然后再轉(zhuǎn)運(yùn)到銷售目的地。有時(shí)，經(jīng)轉(zhuǎn)運(yùn)比直接運(yùn)到目的地更為經(jīng)濟(jì)(如下頁圖)。因此，在決定運(yùn)輸方案時(shí)有必要把轉(zhuǎn)運(yùn)也考慮進(jìn)去。二、有轉(zhuǎn)運(yùn)的運(yùn)輸問題.ABC301010201042211.建立一般意義上的數(shù)學(xué)模型，設(shè)：ai：第i個(gè)產(chǎn)地的產(chǎn)量(凈供應(yīng)量)；bj：第j個(gè)銷地的銷量(凈需要量)；xij：由第i個(gè)發(fā)送地運(yùn)到第j個(gè)接收地的物品數(shù)量；cij：由第i個(gè)發(fā)送地到第j個(gè)接收地的單位運(yùn)價(jià)，ti：第i個(gè)地點(diǎn)轉(zhuǎn)運(yùn)物品的數(shù)量；ci：第i個(gè)地點(diǎn)轉(zhuǎn)運(yùn)單位物品的費(fèi)用。將產(chǎn)地和銷地統(tǒng)一編號(hào)，并把產(chǎn)地排在前面。銷地排在后面，則有：.令：建立數(shù)學(xué)模型：.注：所有i=j，cij=-ci..例：如圖所示是一個(gè)運(yùn)輸系統(tǒng)，它包括二個(gè)產(chǎn)地（1和2）、二個(gè)銷地(4和5)及一個(gè)中間轉(zhuǎn)運(yùn)站(3)，各產(chǎn)地的產(chǎn)量和各銷地的銷量用相應(yīng)節(jié)點(diǎn)處箭線旁的數(shù)字表示，節(jié)點(diǎn)聯(lián)線上的數(shù)字表示其間的運(yùn)輸單價(jià)，節(jié)點(diǎn)旁的數(shù)字為該地的轉(zhuǎn)運(yùn)單價(jià)，試確定最優(yōu)運(yùn)輸方案。.該運(yùn)輸問題的運(yùn)輸表.該運(yùn)輸問題的最優(yōu)調(diào)運(yùn)方案總運(yùn)費(fèi)：10*2+20*2+20*4+20*5+（50-30）*3=300.第四節(jié)運(yùn)輸問題的應(yīng)用舉例.

例1：某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供15、20、25、20臺(tái)同一規(guī)格的設(shè)備。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)設(shè)備的成本如下表。又知如果生產(chǎn)出來的設(shè)備當(dāng)季度不交貨，每臺(tái)每季度的存儲(chǔ)維護(hù)費(fèi)為0.1萬元。試安排全年生產(chǎn)計(jì)劃，使總費(fèi)用最低。.

解：設(shè)xij（n=1,2,…,4

；n=1,2,…,4）表示第i季生產(chǎn)第j季銷售的設(shè)備數(shù)量，xi5表示第i季度實(shí)際生產(chǎn)數(shù)量與該季度生產(chǎn)能力之間的差值。列出如下產(chǎn)銷平衡運(yùn)輸表。.季度

季度

1

2

3

4

5

(虛銷地)

產(chǎn)量

12.0

12.1

12.2

12.3

0

1

0

20

25

M

11.0

11.1

11.2

0

2

0

20

10

35

M

M

11.5

11.6

0

3

15

20

30

M

M

M

12.5

0

4

15

20

銷量

15

20

25

20

30

110

所有檢驗(yàn)數(shù)都大于等于0，因此該解為最優(yōu)解。求初始生產(chǎn)計(jì)劃方案并進(jìn)行檢驗(yàn)：10uivj12.012.10-1.1012.2-0.712.3（0）（0）（M-10.9）（0）（1.1）（0.7）（0.2）（注：其余空格檢驗(yàn)數(shù)顯然大于0，省略未寫）.

例2:某航運(yùn)公司承擔(dān)六個(gè)港口城市A,B,C,D,E,F間四條航線的貨物運(yùn)輸任務(wù)。已知（1）各航線的起點(diǎn)、終點(diǎn)、日航班數(shù)（下表左）；（2）各城市間的航行時(shí)間（下表右）；（3）所有航線都使用同一種船只，每次裝船和卸船時(shí)間均為1天。問該公司至少應(yīng)配備多少條船才能滿足所有航線運(yùn)輸?shù)男枰?解：所需船只分成兩部分(1)載貨航行需要的船只數(shù)：3*19+2*5+9+15=91條.

(2)各港口間調(diào)度需要的船只數(shù).

各港口每天船只的余缺數(shù)為:.調(diào)度需要船只：2+13+5+17+3=40至

從

A

B

E

產(chǎn)量

2

3

5

C

1

1

0

2

14

13

17

D

（-2）

2

2

7

8

3

F

1

1

銷量

1

1

3

（0）（7）（7）（2）（0）（7）（9）.(1)運(yùn)輸問題是一種特殊的線性規(guī)劃模型，因而求解結(jié)果也可能出現(xiàn)下列四種情況之一：有唯一最優(yōu)解，有無窮多最優(yōu)解，無界解，無可行解。(2)在運(yùn)輸問題中，只要任意給出一組含（m+n-1）個(gè)非零的｛xij｝，且滿足，就可