運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用(第五版)(第三章運(yùn)輸問(wèn)題)

2023/1/291運(yùn)籌學(xué)

OPERATIONSRESEARCH

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

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

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

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

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

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

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

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

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

B1

B2

B3

B4產(chǎn)量

A1

4

3730

A2

3

1410

A3

6

3930銷量

30

60

540

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

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

B1

B2

B3

B4

A1

5

20007

A2

3

11116

A36

312222

5

1111

3322

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

判別解的最優(yōu)性需要：計(jì)算檢驗(yàn)數(shù)。方法有兩種閉回路：是在已給出的調(diào)運(yùn)方案的運(yùn)輸表上從一個(gè)代表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)，遇到代表基變量的填入數(shù)字的格可轉(zhuǎn)90度（當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個(gè)空格，由此形成的封閉折線叫做閉回路。一個(gè)空格存在唯一的閉回路。1.閉回路法因?yàn)槿我夥腔蛄烤杀硎緸榛蛄康奈ㄒ痪€性組合，因此對(duì)于任意空格都能夠找到、并且只能找到唯一的一條閉回路。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ā)，找到一個(gè)閉回路如上表所示?；芈酚兴膫€(gè)頂點(diǎn)，除

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

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

我們先給u1賦個(gè)任意數(shù)值，不妨設(shè)u1=0，則從基變量x11的檢驗(yàn)數(shù)求得v3=c13-u1=3-0=3。同理可以求得v4=10，u2=-1，等等見(jiàn)上表。檢驗(yàn)數(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ì)法計(jì)算檢驗(yàn)數(shù)：

檢驗(yàn)數(shù)：又因?yàn)榛兞康臋z驗(yàn)數(shù)為0，于是由（m+n-1)個(gè)基變量的檢驗(yàn)數(shù)可解出，進(jìn)而計(jì)算其他非基變量的檢驗(yàn)數(shù)。其中第i個(gè)分量第m+j個(gè)分量2023/1/2921三、改進(jìn)運(yùn)輸方案的辦法——閉回路調(diào)整法當(dāng)表中的某個(gè)檢驗(yàn)數(shù)小于零時(shí)，方案不為最優(yōu)，需要調(diào)整。方法是：選取所有負(fù)檢驗(yàn)數(shù)中最小的非基變量作為入基變量，以求盡快實(shí)現(xiàn)最優(yōu)。（1）確定調(diào)整量：例：取，表明增加一個(gè)單位的運(yùn)輸量，可使得總運(yùn)費(fèi)減少1。在以為出發(fā)點(diǎn)的閉回路中，找出所有偶數(shù)頂點(diǎn)的調(diào)運(yùn)量：，則調(diào)整量（2）調(diào)整方法：把所有閉回路上為偶數(shù)頂點(diǎn)的運(yùn)輸量都減少這個(gè)值，奇數(shù)頂點(diǎn)的運(yùn)輸量都增加這個(gè)值(見(jiàn)下表)。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)整運(yùn)量后的新方案：銷地產(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對(duì)上表用位勢(shì)法進(jìn)行檢驗(yàn)如下表，可知已達(dá)最優(yōu)解。表上作業(yè)法的一般步驟：1、用最小元素法或Vogel法確定初始基可行解；2、判斷是否為最優(yōu)：用閉回路法或位勢(shì)法計(jì)算空格檢驗(yàn)數(shù)，若所有檢驗(yàn)數(shù)均非負(fù)，則已得到最優(yōu)解；否則進(jìn)入第三步；3、從所有負(fù)檢驗(yàn)數(shù)中選擇最小者對(duì)應(yīng)空格作為進(jìn)基變量，從此點(diǎn)出發(fā)作閉回路，確定調(diào)整量，奇點(diǎn)處增加，偶點(diǎn)處減少。2023/1/2924例：用表上作業(yè)法，求解下面的運(yùn)輸問(wèn)題：銷地產(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àn)數(shù)均非負(fù)，故已達(dá)最優(yōu)解。2023/1/2928一、產(chǎn)銷不平衡的運(yùn)輸問(wèn)題例1：某公司從兩個(gè)產(chǎn)地，，將產(chǎn)品運(yùn)往三個(gè)銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最小？銷地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3產(chǎn)量（件）A1646200A2655300

銷量（件）250200200

500650§3

產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及應(yīng)用

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

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

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