運籌學基礎及應用(第五版)(第三章運輸問題)

2023/1/291運籌學

OPERATIONSRESEARCH

2023/1/292第三章運輸問題運輸問題的數(shù)學模型表上作業(yè)法產(chǎn)銷不平衡的運輸問題及應用2023/1/293§1運輸問題的典例及數(shù)學模型

一、引例某公司從三個產(chǎn)地，，將產(chǎn)品運往四個銷地，

，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運費單價如表所示。應如何調(diào)運可使運費最?。夸N地運費單價產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059銷量（噸）36562023/1/294解：從表中可知：總產(chǎn)量=總銷量。這是一個產(chǎn)銷平衡的運輸問題。假設表示從產(chǎn)地運往銷地的產(chǎn)品數(shù)量，建立如下表格：于是可建立如下的數(shù)學模型：銷地運費單價產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059銷量（噸）36562023/1/295目標函數(shù)：約束條件：產(chǎn)量約束銷量約束20202023/1/296設有m個產(chǎn)地，分別為;n個銷地，分別是；從產(chǎn)地運往銷地的單位運價是，運量是產(chǎn)地的產(chǎn)量；是銷地的銷量。

二、一般運輸問題數(shù)學模型則該運輸問題的模型如下：2023/1/297說明：當時，稱其為產(chǎn)銷平衡的運輸問題，否則產(chǎn)銷不平衡。2023/1/298說明：從上述模型可以看出：（1）這是一個線性規(guī)劃的模型；（2）變量有m×n個；（3）約束條件有m+n個；（4）系數(shù)矩陣非常稀疏；系數(shù)矩陣的秩一般為（m+n-1),而非m+n。若直接用單純形法求解，顯然單純形表比較龐大，于是在單純形法的基礎上創(chuàng)建了表上作業(yè)法求解運輸問題這一特殊的線性規(guī)劃問題2023/1/299從第一節(jié)的運輸問題的數(shù)學模型可知，運輸問題實際上也屬于線性規(guī)劃，但由于運輸問題的特殊性（變量個數(shù)較多，系數(shù)矩陣的特點），如果用單純形表格方法迭代，計算量很大。今天介紹的“表上作業(yè)法”，是針對運輸問題的特殊求解方法，實質(zhì)還是單純形法，但減少了計算量。

表上作業(yè)法適用于求解產(chǎn)銷平衡的運輸問題。（產(chǎn)銷不平衡的問題可轉(zhuǎn)化為平衡問題）§2

運輸問題的表上作業(yè)法

2023/1/2910表上作業(yè)法一般步驟：1、找出初始基本可行解；2、檢查各非基變量的檢驗數(shù)，是否達到最優(yōu)性條件，若達到，則得最優(yōu)解；否則轉(zhuǎn)第三步；3、確定出基變量、進基變量，用閉回路方法進行調(diào)整，得到新的基可行解；4、重復第二、第三步，直至得到最優(yōu)解。銷地運費單價產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059銷量（噸）36562023/1/2911一、確定初始基本可行解：

對于有m個產(chǎn)地n個銷地的產(chǎn)銷平衡問題，有m個關于產(chǎn)量的約束方程和n個關于銷量的約束方程。表面上，共有m+n個約束方程。但由于產(chǎn)銷平衡，其模型最多只有m+n-1個獨立的約束方程，所以運輸問題實際上有m+n-1個基變量。在m×n的產(chǎn)銷平衡表上給出m+n-1個數(shù)字格，其相對應的調(diào)運量的值即為基變量的值。那么在該例中，應有3+4-1=6個基變量。2023/1/29121.最小元素法

最小元素法的思想是就近供應，即對單位運價最小的變量分配運輸量。在表上找到單位運價最小的x21，并使x21取盡可能大的值，即x21=3,把A1的產(chǎn)量改為1，B1的銷量改為0，并把B1列劃去。在剩下的3×3矩陣中再找最小運價，同理可得其他的基本可行解。銷地產(chǎn)地

B1

B2

B3

B4產(chǎn)量

A1

4

3730

A2

3

1410

A3

6

3930銷量

30

60

540

63020203113108510294712023/1/2913表中填有數(shù)字的格對應于基變量(取值即為格中數(shù)字），而空格對應的是非基變量（取值為零）.在求初始基本可行解時要注意的一個問題：當我們?nèi)《▁ij的值之后，會出現(xiàn)Ai的產(chǎn)量與Bj的銷量都改為零的情況，這時只能劃去Ai行或Bj列，但不能同時劃去Ai行與Bj列。（或者在同時劃去Ai行與Bj列時，在該行或該列的任意空格處填加一個0。）這樣可以保證填過數(shù)或零的格為m+n-1個，即保證基變量的個數(shù)為m+n-1個。2023/1/29142.Vogel法

Vogel法的思想是:一地的產(chǎn)品如果不能按照最小運費就近供應，就考慮次小運費，這就有差額，差額越大，說明不能按最小運費調(diào)運時，運費增加得越多。因而差額越大處，就應當采用最小運費調(diào)運。銷地產(chǎn)地

B1

B2

B3

B4

A1

5

20007

A2

3

11116

A36

312222

5

1111

3322

20203113102947110852023/1/2915二、最優(yōu)解的判別

判別解的最優(yōu)性需要：計算檢驗數(shù)。方法有兩種閉回路：是在已給出的調(diào)運方案的運輸表上從一個代表非基變量的空格出發(fā)，沿水平或垂直方向前進，遇到代表基變量的填入數(shù)字的格可轉(zhuǎn)90度（當然也可以不改變方向）繼續(xù)前進，這樣繼續(xù)下去，直至回到出發(fā)的那個空格，由此形成的封閉折線叫做閉回路。一個空格存在唯一的閉回路。1.閉回路法因為任意非基向量均可表示為基向量的唯一線性組合，因此對于任意空格都能夠找到、并且只能找到唯一的一條閉回路。2023/1/2916銷地產(chǎn)地

B1

B2

B3

B4產(chǎn)量

A1（+）1

4（-）3

7

A2（-）3

1（+）

4

A363

9銷量

3

6

5

6

108531131029471從非基變量出發(fā)，找到一個閉回路如上表所示?；芈酚兴膫€頂點，除

外，其余都為基變量。調(diào)整調(diào)運量：，運費增加了3元；，運費減少3元，運費增加2元；，運費減少1元調(diào)整后，總運費增加：3-3+2-1=1元。說明如果讓為基變量，運費就會增加，其增加值1作為的檢驗數(shù)，2023/1/2917閉回路法計算檢驗數(shù)：就是對于代表非基變量的空格（其調(diào)運量為零），把它的調(diào)運量調(diào)整為1，由于產(chǎn)銷平衡的要求,必須對這個空格的閉回路中的各頂點的調(diào)運量加上或減少1。最后計算出由這些變化給整個運輸方案的總運輸費帶來的變化。以這個變化的數(shù)值，作為各空格（非基變量）的檢驗數(shù)。判別最優(yōu)解準則：如果所有代表非基變量的空格的檢驗數(shù)都大于等于零，則已求得最優(yōu)解；否則繼續(xù)改進找出最優(yōu)解。2023/1/29182.位勢法

（1）對運輸表上的每一行賦予一個數(shù)值，對每一列賦予一個數(shù)值，稱為行（列)位勢。（2）行（列)位勢的數(shù)值是由基變量的檢驗數(shù)所決定的，即基變量要滿足：非基變量的檢驗數(shù)就可以用公式求出。2023/1/2919

我們先給u1賦個任意數(shù)值，不妨設u1=0，則從基變量x11的檢驗數(shù)求得v3=c13-u1=3-0=3。同理可以求得v4=10，u2=-1，等等見上表。檢驗數(shù)的求法，即用公式，如。銷地產(chǎn)地

B1

B2

B3

B4

ui

A1

1

2

4

3

0

A2

3

1

1

-1

-1

A3

10

6

12

3

-5

vj

2

9

3

10

3113108510294712023/1/2920位勢法計算檢驗數(shù)：

檢驗數(shù)：又因為基變量的檢驗數(shù)為0，于是由（m+n-1)個基變量的檢驗數(shù)可解出，進而計算其他非基變量的檢驗數(shù)。其中第i個分量第m+j個分量2023/1/2921三、改進運輸方案的辦法——閉回路調(diào)整法當表中的某個檢驗數(shù)小于零時，方案不為最優(yōu)，需要調(diào)整。方法是：選取所有負檢驗數(shù)中最小的非基變量作為入基變量，以求盡快實現(xiàn)最優(yōu)。（1）確定調(diào)整量：例：取，表明增加一個單位的運輸量，可使得總運費減少1。在以為出發(fā)點的閉回路中，找出所有偶數(shù)頂點的調(diào)運量：，則調(diào)整量（2）調(diào)整方法：把所有閉回路上為偶數(shù)頂點的運輸量都減少這個值，奇數(shù)頂點的運輸量都增加這個值(見下表)。2023/1/2922銷地產(chǎn)地

B1

B2

B3

B4

ui

A1

4(+1)

3(-1)

0

A2

3

1(-1)

+1

-1

A3

6

3

-5

vj

2

9

3

10

311310851029471調(diào)整運量后的新方案：銷地產(chǎn)地

B1

B2

B3

B4產(chǎn)量

A1

5

2

7

A2

3

1

4

A3

6

3

9銷量

3

6

5

6

2023/1/2923銷地產(chǎn)地

B1

B2

B3

B4

ui

A1

0

2

5

2

0

A2

3

2

1

1

-2

A3

9

6

12

3

-5

vj

3

9

3

10

311310851029471對上表用位勢法進行檢驗如下表，可知已達最優(yōu)解。表上作業(yè)法的一般步驟：1、用最小元素法或Vogel法確定初始基可行解；2、判斷是否為最優(yōu)：用閉回路法或位勢法計算空格檢驗數(shù)，若所有檢驗數(shù)均非負，則已得到最優(yōu)解；否則進入第三步；3、從所有負檢驗數(shù)中選擇最小者對應空格作為進基變量，從此點出發(fā)作閉回路，確定調(diào)整量，奇點處增加，偶點處減少。2023/1/2924例：用表上作業(yè)法，求解下面的運輸問題：銷地產(chǎn)地甲乙丙丁產(chǎn)量137645224322343853銷量3322解:用最小元素法確定初始基可行解，如下表所示：2023/1/2925銷地產(chǎn)地甲乙丙丁產(chǎn)量1

33

70

62

405（0）2

2

4

3

22

2(-2）3

4

33

8

53（-4）銷量3（3）3（7）2（6）2（4）銷地產(chǎn)地甲乙丙丁產(chǎn)量1

3

0

2

05（0）21

-1-1

2

2(-2）35

3653（-4）銷量3（3）3（7）2（6）2（4）++--2023/1/2926銷地產(chǎn)地甲乙丙丁產(chǎn)量1

33

70

6

425（0）2

2

4

32

20

2(-2）3

4

33

8

53（-4）銷量3（3）3（7）2（5）2（4）銷地產(chǎn)地甲乙丙丁產(chǎn)量1

3

01

25（0）21

-12

0

2(-2）35

3753（-4）銷量3（3）3（7）2（5）2（4）++--2023/1/2927銷地產(chǎn)地甲乙丙丁產(chǎn)量1

33

7

6

425（0）2

2

40

32

20

2(-2）3

4

33

8

53（-3）銷量3（3）3（6）2（5）2（4）1

311

25（0）21

0

2

0

2(-2）34

3643（-3）銷量3（3）3（6）2（5）2（4）此時所有非基變量的檢驗數(shù)均非負，故已達最優(yōu)解。2023/1/2928一、產(chǎn)銷不平衡的運輸問題例1：某公司從兩個產(chǎn)地，，將產(chǎn)品運往三個銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運費單價如表所示。應如何調(diào)運可使運費最小？銷地運費單價產(chǎn)地B1B2B3產(chǎn)量（件）A1646200A2655300

銷量（件）250200200

500650§3

產(chǎn)銷不平衡的運輸問題及應用

例1：某公司從兩個產(chǎn)地，，將產(chǎn)品運往三個銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運費單價如表所示。應如何調(diào)運可使運費最??？例1：某公司從兩個產(chǎn)地，，將產(chǎn)品運往三個銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運費單價如表所示。應如何調(diào)運可使運費最?。坷?：某公司從兩個產(chǎn)地，，將產(chǎn)品運往三個銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運費單價如表所示。應如何調(diào)運可使運費最??？例1：某公司從兩個產(chǎn)地，，將產(chǎn)品運往三個銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運費單價如表所示。應如何調(diào)運可使運費最??？例1：某公司從兩個產(chǎn)地，，將產(chǎn)品運往三個銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運費單價如表所示。應如何調(diào)運可使運費最?。坷?：某公司從兩個產(chǎn)地，，將產(chǎn)品運往三個銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運費單價如表所示。應如何調(diào)運可使運費最??？2023/1/2929易知這個問題中：總產(chǎn)量＜總銷量，即這時可考慮增加一個假想產(chǎn)地，其產(chǎn)量是（總銷量－總產(chǎn)量＝150)他到各銷地的單位運費是０．于是得到如下的表格：銷地運費單價產(chǎn)地B1B2B3產(chǎn)量（件）A1646200A2655300A３０００１５０

銷量（件）2502002006502023/1/2930例2：某單位有三個區(qū)，一區(qū)、二區(qū)、三區(qū)；每年需要生活用煤和取暖用煤各3000噸，1000噸，2000噸；由河北臨城、山西盂縣兩處煤礦負責供應，兩地價格和煤質(zhì)相同，兩煤礦的供應能力分別是1500噸，和4000噸。由煤礦至該單位三個區(qū)的單位運價如表所示。銷地運費單價產(chǎn)地一區(qū)二區(qū)三區(qū)供應量（噸）盂縣1.81.71.554000臨城1.61.51.751500需要量（噸）300010002000由于供應能力限制，經(jīng)研究決定，一區(qū)供應量可減少0~300噸，二區(qū)全部滿足，三區(qū)不能少于1500噸，試求使得運費最小的運輸方案？2023/1/2931根據(jù)題意，添加虛擬產(chǎn)地后，可作出產(chǎn)銷平衡的運價表：銷地運費單價產(chǎn)地一區(qū)B1一區(qū)1B1’二區(qū)B2三區(qū)B3三區(qū)1B3’供應量（噸）盂縣1.81.81.71.551.554000臨城1.61.61.51.751.751500虛擬產(chǎn)地M0MM0500需要量（噸）27003001000150050060002023/1/2932銷地運費單價產(chǎn)地ⅠⅡⅢⅣ供應量（萬噸）A1613221750B1413191560C192023_50最低需求／萬噸3070010最高需求／萬噸507030不限例３：設有三個化肥廠供應四個地區(qū)的化肥，假設等量的化肥在這個地區(qū)的使用效果相同。各廠的產(chǎn)量、各地區(qū)的需要量、單位運價如表所示。求出運費最省的調(diào)撥方案。2023/1/2933解：無論考慮需求的上限還是下限，這都是一個產(chǎn)銷不平衡的問題。當考慮下限時，產(chǎn)〉銷；當考慮需求上限時，產(chǎn)〈銷。于是可以考慮在滿足最低需求的情況下，兼顧最高需求。即將每個地區(qū)的需求分為最低需求和（最高-最低）需求，最低部分必須滿足，高出的部分可滿足也可不滿足。雖然銷地Ⅳ的需求無上限，但根據(jù)生產(chǎn)能力，最多可以給她分配60萬噸。另外若將最高需求考慮進來，則需添加虛擬產(chǎn)地D，其產(chǎn)量應為

50萬噸。于是可給出如下的產(chǎn)銷平衡及運價表。2023/1/2934銷地運費單價產(chǎn)地ⅠⅠ’ⅡⅢⅢ’ⅣⅣ’供應量（噸）A1616132222171750B1414131919151560C1919202323MM50假想DM0MM0M050最高需求／萬噸30207003010502102023/1/2935二、生產(chǎn)與存儲問題例4：某廠按照合同規(guī)定須于當年每季度末分別提供10，15，25，20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如表所示。又如果生產(chǎn)出來的柴油機當季不交貨，每臺每積壓一個季度，存儲維護費用0.15萬元。要求在完成合同的情況下，使得全年生產(chǎn)（存儲）費用最小的決策。季度生產(chǎn)能力/臺單位成本/萬元Ⅰ2510.8Ⅱ3511.1Ⅲ3011.0Ⅳ1011.32023/1/2936銷售運費單價生產(chǎn)ⅠⅡⅢⅣ虛擬D供應量（臺）Ⅰ10.810.8+0.1511.1011.25025ⅡM11.1011.2511.40035ⅢMM11.011.15030ⅣMMM11.30010需求量/臺1015252030注意：單位運價如何確定故設：表示第季度生產(chǎn)，用于第季度交貨