5.3-運輸問題的求解方法匯總課件

1、第3節(jié) 運輸問題的求解方法表上作業(yè)法產(chǎn)銷平衡表與單位運價表 表上作業(yè)法產(chǎn)銷不平衡的運輸問題的求解方法一、產(chǎn)銷平衡表與單位運價表 運輸問題還可用產(chǎn)銷平衡表與單位運價表進行描述。 假設某種物資有m個生產(chǎn)地點Ai（i=1，2，m），其產(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)銷平衡表和單位運價表5.3.1。銷地產(chǎn)地產(chǎn)量銷量表5.3.1 產(chǎn)銷平衡表與單位運價表 運輸這一類特殊問題可用更加簡便的求解方法表上作業(yè)法求解，實質(zhì)仍是單純形法，步驟如下： （1

2、）確定初始調(diào)運方案，即找出初始基可行解,在產(chǎn)銷平衡表上給出m+n-1個數(shù)字格。 二、表上作業(yè)法 （2）求非基變量的檢驗數(shù)，即在表上計算空格的檢驗數(shù)，判別是否達到最優(yōu)解：是否存在負的檢驗數(shù)？如果存在負的檢驗數(shù)，則初始調(diào)運方案不是最優(yōu)方案；如果所有檢驗數(shù)都非負，則初始調(diào)運方案已經(jīng)是最優(yōu)方案了。如果已經(jīng)得到最優(yōu)調(diào)運方案，則停止計算，否則轉(zhuǎn)入下一步。 （3）確定換入變量和換出變量，找出新的調(diào)運方案（新的基可行解），即在表上用閉回路法進行調(diào)整。 (4）重復（1）（2），直到求出最優(yōu)解為止。 （一）確定初始可行基的方法最小元素法 從單位運價表中最小的運價開始確定供銷關系，然后考慮運價次小的，一直到給出初始

3、基可行解為止。伏格爾法 采用最小元素法可能造成其他處的更多浪費，伏格爾法考慮最小運費與次小運費之間的差額，差額越大，就按次小運費調(diào)運。 （二）最優(yōu)解的判別 計算非基變量（空格）的檢驗數(shù),當所有的檢驗數(shù) 時，為最優(yōu)解。 求空格檢驗數(shù)的方法有：閉回路法 以某一空格為起點找一條閉回路，用水平或垂直線向前劃，每碰到一數(shù)字格轉(zhuǎn)900后，繼續(xù)前進，直到回到起始空格為止。 閉回路如圖5.3.1的（a）、（b）、（c）等所示。從每一個空格出發(fā)一定存在并且可以找到唯一的閉回路。因為，m+n-1個數(shù)字格（基變量）對應的系數(shù)向量是一個基，任一空格（非基變量）對應的系數(shù)向量是這個基的線性組合。圖5.3.1 閉回路示意

4、圖 舉例說明： 可表示為而這些向量構(gòu)成了閉回路見圖 位勢法 一種較為簡便的求檢驗數(shù)的方法。 設 是對應運輸問題的m+n個約束條件的對偶變量。B是含有一個人工變量Xa的初始基矩陣。 Xa在目標函數(shù)中的系數(shù)Ca ，由線性規(guī)劃的對偶理論可知 而每一個決策變量Xij的系數(shù)向量 ，所以 由單純形法可知，所有基變量的檢驗數(shù)等于0，即例1：假設某種物資共有3個產(chǎn)地，其日產(chǎn)量分別是：A1為7 t， A2為4 t， A3為9 t；該種物資的4個銷售地，其日銷量分別： B1為3 t， B2為6 t， B3為5 t， B4為6 t；各產(chǎn)地到銷售地的單位物資的運價如表5.3.2所示。在滿足各銷售點需要量的前提下，如何

5、調(diào)運該種物資，才能使總運費達到最??？銷地產(chǎn)地B1B2B3B4A1A2A3317119432101085表5.3.2下面用具體例子說明表上作業(yè)法的計算步驟。解：首先列出這一問題的產(chǎn)銷平衡表，見表5.3.3。 表5.3.3 某物資運輸?shù)漠a(chǎn)銷平衡表 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3749銷量3656 用最小元素法求解： 第1步，從表5.3.4中找出最小運價為1，表示應先將A2 的產(chǎn)品供應 B1 。在表5.3.3中（ A2 B1 ）的交叉格處填上3，得表5.3.4。將表5.3.4中的B1 列運價劃去，得表5.3.5。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A33749銷量3656表5.3.4銷地產(chǎn)

6、地B1B2B3B4A1A2A3119432101085表5.3.5 第2步，在表5.3.5未劃去的元素中再找出最小運價為2，確定A2多余的1 t物資供應B3 。得表5.3.6。將表5.3.5的行運價劃去，得表5.3.7。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A331749銷量3656表5.3.6銷地產(chǎn)地B1B2B3B4A1A2A3119432101085表5.3.7 第3步 ，按照上述方法直到單位運價表上的所有元素被劃去為止。最后在產(chǎn)銷平衡表上得到一個調(diào)運方案，即初始基可行解，見表5.3.8。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A331749銷量3656表5.3.8 伏格爾法的步驟是： 第1步：

7、在表5.3.2中分別計算出各行、各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行，見表5.3.9。銷地產(chǎn)地B1B2B3B4行差額 A1A2A3317119432101085011列差額 2513表5.3.9 第2步：從行或列差額中選出最大者，選擇它所在行或列中的最小元素。在表5.3.9中，可確定A3的產(chǎn)品應首先供應B2，得表5.3. 10。將單位運價表中的列的數(shù)字劃去，得表5.3.11。表5.3.10銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A36749銷量3656銷地產(chǎn)地B1B2B3B4A1A2A331732101085表5.3.11 第3步,對表5.3.11中余下的元素再分別計算出各

8、行、各列的最小運費和次最小運費的差額，重復第1、第2步，直到給出初始基可行解為止。初始基可行解列于表5.3.12。表5.3.12銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3365213749銷量3656 伏格爾法給出的初始基可行解更接近最優(yōu)解。本例中用伏格爾法給出的初始基可行解就是最優(yōu)解。 用閉回路法判別檢驗：閉回路法計算檢驗數(shù)的經(jīng)濟解釋為,在已給出初始基可行解的表中，可從任一空格出發(fā)，如（A1, B1），若讓A1的產(chǎn)品調(diào)運1 t給B1，為了保持產(chǎn)銷平衡，就要依次進行調(diào)整,就構(gòu)成了以（ A1, B1）空格為起點，其他為數(shù)字格的閉回路，如表5.3.13中的虛線所示。閉回路各頂點所在格的右上角數(shù)字是單

9、位運價。 表5.3.13調(diào)整的方案使運費增加 將“1”填（A1, B1）格中，這就是檢驗數(shù)。按上述辦法，可找出所有空格的檢驗數(shù)，見表5.3.14。當檢驗數(shù)還有負數(shù)時，需要對原方案進行改造。表5.3.14 用位勢法檢驗: 第1步,按最小元素法給出表5.3.8的初始基可行解，作表5.3.15。在對應表5.3.8的數(shù)字格處填入單位運價。銷地產(chǎn)地B1B2B3B4A1A2A31432105表5.3.15 第2步,在上表增加一行一列，在列中填入 ，在行中填入 ，得表5.3.16。銷地產(chǎn)地B1B2B3B4A1A2A314321050-1-529310表5.3.16 首先令u1=0,然后按 可確定所有和的數(shù)值

10、。 第3步,按 計算所有空格的檢驗數(shù)，特設計計算表5.3.17。表5.3.17 改進的方法閉回路調(diào)整法: 在表5.3.17中，(A2, B4)為調(diào)入格，以此格為出發(fā)點，作一閉回路,得表5.3.18。表5.3.18 格的調(diào)入量 是選擇閉回路上具有（-1）的數(shù)字格中的最小者即 ，然后，按閉回路上的正、負號，加、減此值得到調(diào)整方案，如表5.3.19所示。再用閉回路法或位勢法求各空格的檢驗數(shù)，得表5.3.20。在表5.3.20中，因為所有檢驗數(shù)都非負，故得最優(yōu)解，這時，得到最小運費為85（元）。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3365213749銷量3656銷地產(chǎn)地B1B2B3B4A1A2A30922112表5.3.19表5.3.20三、產(chǎn)銷不平衡的運輸問題的求解方法 前面求解運輸問題的表上作業(yè)法，是以產(chǎn)銷平衡為前提的 ，即 實際情況需要把產(chǎn)銷不平衡的問題化成產(chǎn)銷平衡的問題。 當產(chǎn)大于銷 運輸問題的數(shù)學模型為求使 且滿足 考慮多余的物資在哪一個產(chǎn)地就地儲存的問題。設 是產(chǎn)地Ai的儲存