運(yùn)輸問題及解法

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

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

第2頁,共42頁，2024年2月25日，星期天2.產(chǎn)銷不平衡問題此時分為兩種情形來考慮：供不應(yīng)求：即產(chǎn)量小于銷量時有

供過于求：即產(chǎn)量大于銷量時有第3頁,共42頁，2024年2月25日，星期天二.運(yùn)輸問題的模型產(chǎn)銷平衡問題模型第4頁,共42頁，2024年2月25日，星期天將約束方程式展開可得約束方程式中共mn個變量，m+n個約束。第5頁,共42頁，2024年2月25日，星期天第6頁,共42頁，2024年2月25日，星期天第7頁,共42頁，2024年2月25日，星期天2.m+n個約束中有一個是多余的（因為其間含有一個平衡關(guān)系式）所以R(A)=m+n-1，即解的mn個變量中基變量為m+n-1個。第8頁,共42頁，2024年2月25日，星期天三.運(yùn)輸問題的解法運(yùn)輸問題仍然是線性規(guī)劃問題，可以用線性規(guī)劃法中的單純形法來解決。但是：

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

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

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

B2，B3，B4。各加工廠每天的產(chǎn)量、各門市部每天的銷售量以及從各加工廠到各門市部的運(yùn)價如下表所示。問：該公司應(yīng)如何調(diào)運(yùn)，在滿足各門市部銷售需要的情況下，使得運(yùn)費支出為最少？第11頁,共42頁，2024年2月25日，星期天運(yùn)輸問題一般用表上作業(yè)法求解，需建立表格模型：單位運(yùn)價表產(chǎn)銷平衡表用線性規(guī)劃法處理此問題。設(shè)由產(chǎn)地i到銷地j的運(yùn)量為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)第12頁,共42頁，2024年2月25日，星期天給出初始調(diào)運(yùn)方案最常用的方法——最小元素法314633初始方案運(yùn)費Z0=3×1+6×4+4×3+1×2+3×10+3×5=86(元)第13頁,共42頁，2024年2月25日，星期天表上作業(yè)法要求，調(diào)運(yùn)方案的數(shù)字格必須為m+n-1個，且所有數(shù)字格不構(gòu)成閉回路。一般，用最小元素法給出的方案符合這一要求。閉回路:從方案中某一始格出發(fā)，沿同行或同列前進(jìn)，當(dāng)遇到一個數(shù)字格時可以可轉(zhuǎn)90度或繼續(xù)前進(jìn)，按此方法進(jìn)行，直到回到始點的一個封閉曲線。同行或同列最多有兩個點。第14頁,共42頁，2024年2月25日，星期天最小元素法中的退化情況360542出現(xiàn)退化時，要在同時被劃去的行列中任選一個空格填0，此格作為有數(shù)字格。第15頁,共42頁，2024年2月25日，星期天

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

B1

）→（A1

B3

）→（A2

B3）→（A2

B1

）；

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

-c13+c23-c21=1

314633第16頁,共42頁，2024年2月25日，星期天③計算出此空格的檢驗數(shù)σij,若σij≥０，則該方案為最優(yōu)方案，否則轉(zhuǎn)３；

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

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

Ai

→

Bj增運(yùn)１單位所引起的總費用的增量。

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

Ai

→

Bj上增運(yùn)。第17頁,共42頁，2024年2月25日，星期天3.調(diào)整:從σij為最大正值的空格出發(fā).對其閉回路上的奇數(shù)頂點運(yùn)量增加θ,偶數(shù)頂點的運(yùn)量減少θ(這才能保證新的平衡)，其中θ為該空格閉回路中偶數(shù)頂點的最小值?！擀?4=-1<0，∴從（A2

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

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

2。σ11=1，σ12=2σ22=1，σ24=-1σ31=10，σ33=12314633第18頁,共42頁，2024年2月25日，星期天經(jīng)再計算新方案的檢驗數(shù)全部大于0。所以，該新方案為最優(yōu)方案，可計算得總運(yùn)費為85元。注：若閉回路的偶數(shù)頂點中同時有兩個格以上運(yùn)量為θ，則調(diào)整后其中一個變空格，其余填0。（保證基變量個數(shù)不變）

3

6

1

3

2

5第19頁,共42頁，2024年2月25日，星期天2.確定初始方案的方法之二—伏格爾法（Vogel法）⑴求各行各列運(yùn)價最小與次小之差額，選其中最大的行或列中最小運(yùn)價進(jìn)行供應(yīng)；

⑵如果某一行或某一列按照這種方法已被供應(yīng)滿，則劃去該行或該列，在剩下的行列中重復(fù)這種方法，即得最優(yōu)方案。第20頁,共42頁，2024年2月25日，星期天3635122762第21頁,共42頁，2024年2月25日，星期天3.求空格檢驗數(shù)的方法之二—位勢法原理：設(shè)有運(yùn)輸問題的對偶問題為第22頁,共42頁，2024年2月25日，星期天

3146333101245仍以例一為例：對偶變量表面上是7個，實際上只有6個?！嘤幸粋€是自由變量。第23頁,共42頁，2024年2月25日，星期天當(dāng)找出σij<0的格后，調(diào)整方法仍用閉回路法。位勢法步驟：

①由有數(shù)格cij=ui+vj求得ui和vj（先令u1=0），原有數(shù)格（基變量）的檢驗數(shù)σij=0；

②空格σij=cij—

(ui+vj)；

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

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

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

見表3-33。第37頁,共42頁，2024年2月25日，星期天假定各條航線使用相同型號的船只，又各城市間的航程天數(shù)見表3-34。第38頁,共42頁，2024年2月25日，星期天又知每條船只每次裝卸貨的時間各需1天，則該航運(yùn)公司至少應(yīng)配備多少條船，才能滿足