運籌學(xué)課件運輸問題

第三章運輸問題第一節(jié)運輸問題典例及數(shù)學(xué)模型例：三個產(chǎn)地四個銷地的運輸問題示意圖運輸問題的線性規(guī)劃模型需求約束供應(yīng)約束上述模型是根據(jù)上圖的具體問題寫出的。一般運輸問題的模型形式基本類似。當(dāng)產(chǎn)銷平衡時，約束中的不等號可改為等號。運輸問題的線性規(guī)劃模型的系數(shù)矩陣的列向量都是由兩個單位坐標(biāo)向量疊加構(gòu)成。從上例中模型的系數(shù)矩陣A就很容易看出這個特點。產(chǎn)銷平衡運輸問題的表上作業(yè)法步驟:（1）在運價表上用Vogel法求出調(diào)運方案表；（2）在運價表上用位勢法求非基變量的檢驗數(shù)；（3）檢驗方案是否最優(yōu)。是，停止；否，繼續(xù)（4）；（4）在調(diào)運方案表上用閉回路調(diào)整法得到新的調(diào)運方案；（5）重復(fù)（2）。例:某食品公司經(jīng)銷的主要產(chǎn)品之一是糖果。它下面設(shè)有三個加工廠，每天的生產(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法求出調(diào)運方案表B1B2B3B4同行最小兩元素的差產(chǎn)量產(chǎn)地剩余量調(diào)整次序調(diào)整次序123456123456A1311[3][10]0007107777200A2[1]92[8]1116884441110A37[4]10[5]129300000同列最小兩元素的差調(diào)整次序12513Vogel法求初始調(diào)運方案a.求出各行、各列最小兩元素的差值；b.在運價表中找出最小差值對應(yīng)的行或列的最小元的位置，并用“[]”或“○”標(biāo)記；c.畫“[]”元對應(yīng)的產(chǎn)地的產(chǎn)品盡可能多地調(diào)往畫“[]”元對應(yīng)的銷地，并將調(diào)運量填入調(diào)運方案表中的相應(yīng)位置，同時，產(chǎn)或銷地調(diào)運后的剩余量記入本表右上角相應(yīng)位置。d.若該產(chǎn)地的產(chǎn)量被全部調(diào)運完，則該產(chǎn)地在運價表中的行用一條虛線劃去；若該銷地的需求量被全部滿足，則該銷地在運價表中的列用一條虛線劃去；凡是被劃去的行或列不再予以考慮。e.若運價表中所有行和列都被劃去，停止。否則，回到步驟a.。221332124125268銷

量3656銷

地

剩

余

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

量3656方案產(chǎn)地表3：初始調(diào)運方案調(diào)運方案表中出現(xiàn)的數(shù)字被稱為有效數(shù)字，它們分別對應(yīng)此時基變量的值，空格單元的對應(yīng)變量即是此時的非基變量，其值為0。本表中，基變量x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,非基變量x11=x12=x22=x23=x31=x32=0.二、最優(yōu)性檢驗與方案的調(diào)整：(在運價表上用位勢法求非基變量的檢驗數(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ù)字（基變量）對應(yīng)的運價要畫上“[]”。*在u所在列的第一個位置填上u1=0。*然后由等式ui+vj=[cij

]求出所有ui，vj

的值。其中，[cij

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

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

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

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

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

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

量3656調(diào)運方案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)解，須用閉回路調(diào)整法在調(diào)運方案表上進(jìn)行調(diào)運方案的調(diào)整。方案B1B2B3B4產(chǎn)量A14(2)3(1)7A231(3)(0)4A3639銷

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

被換出，x24

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

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

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

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

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

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

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

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

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