第三章運輸問題

第三章運輸問題第1頁，共41頁，2023年，2月20日，星期三第三章運輸問題

3.1運輸問題的數(shù)學模型已知有m個生產(chǎn)地點Ai，i=1，2，…，m，可供應(yīng)某種物資，其供應(yīng)量（產(chǎn)量）分別為ai，i=1，2，…，m，有n個銷地Bj，j=1，2，…，n，其需要量分別為bj，j=1，2，…，n，從Ai到Bj運輸單位物資的運價（單價）為cij，這些數(shù)據(jù)可匯總于產(chǎn)銷平衡表和單位運價表中，見下表。（）第2頁，共41頁，2023年，2月20日，星期三

若用xij表示從Ai到Bj的運量，那么在產(chǎn)銷平衡條件下，要求得總運費最小的調(diào)運方案，可求解以下數(shù)學模型：第三章運輸問題項目銷地產(chǎn)量

12…n產(chǎn)地12…m

c11c12…c1nc21c22…c2n…cm1cm2…cmna1a2…am銷量

b1b2…bn第3頁，共41頁，2023年，2月20日，星期三第三章運輸問題這就是運輸問題的數(shù)學模型。它包括m×n個變量，（m+n）個約束方程，其系數(shù)矩陣結(jié)構(gòu)比較松散，且特殊：第4頁，共41頁，2023年，2月20日，星期三第三章運輸問題第5頁，共41頁，2023年，2月20日，星期三系數(shù)矩陣中對應(yīng)于變量xij的系數(shù)向量Pij，其分量除第i個和第m+j個為1外，其余的均為零。即

Pij=（0…1…1…0）T=ei+em+j對于產(chǎn)銷平衡的運輸問題由于存在：可以證明：只有m+n-1個獨立約束方程。即系數(shù)矩陣的秩=m+n-1。由于以上特征，所以求解運輸問題時，可用比較簡便的計算方法，習慣上稱為表上作業(yè)法。

3.2

表上作業(yè)法表上作業(yè)法是單純形法在求解運輸問題的一種簡化方法。其實質(zhì)是單純形法。但具體計算術(shù)語有所不同，可歸納為：（1）找出初始基本可行解，即在（m×n）產(chǎn)銷平衡表上給出m+n-1個獨立的數(shù)字格。第三章運輸問題第6頁，共41頁，2023年，2月20日，星期三（2）求各非基變量的檢驗數(shù)，即在表上計算空格的檢驗數(shù)，判別是否達到最優(yōu)解。如已是最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一步。（3）確定調(diào)入變量和調(diào)出變量，找出新的基本可行解。在表上用閉合回路法調(diào)整。（4）重復（2）（3），直到得到最優(yōu)解。以上算法都可以在表上完成。下面通過例子說明表上作業(yè)法的計算步驟。

例3.1

某公司經(jīng)銷一種產(chǎn)品，公司有三個加工廠A1、A2、A3，其產(chǎn)量分別為7t、4t、9t。公司有四個經(jīng)銷點B1、B2、B3、B4，其銷量分別為3t、6t、5t、6t。已知各加工廠到各銷售點的單位產(chǎn)品運費如下表所示，問公司應(yīng)如何調(diào)運產(chǎn)品，在滿足各銷售點的需求量的前提下，使總運費最小。第三章運輸問題第7頁，共41頁，2023年，2月20日，星期三解先畫出該問題的單位運價表和產(chǎn)銷平衡表，如下：第三章運輸問題B1B2B3B4A1A2A3317119432101085銷地產(chǎn)量B1B2B3B4產(chǎn)地A1A2A3749銷量36563.2.1

確定初始基本可行解與一般線性規(guī)劃問題不同。產(chǎn)銷平衡的運輸問題總是存在可行解。第8頁，共41頁，2023年，2月20日，星期三設(shè)第三章運輸問題令這就是一個可行解，又因變量有界，即由線性方程組理論，運輸問題最多有Cn×nm+n-1個基解，在這有限個基本解中必存在最優(yōu)解。確定初始基本可行解的方法有很多，一般希望的方法既簡便又盡可能接近最優(yōu)解，最常用的方法有兩種：最小元素法和伏格爾（Vogel）法。第9頁，共41頁，2023年，2月20日，星期三

1.最小元素法基本思想：就近供應(yīng)，即從單位單價表中最小的運價開始確定供銷關(guān)系，然后次小。一直到給出初始基本可行解為止。第三章運輸問題項目銷地產(chǎn)量B1B2B3B4A1437A2314A3639銷量3656項目B1B2B3B4A1311310A21928A374105該方案的總費用為86元。①②③④⑤⑥第10頁，共41頁，2023年，2月20日，星期三

2.伏格爾法最小元素法的缺點：為了節(jié)省一處的費用，有時造成其他處要多花幾倍的運費。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應(yīng)，就考慮次小費用，這就有一個差額，差額越大，說明不能按最小運費調(diào)運時運費增加越多。因而對差額最大處，就應(yīng)當采用最小運費調(diào)運?；诖?，伏格爾法的步驟是：

第一步：分別計算出各行和各列的最小運費和次小運費之間的差額，并填入最右列和最下行。

第二步：從行和列差額中選擇最大者，選擇它所在的行或列的最小元素。

第三步：對未劃的行和列再分別計算各行、各列的最小運費和次小運費的差額，重復一、二步。第三章運輸問題第11頁，共41頁，2023年，2月20日，星期三第三章運輸問題B1B2B3B4行差額A13113100A219281A3741051列差額2513項目銷地產(chǎn)量B1B2B3B4A1527A23

14A3639銷量36562276①②③④⑤⑥第12頁，共41頁，2023年，2月20日，星期三由上可見：伏格爾法與最小元素法除在確定供求關(guān)系的原則上不同外，其余步驟均相同。伏格爾法得出的初始解比最小元素法給出的初始解更接近最優(yōu)解。本例用伏格爾法給出的初始解即為最優(yōu)解，最優(yōu)值是85元。

3.2.2最優(yōu)解的判別判別的方法是計算空格（非基變量）的檢驗數(shù)cij-CBB-1Pij都大于等于零（為什么？）。下面介紹兩種求空格檢驗數(shù)的方法。

1.閉回路法從每個空格出發(fā)找一條閉回路，它是以某空格為起點，用水平或垂直線向前劃，每碰到一個數(shù)字時可以轉(zhuǎn)90°后繼續(xù)前進，直到回到起始空格為止。第三章運輸問題第13頁，共41頁，2023年，2月20日，星期三可以證明：如果不區(qū)分閉回路的方向，每一個非基變量空格都存在唯一一個閉回路。閉回路法是用來檢查一個非基變量從零增加到大于零時能不能改變目標函數(shù)值的一種方法。以上例采用最小元素法得出的調(diào)運表為例。第三章運輸問題第14頁，共41頁，2023年，2月20日，星期三第三章運輸問題項目銷地產(chǎn)量B1B2B3B4A1437A2314A3639銷量3656項目B1B2B3B4A1311310A21928A374105第15頁，共41頁，2023年，2月20日，星期三例如在上表中，如果x22增加一個單位，那么要保持解的可行性，就要把x22回路中每個轉(zhuǎn)角點的數(shù)字加以調(diào)整：減少一個x32，增加一個x34，減少一個x14，增加一個x13，減少一個x23。這樣的改變可以繼續(xù)保持供求的平衡假如C22’表示增加一個單位x22后運費的增加數(shù)，那么由運費表可知：

c22’=c22-c32-+c34-c14+c13-c23=

9-4+5-10+3-2=1

說明如果把x22增加一個單位，那么總運費要增加1元。

我們計算x24的檢驗數(shù)：

c24’=?第三章運輸問題第16頁，共41頁，2023年，2月20日，星期三已知運輸問題的產(chǎn)銷平衡和單位運價表，試用伏格爾法求出一個調(diào)運方案，并判斷該方案是否是最優(yōu)的。作業(yè)項目銷地產(chǎn)量B1B2B3B4A184127A2694725A3534326銷量10102015第17頁，共41頁，2023年，2月20日，星期三作業(yè)項目銷地產(chǎn)量B1B2B3B4A198121318A21010121424A38911126A41010111212銷量614355第18頁，共41頁，2023年，2月20日，星期三

2.位勢法用閉回路法求檢驗數(shù)時，需要給每一空格找一條閉回路。當產(chǎn)銷點多時，這種計算很繁瑣。下面介紹一種更為簡便的方法—位勢法（乘數(shù)法）。位勢法的原理是線性規(guī)劃的對偶理論。下面通過一個簡單的例子來說明。設(shè)有一個兩個產(chǎn)地、三個銷地的運輸問題，其線性規(guī)劃模型如下：第三章運輸問題第19頁，共41頁，2023年，2月20日，星期三

共有6個決策變量，在基本解中，應(yīng)有四個基變量（為什么？），2個非基變量。設(shè)u1，u2為對應(yīng)于產(chǎn)地的對偶變量，v1，v2，v3為對應(yīng)于銷地的對偶變量，則其對偶問題是：第三章運輸問題第20頁，共41頁，2023年，2月20日，星期三

如果原始問題得到一個調(diào)運方案（基本可行解），則對偶問題的約束條件是相應(yīng)各變量的最優(yōu)條件。對應(yīng)于基變量的約束條件等式成立，對應(yīng)于非基變量的約束條件，將不等號兩邊相減，即得到它的檢驗數(shù)。第三章運輸問題第21頁，共41頁，2023年，2月20日，星期三例如，在這個調(diào)運方案中，x11，x12，x13，x21是基變量，則對偶約束條件中，前4個約束條件等式成立，即：這是一個有5個變量、4個方程的方程組，令任一變量等于零（不妨令u1=0），則可解出其他ui、vj變量的值。將求出的ui、vj代入到非基變量對應(yīng)的約束條件，兩邊相減，即得到它們的檢驗數(shù)：第三章運輸問題第22頁，共41頁，2023年，2月20日，星期三

由于運輸模型的特殊性，上述計算過程相對比較簡單。在例3.1由最小元素法的得到的初始解中x23，x34，x21，x32，x13，x14是基變量，這時對應(yīng)的檢驗數(shù)是：第三章運輸問題項目銷地產(chǎn)量B1B2B3B4A1437A2314A3639銷量3656第23頁，共41頁，2023年，2月20日，星期三基變量檢驗數(shù)如果設(shè)u1=0，則可以求得：

u1=0，u2=-1，u3=-5，v1=2，v2=9，v3=3，v4=10，因此非基變量的檢驗數(shù)：

σij=cij-(ui+vj)這樣就可以從已知的ui，vj中求得。這些計算可以在表格中進行，以例3.1說明。第三章運輸問題第24頁，共41頁，2023年，2月20日，星期三第一步，按最小元素法給出初始解，制成表格。

第二步，在上表中增加一行、一列，在列中填入ui，在行中填入vj。令u1=0，然后依據(jù)ui+vj=cij，相繼確定ui，vj，依次求出所有的ui、vi的值。例如由u1+v3=3可得出v3=3；由u1+v4=10得出v4=10；由u3+v4=5得出u3=-5以此類推。第三章運輸問題項目銷地B1B2B3B4A143A231A363第25頁，共41頁，2023年，2月20日，星期三

第三章運輸問題項目銷地uiB1B2B3B4A112430A2311-1-1A3106123-5vj29310B1B2B3B4A1A2A3317119432101085第26頁，共41頁，2023年，2月20日，星期三第三步，按σij=cij-(ui+vj)計算所有空格的檢驗數(shù)。如：

σ11=c11-(u1+v1)=3-(0+2)=1

σ12=c12-(u1+v2)=11-(0+9)=2

這些計算可直接在表上進行。這和前面的計算結(jié)果是一樣的。在上表中還有負的檢驗數(shù)，說明未得最優(yōu)解，還可以改進。

第三章運輸問題第27頁，共41頁，2023年，2月20日，星期三

3.2.3改進的計算方法在所有為負值的檢驗數(shù)中選最小的負檢驗數(shù)，以它對應(yīng)的非基變量為調(diào)入變量，如在例3.1中σ24=-1，選非基變量x24為調(diào)入變量，并以x24所在的表格為出發(fā)點作出一個閉回路，如下表：第三章運輸問題項目銷地產(chǎn)量B1B2B3B4A1437A2314A3639銷量3656第28頁，共41頁，2023年，2月20日，星期三由于σ24=-1，表明增加一個單位的x24的運輸量，就可以使總運輸量減少1。我們應(yīng)盡量多地增加x24的運輸量，但為了保證運輸方案的可行性（即所有調(diào)運量必須大于等于零），所以以出發(fā)點x24所在空格為1的閉回路頂點的序號序號中，找到所有偶數(shù)的頂點的調(diào)運量：x14=3，x23=1，取其最小的值為x24的值，即x24=min(3,1)=1。為例使產(chǎn)銷平衡，把所有閉回路上為偶數(shù)頂點的運輸量都減少這個值，而其他頂點運輸量增加這個值，即得到調(diào)整后的運輸方案，如下表：第三章運輸問題第29頁，共41頁，2023年，2月20日，星期三

對此表格出的運輸方案，我們用位勢法進行檢驗：第三章運輸問題項目銷地產(chǎn)量B1B2B3B4A1527A2314A3639銷量3656第30頁，共41頁，2023年，2月20日，星期三

可知所有檢驗數(shù)都大于等于零，此解是最優(yōu)解，這時最小總費用為85元。第三章運輸問題項目銷地uiB1B2B3B4A102520A23211-1A396123-5vj29310第31頁，共41頁，2023年，2月20日，星期三

3.3產(chǎn)銷不平衡的運輸問題及其求解方法前面講的表上作業(yè)法，都是以產(chǎn)銷平衡為前提的。但實際問題中往往是產(chǎn)銷不平衡的，就需要把產(chǎn)銷不平衡問題轉(zhuǎn)化成產(chǎn)銷平衡問題。當產(chǎn)大于銷時，運輸問題的數(shù)學模型可寫成：第三章運輸問題第32頁，共41頁，2023年，2月20日，星期三

由于總的產(chǎn)量大于銷量，就要考慮多余的物資在哪一地貯存問題。設(shè)xi,n+1是產(chǎn)地Ai的貯存量，于是有：第三章運輸問題第33頁，共41頁，2023年，2月20日，星期三

令c’ij=cij，當i=1，…，m，j=1，…n時；

c’ij=0，當i=1，…，m，j=n+1時將其分別代入，得到：第三章運輸問題第34頁，共41頁，2023年，2月20日，星期三

由于這模型中所以這是一個產(chǎn)銷平衡的運輸問題。第三章運輸問題第35頁，共41頁，2023年，2月20日，星期三當產(chǎn)大于銷時，只要增加一個假想的銷地j=n+1（實際上是存儲地），該銷地總需求量為。而在單位運價表中從各地到假想銷地的單位運價為c’i,n+1=0，就轉(zhuǎn)化為一個產(chǎn)銷平衡的運輸問題。類似地，當銷大于產(chǎn)時，可以從產(chǎn)銷平衡表中增加一個假想的產(chǎn)地i=m+1，該產(chǎn)地的產(chǎn)量為。在單位運價表上令該假想產(chǎn)地到各銷地的單位運價c’m+1,j=0，同樣可以轉(zhuǎn)化為一個產(chǎn)銷平衡的運輸問題。第三章運輸問題第36頁，共41頁，2023年，2月20日，星期三例3.2設(shè)有三個化肥廠供應(yīng)四個地區(qū)的農(nóng)田化肥。各化肥廠年產(chǎn)量，各地區(qū)年需求量及從化肥廠到各地區(qū)運送化肥的運價表如下，試求總運費最節(jié)省的化肥調(diào)撥方案。第三章運輸問題項目銷地產(chǎn)量IIIIIIIV產(chǎn)地ABC1614191313202219231715506050最低需求3070010最高需求507030不限第37頁，共41頁，2023年，2月20日，星期三解：這是一個產(chǎn)銷不平衡的運輸問題，總產(chǎn)量為160萬噸，四個地區(qū)的最低需求為110萬噸。最高需求無限制。根據(jù)現(xiàn)有產(chǎn)量，第IV個地區(qū)每年最多能分配到60萬噸。這樣最高需求為210萬噸，大于產(chǎn)量。為了求得平衡，在產(chǎn)銷平衡表中增加一個虛擬的化肥廠D，其產(chǎn)量為50噸。由于各地區(qū)的需求包括兩部分，如地區(qū)I，其中30萬噸是最低需求，故不能由D供給，令相應(yīng)的運價為M（任意大正數(shù)），而另一部分20萬噸或滿足，或不滿足均可以，因此可由D供給，且令相應(yīng)的運價為0。對凡是需求分兩種情況的地區(qū)，實際上可按兩個地區(qū)看待。這樣可以寫出這個問題的產(chǎn)銷平衡表和單位運價表，如下：第三章運輸問題第38頁，共41頁，2023年，2月20日，星期三

第三章運輸問題項目銷地產(chǎn)量I’I”IIIIIIV’IV”產(chǎn)地ABCD50605050銷量30207030