第三章 運(yùn)輸問題

第三章運(yùn)輸問題3.1運(yùn)輸問題的表示

3.2初始基礎(chǔ)可行解3.3非基變量的檢驗(yàn)數(shù)3.4基解的調(diào)整3.5運(yùn)輸問題的進(jìn)一步討論2/5/20231浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系本章學(xué)習(xí)要求掌握表上作業(yè)法及其在產(chǎn)銷平衡運(yùn)輸問題求解中的應(yīng)用掌握產(chǎn)銷不平衡運(yùn)輸問題的求解方法2/5/20232浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系3.1運(yùn)輸問題的表示網(wǎng)絡(luò)圖表示線性規(guī)劃模型運(yùn)輸表2/5/20233浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系某種物資從兩個供應(yīng)地A1，A2運(yùn)往三個需求地B1，B2，B3。各供應(yīng)地的供應(yīng)量、各需求地的需求量、每個供應(yīng)地到每個需求地每噸物資的運(yùn)輸價格如下表：運(yùn)價（元/噸）B1B2B3供應(yīng)量（噸）A123535A247825需求量（噸）10302060求總運(yùn)費(fèi)最低的運(yùn)輸方案。2/5/20234浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系運(yùn)價（元/噸）B1B2B3供應(yīng)量（噸）A123535A247825需求量（噸）10302060minz=2x11+3x12+5x13+4x21+7x22+8x23s.t.x11+x12+x13=35供應(yīng)地A1x21+x22+x23=25供應(yīng)地A2x11+x21=10需求地B1x12+x22=30需求地B2x13+x23=20需求地B3x11,x12,x13,x21,x22,x23≥02/5/20235浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系運(yùn)輸問題的一般提法：假設(shè)有m個生產(chǎn)地點(diǎn)，可以供應(yīng)某種物資（以后稱為產(chǎn)地），用Ai來表示，i=1,…,m,有n個銷地，用Bj來表示，j=1,…,n，產(chǎn)地的產(chǎn)量和銷地的銷量分別為ai,bj，從產(chǎn)地Ai到銷地Bj運(yùn)輸一個單位物資的運(yùn)價為Cij，這些數(shù)據(jù)可匯總于下表，在假設(shè)產(chǎn)銷平衡的條件下，即∑ai=∑bj，問該如何調(diào)運(yùn)物品使總運(yùn)費(fèi)最?。緽1B2…Bn產(chǎn)量A1C11C12…C1na1A2C21C22…C2na2………………AmCm1Cm2…Cmnam銷量b1b2…bn2/5/20236浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系建模：設(shè)xij表示從Ai到Bj的運(yùn)量，則所求的數(shù)學(xué)模型為：minΖ=ΣΣcijxij

s.t.Σxij=aii=1,…mΣxij=bjj=1,…,nj=1ni=1mi=1mj=1nxij≥0i=1,…m,j=1,…,n2/5/20237浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系1.運(yùn)輸問題的網(wǎng)絡(luò)圖表示2312341d1=22d2=13d3=12d4=13s2=27s3=19s1=14產(chǎn)地運(yùn)價銷地6753482759106產(chǎn)量銷量總產(chǎn)量60噸總銷量60噸產(chǎn)銷平衡的運(yùn)輸問題2/5/20238浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系2.運(yùn)輸問題線性規(guī)劃模型產(chǎn)地約束銷地約束由于前m個產(chǎn)地約束和后n個銷地約束是線性相關(guān)的，因此運(yùn)輸問題系數(shù)矩陣的秩<m+n?？梢宰C明，運(yùn)輸問題系數(shù)矩陣的秩為m+n-1。即運(yùn)輸問題有m+n-1個基變量，mn-(m+n-1)個非基變量。例如以上問題m=3，n=4，基變量為3＋4－1＝6個，非基變量為12－6＝6個。2/5/20239浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系3.運(yùn)輸問題的表格表示2/5/202310浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系3.2初始基可行解運(yùn)輸問題基的表示西北角法最小元素法沃格爾法2/5/202311浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系1.運(yùn)輸問題基的表示m個產(chǎn)地、n個銷地的運(yùn)輸問題，任何一個基要滿足以下三個條件：基變量的個數(shù)為m+n-1；基變量不能形成閉回路；2/5/202312浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系123412312341231234123123412312341231234123基在運(yùn)輸表中的表示2/5/202313浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系2.初始基礎(chǔ)可行解—西北角法813131466方法：優(yōu)先滿足運(yùn)輸表中左上角空格的供銷要求－填一個數(shù)字只能劃去一行或一列2/5/202314浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系3.初始基礎(chǔ)可行解—最小元素法12015130113021930120200方法：按單位運(yùn)價的大小，決定供應(yīng)的先后，優(yōu)先滿足單位運(yùn)價最小者的供銷要求（就近供應(yīng)）2/5/202315浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系4.初始基礎(chǔ)可行解—沃格爾法3212323311*3113行罰數(shù)列罰數(shù)414*13*1219方法：計算出每一行及每一列中單位運(yùn)價最小和次小的兩個元素之間的差值，再從差值最大的行或列中找出單位運(yùn)價最小者，優(yōu)先滿足其供銷關(guān)系。2/5/202316浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系3.3非基變量的檢驗(yàn)數(shù)閉回路法位勢法2/5/202317浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系1.非基變量檢驗(yàn)數(shù)—閉回路法(1)方法求非基變量檢驗(yàn)數(shù)σij,以該變量為定點(diǎn)，其他頂點(diǎn)為基變量找一個閉回路，從該非基變量定點(diǎn)為“＋”，“－”，“＋”，“－”依次加減其運(yùn)價，即為檢驗(yàn)數(shù)。意義：以該非基變量充當(dāng)基變量時單位運(yùn)量運(yùn)費(fèi)的損失。當(dāng)所有的σij≥0，則已得運(yùn)輸問題的最有解。即單位物品由i-j引起總運(yùn)費(fèi)的變化。2/5/202318浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314661.非基變量檢驗(yàn)數(shù)—閉回路法(1)σ12

=c12-c22+c21-c11=7-4+8-6=552/5/202319浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314661.非基變量檢驗(yàn)數(shù)—閉回路法(2)5σ13

=c13-c23+c21-c11=5-2+8-6=552/5/202320浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314661.非基變量檢驗(yàn)數(shù)—閉回路法(3)55σ14

=(c14-c34+c33-c23+c21-c11)=3-6+10-2+8-6=772/5/202321浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314661.非基變量檢驗(yàn)數(shù)—閉回路法(4)557σ12

=c24-c34+c33-c23=7-6+10-2=992/5/202322浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314661.非基變量檢驗(yàn)數(shù)—閉回路法(5)5579σ32

=c32-c24+c23-c33=9-4+2-10=-3-32/5/202323浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314661.非基變量檢驗(yàn)數(shù)—閉回路法(6)5579-3σ31

=c31-c21+c23-c32=5-8+2-10=-11-112/5/202324浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系2.非基變量檢驗(yàn)數(shù)—位勢法該法也稱對偶變量法，我們知道一般標(biāo)準(zhǔn)運(yùn)輸問題的對偶問題為：Ui,Vj無約束由LP中σij的定義：

σij

=Cij-CBB-1Pij＝Cij-YPij=Cij-(u1,u2,……,um,v1,v2,……,vn)Pij=

cij-(ui+vj)對基變量而言：

cij=(ui+vj)由m+n-1個基變量對應(yīng)m+n-1個線性方程而LD的變量有m+n個，對偶問題有無窮多解，則可設(shè)其中一個最優(yōu)解為0，而推導(dǎo)出其他分量。從而求出非基變量的檢驗(yàn)數(shù)。2/5/202325浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314662.非基變量檢驗(yàn)數(shù)—位勢法(1)uivj0622010-42/5/202326浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314662.非基變量檢驗(yàn)數(shù)—位勢法(2)uivj0622010-45579-13-32/5/202327浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系3.4基解的調(diào)整－閉回路法與單純形法一樣，如果所有非基變量檢驗(yàn)數(shù)σij≥0，則該基解為最優(yōu)解，否則不是最優(yōu)解，需要進(jìn)行基變換，換入變量的確定方法一樣，設(shè)換入變量為σlk

，換出變量為σsf：以xlk和基變量為頂點(diǎn)找一個閉回路，分別標(biāo)號”+”,”-”,”+”,”_”；在標(biāo)號為”-”的最小的運(yùn)量為調(diào)整量，在閉回路上進(jìn)行調(diào)整，“＋”的加，“-”的減，當(dāng)存在xsf為0時，為換出變量，得一新的基可行解，再求檢驗(yàn)數(shù)。2/5/202328浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314661.基變換-確定換入換出變量5579-3-11-11＋-＋-62/5/202329浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314661.基變換－得新的基解＋-＋-62122/5/202330浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系1313141.基變換－得新的基解62122/5/202331浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系確定初始基礎(chǔ)可行解西北角法沃格爾法求非基變量的檢驗(yàn)數(shù)閉回路法對偶變量法確定進(jìn)基變量確定離基變量得到新的基礎(chǔ)可行解表上作業(yè)法總結(jié)沿閉回路調(diào)整運(yùn)量最小元素法2/5/202332浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系單純形法與表上作業(yè)法比較單純形法（Min）表上作業(yè)法確定初始基變量XB+松馳變量+（人工變量）XB——系數(shù)矩陣為I，m個其余XN最小元素法、沃格爾法XB——數(shù)字格，m+n-1個XN——空格檢驗(yàn)數(shù)基變量j=0非基變量j=cj-cBB-1pj基變量ij=0非基變量ij=cij-Ui-Vj調(diào)整進(jìn)基：min{j∣j<0}出基：θ＝min{bi/aik，aik＞0}進(jìn)基：min{ij∣ij<0}出基：θ＝min{閉回路上偶數(shù)點(diǎn)xij}2/5/202333浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系3.5運(yùn)輸問題的進(jìn)一步討論一、產(chǎn)銷不平衡的運(yùn)輸問題1）產(chǎn)大于銷，即∑ai>∑bj方法：虛購一銷地Bn+1，其銷量bn+1=∑ai-∑bjAi運(yùn)往Bn+1物資的數(shù)量xin+1，就是產(chǎn)地就地貯存的物資量，因此，產(chǎn)地到虛銷地的單位運(yùn)價均為0，即cin+1=0，這樣，就轉(zhuǎn)化成了一個產(chǎn)銷平衡問題。2/5/202334浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系例：某建筑公司有A1、A2、A3三個水泥庫，其水泥貯存量分別為30噸、50噸、60噸，四個工地B1、B2、B3、B4需要水泥的數(shù)量依次為15噸、10噸、40噸、45噸，已知從各庫到各工地運(yùn)送每噸水泥的費(fèi)用如下表，求使運(yùn)費(fèi)最少的調(diào)運(yùn)方案？B1B2B3B4產(chǎn)量27040806050A310030502060銷量15104045解：計算∑ai=140，∑bj=110，∑ai>∑bj

所以要虛構(gòu)一銷地B4，其銷量b5=30，而ci5=0，這樣，就轉(zhuǎn)化成了一個產(chǎn)銷平衡問題。

2/5/202335浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系2）產(chǎn)小于銷，即∑ai＜∑bj方法：虛購一產(chǎn)地Am+1，其產(chǎn)量Am+1=∑bj-∑aiAm+1運(yùn)往Bj物資的數(shù)量xm+1j，就是各銷地缺貨的物資量，因此，虛產(chǎn)地到各銷地的單位運(yùn)價均為0，即cm+1j=0，這樣，就轉(zhuǎn)化成了一個產(chǎn)銷平衡問題。例如：B1B2B3B4產(chǎn)量A13113109A219284A3741057銷量1361562/5/202336浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系二、一些變形和推廣1、最大化問題作法：1）找出單位物資效益表（cij）中的最大元素M，即M=max{cij}2)令bij=M-cij，并視為運(yùn)價。3）由bij構(gòu)成單位運(yùn)價表，按通常的表上作業(yè)法求解，求得最優(yōu)解后還要把所得結(jié)果轉(zhuǎn)換為原問題的答案。2、銷量不確定（有最高需求和最低需求）設(shè)銷地Bk的最低需求為bk’，最高需求為bk’’，這時可把看作Bk’和Bk’’兩個銷地，Bk’需求量bk’，Bk’’的需求量bk’’-bk’2/5/202337浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系例：設(shè)某種材料有A1、A2、A3三個生產(chǎn)廠家，其產(chǎn)品供應(yīng)B1、B2、B3、B4四個城市，假定等量的材料在這些城市的使用效果相同，已知各建材廠的年產(chǎn)量、各城市的年需求量以及各廠到各城市運(yùn)送單位建材的運(yùn)價如表所示，求使運(yùn)費(fèi)最少的調(diào)運(yùn)方案？B1B2B3B4產(chǎn)量A11613221750A21413191560A3192023M50最低需求3070010最低需求507030不限解釋c34=M（M是一個無窮大的正數(shù)），這意味著不允許從A3運(yùn)貨至B4，或者因?yàn)榻煌ú环奖愕仍?，使從A3到B4不可能送貨。2/5/202338浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系B1B2B3B4產(chǎn)量A11613221750A21413191560A3192023M50最低需求3070010最低需求507030不限B1’B1’’B2B3B4’B4’’銷量302070301050A1A2A3A4產(chǎn)量50605050161419M1614190131320M22192301715MM1715M02/5/202339浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系3、指定銷售問題如規(guī)定銷地1的需求量必須由產(chǎn)地4供應(yīng)，如何處理？1）直接令x41=b12)令c41=-M，或者c11=c21=c31=M這樣銷地1的需求量肯定是由產(chǎn)地1供應(yīng)了。2/5/202340浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系4、缺貨損失問題

如下表，設(shè)銷地1不允許缺貨；銷地2缺貨，單位損失費(fèi)3元；銷地3缺貨，單位損失費(fèi)2元，問如何處理？B1B2B3產(chǎn)量A151710A264680A332515銷量655525B1B2B3產(chǎn)量A151710A264680A332515銷量655525A440M322/5/202341浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系三、生產(chǎn)與存儲問題例：某廠按合同須于當(dāng)年每個季度末分別提供10、15、25、20臺同一規(guī)格的起重機(jī)，已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺起重機(jī)的成本如表所示，若生產(chǎn)出來的起重機(jī)當(dāng)季不交貨，每臺每積壓一個季度工廠需支付保管及維護(hù)費(fèi)0.15萬元，試問在按合同完成任務(wù)的情況下，工廠應(yīng)如何安排生產(chǎn)計劃才能使全年消耗的生產(chǎn)與存貯費(fèi)用的總和最少？季度工廠生產(chǎn)能力（臺/季）成本（萬元/臺）交貨量（臺）12510.81023511.101533011.002541011.30202/5/202342浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系發(fā)貨點(diǎn)：生產(chǎn)起重機(jī)的四個季度

發(fā)貨量：生產(chǎn)能力

收貨點(diǎn)：按合同交付起重機(jī)的四個季度

收貨量：按合同提供起重機(jī)的數(shù)量

cij=第i季度每臺起重機(jī)的生產(chǎn)成本+（j-i）個季度每臺起重機(jī)的存貯費(fèi)（j>i）12345發(fā)量（臺）125235330410收量（臺）101525203010.8010.9511.1011.25M11.1011.2511.40MM11.0011.15MMM11.3000002/5/202343浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系四、有轉(zhuǎn)運(yùn)的運(yùn)輸問題1、運(yùn)輸表的構(gòu)成1）產(chǎn)地：原產(chǎn)地、中間轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)物資的銷地2）銷地：原銷地、中間轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)物資的產(chǎn)地3）設(shè)各轉(zhuǎn)運(yùn)站轉(zhuǎn)運(yùn)物資的數(shù)量均為∑ai這樣專職轉(zhuǎn)運(yùn)站的產(chǎn)量和銷量均為∑ai而原產(chǎn)地Ai的產(chǎn)量均為（ai+∑ai）原銷地Bj的銷量均為（bj+∑ai）4)將各條線路實(shí)際的運(yùn)輸單位列成單位運(yùn)價表，其中不可能的運(yùn)輸其單位運(yùn)價用M表示。2/5/20234