第三章運(yùn)輸問(wèn)題

第三章運(yùn)輸問(wèn)題第1頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月第三章運(yùn)輸問(wèn)題

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

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

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

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

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

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

3.2

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

例3.1

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

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

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

2.伏格爾法最小元素法的缺點(diǎn)：為了節(jié)省一處的費(fèi)用，有時(shí)造成其他處要多花幾倍的運(yùn)費(fèi)。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小費(fèi)用，這就有一個(gè)差額，差額越大，說(shuō)明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)運(yùn)費(fèi)增加越多。因而對(duì)差額最大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)?；诖耍駹柗ǖ牟襟E是：

第一步：分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)之間的差額，并填入最右列和最下行。

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

第三步：對(duì)未劃的行和列再分別計(jì)算各行、各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，重復(fù)一、二步。第三章運(yùn)輸問(wèn)題第11頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月第三章運(yùn)輸問(wèn)題B1B2B3B4行差額A13113100A219281A3741051列差額2513項(xiàng)目銷地產(chǎn)量B1B2B3B4A1527A23

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

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

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

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

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

說(shuō)明如果把x22增加一個(gè)單位，那么總運(yùn)費(fèi)要增加1元。

我們計(jì)算x24的檢驗(yàn)數(shù)：

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

2.位勢(shì)法用閉回路法求檢驗(yàn)數(shù)時(shí)，需要給每一空格找一條閉回路。當(dāng)產(chǎn)銷點(diǎn)多時(shí)，這種計(jì)算很繁瑣。下面介紹一種更為簡(jiǎn)便的方法—位勢(shì)法（乘數(shù)法）。位勢(shì)法的原理是線性規(guī)劃的對(duì)偶理論。下面通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明。設(shè)有一個(gè)兩個(gè)產(chǎn)地、三個(gè)銷地的運(yùn)輸問(wèn)題，其線性規(guī)劃模型如下：第三章運(yùn)輸問(wèn)題第19頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月

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

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

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

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

σij=cij-(ui+vj)這樣就可以從已知的ui，vj中求得。這些計(jì)算可以在表格中進(jìn)行，以例3.1說(shuō)明。第三章運(yùn)輸問(wèn)題第24頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月第一步，按最小元素法給出初始解，制成表格。

第二步，在上表中增加一行、一列，在列中填入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以此類推。第三章運(yùn)輸問(wèn)題項(xiàng)目銷地B1B2B3B4A143A231A363第25頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月

第三章運(yùn)輸問(wèn)題項(xiàng)目銷地uiB1B2B3B4A112430A2311-1-1A3106123-5vj29310B1B2B3B4A1A2A3317119432101085第26頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月第三步，按σij=cij-(ui+vj)計(jì)算所有空格的檢驗(yàn)數(shù)。如：

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

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

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

第三章運(yùn)輸問(wèn)題第27頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月

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

對(duì)此表格出的運(yùn)輸方案，我們用位勢(shì)法進(jìn)行檢驗(yàn)：第三章運(yùn)輸問(wèn)題項(xiàng)目銷地產(chǎn)量B1B2B3B4A1527A2314A3639銷量3656第30頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月

可知所有檢驗(yàn)數(shù)都大于等于零，此解是最優(yōu)解，這時(shí)最小總費(fèi)用為85元。第三章運(yùn)輸問(wèn)題項(xiàng)目銷地uiB1B2B3B4A102520A23211-1A396123-5vj29310第31頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月

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

由于總的產(chǎn)量大于銷量，就要考慮多余的物資在哪一地貯存問(wèn)題。設(shè)xi,n+1是產(chǎn)地Ai的貯存量，于是有：第三章運(yùn)輸問(wèn)題第33頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月

令c’ij=cij，當(dāng)i=1，…，m，j=1，…n時(shí)；

c’ij=0，當(dāng)i=1，…，m，j=n+1時(shí)將其分別代入，得到：第三章運(yùn)輸問(wèn)題第34頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月

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

第三章運(yùn)輸問(wèn)題項(xiàng)目銷地產(chǎn)量I’I”IIIIIIV’IV”產(chǎn)地ABCD50605050銷量3020703010