第三章(運輸問題)

第三章運輸問題3.1運輸問題及其數(shù)學模型

3.2表上作業(yè)法3.3運輸問題的進一步討論2/6/20231浙江科技學院經(jīng)濟管理學院管工系本章學習要求掌握表上作業(yè)法及其在產(chǎn)銷平衡運輸問題求解中的應用掌握產(chǎn)銷不平衡運輸問題的求解方法2/6/20232浙江科技學院經(jīng)濟管理學院管工系3.1運輸問題及其數(shù)學模型1.運輸問題的一般提法：假設有m個生產(chǎn)地點，可以供應某種物資（以后稱為產(chǎn)地），用Ai來表示，i=1,…,m,有n個銷地，用Bj來表示，j=1,…,n，產(chǎn)地的產(chǎn)量和銷地的銷量分別為ai,bj，從產(chǎn)地Ai到銷地Bj運輸一個單位物資的運價為Cij，這些數(shù)據(jù)可匯總于下表，在假設產(chǎn)銷平衡的條件下，即∑ai=∑bj，問該如何調(diào)運物品使總運費最小？B1B2…Bn產(chǎn)量A1C11C12…C1na1A2C21C22…C2na2………………AmCm1Cm2…Cmnam銷量b1b2…bn2/6/20233浙江科技學院經(jīng)濟管理學院管工系建模：設xij表示從Ai到Bj的運量，則所求的數(shù)學模型為：minΖ=ΣΣcijxij

s.t.Σxij=aii=1,…mΣxij=bjj=1,…,nj=1ni=1mi=1mj=1nxij≥0i=1,…m,j=1,…,n2/6/20234浙江科技學院經(jīng)濟管理學院管工系2.例如：三個產(chǎn)地四個銷地，用網(wǎng)絡表示2312341b1=22b2=13b3=12b4=13a2=27a3=19a1=14產(chǎn)地運價銷地6753482759106產(chǎn)量銷量總產(chǎn)量60噸總銷量60噸產(chǎn)銷平衡的運輸問題2/6/20235浙江科技學院經(jīng)濟管理學院管工系運輸問題線性規(guī)劃模型產(chǎn)地約束銷地約束2/6/20236浙江科技學院經(jīng)濟管理學院管工系運輸問題的表格表示2/6/20237浙江科技學院經(jīng)濟管理學院管工系注意：運輸問題有可行解的充要條件為：平衡運輸問題有最優(yōu)解平衡運輸問題的約束方程組的系數(shù)矩陣的系數(shù)矩陣A的秩為m+n-1運輸問題的求解過程與單純形法類似，只是更簡單，通常稱表上作業(yè)法，而且是求解極小化問題。運輸問題的系數(shù)矩陣具有什么特點？運輸問題的LD是怎樣的？2/6/20238浙江科技學院經(jīng)濟管理學院管工系3.2表上作業(yè)法初始基可行解的確定最優(yōu)性檢驗基變換2/6/20239浙江科技學院經(jīng)濟管理學院管工系運輸問題基的表示

m個產(chǎn)地、n個銷地的運輸問題，除了滿足可行的條件外，任何一個基要滿足以下條件：基變量的個數(shù)為m+n-1；基變量不能形成閉回路；2/6/202310浙江科技學院經(jīng)濟管理學院管工系123412312341231234123123412312341231234123基在運輸表中的表示2/6/202311浙江科技學院經(jīng)濟管理學院管工系123412312341231234123123412312341231234123運輸表中同行同列組成回路的變量2/6/202312浙江科技學院經(jīng)濟管理學院管工系一.初始基可行解的確定西北角法最小元素法沃格爾法2/6/202313浙江科技學院經(jīng)濟管理學院管工系1.西北角法813131466方法：優(yōu)先滿足運輸表中左上角空格的供銷要求－填一個數(shù)字只能劃去一行或一列2/6/202314浙江科技學院經(jīng)濟管理學院管工系2.最小元素法12015130113021930120200方法：按單位運價的大小，決定供應的先后，優(yōu)先滿足單位運價最小者的供銷要求（就近供應）2/6/202315浙江科技學院經(jīng)濟管理學院管工系3.沃格爾法3212323311*3113行罰數(shù)列罰數(shù)414*13*1219方法：計算出每一行及每一列中單位運價最小和次小的兩個元素之間的差值，再從差值最大的行或列中找出單位運價最小者，優(yōu)先滿足其供銷關系。2/6/202316浙江科技學院經(jīng)濟管理學院管工系二.最優(yōu)性檢驗－求非基變量的檢驗數(shù)閉回路法位勢法2/6/202317浙江科技學院經(jīng)濟管理學院管工系1.閉回路法方法求非基變量檢驗數(shù)σij,以該變量所在格為頂點，其他頂點為基變量找一個閉回路，從該非基變量頂點為“＋”，“－”，“＋”，“－”依次加減其運價，即為檢驗數(shù)。意義：以該非基變量充當基變量時單位運量運費的損失。當所有的σij≥0，則已得運輸問題的最優(yōu)解。即單位物品由i-j引起總運費的變化。2/6/202318浙江科技學院經(jīng)濟管理學院管工系8131314661.閉回路法(1)σ12

=c12-c22+c21-c11=7-4+8-6=552/6/202319浙江科技學院經(jīng)濟管理學院管工系8131314661.閉回路法(2)5σ13

=c13-c23+c21-c11=5-2+8-6=552/6/202320浙江科技學院經(jīng)濟管理學院管工系8131314661.閉回路法(3)55σ14

=(c14-c34+c33-c23+c21-c11)=3-6+10-2+8-6=772/6/202321浙江科技學院經(jīng)濟管理學院管工系8131314661.閉回路法(4)557σ12

=c24-c34+c33-c23=7-6+10-2=992/6/202322浙江科技學院經(jīng)濟管理學院管工系8131314661.閉回路法(5)5579σ32

=c32-c24+c23-c33=9-4+2-10=-3-32/6/202323浙江科技學院經(jīng)濟管理學院管工系8131314661.閉回路法(6)5579-3σ31

=c31-c21+c23-c32=5-8+2-10=-11-112/6/202324浙江科技學院經(jīng)濟管理學院管工系2.位勢法該法也稱對偶變量法，我們知道一般標準運輸問題的對偶問題為：Ui,Vj無約束由LP中σij的定義：

σij

=Cij-CBB-1Pij＝Cij-Y’Pij=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，而推導出其他分量。從而求出非基變量的檢驗數(shù)。2/6/202325浙江科技學院經(jīng)濟管理學院管工系8131314662.位勢法(1)uivj0622010-42/6/202326浙江科技學院經(jīng)濟管理學院管工系8131314662.位勢法(2)uivj0622010-45579-13-32/6/202327浙江科技學院經(jīng)濟管理學院管工系三.基變換－閉回路法與單純形法一樣，如果所有非基變量檢驗數(shù)σij≥0，則該基解為最優(yōu)解，否則不是最優(yōu)解，需要進行基變換，換入變量的確定方法一樣，設換入變量xlk的檢驗數(shù)為σlk

，換出變量為xsf

以xlk和基變量為頂點找一個閉回路，分別標號”+”,”-”,”+”,”_”；在標號為”-”的最小的運量為調(diào)整量，在閉回路上進行調(diào)整，“＋”的加“-”的減，當存在xsf為0時，為換出變量，得一新的基可行解，再求檢驗數(shù)。2/6/202328浙江科技學院經(jīng)濟管理學院管工系8131314661.基變換-確定換入換出變量5579-3-11-11＋-＋-62/6/202329浙江科技學院經(jīng)濟管理學院管工系8131314661.基變換－得新的基解＋-＋-62122/6/202330浙江科技學院經(jīng)濟管理學院管工系1313141.基變換－得新的基解62122/6/202331浙江科技學院經(jīng)濟管理學院管工系確定初始基礎可行解西北角法沃格爾法求非基變量的檢驗數(shù)閉回路法對偶變量法確定進基變量確定離基變量得到新的基礎可行解表上作業(yè)法總結沿閉回路調(diào)整運量最小元素法2/6/202332浙江科技學院經(jīng)濟管理學院管工系單純形法與表上作業(yè)法比較單純形法（Min）表上作業(yè)法確定初始基變量XB+松馳變量+（人工變量）XB——系數(shù)矩陣為I，m個其余XN最小元素法、沃格爾法等XB——數(shù)字格，m+n-1個XN——空格檢驗數(shù)基變量j=0非基變量j=cj-cBB-1pj基變量ij=0非基變量ij=cij-Ui-Vj調(diào)整進基：min{j∣j<0}出基：θ＝min{bi/aik，aik＞0}進基：min{ij∣ij<0}出基：θ＝min{閉回路上偶數(shù)點xij}2/6/202333浙江科技學院經(jīng)濟管理學院管工系例（P104，3.7）：該問題是一個產(chǎn)銷平衡問題，也是求極小化問題，可用表上作業(yè)法求解。2/6/202334浙江科技學院經(jīng)濟管理學院管工系解：1.用沃格爾法求初始基可行解行罰數(shù)列罰數(shù)3122111*5012*6254*215*1332/6/202335浙江科技學院經(jīng)濟管理學院管工系解：2.用位勢法求非基變量檢驗數(shù)(求位勢）562133uivj01410012/6/202336浙江科技學院經(jīng)濟管理學院管工系解：2.用位勢法求非基變量檢驗數(shù)（求檢驗數(shù)）562133uivj0141001361115由此可知，所有非基變量檢驗數(shù)全≥0，已得最優(yōu)調(diào)運方案；總運費為：5×1+3×4+6×1+2×0+3×5+1×1=392/6/202337浙江科技學院經(jīng)濟管理學院管工系3.3運輸問題的進一步討論一、產(chǎn)銷不平衡問題（變成產(chǎn)銷平衡問題）當總產(chǎn)量>總銷量時，可增加一個假想銷地Bn+1,銷量＝∑ai－∑bj，Ci,n+1=0，當總產(chǎn)量<總銷量時，可增加一個假想產(chǎn)地Am+1,產(chǎn)量＝∑bj

－∑ai

，Cm+1，j=02/6/202338浙江科技學院經(jīng)濟管理學院管工系例：某建筑公司有A1、A2、A3三個水泥庫，其水泥貯存量分別為30噸、50噸、60噸，四個工地B1、B2、B3、B4需要水泥的數(shù)量依次為15噸、10噸、40噸、45噸，已知從各庫到各工地運送每噸水泥的費用如下表，求使運費最少的調(diào)運方案？B1B2B3B4產(chǎn)量27040806050A310030502060銷量15104045140110解：計算∑ai=140，∑bj=110，∑ai>∑bj（產(chǎn)量>銷量）所以要虛構一銷地B5，其銷量b5=30，而ci5=0，這樣，就轉(zhuǎn)化成了一個產(chǎn)銷平衡問題。

B1B2B3B4B5產(chǎn)量A130508040030A270408060050A3100305020060銷量15104045301401402/6/202339浙江科技學院經(jīng)濟管理學院管工系例如：B1B2B3B4產(chǎn)量A13113109A219284A3741057銷6/202340浙江科技學院經(jīng)濟管理學院管工系二、一些變形和推廣1、最大化問題1）找出單位物資效益表（cij）中的最大元素M，即M=max{cij}2)令c’ij=M-cij，并視為運價。3）由c’ij構成單位運價表，按通常的表上作業(yè)法求解，求得最優(yōu)解后把所得結果轉(zhuǎn)換為原問題的答案。2、銷量不確定（有最高需求和最低需求）設銷地Bk的最低需求為bk’，最高需求為bk”，這時可把看作Bk’和Bk”兩個銷地，Bk’需求量bk’，Bk”的需求量bk”-bk’2/6/202341浙江科技學院經(jīng)濟管理學院管工系例：設某種材料有A1、A2、A3三個生產(chǎn)廠家，其產(chǎn)品供應B1、B2、B3、B4四個城市，假定等量的材料在這些城市的使用效果相同，已知各建材廠的年產(chǎn)量、各城市的年需求量以及各廠到各城市運送單位建材的運價如表所示，求使運費最少的調(diào)運方案？B1B2B3B4產(chǎn)量A11613221750A21413191560A3192023M50最低需求3070010最高需求507030不限2/6/202342浙江科技學院經(jīng)濟管理學院管工系B1B2B3B4產(chǎn)量A11613221750A21413191560A3192023M50最低需求3070010最高需求507030不限B1’B1’’B2B3B4’B4’’銷量302070301050A1A2A3A4產(chǎn)量50605050161419M1614190131320M22192301715MM1715M02/6/202343浙江科技學院經(jīng)濟管理學院管工系4、缺貨損失問題

如下表，設銷地1不允許缺貨；銷地2缺貨，單位損失費3元；銷地3缺貨，單位損失費2元，問如何處理？B1B2B3產(chǎn)量A151710A264680A332515銷量655525B1B2B3產(chǎn)量A151710A264680A332515銷量655525A440M323、指定銷售問題如規(guī)定銷地1的需求量必須由產(chǎn)地4供應，如何處理？1）直接令x41=b12)令c41=-M，或者c11=c21=c31=M這樣銷地1的需求量肯定是由產(chǎn)地1供應了。2/6/202344浙江科技學院經(jīng)濟管理學院管工系三、生產(chǎn)與存儲問題例：某廠按合同須于當年每個季度末分別提供10、15、25、20臺同一規(guī)格的起重機，已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺起重機的成本如表所示，若生產(chǎn)出來的起重機當季不交貨，每臺每積壓一個季度工廠需支付保管及維護費0.15萬元，試問在按合同完成任務的情況下，工廠應如何安排生產(chǎn)計劃才能使全年消耗的生產(chǎn)與存貯費用的總和最少？季度工廠生產(chǎn)能力（臺/季）成本（萬元/臺）交貨量（臺）12510.81023511.101533011.002541011.30202/6/202345浙江科技學院經(jīng)濟管理學院管工系發(fā)貨點：生產(chǎn)起重機的四個季度

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

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

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

cij=第i季度每臺起重機的生產(chǎn)成本+（j-i）個季度每臺起重機的存貯費（j>i）12345發(fā)量（臺）125235330410收量（臺）101525203010.8010.9511.1011.25