運籌學課件運輸問題

第三章運輸問題第一節(jié)運輸問題典例及數(shù)學模型例：三個產(chǎn)地四個銷地的運輸問題示意圖運輸問題的線性規(guī)劃模型需求約束供應約束上述模型是根據(jù)上圖的具體問題寫出的。一般運輸問題的模型形式基本類似。當產(chǎn)銷平衡時，約束中的不等號可改為等號。運輸問題的線性規(guī)劃模型的系數(shù)矩陣的列向量都是由兩個單位坐標向量疊加構成。從上例中模型的系數(shù)矩陣A就很容易看出這個特點。產(chǎn)銷平衡運輸問題的表上作業(yè)法步驟:（1）在運價表上用Vogel法求出調運方案表；（2）在運價表上用位勢法求非基變量的檢驗數(shù)；（3）檢驗方案是否最優(yōu)。是，停止；否，繼續(xù)（4）；（4）在調運方案表上用閉回路調整法得到新的調運方案；（5）重復（2）。例:某食品公司經(jīng)銷的主要產(chǎn)品之一是糖果。它下面設有三個加工廠，每天的生產(chǎn)量分別為:A1－7噸，A2－4噸，A3－9噸。擬把這些糖果運往四個門市銷售，各門市的每日銷量為B1－3噸，B2－6噸，B3－5噸，B4－6噸。運價表如下，問：如何運送使總運費最??？B1B2B3B4

A1311310

A21928

A374105表1：單位運價表門市加工廠B1B2B3B4產(chǎn)量

A17

A24

A39表2：產(chǎn)銷平衡表銷地產(chǎn)地

銷量3656一、初始方案的確定：在運價表上用Vogel法求出調運方案表B1B2B3B4同行最小兩元素的差產(chǎn)量產(chǎn)地剩余量調整次序調整次序123456123456A1311[3][10]0007107777200A2[1]92[8]1116884441110A37[4]10[5]129300000同列最小兩元素的差調整次序12513Vogel法求初始調運方案a.求出各行、各列最小兩元素的差值；b.在運價表中找出最小差值對應的行或列的最小元的位置，并用“[]”或“○”標記；c.畫“[]”元對應的產(chǎn)地的產(chǎn)品盡可能多地調往畫“[]”元對應的銷地，并將調運量填入調運方案表中的相應位置，同時，產(chǎn)或銷地調運后的剩余量記入本表右上角相應位置。d.若該產(chǎn)地的產(chǎn)量被全部調運完，則該產(chǎn)地在運價表中的行用一條虛線劃去；若該銷地的需求量被全部滿足，則該銷地在運價表中的列用一條虛線劃去；凡是被劃去的行或列不再予以考慮。e.若運價表中所有行和列都被劃去，停止。否則，回到步驟a.。221332124125268銷

量3656銷

地

剩

余

量調整次序130562305330053400035000160000產(chǎn)地銷地運價Vogel法求調運方案銷地B1B2B3B4產(chǎn)量A1527A2314A3639銷

量3656方案產(chǎn)地表3：初始調運方案調運方案表中出現(xiàn)的數(shù)字被稱為有效數(shù)字，它們分別對應此時基變量的值，空格單元的對應變量即是此時的非基變量，其值為0。本表中，基變量x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,非基變量x11=x12=x22=x23=x31=x32=0.二、最優(yōu)性檢驗與方案的調整：(在運價表上用位勢法求非基變量的檢驗數(shù)。)B1B2B3B4uA139u1=0311[3][10]02A271u2=-2[1]92[8]21A3-2-2u3=-57[4]10[5]912vv1=3v2=9v3=3v4=10產(chǎn)地銷地方案位勢法求非基變量的檢驗數(shù)表4*首先將運價置于各單元格的中央，有效數(shù)字（基變量）對應的運價要畫上“[]”。*在u所在列的第一個位置填上u1=0。*然后由等式ui+vj=[cij

]求出所有ui，vj

的值。其中，[cij

]對應表4的畫“[]”的運價。如表4中A1B3處基變量x13對應運價是“[3]”，則由u1+v3=[c13

]=3，得v3=3.*將ui+vj

的計算值分別填入所有未畫“[]”運價的單元格的左上角。*將cij

-ui+vj的計算值分別填入所有未畫“[]”運價的單元格的右下角。每個單元格右下角的數(shù)值即為非基變量的檢驗數(shù)。（3）檢驗方案是否最優(yōu)。是，則停止；否則，繼續(xù)第（4）步。具體法則為：若所有非基變量的檢驗數(shù)都

0，則取得最優(yōu)解；否則，進行調運方案調整（4），即換基迭代。顯然，表4中非基變量的檢驗數(shù)都

0，故已取得最優(yōu)解。停止。（4）在調運方案表上用閉回路調整法得新的調運方案。在一些簡單問題中，Vogel法往往能直接求出最優(yōu)調運方案，上例即是如此。若現(xiàn)在調運方案為方案B1B2B3B4產(chǎn)量A1437A2314A3639銷

量3656調運方案1表5運價B1B2B3B4uA129u1=0311[3][10]12A279u2=-1[1]9[2]82-1A3-2-2u3=-57[4]10[5]912vv1=2v2=9v3=3v4=10位勢法求非基變量的檢驗數(shù)

表6此時，非基變量x24的檢驗數(shù)<0，未取得最優(yōu)解，須用閉回路調整法在調運方案表上進行調運方案的調整。方案B1B2B3B4產(chǎn)量A14(2)3(1)7A231(3)(0)4A3639銷

量3656閉回路調整法表中閉回路上奇數(shù)序號對應的有效數(shù)字中的最小值為1.表71.先從所有負檢驗數(shù)中找到絕對值最大的，對應的單元格出發(fā)構造一個閉回路。但這個閉回路必須滿足除出發(fā)單元格以外的其余每個拐角點處都是有效數(shù)字單元這一條件。表7所示的閉回路即是按此規(guī)則做出。2.從出發(fā)單元格開始，給這個閉回路上各拐角點依次標上(0),(1),(2),……,序號。3.找出奇數(shù)序號對應的有效數(shù)字中的最小值，然后將閉回路上所有奇數(shù)序號對應的有效數(shù)字減去這個最小值，所有偶數(shù)序號對應的有效數(shù)字加上這個最小值。得到調整后的調運方案。這個過程就是單純形法的換基迭代。調整前，表中x23是基變量，x23=1，且為奇數(shù)序號對應的有效數(shù)字中的最小值，x24是非基變量x24=0，調整后，新的調運方案表8中x23=0,x24=1，即此時x23

被換出，x24

被換入為新基下的基變量。方案B1B2B3B4產(chǎn)量A1527A2314A3639銷

量3656調運方案2表8由前述工作知，已取得最優(yōu)解。

表上作業(yè)法與單純形法的關系運輸問題的模型形式實際上是一種系數(shù)矩陣僅含0，1元素的線性規(guī)劃模型。所以可以利用單純形法求解。由于模型的特點，使單純形法求解的過程可用表上作業(yè)法這一簡潔形式表現(xiàn)出來，但表上作業(yè)法的單純形法實質沒有絲毫改變：表上作業(yè)法中的“位勢法”實質上是在求單純表中的檢驗數(shù)；調運方案表中的有效數(shù)字實質上就是單純形法中基變量的值；調運方案表上的“閉回路調整法”實質上是在做單純表上的換基迭代。注：方案B1B2B3B4產(chǎn)量A1437A205＊5A3639銷

量46560添加有效數(shù)字0調運方案3表9(0)方案B1B2B3B4產(chǎn)量A14

（0）2(1)6A22(5)5(4)7A32(3)3(2)5銷

量4275調運方案4表10表中奇數(shù)序號有效數(shù)字的“最小值”為2，“最小值”出現(xiàn)在三個奇數(shù)序號(1),(3),(5)上方案B1B2B3B4產(chǎn)量A1426A2077A3055銷

量4275調運方案5表11有效數(shù)字0有效數(shù)字0方案B1B2B3B4產(chǎn)量A14(2)3(1)7A230(3)(0)3A3639銷

量3646調運方案6表12表中奇數(shù)序號為(3)的有效數(shù)字為0(“最小值”）方案B1B2B3B4產(chǎn)量A1437A2303A3639銷

量3646調運方案7表13新入基的變量x24值為有效數(shù)字0。產(chǎn)銷不平衡問題轉運問題化肥供應問題：設由三個化肥場供應四個地區(qū)的農(nóng)用化肥，假定等量的化肥在這些地區(qū)使用效果相同。已知各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各各地區(qū)的單位運價表，試決定使得總運費最省的化肥調