運(yùn)輸問題的典例

運(yùn)輸問題的典例運(yùn)輸問題的數(shù)學(xué)模型求解方法——表上作業(yè)法第三章運(yùn)輸問題特殊的線性規(guī)劃運(yùn)輸問題的典例運(yùn)輸問題的數(shù)學(xué)模型求解方法——表上作業(yè)法第三章運(yùn)輸問題特殊的線性規(guī)劃運(yùn)輸問題的典例例1.某食品公司經(jīng)銷的主要產(chǎn)品之一是糖果.它下面設(shè)有三個(gè)加工廠,每天的糖果產(chǎn)量分別為:A1-7t,A2-4t,A3-9t.該公司把這些糖果分別運(yùn)往四個(gè)地區(qū)的門市銷售,各地區(qū)每天的銷售量分別為：B1-3t,B2-5t,B3-6t.已知從每個(gè)加工廠到各銷售門市部每噸的運(yùn)價(jià)如表3-1所示，問該食品公司應(yīng)如何調(diào)運(yùn),在滿足各門市部銷售需要的情況下，使得總的運(yùn)費(fèi)支出為最少.8291A251047A3103113A1B4B3B2B1門市部加工廠表3-1單位：元/t

運(yùn)輸問題的一般提法現(xiàn)有一批貨物,從m個(gè)供應(yīng)地運(yùn)往n個(gè)銷售地,Ai(i=1,‥‥,m)處有貨物aj噸，Bj(j=1,‥‥,n)處需貨物bj噸,已知從Ai到Bj的運(yùn)價(jià)為cij

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

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

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

運(yùn)輸問題的典例運(yùn)輸問題的數(shù)學(xué)模型求解方法——表上作業(yè)法第三章運(yùn)輸問題特殊的線性規(guī)劃運(yùn)輸問題的典例運(yùn)輸問題的數(shù)學(xué)模型求解方法——表上作業(yè)法第三章運(yùn)輸問題特殊的線性規(guī)劃表上作業(yè)法作業(yè)表（產(chǎn)銷平衡表）：將運(yùn)輸問題的有關(guān)信息表和決策變量——調(diào)運(yùn)量結(jié)合在一起構(gòu)成“作業(yè)表”（產(chǎn)銷平衡表）。運(yùn)輸問題的典例1023206563銷量9563474829217101143

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

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

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

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

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

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

銷地產(chǎn)地633521一般當(dāng)產(chǎn)銷地?cái)?shù)量不多時(shí)，(Vogel)法給出的初始方案有時(shí)就是最優(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>8530練習(xí).求下表給出的運(yùn)輸問題的初始基本可行解．

(一)初始方案的給定315100151010(一)初始方案的給定325100151010(一)初始方案的給定

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

x25

x23B1B2B3B4B5A1A2A3

x35A4

x43x11x12x31

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

運(yùn)輸問題中的閉回路將如下表中6個(gè)頂點(diǎn)間用水平或垂直線段連接起來，組成一條封閉的回路。1023206563銷量95346748191371034113產(chǎn)量

銷地產(chǎn)地(A2,B1),(A3,B2)無法連入閉回路中運(yùn)輸問題中的閉回路孤立格是指在所在行或列中唯一出現(xiàn)的變量。孤立格一定不會(huì)成為閉回路的頂點(diǎn)目的：計(jì)算解中各非基變量(空格)的檢驗(yàn)數(shù)基本思路：對(duì)于代表非基變量的空格（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為1；由于產(chǎn)銷平衡的要求我們必須對(duì)這個(gè)空格的閉回路的頂點(diǎn)的調(diào)運(yùn)量加上或減少1(可行條件)；計(jì)算出由這些變化給整個(gè)運(yùn)輸方案的總運(yùn)輸費(fèi)帶來的變化，這里稱之為檢驗(yàn)數(shù)。如果所有代表非基變量的空格的檢驗(yàn)數(shù)也即非基變量的檢驗(yàn)數(shù)都大于等于零，則已求得最優(yōu)解，否則進(jìn)行方案調(diào)整（后續(xù)）閉回路法求檢驗(yàn)數(shù)23206563銷量9544

11

3710產(chǎn)量

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

3710產(chǎn)量

銷地產(chǎn)地6433-1+1-1+1-1+1總運(yùn)費(fèi)變化＝7

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

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

1

374產(chǎn)量

銷地產(chǎn)地

6

33

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

375產(chǎn)量

銷地產(chǎn)地

6

32

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

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

=min{該閉回路中偶數(shù)次頂點(diǎn)運(yùn)輸量xij}運(yùn)輸量的變化＝閉回路法求調(diào)整方案位勢法

在閉回路方法當(dāng)中，要判斷一個(gè)方案是否最優(yōu)，需要通過每一個(gè)空格來尋找回路，以及根據(jù)閉回路求出每個(gè)空格的檢驗(yàn)數(shù)，當(dāng)一個(gè)運(yùn)輸問題的產(chǎn)地和銷地很多時(shí)，用此方法工作量十分繁重.位勢法是根據(jù)對(duì)偶理論推導(dǎo)出來的一種求解檢驗(yàn)數(shù)方法.運(yùn)輸方案的調(diào)整同前面的閉回路法.47位勢法求檢驗(yàn)數(shù)原問題對(duì)偶問題48記原問題基變量XB的下標(biāo)集合為I，有如下式子成立：解上面第一個(gè)方程，將ui、vj代入第二個(gè)方程求出檢驗(yàn)數(shù),稱ui(i=1,…,m),vj(