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

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

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

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

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

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

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

A2，A3，和4個(gè)門市部B1，

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

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

B1

）→（A1

B3

）→（A2

B3）→（A2

B1

）；

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

-c13+c23-c21=1

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

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

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

Ai

→

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

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

Ai

→

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

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

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

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

3

6

1

3

2

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

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

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

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

②空格σij=cij—

(ui+vj)；

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

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

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

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