第三章 運輸問題

第三章運輸問題3.1運輸問題的表示

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

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

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

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

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

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

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

=c31-c21+c23-c32=5-8+2-10=-11-112/5/202324浙江科技學院經濟管理學院管工系2.非基變量檢驗數—位勢法該法也稱對偶變量法，我們知道一般標準運輸問題的對偶問題為：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個基變量對應m+n-1個線性方程而LD的變量有m+n個，對偶問題有無窮多解，則可設其中一個最優(yōu)解為0，而推導出其他分量。從而求出非基變量的檢驗數。2/5/202325浙江科技學院經濟管理學院管工系8131314662.非基變量檢驗數—位勢法(1)uivj0622010-42/5/202326浙江科技學院經濟管理學院管工系8131314662.非基變量檢驗數—位勢法(2)uivj0622010-45579-13-32/5/202327浙江科技學院經濟管理學院管工系3.4基解的調整－閉回路法與單純形法一樣，如果所有非基變量檢驗數σij≥0，則該基解為最優(yōu)解，否則不是最優(yōu)解，需要進行基變換，換入變量的確定方法一樣，設換入變量為σlk

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

所以要虛構一銷地B4，其銷量b5=30，而ci5=0，這樣，就轉化成了一個產銷平衡問題。

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

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

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

收貨點：按合同交付起重機的四個季度

收貨量：按合同提供起重機的數量

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