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

1、2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,1,第三章 運(yùn)輸問(wèn)題,3.1 運(yùn)輸問(wèn)題及其數(shù)學(xué)模型 3.2 表上作業(yè)法 3.3 運(yùn)輸問(wèn)題的進(jìn)一步討論,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,2,本章學(xué)習(xí)要求,掌握表上作業(yè)法及其在產(chǎn)銷平衡運(yùn)輸問(wèn)題求解中的應(yīng)用 掌握產(chǎn)銷不平衡運(yùn)輸問(wèn)題的求解方法,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,3,3.1 運(yùn)輸問(wèn)題及其數(shù)學(xué)模型,1.運(yùn)輸問(wèn)題的一般提法：假設(shè)有m個(gè)生產(chǎn)地點(diǎn)，可以供應(yīng)某種物資（以后稱為產(chǎn)地），用Ai來(lái)表示，i=1,m,有n個(gè)銷地，用Bj來(lái)表示，j=1,n，產(chǎn)地的產(chǎn)量和銷地的銷量分別為ai,bj，從產(chǎn)地Ai到銷地Bj運(yùn)輸

2、一個(gè)單位物資的運(yùn)價(jià)為Cij，這些數(shù)據(jù)可匯總于下表，在假設(shè)產(chǎn)銷平衡的條件下，即ai= bj，問(wèn)該如何調(diào)運(yùn)物品使總運(yùn)費(fèi)最小？,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,4,建模：設(shè)xij表示從Ai到Bj的運(yùn)量，則所求的數(shù)學(xué)模型為：,min =cijxij,s.t. xij=ai i=1,m,xij=bj j=1,n,j=1,n,i=1,m,i=1,m,j=1,n,xij0 i=1,m,j=1,n,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,5,2.例如：三個(gè)產(chǎn)地四個(gè)銷地，用網(wǎng)絡(luò)表示,產(chǎn)地,運(yùn)價(jià),銷地,產(chǎn)量,銷量,總產(chǎn)量60噸,總銷量60噸,產(chǎn)銷平衡的運(yùn)輸問(wèn)題,2020/9/18,

3、浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,6,運(yùn)輸問(wèn)題線性規(guī)劃模型,產(chǎn)地約束,銷地約束,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,7,運(yùn)輸問(wèn)題的表格表示,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,8,注意： 運(yùn)輸問(wèn)題有可行解的充要條件為： 平衡運(yùn)輸問(wèn)題有最優(yōu)解 平衡運(yùn)輸問(wèn)題的約束方程組的系數(shù)矩陣的系數(shù)矩陣A的秩為m+n-1 運(yùn)輸問(wèn)題的求解過(guò)程與單純形法類似，只是更簡(jiǎn)單，通常稱表上作業(yè)法，而且是求解極小化問(wèn)題。 運(yùn)輸問(wèn)題的系數(shù)矩陣具有什么特點(diǎn)？ 運(yùn)輸問(wèn)題的LD是怎樣的？,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,9,3.2 表上作業(yè)法,初始基可行解的確定 最優(yōu)性檢驗(yàn) 基變換,

4、2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,10,運(yùn)輸問(wèn)題基的表示,m個(gè)產(chǎn)地、n個(gè)銷地的運(yùn)輸問(wèn)題，除了滿足可行的條件外，任何一個(gè)基要滿足以下條件： 基變量的個(gè)數(shù)為m+n-1； 基變量不能形成閉回路；,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,11,基在運(yùn)輸表中的表示,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,12,運(yùn)輸表中同行同列組成回路的變量,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,13,一. 初始基可行解的確定,西北角法 最小元素法 沃格爾法,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,14,1.西北角法,8,13,13,14,6,6,方法：

5、優(yōu)先滿足運(yùn)輸表中左上角空格的供銷要求填一個(gè)數(shù)字只能劃去一行或一列,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,15,2.最小元素法,12,0,15,13,0,1,13,0,2,19,3,0,1,2,0,2,0,0,方法：按單位運(yùn)價(jià)的大小，決定供應(yīng)的先后，優(yōu)先滿足單位運(yùn)價(jià)最小者的供銷要求（就近供應(yīng)）,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,16,3.沃格爾法,3,2,12,3,2,3,3,1,1,*,3,1,13,行罰數(shù),列罰數(shù),4,1,4,*,13,*,1,2,19,方法：計(jì)算出每一行及每一列中單位運(yùn)價(jià)最小和次小的兩個(gè)元素之間的差值，再?gòu)牟钪底畲蟮男谢蛄兄姓页鰡挝贿\(yùn)價(jià)最小者

6、，優(yōu)先滿足其供銷關(guān)系。,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,17,二. 最優(yōu)性檢驗(yàn)求非基變量的檢驗(yàn)數(shù),閉回路法 位勢(shì)法,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,18,1.閉回路法,方法 求非基變量檢驗(yàn)數(shù)ij,以該變量所在格為頂點(diǎn)，其他頂點(diǎn)為基變量找一個(gè)閉回路，從該非基變量頂點(diǎn)為“”，“”，“”，“”依次加減其運(yùn)價(jià)，即為檢驗(yàn)數(shù)。 意義： 以該非基變量充當(dāng)基變量時(shí)單位運(yùn)量運(yùn)費(fèi)的損失。當(dāng)所有的ij0，則已得運(yùn)輸問(wèn)題的最優(yōu)解。即單位物品由i-j引起總運(yùn)費(fèi)的變化。,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,19,8,13,13,14,6,6,1.閉回路法(1),12

7、 =c12-c22+c21-c11=7-4+8-6=5,5,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,20,8,13,13,14,6,6,1.閉回路法(2),5,13 =c13-c23+c21-c11=5-2+8-6=5,5,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,21,8,13,13,14,6,6,1. 閉回路法(3),5,5,14 =(c14-c34+ c33 - c23 + c21 -c11)=3-6+10-2+8-6=7,7,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,22,8,13,13,14,6,6,1. 閉回路法(4),5,5,7,12 =c24-c

8、34+ c33-c23=7-6+10-2=9,9,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,23,8,13,13,14,6,6,1. 閉回路法(5),5,5,7,9,32 =c32-c24+ c23-c33=9-4+2-10=-3,-3,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,24,8,13,13,14,6,6,1. 閉回路法(6),5,5,7,9,-3,31 =c31-c21+ c23-c32=5-8+2-10=-11,-11,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,25,2. 位勢(shì)法,該法也稱對(duì)偶變量法，我們知道一般標(biāo)準(zhǔn)運(yùn)輸問(wèn)題的對(duì)偶問(wèn)題為：,Ui,Vj無(wú)

9、約束,由LP中ij 的定義： ij =Cij-CBB-1Pij Cij-YPij=Cij-(u1,u2,um,v1,v2,vn)Pij = cij-(ui+vj),對(duì)基變量而言： cij=(ui+vj) 由m+n-1個(gè)基變量對(duì)應(yīng)m+n-1個(gè)線性方程,而LD的變量有m+n個(gè)，對(duì)偶問(wèn)題有無(wú)窮多解，則可設(shè)其中一個(gè)最優(yōu)解為0，而推導(dǎo)出其他分量。從而求出非基變量的檢驗(yàn)數(shù)。,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,26,8,13,13,14,6,6,2. 位勢(shì)法(1),ui,vj,0,6,2,2,0,10,-4,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,27,8,13,13,14,6

10、,6,2. 位勢(shì)法(2),ui,vj,0,6,2,2,0,10,-4,5,5,7,9,-13,-3,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,28,三. 基變換閉回路法,與單純形法一樣，如果所有非基變量檢驗(yàn)數(shù)ij 0，則該基解為最優(yōu)解，否則不是最優(yōu)解，需要進(jìn)行基變換，換入變量的確定方法一樣，設(shè)換入變量xlk的檢驗(yàn)數(shù)為lk ，換出變量為xsf,以xlk和基變量為頂點(diǎn)找一個(gè)閉回路，分別標(biāo)號(hào)”+”,”-”,”+”,”_”；在標(biāo)號(hào)為”-”的最小的運(yùn)量為調(diào)整量，在閉回路上進(jìn)行調(diào)整，“”的加“-”的減，當(dāng)存在xsf為0時(shí)，為換出變量，得一新的基可行解，再求檢驗(yàn)數(shù)。,2020/9/18,浙江科技學(xué)

11、院經(jīng)濟(jì)管理學(xué)院管工系,29,8,13,13,14,6,6,1.基變換-確定換入換出變量,5,5,7,9,-3,-11,-11,-,-,6,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,30,8,13,13,14,6,6,1.基變換得新的基解,-,-,6,2,12,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,31,13,13,14,1.基變換得新的基解,6,2,12,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,32,確定初始基礎(chǔ)可行解,西北角法,沃格爾法,求非基變量的檢驗(yàn)數(shù),閉回路法,對(duì)偶變量法,確定進(jìn)基變量,確定離基變量,得到新的基礎(chǔ)可行解,表上作業(yè)法總結(jié),沿閉回路調(diào)整運(yùn)

12、量,最小元素法,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,33,單純形法與表上作業(yè)法比較,確定初始基變量XB,+松馳變量+（人工變量） XB系數(shù)矩陣為I，m個(gè) 其余XN,最小元素法、沃格爾法等 XB數(shù)字格，m+n-1個(gè) XN 空格,檢驗(yàn)數(shù),基變量j =0 非基變量j =cj-cBB-1pj,基變量ij=0 非基變量ij =cij-Ui-Vj,調(diào)整,進(jìn)基：minj j 0 出基： minbi/aik，aik0,進(jìn)基：minij ij0 出基： min閉回路上偶數(shù)點(diǎn)xij,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,34,例（P104，3.7）：,該問(wèn)題是一個(gè)產(chǎn)銷平衡問(wèn)題，也是求

13、極小化問(wèn)題，可用表上作業(yè)法求解。,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,35,解：,1.用沃格爾法求初始基可行解,行罰數(shù),列罰數(shù),3,1,2,2,1,1,1,*,5,0,1,2,*,6,2,5,4,*,2,1,5,*,1,3,3,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,36,解：,2.用位勢(shì)法求非基變量檢驗(yàn)數(shù)(求位勢(shì)）,5,6,2,1,3,3,ui,vj,0,1,4,1,0,0,1,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,37,解：,2.用位勢(shì)法求非基變量檢驗(yàn)數(shù)（求檢驗(yàn)數(shù)）,5,6,2,1,3,3,ui,vj,0,1,4,1,0,0,1,3,6,1,1,1

14、,5,由此可知，所有非基變量檢驗(yàn)數(shù)全0，已得最優(yōu)調(diào)運(yùn)方案；總運(yùn)費(fèi)為：51+ 34+ 61+ 20+ 35+ 11=39,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,38,3.3 運(yùn)輸問(wèn)題的進(jìn)一步討論,一、產(chǎn)銷不平衡問(wèn)題 （變成產(chǎn)銷平衡問(wèn)題） 當(dāng)總產(chǎn)量總銷量時(shí)，可增加一個(gè)假想銷地Bn+1, 銷量 ai bj，Ci,n+1=0， 當(dāng)總產(chǎn)量總銷量時(shí)，可增加一個(gè)假想產(chǎn)地Am+1,產(chǎn)量 bj ai ，Cm+1，j=0,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,39,例：某建筑公司有A1、 A2、 A3三個(gè)水泥庫(kù)，其水泥貯存量分別為30噸、 50噸、 60噸，四個(gè)工地B1、 B2、 B3

15、 、 B4需要水泥的數(shù)量依次為15噸、 10噸、 40噸、 45噸，已知從各庫(kù)到各工地運(yùn)送每噸水泥的費(fèi)用如下表，求使運(yùn)費(fèi)最少的調(diào)運(yùn)方案？,解：計(jì)算ai=140，bj =110， aibj（產(chǎn)量銷量）所以要虛構(gòu)一銷地B5，其銷量b5=30，而ci5 =0，這樣，就轉(zhuǎn)化成了一個(gè)產(chǎn)銷平衡問(wèn)題。,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,40,例如：,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,41,二、一些變形和推廣 1、最大化問(wèn)題 1）找出單位物資效益表（cij）中的最大元素M，即M=maxcij 2)令cij =M-cij，并視為運(yùn)價(jià)。 3）由cij構(gòu)成單位運(yùn)價(jià)表，按通常的表上

16、作業(yè)法求解，求得最優(yōu)解后把所得結(jié)果轉(zhuǎn)換為原問(wèn)題的答案。 2、銷量不確定（有最高需求和最低需求） 設(shè)銷地Bk的最低需求為bk，最高需求為bk” ，這時(shí)可把看作Bk和Bk”兩個(gè)銷地， Bk需求量bk ，Bk”的需求量bk” - bk,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,42,例：設(shè)某種材料有A1、 A2、 A3三個(gè)生產(chǎn)廠家，其產(chǎn)品供應(yīng)B1、 B2、 B3 、 B4四個(gè)城市，假定等量的材料在這些城市的使用效果相同，已知各建材廠的年產(chǎn)量、各城市的年需求量以及各廠到各城市運(yùn)送單位建材的運(yùn)價(jià)如表所示，求使運(yùn)費(fèi)最少的調(diào)運(yùn)方案？,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,43,B1,

17、B1,B2,B3,B4,B4,銷量,30,20,70,30,10,50,A1,A2,A3,A4,產(chǎn)量,50,60,50,50,16,14,19,M,16,14,19,0,13,13,20,M,22,19,23,0,17,15,M,M,17,15,M,0,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,44,4、缺貨損失問(wèn)題如下表，設(shè)銷地1不允許缺貨；銷地2缺貨，單位損失費(fèi)3元；銷地3缺貨，單位損失費(fèi)2元，問(wèn)如何處理？,A4,40,M,3,2,3、指定銷售問(wèn)題 如規(guī)定銷地1的需求量必須由產(chǎn)地4供應(yīng)，如何處理？ 1）直接令x41=b1 2)令c41=-M，或者c11=c21=c31=M這樣銷地

18、1的需求量肯定是由產(chǎn)地1供應(yīng)了。,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,45,三、生產(chǎn)與存儲(chǔ)問(wèn)題,例：某廠按合同須于當(dāng)年每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的起重機(jī)，已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)起重機(jī)的成本如表所示，若生產(chǎn)出來(lái)的起重機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度工廠需支付保管及維護(hù)費(fèi)0.15萬(wàn)元，試問(wèn)在按合同完成任務(wù)的情況下，工廠應(yīng)如何安排生產(chǎn)計(jì)劃才能使全年消耗的生產(chǎn)與存貯費(fèi)用的總和最少？,2020/9/18,浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系,46,發(fā)貨點(diǎn)：生產(chǎn)起重機(jī)的四個(gè)季度發(fā)貨量：生產(chǎn)能力收貨點(diǎn)：按合同交付起重機(jī)的四個(gè)季度收貨量：按合同提供起重機(jī)的數(shù)量cij=第i季度每臺(tái)起重機(jī)的生產(chǎn)成本+（j-i）個(gè)季度每臺(tái)起重機(jī)的存貯費(fèi)（ji）,30,10.80,10.95,11.10,