運籌學(第3章 運輸問題)

運籌學基礎及應用(OperationsResearch)主講：楊啟明運輸問題的典例和數(shù)學模型1求解方法——表上作業(yè)法2產(chǎn)銷不平衡運輸問題3第3章運輸問題3.1運輸問題的典例和數(shù)學模型例1.某食品公司經(jīng)銷的主要產(chǎn)品之一是糖果.它下面設有三個加工廠,每天的糖果產(chǎn)量分別為:A1-7t,A2-4t,A3-9t.該公司把這些糖果分別運往四個地區(qū)的門市銷售,各地區(qū)每天的銷售量分別為：B1-3t,B2-6t，B3-5t,B3-6t.已知從每個加工廠到各銷售門市部每噸的運價如表所示，問該食品公司應如何調(diào)運,在滿足各門市部銷售需要的情況下，使得總的運費支出為最少。加工廠A17T加工廠A24T加工廠A39T門市B13t門市B26t門市B35t門市B46t1113109287410153表3-1單位：元/tB1B2B3B4生產(chǎn)能力A13113107A219284A3741059需求3656食品調(diào)運問題：確定合理的調(diào)運方案，使得總運費支出最少。B1B2B3B4生產(chǎn)能力A13113107A219284A3741059需求3656運輸問題的數(shù)學模型設xij為從產(chǎn)地Ai運往銷地Bj的物資數(shù)量(i=1,…m;j=1,…n），建立規(guī)劃模型AiBj

運輸問題的一般提法

現(xiàn)有一批貨物,從m個供應地運往n個銷售地,Ai(i=1,‥‥,m)處有貨物ai噸，Bj(j=1,‥‥,n)處需貨物bj噸,已知從Ai到Bj的運價為cij

元/噸.

問如何安排，既可以滿足各銷地需要，又使總費用最??？A1A2Am︰︰B1B2Bn︰︰a1a2am︰︰b1b2bm︰︰供應量需求地供應地需求量調(diào)運量xij運輸問題的框圖表示產(chǎn)銷表運輸問題的數(shù)學模型單位運價表運輸問題的數(shù)學模型運輸表（運價，運量）作業(yè)表銷量產(chǎn)量銷地產(chǎn)地產(chǎn)銷平衡條件下設xij為從產(chǎn)地Ai運往銷地Bj的物資數(shù)量(i=1,…m;j=1,…n）從Ai運出的物資總量應等于Ai的產(chǎn)量ai，xij應滿足：

運到Bj的物資總量應該等于Bj的銷量bj，xij還應滿足：運輸問題的數(shù)學模型總運費為：運輸問題的數(shù)學模型運輸問題的數(shù)學模型在產(chǎn)銷平衡條件下，線性規(guī)劃模型可寫為：1.約束條件都是等式約束2.總產(chǎn)量＝總銷量產(chǎn)銷平衡的運輸問題的特點與性質(zhì)3.系數(shù)矩陣是一個結(jié)構(gòu)特殊的稀疏矩陣將約束方程組展開約束方程組共包含m×n個變量，(m+n)個約束條件產(chǎn)銷平衡的運輸問題的特點與性質(zhì)產(chǎn)銷平衡的運輸問題的特點與性質(zhì)系數(shù)矩陣A：m行n行

矩陣的元素均為1或0；每一列只有兩個元素為1，其余元素均為0；將矩陣分塊,特點是:前m行構(gòu)成m個m×n階矩陣,而且第k個矩陣只有第k行元素全為1,其余元素全為0（k=1,…,m）;后n行構(gòu)成m個n階單位陣。A的秩一般為m+n-1

m行n行為什么？第i行第m+j行

作業(yè)表（產(chǎn)銷平衡表）：將運輸問題的有關信息表和決策變量——調(diào)運量結(jié)合在一起構(gòu)成“作業(yè)表”（產(chǎn)銷平衡表）。表上作業(yè)法是單純形法求解運輸問題的一種簡化方法，實質(zhì)是單純形法。但是具體計算和術語有所不同。銷量產(chǎn)量銷地產(chǎn)地3.2表上作業(yè)法運輸問題中尋找可行解1023206563銷量9563474829217101143

3產(chǎn)量銷地產(chǎn)地填有數(shù)字的格:對應運輸問題解中的基變量取值，這里為3+4-1=6個空格：對應解中非基變量表上作業(yè)法的基本思想是:先設法給出一個初始方案(如典例所示),然后根據(jù)確定的判別準則對初始方案進行檢查、調(diào)整、改進，直至求出最優(yōu)方案。表上作業(yè)法和單純形法的求解思想完全一致，但是具體作法更加簡捷。3.2表上作業(yè)法

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

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

判定是否最優(yōu)？是結(jié)束最優(yōu)方案——求解思路圖表上作業(yè)法1.最小元素法2.沃格爾（Vogel）法(一)初始方案的給定給定初始方案的方法很多(如前例)，一般來說，希望方法簡便易行，并能給出較好的方案。減少迭代次數(shù)。這里介紹1.最小元素法基本思想：就近供應，即優(yōu)先考慮單位運價最?。ɑ蜻\距最短）的供銷業(yè)務，最大限度地滿足其供銷量。銷地產(chǎn)地產(chǎn)量311310719284741059銷量3656203－3－31－1－1－4－4-6－66433－3－3-3-3銷地產(chǎn)地產(chǎn)量311310719284741059銷量365620316433Z=4*3+3*10+3*1+1*2+6*4+3*5=86最小元素法的說明退化現(xiàn)象：

部分產(chǎn)量和＝部分銷量和在迭代過程中，可能出現(xiàn)一行和一列同時被劃去。銷地產(chǎn)地產(chǎn)量31145777384121069銷量36562034－4－4－1－1-6－6616－3－3－6-60為使迭代過程中基變量的個數(shù)恰好為(m+n-1)個，應在同時劃去的一行或一列中的某個格中填入數(shù)字0，表示這個格中的變量是取值為0的基變量。以便當做有數(shù)字的格看待。銷地產(chǎn)地產(chǎn)量31145777384121069銷量365620346160基本思想：優(yōu)選考慮最大差額（最小運價優(yōu)勢）方案行（列）差額（罰數(shù)）=次小運價系數(shù)-最小運價系數(shù)2.沃格爾（Vogel）法(差額法)行差額列差額1023206563銷量95474891710113產(chǎn)量

銷地產(chǎn)地0112513()6220071312121162()33()521108()1023206563銷量95474891710113產(chǎn)量

銷地產(chǎn)地633521一般當產(chǎn)銷地數(shù)量不多時，(Vogel)法給出的初始方案有時就是最優(yōu)方案。沃格爾法Z=5*3+2*10+3*1+1*8+6*4+3*5=85最小元素法Z=4*3+3*10+3*1+1*2+6*4+3*5=86>8529練習.求下表給出的運輸問題的初始基本可行解．

B1B2B3B4產(chǎn)量A14104420A2773815A31210615銷量510251050(一)初始方案的給定30

銷地產(chǎn)地B1B2B3B4aiA14104420A2773815A31210615銷量5102510505100151010(一)初始方案的給定31BjAiB1B2B3B4aiA14104420A2773815A31210615bj5102510505100151010(一)初始方案的給定

最小元素法或Vogel法給出的是一個運輸問題的基可行解，需要通過最優(yōu)性檢驗判別該解得目標函數(shù)值是否最優(yōu)，當為否時，應進行調(diào)整得到優(yōu)化.(二)最優(yōu)性檢驗與方案的調(diào)整基本思想：計算非基變量（未填上數(shù)值的格，即空格）的檢驗數(shù)（也稱為空格的檢驗數(shù)），若全部大于等于零，則該方案就是最優(yōu)調(diào)運方案，否則就應進行調(diào)整。1.閉回路法2.對偶變量法（位勢法）沿水平或垂直方向前，向左或右轉(zhuǎn)90度（當然也可以不改變方向）繼續(xù)前進，這樣繼續(xù)下去，直至回到出發(fā)的那個空格，由此形成的封閉折線叫做閉回路。閉回路

x25x23

B1B2B3B4B5A1

A2

A3

x35A4

x43

x11x12x31

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

運輸問題中的閉回路有關閉回路的一些重要結(jié)果

定理3-設是一個閉回路，則該閉回路中的變量所對應的系數(shù)列向量具有下面的關系：推論

若一組變量包含閉回路，則這組變量所對應的系數(shù)列向量線性相關。

推論

m+n-1個變量構(gòu)成基變量的充要條件是該變量組不含閉回路。將如下表中6個頂點間用水平或垂直線段連接起來，組成一條封閉的回路。1023206563銷量95346748191371034113產(chǎn)量

銷地產(chǎn)地(A2,B1),(A3,B2)無法連入閉回路中閉回路孤立格是指在所在行或列中唯一出現(xiàn)的變量。孤立格一定不會成為閉回路的頂點最小元素法得初始方案

以確定了初始調(diào)運方案的作業(yè)表為基礎，以一個非基變量作為起始頂點，尋求閉回路。

該閉回路的特點是：除了起始頂點是非基變量（對應著空格）外，其他頂點均為基變量（對應著填有數(shù)字的格）。對于每一個非基變量而言，以其為起點的閉回路存在且唯一。運輸問題中的閉回路目的：計算解中各非基變量(空格)的檢驗數(shù)基本思路：對于代表非基變量的空格（其調(diào)運量為零），把它的調(diào)運量調(diào)整為1（每次調(diào)整一個非基變量）；由于產(chǎn)銷平衡的要求我們必須對這個空格的閉回路的頂點的調(diào)運量加上或減少1(可行條件)；計算出由這些變化給整個運輸方案的總運輸費帶來的變化，這里稱之為檢驗數(shù)。閉回路法求檢驗數(shù)4.如果所有代表非基變量的空格的檢驗數(shù)也即非基變量的檢驗數(shù)都大于等于零，則已求得最優(yōu)解，否則進行方案調(diào)整（后續(xù)）23206563銷量9544

11

3710

產(chǎn)量

銷地產(chǎn)地64333同理可以找出所有空格（即非基變量）的檢驗數(shù)。+1－1＋1－1總運費變化＝即此新可行解較原來解運費增加1元閉回路法求檢驗數(shù)閉回路法求檢驗數(shù)23206563銷量954411

3710

產(chǎn)量

銷地產(chǎn)地6433-1+1-1+1-1+1總運費變化＝7

約定作為起始頂點的非基變量為第一個奇數(shù)次頂點，相鄰頂點為偶次頂點，其它頂點依次排列，那么，該非基變量xij的檢驗數(shù)：=（閉回路上奇數(shù)次頂點運價之和）－（閉回路上偶數(shù)次頂點運價之和）

-11A21210A321A1B4B3B2B1銷地產(chǎn)地檢驗數(shù)表閉回路法求檢驗數(shù)當至少有一個非基變量的檢驗數(shù)是負值時，說明作業(yè)表上當前的調(diào)運方案不是最優(yōu)的，應進行調(diào)整。請畫出下表空格(1,1)和(1,4)的閉回路10050120708090閉回路法求調(diào)整方案選一個非基變量變?yōu)榛兞窟M基選一個基變量變?yōu)榉腔兞侩x基反映在運輸表上就是要選一個空格填上大于0的數(shù)選擇入基的原則是：從絕對值最大的負檢驗數(shù)格(k,l)出發(fā)閉回路法求調(diào)整方案-11A21210A321A1B4B3B2B1銷地產(chǎn)地檢驗數(shù)表在作業(yè)表上以（A2,B4）為起點作一條除該空格外其余頂點均為有數(shù)字格組成的閉回路閉回路法求調(diào)整方案206563銷量94

1

374

產(chǎn)量銷地產(chǎn)地

6

33

調(diào)運方案（最小元素法得到）+1-1=min{3,1}=1離基？在作業(yè)表上以（A2,B4）為起點作一條除該空格外其余頂點均為有數(shù)字格組成的閉回路在這條閉回路上，在保持產(chǎn)銷平衡的條件下對偶數(shù)頂點格子的運量做最大可能的調(diào)整+1-1閉回路法求調(diào)整方案（A2,B4）為起點作一條出該空格外其余頂點均為有數(shù)字各組成的閉回路206563銷量94

375

產(chǎn)量

銷地產(chǎn)地

6

32

調(diào)運方案（最小元素法得到）1=min{3,1}=1繼續(xù)用閉回路檢驗，直到檢驗數(shù)σ≥01.在作業(yè)表上從絕對值最大的負檢驗數(shù)格(k,l)出發(fā),即xkl為起始變量作出閉回路。2.以空格(k,l)為第一個奇數(shù)頂點，沿閉回路的順（或逆）時針方向依次對頂點編號。3.在閉回路上的所有偶數(shù)頂點中，找出運輸量最小的格子，以該格對應的變量為離基變量。4.調(diào)整量5.將該閉回路上所有奇數(shù)頂點處的運輸量都增加

所有偶數(shù)頂點處的運輸量都減去ij

=min{該閉回路中偶數(shù)次頂點運輸量xij}閉回路法求調(diào)整方案

在閉回路方法當中，要判斷一個方案是否最優(yōu)，需要通過每一個空格來尋找回路，以及根據(jù)閉回路求出每個空格的檢驗數(shù)，當一個運輸問題的產(chǎn)地和銷地很多時，用此方法工作量十分繁重.位勢法位勢法是根據(jù)對偶理論推導出來的一種求解檢驗數(shù)方法。運輸方案的調(diào)整同前面的閉回路法.49位勢法求檢驗數(shù)原問題對偶問題50記原問題基變量XB的下標集合為I，有如下式子成立：解上面第一個方程，將ui、vj代入第二個方程求出檢驗數(shù),稱ui(i=1,…,m),vj(j=1,…,n)分別成為第i行和第j列的位勢回憶：這里Pij有如何特殊形式?位勢法求檢驗數(shù)對偶變量uiu1u2u3對偶變量vjv1v2v3v4不妨令v1=1，則u2=0;v3=2;u1=1;v4=9;u3=-4;v2=8.(1)(0)(-4)(1)(8)(2)(9)1023206563銷量95346748191371034113產(chǎn)量

銷地產(chǎn)地注意：由于這些位勢的數(shù)值是相互關聯(lián)的，所以填寫時可以先任意決定其中的一個，然后推導出其他位勢的數(shù)值。A2A3A1B4B3B2B1銷地產(chǎn)地檢驗數(shù)表121-11012uiu1u2u3vjv1v2v3v4(1)(0)(-4)(1)(8)(2)(9)1023206563銷量95346748191371034113產(chǎn)量

銷地產(chǎn)地位勢法計算非基變量xij檢驗數(shù)的公式σij=cij-（ui+vj）=（閉回路上奇數(shù)次頂點運距或運價之和）-（閉回路上偶數(shù)次頂點運距或運價之和）閉回路法計算非基變量xij檢驗數(shù)的公式：復習比較檢驗數(shù)計算的兩種方法思考：試解釋位勢變量的含義（提示：寫出運輸問題的對偶問題）表

上

作

業(yè)

法得到最優(yōu)方案算出的總運價分析實際問題列出產(chǎn)銷平衡表及單位運價表求檢驗數(shù)（閉回路法或位勢法）

是確定初始調(diào)運方案（最小元素法或Vogel法）

找出絕對值最大的負的檢驗數(shù)用閉回路調(diào)整，得出新的調(diào)運方案否循環(huán)所有檢驗數(shù)≥0求

解步驟1產(chǎn)銷2銷產(chǎn)3.擴大的運輸問題（中轉(zhuǎn)站）3.3產(chǎn)銷不平衡運輸問題及其應用Minz=cij·xijni=1j=1mMinz=cij·xij+0xi,n+1ni=1j=1mi=1m相當于：增加一個假想銷地1.產(chǎn)銷問題ai>bj產(chǎn)地銷地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnBn+1０

０┆０銷量產(chǎn)量b1 b2 ┈

bna1a2┊a(chǎn)maibj相當于：增加一個假想銷地產(chǎn)銷問題單位運價表Minz=cij·xijni=1j=1mMinz=cij·xij+0xm+1,jni=1j=1mj=1n銷產(chǎn)問題相當于：增加一個假想產(chǎn)地ai<bj產(chǎn)地銷地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnAm+10 0 ┈ 0銷量產(chǎn)量b1 b2 ┈

bna1a2┊a(chǎn)mbjai銷產(chǎn)問題單位運價表相當于：增加一個假想產(chǎn)地例一：某工廠按合同規(guī)定必須于當年的每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如表示。又如果生產(chǎn)出來的柴油機當季不交貨，每臺每積壓一個季度需要存儲維護費用0.15萬元。要求在完成合同的情況下，做出使全年生產(chǎn)費用最小的決策。季度生產(chǎn)能力(臺)單位成本(萬元/臺)ⅠⅡⅢⅣ2535301010.811.111.011.3運輸問題案例1數(shù)學模型：設xij第i季度生產(chǎn)，用于第j季度交貨的數(shù)量。目標函數(shù)：

minz=cijxiji=1j=1

44x11+x12+x13+x1425

x22+x23+x2435

x33+x3430

x4410x11=10x12+x22

=15x13+x23+x33

=25x14+x24+x34+x44=20xij0,(i=1,····,4;j=1,····,4)供應：ⅠⅡⅢⅣⅠⅡⅢⅣ需求：季度生產(chǎn)能力(臺)單位成本(萬元/臺)ⅠⅡⅢⅣ2535301010.811.111.011.3某工廠按合同規(guī)定必須于當年的每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。合同要求交貨不得超過生產(chǎn)力產(chǎn)>銷數(shù)學模型：季度生產(chǎn)能力(臺)單位成本(萬元/臺)ⅠⅡⅢⅣ2535301010.811.111.011.3每臺每積壓一個季度需要存儲維護費用0.15萬元。單位運價表：ⅠⅡⅢⅣ銷量ⅠⅡ Ⅲ ⅣD產(chǎn)量10.8 10.95 11.1011.25025

M11.1011.25

11.40035

M

M 11.00

11.15030單位：萬元供應需求10 15 25

2030M MM

11.30010當i>j時，必須xij=0，令cij=M(很大的正數(shù))，加以懲罰產(chǎn)>銷

例二有A、B、C三個化肥廠供應四個地區(qū)Ⅰ、Ⅱ、Ⅲ、Ⅳ的農(nóng)用化肥，三個工廠每年各自的產(chǎn)量為A--50萬噸，B--60萬噸，C--50萬噸。四個地區(qū)的需求量分別是Ⅰ地區(qū)最高50萬噸，最低30萬噸，Ⅱ地區(qū)為70萬噸，Ⅲ地區(qū)為30萬噸以下，Ⅳ地區(qū)不低于10萬噸。問：如何調(diào)運，可使總的調(diào)運費用最小？單位調(diào)運費用如下表所示。產(chǎn)地銷地A1A2A3B1B2B3B4產(chǎn)量銷量1613221714131915192023―單位運價表50605030-50700-3010-單位：萬元/萬噸設xij--第i工廠調(diào)至第j需求地區(qū)的化肥數(shù)量運輸問題案例2銷產(chǎn)上限50運輸問題案例2ABCDⅠ Ⅰ Ⅱ Ⅲ Ⅳ Ⅳ

16 16 13 22 17 1714 14 13 19 15 1519 19 20 23 M MM 0 M 0 M 0供應需求產(chǎn)量銷量50605050

30

20

70

30

10

50修正運價表產(chǎn)地銷地A1A2A3B1B2B3B4產(chǎn)量銷量1613221714131915192023―單位運價表50605030-50700-3010-單位：萬元/萬噸設xij--第i工廠調(diào)至第j需求地區(qū)的化肥數(shù)量銷產(chǎn)擴大的運輸問題例：在前面的糖果例題中，若既可以從Ai運到Bj，也可以經(jīng)過中間站T1、T2、T3、T4或者Ai、Bj轉(zhuǎn)運，稱擴大的運輸問題。幾點說明：1.所有的產(chǎn)地、銷地、中間站均視作產(chǎn)地、銷地；2.所有中轉(zhuǎn)站的轉(zhuǎn)運量等于總的產(chǎn)量之和；3.不能出現(xiàn)循環(huán)倒運現(xiàn)象，允許自身往自身最多調(diào)運一次，運價為Cij=0；4.實際產(chǎn)地產(chǎn)量為轉(zhuǎn)運量與該產(chǎn)地實際產(chǎn)量之和，實際銷地銷量為轉(zhuǎn)運量與實際銷量之和。A1A2A3T1T2T3T4B1B2B3B4A1A2A3T1T2T3T4B1B2B3B401310-3-0214335-21-2331131019287410523115-4-232331711943210108501321011310221202846452718241-262411858-422267460142102142032130產(chǎn)銷產(chǎn)量銷量27242920202020202020202020202020202023262526產(chǎn)銷平衡表

某餐館承辦宴會，每晚連續(xù)舉行，共舉行五次。宴會上需用特殊的餐巾，根據(jù)參加的人數(shù)，預計