運輸問題及解法

第五章運輸問題一.運輸問題的一般提法在經(jīng)濟建設(shè)中，經(jīng)常碰到物資調(diào)撥中的運輸問題。例如煤、鋼材、糧食、木材等物資，在全國都有若干生產(chǎn)基地，分別將這些物資調(diào)到各消費基地去，應(yīng)如何制定調(diào)運方案，使總的運輸費用最少？運輸問題的一般提法是：

1.產(chǎn)銷平衡問題

2.產(chǎn)銷不平衡問題此時分為兩種情形來考慮：供不應(yīng)求：即產(chǎn)量小于銷量時有

供過于求：即產(chǎn)量大于銷量時有二.運輸問題的模型產(chǎn)銷平衡問題模型將約束方程式展開可得約束方程式中共mn個變量，m+n個約束。2.m+n個約束中有一個是多余的（因為其間含有一個平衡關(guān)系式）所以R(A)=m+n-1，即解的mn個變量中基變量為m+n-1個。三.運輸問題的解法

運輸問題仍然是線性規(guī)劃問題，可以用線性規(guī)劃法中的單純形法來解決。但是：

1.運輸問題所涉及的變量多，造成單純形表太大；

2.若把技術(shù)系數(shù)矩陣A中的0迭代成非0，會使問題更加復雜。以上兩個原因使得我們不得不利用運輸問題的特點設(shè)計出它的特殊解法——表上作業(yè)法。表上作業(yè)法，實質(zhì)上還是單純形法。其步驟如下：1.確定一個初始可行調(diào)運方案?？梢酝ㄟ^最小元素法、Vogel法來完成；2.檢驗當前可行方案是否最優(yōu)，常用的方法有閉回路法和位勢法，用這兩種方法計算出檢驗數(shù)，從而判別方案是否最優(yōu)；3.方案調(diào)整，從當前方案出發(fā)尋找更好方案，常采用閉回路法。（Ⅰ）運輸問題的常用解法：最小元素法（確定初始方案）→閉回路法（檢驗當前方案）→閉回路法（方案調(diào)整）以下面例題說明這種方法的具體步驟：例12：某食品公司下設(shè)3個加工廠A1，

A2，A3，和4個門市部B1，

B2，B3，B4。各加工廠每天的產(chǎn)量、各門市部每天的銷售量以及從各加工廠到各門市部的運價如下表所示。問：該公司應(yīng)如何調(diào)運，在滿足各門市部銷售需要的情況下，使得運費支出為最少？

運輸問題一般用表上作業(yè)法求解，需建立表格模型：單位運價表產(chǎn)銷平衡表

用線性規(guī)劃法處理此問題。設(shè)由產(chǎn)地i到銷地j的運量為xij，模型為：minz=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij≥0(i=1,2,3;j=1,2,3,4)給出初始調(diào)運方案最常用的方法——最小元素法314633初始方案運費Z0=3×1+6×4+4×3+1×2+3×10+3×5=86(元)

表上作業(yè)法要求，調(diào)運方案的數(shù)字格必須為m+n-1個，且所有數(shù)字格不構(gòu)成閉回路。一般，用最小元素法給出的方案符合這一要求。閉回路:從方案中某一始格出發(fā)，沿同行或同列前進，當遇到一個數(shù)字格時可以可轉(zhuǎn)90度或繼續(xù)前進，按此方法進行，直到回到始點的一個封閉曲線。同行或同列最多有兩個點。最小元素法中的退化情況360542

出現(xiàn)退化時，要在同時被劃去的行列中任選一個空格填0，此格作為有數(shù)字格。

①找出任意空格的閉回路—除此空格外，其余頂點均為有數(shù)格。如可找（A1

B1

）→（A1

B3

）→（A2

B3）→（A2

B1

）；

2.檢驗（閉回路法:計算空格的檢驗數(shù)）②計算出空格的檢驗數(shù)—等于閉回路上由此空格起奇數(shù)頂點運價與偶數(shù)頂點運價的代數(shù)和。如σ11＝c11

-c13+c23-c21=1

314633③計算出此空格的檢驗數(shù)σij,若σij≥０，則該方案為最優(yōu)方案，否則轉(zhuǎn)３；

注：檢驗數(shù)的經(jīng)濟意義，以σ11為例，空格表示原方案中X11=0,即A1→B1

的運輸量為0。若試著運1單位，則這樣所引起的總費用的變化恰是σ11，可見檢驗數(shù)σij的意義是：

Ai

→

Bj增運１單位所引起的總費用的增量。

σij>０，說明若增運一單位則在總運輸量不變情況下，總運費會增加。此時不應(yīng)在

Ai

→

Bj上增運。3.調(diào)整:從σij

為最大正值的空格出發(fā).對其閉回路上的奇數(shù)頂點運量增加θ,偶數(shù)頂點的運量減少θ(這才能保證新的平衡)，其中θ為該空格閉回路中偶數(shù)頂點的最小值?！擀?4=-1<0，∴從（A2

B4）出發(fā)其閉回路上θ=1，調(diào)整后得到一個新方案（如下表），運量為θ=1的（A2

B3）變空格，得到新方案后再轉(zhuǎn)

2。σ11=1，σ12=2σ22=1，σ24=-1σ31=10，σ33=12314633經(jīng)再計算新方案的檢驗數(shù)全部大于0。所以，該新方案為最優(yōu)方案，可計算得總運費為85元。注：若閉回路的偶數(shù)頂點中同時有兩個格以上運量為θ，則調(diào)整后其中一個變空格，其余填0。（保證基變量個數(shù)不變）3613252.確定初始方案的方法之二—伏格爾法（Vogel法）⑴求各行各列運價最小與次小之差額，選其中最大的行或列中最小運價進行供應(yīng)；

⑵如果某一行或某一列按照這種方法已被供應(yīng)滿，則劃去該行或該列，在剩下的行列中重復這種方法，即得最優(yōu)方案。36351227623.求空格檢驗數(shù)的方法之二—位勢法原理：設(shè)有運輸問題的對偶問題為

3146333101245仍以例一為例：對偶變量表面上是7個，實際上只有6個?！嘤幸粋€是自由變量。當找出σij<0的格后，調(diào)整方法仍用閉回路法。位勢法步驟：

①由有數(shù)格cij=ui+vj求得ui和vj

（先令u1=0），原有數(shù)格（基變量）的檢驗數(shù)σij=0；

②空格σij=cij—

(ui+vj)；

③由此可得檢驗數(shù)表。（Ⅲ）產(chǎn)銷不平衡的運輸問題1.產(chǎn)大于銷的情況：添加松弛變量xi,n+1xin+1的定義：由Ai向Bn+1的運量，而Bn+1并不存在，相當于增加了一個虛設(shè)的銷地—Ai自己的倉庫里，自己往自己的地方運，運費cin+1顯然為0。實際上xin+1即Ai的剩余量。A1AmB1……BnBn+1C1100C1nCm1Cmn產(chǎn)大于銷的單位運價表產(chǎn)大于銷的產(chǎn)銷量表A1Ama1amB1……BnBn+1b1……bn2.銷大于產(chǎn)的情況：添加松弛變量xm+1j同理，此時xm+1j的意義為銷售短缺的量，同樣，Am+1不存在，cm+1j為0。銷大于產(chǎn)的產(chǎn)銷量表A1Ama1amB1……Bnb1……bnAm+1A1AmB1……BnC1100C1nCm1Cmn銷大于產(chǎn)的單位運價表Am+1……四應(yīng)用舉例由于在變量個數(shù)相等的情況下，表上作業(yè)法的計算遠比單純形法簡單得多。所以在解決實際問題時，人們常常盡可能把某些線性規(guī)劃的問題化為運輸問題的數(shù)學模型。下面介紹幾個典型的例子。例3某廠按合同規(guī)定須于當年每個季度末分別提供10，15，25，20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如表3-29所示。又如果生產(chǎn)出來的柴油機當季不交貨的，每臺每積壓一個季度需儲存、維護等費用0.15萬元。要求在完成合同的情況下，作出使該廠全年生產(chǎn)(包括儲存、維護)費用最小的決策。解由于每個季度生產(chǎn)出來的柴油機不一定當季交貨，所以設(shè)xij為第i季度生產(chǎn)的用于第j季度交貨的柴油機數(shù)。根據(jù)合同要求，必須滿足又每季度生產(chǎn)的用于當季和以后各季交貨的柴油機數(shù)不可能超過該季度的生產(chǎn)能力，故又有：第i季度生產(chǎn)的用于j季度交貨的每臺柴油機的實際成本cij應(yīng)該是該季度單位成本加上儲存、維護等費用。cij的具體數(shù)值見表3-30。設(shè)用ai表示該廠第i季度的生產(chǎn)能力，bj表示第i季度的合同供應(yīng)量，則問題可寫成：

顯然，這是一個產(chǎn)大于銷的運輸問題模型。注意到這個問題中當i＞j時，xij=0，所以應(yīng)令對應(yīng)的cij=M，再加上一個假想的需求D，就可以把這個問題變成產(chǎn)銷平衡的運輸模型，并寫出產(chǎn)銷平衡表和單位運價表(合在一起，見表3-31)。

經(jīng)用表上作業(yè)法求解，可得多個最優(yōu)方案，表3-32中列出最優(yōu)方案之一。即第Ⅰ季度生產(chǎn)25臺，10臺當季交貨，15臺Ⅱ季度交貨；Ⅱ季度生產(chǎn)5臺，用于Ⅲ季度交貨；Ⅲ季度生產(chǎn)30臺，其中20臺于當季交貨，10臺于Ⅳ季度交貨。Ⅳ季度生產(chǎn)10臺，于當季交貨。按此方案生產(chǎn)，該廠總的生產(chǎn)(包括儲存、維護)的費用為773萬元。例4某航運公司承擔六個港口城市A、B、C、D、E、F的四條固定航線的物資運輸任務(wù)。已知各條航線的起點、終點城市及每天航班數(shù)

見表3-33。假定各條航線使用相同型號的船只，又各城市間的航程天數(shù)見表3-34。又知每條船只每次裝卸貨的時間各需1天，則該航運公司至少應(yīng)配備多少條船，才能滿足所有航線的運貨需求?解該公司所需配備船只分兩部分。(1)載貨航程需要的周轉(zhuǎn)船只數(shù)。例如航線1，在港口E裝貨1天，E→D航程17天，在D卸貨1天，總計19天。每天3航班，故該航線周轉(zhuǎn)船只需57條。各條航線周轉(zhuǎn)所需船只數(shù)見表3-35。以上累計共需周轉(zhuǎn)船只數(shù)91條

.第4節(jié)應(yīng)用舉例(2)各港口間調(diào)度所需船只數(shù)。有些港口每天到達船數(shù)多于需要船數(shù)，例如港口D，每天到達3條，需求1條；而有些港口到達數(shù)少于需求數(shù)，例如港口B