管理運(yùn)籌學(xué) 課件 04運(yùn)輸問題

運(yùn)籌學(xué)——

第三章運(yùn)輸問題運(yùn)輸問題的數(shù)學(xué)模型及其應(yīng)用表上作業(yè)法

銷地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059

銷量（噸）3656運(yùn)輸問題的典例：運(yùn)輸問題的典例m個(gè)產(chǎn)地n個(gè)銷地問題及分析運(yùn)輸問題的典例問題及分析15運(yùn)輸問題的典例問題及分析問題建立表格模型哈爾濱大連拉薩產(chǎn)量北京53113上海96132銷量221運(yùn)輸問題表格模型——產(chǎn)銷平衡表12…n產(chǎn)量12…ma1a2…am銷量b1

b2…bn

銷地產(chǎn)地運(yùn)輸問題表格模型——單位運(yùn)價(jià)表12…n12…m

銷地產(chǎn)地C11C12…

C1nC21C22…

C2n…………Cm1Cm2…

Cmn運(yùn)輸問題表格模型12…n產(chǎn)量12…ma1a2…am銷量b1

b2…bn

銷地產(chǎn)地C11C12…

C1nC21C22…

C2n…………Cm1Cm2…

Cmn問題建立表格模型哈爾濱大連拉薩產(chǎn)量北京53113上海96132銷量221求解——表上作業(yè)法

銷地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059

銷量（噸）3656運(yùn)輸問題的典例——求解

銷地運(yùn)價(jià)產(chǎn)地B1B2B3B4A1311310A21928A374105

銷地方案產(chǎn)地B1B2B3B4產(chǎn)量（噸）A17A24A39

銷量（噸）3656運(yùn)輸問題的典例——求解表上作業(yè)法12…n產(chǎn)量12…ma1a2…am銷量b1

b2…bn

銷地產(chǎn)地C11C12…

C1nC21C22…

C2n…………Cm1Cm2…

Cmn產(chǎn)銷不平衡的運(yùn)輸問題建?？偖a(chǎn)量總銷量哈爾濱大連拉薩假想銷地產(chǎn)量北京531103上海961304銷量2311

銷地產(chǎn)地產(chǎn)銷不平衡的運(yùn)輸問題建模總產(chǎn)量>總銷量哈爾濱大連拉薩產(chǎn)量北京53113上海96132假想產(chǎn)地0001銷量231

銷地產(chǎn)地總銷量>總產(chǎn)量產(chǎn)銷不平衡的運(yùn)輸問題建模例2設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的化肥，假設(shè)等量的化肥在各個(gè)地區(qū)的使用效果相同。各廠的產(chǎn)量、各地區(qū)的需要量、單位運(yùn)價(jià)如表所示。求出運(yùn)費(fèi)最省的調(diào)撥方案。產(chǎn)銷不平衡的運(yùn)輸問題建?！N量不確定的情況例2設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的化肥，假設(shè)等量的化肥在各個(gè)地區(qū)的使用效果相同。各廠的產(chǎn)量、各地區(qū)的需要量、單位運(yùn)價(jià)如表所示。求出運(yùn)費(fèi)最省的調(diào)撥方案。產(chǎn)銷不平衡的運(yùn)輸問題建?！N量不確定的情況

銷地運(yùn)費(fèi)單價(jià)產(chǎn)地ⅠⅠ’ⅡⅢⅣⅣ’供應(yīng)量（噸）A1613221750B1413191560C19202350假想產(chǎn)地50需求／萬噸302070301050210解：可建立如下模型：解：求得最優(yōu)方案：50201030302003020例3合同規(guī)定某廠今年每季度末應(yīng)分別提供10、15、25、20臺專用柴油機(jī)。該廠各季度產(chǎn)能及生產(chǎn)成本如下表。產(chǎn)出的柴油機(jī)若當(dāng)季不交貨，每臺積壓一個(gè)季度會產(chǎn)生存儲費(fèi)0.1萬元。要求制定成本費(fèi)用最低的生產(chǎn)計(jì)劃。季度生產(chǎn)能力/臺單位成本/萬元Ⅰ2510.8Ⅱ3511.1Ⅲ3011.0Ⅳ1011.3運(yùn)輸問題的擴(kuò)展應(yīng)用例3合同規(guī)定某廠今年每季度末應(yīng)分別提供10、15、25、20臺專用柴油機(jī)。該廠各季度產(chǎn)能及生產(chǎn)成本如下表。產(chǎn)出的柴油機(jī)若當(dāng)季不交貨，每臺積壓一個(gè)季度會產(chǎn)生存儲費(fèi)0.1萬元。要求制定成本費(fèi)用最低的生產(chǎn)計(jì)劃。運(yùn)輸問題的擴(kuò)展應(yīng)用運(yùn)輸問題的擴(kuò)展應(yīng)用銷售成本生產(chǎn)Ⅰ'Ⅱ'Ⅲ'Ⅳ'虛擬銷地供應(yīng)量（臺）Ⅰ25Ⅱ35Ⅲ30Ⅳ10需求量/臺1015252010070解：建立表格模型8銷售成本生產(chǎn)Ⅰ'Ⅱ'Ⅲ'Ⅳ'虛擬銷地供應(yīng)量（臺）Ⅰ25Ⅱ35Ⅲ30Ⅳ10需求量/艘1015252030解：建立表格模型銷售成本生產(chǎn)Ⅰ'Ⅱ'Ⅲ'Ⅳ'虛擬銷地供應(yīng)量（臺）Ⅰ10.810.911.011.1025ⅡM11.111.211.3035ⅢMM11.011.1030ⅣMMM11.3010需求量/臺1015252030解：建立表格模型問題求解——表上作業(yè)法運(yùn)輸問題的典例四季度三季度二季度一季度例4：運(yùn)輸問題的擴(kuò)展應(yīng)用運(yùn)輸問題生產(chǎn)計(jì)劃

資金管理

人員分配

資源優(yōu)化使用問題建立表格模型哈爾濱大連拉薩產(chǎn)量北京53113上海96132銷量221求解——表上作業(yè)法運(yùn)輸問題的典例

銷地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059

銷量（噸）36563.2.1確定初始調(diào)運(yùn)方案1.最小元素法：從單位運(yùn)價(jià)表上最小的開始確定供銷關(guān)系，直到給出全部答案。例1：已知運(yùn)輸問題的單位運(yùn)價(jià)表和產(chǎn)銷平衡表如下，用

最小元素法求初始方案。3.2表上作業(yè)法最小元素法

求初始方案

銷地運(yùn)價(jià)產(chǎn)地B1B2B3B4A1311310A21928A374105

銷地方案產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1437A2314A3639

銷量（噸）3656最小元素法中解的退化情況

銷地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4A1311310A23948A312105

銷地方案產(chǎn)地B1B2B3B4產(chǎn)量（噸）A17A24A39

銷量（噸）3656最小元素法習(xí)題：例：已知運(yùn)輸問題的單位運(yùn)價(jià)表和產(chǎn)銷平衡表如下，用

最小元素法求初始方案。解：由單位運(yùn)價(jià)表，在產(chǎn)銷平

衡表上計(jì)算初始方案：解：由單位運(yùn)價(jià)表，在產(chǎn)銷平

衡表上計(jì)算初始方案：

銷地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059

銷量（噸）36563.2.1確定初始調(diào)運(yùn)方案1.最小元素法：從單位運(yùn)價(jià)表上最小的開始確定供銷關(guān)系，直到給出全部答案。例1：已知運(yùn)輸問題的單位運(yùn)價(jià)表和產(chǎn)銷平衡表如下，用

最小元素法求初始方案。3.2表上作業(yè)法

銷地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059

銷量（噸）3656例1：已知運(yùn)輸問題的單位運(yùn)價(jià)表和產(chǎn)銷平衡表如下，用Vogel法求初始方案。2.Vogel法求初始調(diào)運(yùn)方案解：

銷地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4A1311310A21928A374105

銷地方案產(chǎn)地B1B2B3B4產(chǎn)量（噸）A17A24A39

銷量（噸）3656

銷地方案產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1527A2314A3639

銷量（噸）3656

銷地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4A1311310A21928A374105說明：

差值最大，說明方案使總的運(yùn)

費(fèi)減少的多。

Vogel法求得方案就是最優(yōu)解或

離最優(yōu)解更近。③最后一步直接選擇最小運(yùn)費(fèi)。解：最小元素法與Vogel法比較

銷地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4A1311310A21928A374105最小元素法求得的初始方案Vogel法求得的初始方案Vogel法習(xí)題：例：已知運(yùn)輸問題的單位運(yùn)價(jià)表和產(chǎn)銷平衡表如下，用

Vogel法求初始方案。解：由單位運(yùn)價(jià)表，在產(chǎn)銷平

衡表上計(jì)算初始方案：3.2.2最優(yōu)解的判別與方案調(diào)整1、計(jì)算檢驗(yàn)數(shù)——閉回路法通過最優(yōu)性檢驗(yàn)判別目標(biāo)函數(shù)值是否最優(yōu)，為否時(shí)應(yīng)進(jìn)行調(diào)整優(yōu)化。方案中由一個(gè)空格和若干個(gè)有數(shù)字格的水平和垂直連線包圍成的封閉回路稱為閉回路。

銷地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059

銷量（噸）3656例：已知運(yùn)輸問題的單位運(yùn)價(jià)表和產(chǎn)銷平衡表如下:已用最小元素法求得初始方案如下：

銷地方案產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1437A2314A3639

銷量（噸）3656已用最小元素法求得初始方案如下：

銷地運(yùn)價(jià)產(chǎn)地B1B2B3B4A1311310A21928A374105

銷地方案產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1437A2314A3639

銷量（噸）3656用閉回路法求該方案的檢驗(yàn)數(shù)。即：檢驗(yàn)數(shù)表為方案銷地及檢驗(yàn)數(shù)產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1（1）（2）437A23（1）1（-1）4A3（10）6（12）39

銷量（噸）3656若所有的檢驗(yàn)數(shù)均非負(fù)，表明對調(diào)動(dòng)方案做出任何改變都不會導(dǎo)致運(yùn)費(fèi)減少，即當(dāng)前方案為最優(yōu)，否則應(yīng)調(diào)整方案。473.2.2最優(yōu)解的判別與方案調(diào)整2.方案調(diào)整——閉回路法

方案銷地及檢驗(yàn)數(shù)產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1（1）（2）437A23（1）1（-1）4A3（10）6（12）39

銷量（噸）3656

從一個(gè)檢驗(yàn)數(shù)為負(fù)數(shù)且最小的空格出發(fā)，在閉回路上進(jìn)行運(yùn)量調(diào)整，使選定空格處的運(yùn)量盡可能地增加。

48得調(diào)整后的方案：3.2.2最優(yōu)解的判別與方案調(diào)整2.方案調(diào)整——閉回路法

方案調(diào)整前后總運(yùn)價(jià)比較

銷地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4A1311310A21928A374105最小元素法求得的初始方案調(diào)整后的方案50重新計(jì)算檢驗(yàn)數(shù)（閉回路法）3.2.2最優(yōu)解的判別與方案調(diào)整

銷地運(yùn)價(jià)產(chǎn)地B1B2B3B4A1311310A21928A374105513.2.2最優(yōu)解的判別與方案調(diào)整注意：（1）多個(gè)最優(yōu)解：如上例，最優(yōu)解及檢驗(yàn)數(shù)表為：523.2.2最優(yōu)解的判別與方案調(diào)整注意：（1）多個(gè)最優(yōu)解：如上例，規(guī)劃求解工具求得結(jié)果：533.2.2最優(yōu)解的判別與方案調(diào)整注意：（2）特殊的閉回路習(xí)題：例：已知運(yùn)輸問題的單位運(yùn)價(jià)表和產(chǎn)銷平衡表如下：已用最小元素法求出初始方案：計(jì)算該方案的檢驗(yàn)數(shù)，如果不是最優(yōu)方案，對方案進(jìn)行調(diào)整并求出最優(yōu)解。解：用閉回路法在初始方案表上計(jì)算檢驗(yàn)數(shù)：解：用閉回路法在初始方案表上計(jì)算檢驗(yàn)數(shù)：調(diào)整，得方案2解：用閉回路法在初始方案表上計(jì)算檢驗(yàn)數(shù)：調(diào)整，得方案2解：用閉回路法在初始方案表上計(jì)算檢驗(yàn)數(shù)：計(jì)算方案2檢驗(yàn)數(shù)計(jì)算方案2檢驗(yàn)數(shù)調(diào)整方案2得方案3計(jì)算方案3的檢驗(yàn)數(shù)計(jì)算方案3的檢驗(yàn)數(shù)64確定初始方案（最小元素法、Vogel法）（閉回路法、位勢法）求檢驗(yàn)數(shù)找出絕對值最大的負(fù)檢驗(yàn)數(shù)，調(diào)整得到新方案（閉回路法）所有檢驗(yàn)數(shù)≥0得到最優(yōu)方案算出總運(yùn)價(jià)是否表上作業(yè)法的求解過程產(chǎn)銷平衡表單位運(yùn)價(jià)表轉(zhuǎn)運(yùn)問題如果假定：（1）每個(gè)工廠生產(chǎn)的糖果不一定直接發(fā)運(yùn)到銷售點(diǎn)，可以

將其中幾個(gè)產(chǎn)地的糖果集中起來一起運(yùn)。（2）運(yùn)往各銷地的糖果可以先運(yùn)給其中幾個(gè)銷地，再轉(zhuǎn)運(yùn)

給其他銷地。（3）除產(chǎn)地、銷地外，中間還可以有幾個(gè)轉(zhuǎn)運(yùn)站，在產(chǎn)地

之間、銷地之間或產(chǎn)地與銷地之間轉(zhuǎn)運(yùn)。已知各產(chǎn)地、銷地、中間轉(zhuǎn)運(yùn)站之間的單位運(yùn)價(jià)，求如何在各地之間進(jìn)行調(diào)運(yùn)，使總的運(yùn)費(fèi)最小。66轉(zhuǎn)運(yùn)問題表3.33產(chǎn)地、銷地、中間轉(zhuǎn)運(yùn)站間運(yùn)價(jià)表：67轉(zhuǎn)運(yùn)問題單位運(yùn)價(jià)表68轉(zhuǎn)運(yùn)問題建立產(chǎn)銷平衡表：求解——表上作業(yè)法§3.2

運(yùn)輸問題的表上作業(yè)法位勢法——另一種計(jì)算檢驗(yàn)數(shù)的方法

銷地運(yùn)費(fèi)單價(jià)產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059

銷量（噸）3656例：已知運(yùn)輸問題的單位運(yùn)價(jià)表和產(chǎn)銷平衡表如下:已用最小元素法求得初始方案如下：

銷地運(yùn)價(jià)產(chǎn)地B1B2B3B4A1311310A21928A374105

銷地方案產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1437A2314A3639

銷量（噸）3656用位勢法求該方案的檢驗(yàn)數(shù)。

銷地運(yùn)價(jià)產(chǎn)地B1B2B3B4A1311310A2