運輸問題的典例

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

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

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

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

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

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

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

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

判定是否最優(yōu)？是結(jié)束最優(yōu)方案——求解思路圖表上作業(yè)法1.最小元素法2.沃格爾（Vogel）法(一)初始方案的給定給定初始方案的方法很多(如前例)，一般來說，希望方法簡便易行，并能給出較好的方案。減少迭代次數(shù)。這里介紹1.最小元素法基本思想：就近供應(yīng)，即優(yōu)先考慮單位運價最?。ɑ蜻\距最短）的供銷業(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)一行和一列同時被劃去。34－4－4－1－1-6－6616－3－3－6-60為使迭代過程中基變量的個數(shù)恰好為(m+n-1)個，應(yīng)在同時劃去的一行或一列中的某個格中填入數(shù)字0，表示這個格中的變量是取值為0的基變量。以便當(dāng)做有數(shù)字的格看待。346160(一)初始方案的給定基本思想：優(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一般當(dāng)產(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>8530練習(xí).求下表給出的運輸問題的初始基本可行解．

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

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

x25

x23B1B2B3B4B5A1A2A3

x35A4

x43x11x12x31

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

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

銷地產(chǎn)地(A2,B1),(A3,B2)無法連入閉回路中運輸問題中的閉回路孤立格是指在所在行或列中唯一出現(xiàn)的變量。孤立格一定不會成為閉回路的頂點目的：計算解中各非基變量(空格)的檢驗數(shù)基本思路：對于代表非基變量的空格（其調(diào)運量為零），把它的調(diào)運量調(diào)整為1；由于產(chǎn)銷平衡的要求我們必須對這個空格的閉回路的頂點的調(diào)運量加上或減少1(可行條件)；計算出由這些變化給整個運輸方案的總運輸費帶來的變化，這里稱之為檢驗數(shù)。如果所有代表非基變量的空格的檢驗數(shù)也即非基變量的檢驗數(shù)都大于等于零，則已求得最優(yōu)解，否則進行方案調(diào)整（后續(xù)）閉回路法求檢驗數(shù)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ù)當(dāng)至少有一個非基變量的檢驗數(shù)是負值時，說明作業(yè)表上當(dāng)前的調(diào)運方案不是最優(yōu)的，應(yīng)進行調(diào)整。閉回路法求調(diào)整方案選一個非基變量變?yōu)榛兞窟M基選一個基變量變?yōu)榉腔兞侩x基反映在運輸表上就是要選一個空格填上大于0的數(shù)選擇入基的原則是：從絕對值最大的負檢驗數(shù)格(k,l)出發(fā)閉回路法求調(diào)整方案-11A21210A321A1B4B3B2B1銷地產(chǎn)地檢驗數(shù)表（A2,B4）為起點作一條除該空格外其余頂點均為有數(shù)字格組成的閉回路閉回路法求調(diào)整方案（A2,B4）為起點作一條出該空格外其余頂點均為有數(shù)字各組成的閉回路206563銷量94

1

374產(chǎn)量

銷地產(chǎn)地

6

33

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

375產(chǎn)量

銷地產(chǎn)地

6

32

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

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

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

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