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

第三章運(yùn)輸問(wèn)題3.1運(yùn)輸問(wèn)題及其數(shù)學(xué)模型

3.2表上作業(yè)法3.3運(yùn)輸問(wèn)題的進(jìn)一步討論2/6/20231浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系本章學(xué)習(xí)要求掌握表上作業(yè)法及其在產(chǎn)銷平衡運(yùn)輸問(wèn)題求解中的應(yīng)用掌握產(chǎn)銷不平衡運(yùn)輸問(wèn)題的求解方法2/6/20232浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系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)輸一個(gè)單位物資的運(yùn)價(jià)為Cij，這些數(shù)據(jù)可匯總于下表，在假設(shè)產(chǎn)銷平衡的條件下，即∑ai=∑bj，問(wèn)該如何調(diào)運(yùn)物品使總運(yùn)費(fèi)最小？B1B2…Bn產(chǎn)量A1C11C12…C1na1A2C21C22…C2na2………………AmCm1Cm2…Cmnam銷量b1b2…bn2/6/20233浙江科技學(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/6/20234浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系2.例如：三個(gè)產(chǎn)地四個(gè)銷地，用網(wǎng)絡(luò)表示2312341b1=22b2=13b3=12b4=13a2=27a3=19a1=14產(chǎn)地運(yùn)價(jià)銷地6753482759106產(chǎn)量銷量總產(chǎn)量60噸總銷量60噸產(chǎn)銷平衡的運(yùn)輸問(wèn)題2/6/20235浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系運(yùn)輸問(wèn)題線性規(guī)劃模型產(chǎn)地約束銷地約束2/6/20236浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系運(yùn)輸問(wèn)題的表格表示2/6/20237浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系注意：運(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是怎樣的？2/6/20238浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系3.2表上作業(yè)法初始基可行解的確定最優(yōu)性檢驗(yàn)基變換2/6/20239浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系運(yùn)輸問(wèn)題基的表示

m個(gè)產(chǎn)地、n個(gè)銷地的運(yùn)輸問(wèn)題，除了滿足可行的條件外，任何一個(gè)基要滿足以下條件：基變量的個(gè)數(shù)為m+n-1；基變量不能形成閉回路；2/6/202310浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系123412312341231234123123412312341231234123基在運(yùn)輸表中的表示2/6/202311浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系123412312341231234123123412312341231234123運(yùn)輸表中同行同列組成回路的變量2/6/202312浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系一.初始基可行解的確定西北角法最小元素法沃格爾法2/6/202313浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系1.西北角法813131466方法：優(yōu)先滿足運(yùn)輸表中左上角空格的供銷要求－填一個(gè)數(shù)字只能劃去一行或一列2/6/202314浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系2.最小元素法12015130113021930120200方法：按單位運(yùn)價(jià)的大小，決定供應(yīng)的先后，優(yōu)先滿足單位運(yùn)價(jià)最小者的供銷要求（就近供應(yīng)）2/6/202315浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系3.沃格爾法3212323311*3113行罰數(shù)列罰數(shù)414*13*1219方法：計(jì)算出每一行及每一列中單位運(yùn)價(jià)最小和次小的兩個(gè)元素之間的差值，再?gòu)牟钪底畲蟮男谢蛄兄姓页鰡挝贿\(yùn)價(jià)最小者，優(yōu)先滿足其供銷關(guān)系。2/6/202316浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系二.最優(yōu)性檢驗(yàn)－求非基變量的檢驗(yàn)數(shù)閉回路法位勢(shì)法2/6/202317浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系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)所有的σij≥0，則已得運(yùn)輸問(wèn)題的最優(yōu)解。即單位物品由i-j引起總運(yùn)費(fèi)的變化。2/6/202318浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314661.閉回路法(1)σ12

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

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

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

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

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

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

σij

=Cij-CBB-1Pij＝Cij-Y’Pij=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ù)。2/6/202325浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314662.位勢(shì)法(1)uivj0622010-42/6/202326浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314662.位勢(shì)法(2)uivj0622010-45579-13-32/6/202327浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系三.基變換－閉回路法與單純形法一樣，如果所有非基變量檢驗(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ù)。2/6/202328浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314661.基變換-確定換入換出變量5579-3-11-11＋-＋-62/6/202329浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系8131314661.基變換－得新的基解＋-＋-62122/6/202330浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系1313141.基變換－得新的基解62122/6/202331浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系確定初始基礎(chǔ)可行解西北角法沃格爾法求非基變量的檢驗(yàn)數(shù)閉回路法對(duì)偶變量法確定進(jìn)基變量確定離基變量得到新的基礎(chǔ)可行解表上作業(yè)法總結(jié)沿閉回路調(diào)整運(yùn)量最小元素法2/6/202332浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系單純形法與表上作業(yè)法比較單純形法（Min）表上作業(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)基：min{j∣j<0}出基：θ＝min{bi/aik，aik＞0}進(jìn)基：min{ij∣ij<0}出基：θ＝min{閉回路上偶數(shù)點(diǎn)xij}2/6/202333浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系例（P104，3.7）：該問(wèn)題是一個(gè)產(chǎn)銷平衡問(wèn)題，也是求極小化問(wèn)題，可用表上作業(yè)法求解。2/6/202334浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系解：1.用沃格爾法求初始基可行解行罰數(shù)列罰數(shù)3122111*5012*6254*215*1332/6/202335浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系解：2.用位勢(shì)法求非基變量檢驗(yàn)數(shù)(求位勢(shì)）562133uivj01410012/6/202336浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系解：2.用位勢(shì)法求非基變量檢驗(yàn)數(shù)（求檢驗(yàn)數(shù)）562133uivj0141001361115由此可知，所有非基變量檢驗(yàn)數(shù)全≥0，已得最優(yōu)調(diào)運(yùn)方案；總運(yùn)費(fèi)為：5×1+3×4+6×1+2×0+3×5+1×1=392/6/202337浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系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=02/6/202338浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系例：某建筑公司有A1、A2、A3三個(gè)水泥庫(kù)，其水泥貯存量分別為30噸、50噸、60噸，四個(gè)工地B1、B2、B3、B4需要水泥的數(shù)量依次為15噸、10噸、40噸、45噸，已知從各庫(kù)到各工地運(yùn)送每噸水泥的費(fèi)用如下表，求使運(yùn)費(fèi)最少的調(diào)運(yùn)方案？B1B2B3B4產(chǎn)量27040806050A310030502060銷量15104045140110解：計(jì)算∑ai=140，∑bj=110，∑ai>∑bj（產(chǎn)量>銷量）所以要虛構(gòu)一銷地B5，其銷量b5=30，而ci5=0，這樣，就轉(zhuǎn)化成了一個(gè)產(chǎn)銷平衡問(wèn)題。

B1B2B3B4B5產(chǎn)量A130508040030A270408060050A3100305020060銷量15104045301401402/6/202339浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系例如：B1B2B3B4產(chǎn)量A13113109A219284A3741057銷6/202340浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系二、一些變形和推廣1、最大化問(wèn)題1）找出單位物資效益表（cij）中的最大元素M，即M=max{cij}2)令c’ij=M-cij，并視為運(yùn)價(jià)。3）由c’ij構(gòu)成單位運(yùn)價(jià)表，按通常的表上作業(yè)法求解，求得最優(yōu)解后把所得結(jié)果轉(zhuǎn)換為原問(wèn)題的答案。2、銷量不確定（有最高需求和最低需求）設(shè)銷地Bk的最低需求為bk’，最高需求為bk”，這時(shí)可把看作Bk’和Bk”兩個(gè)銷地，Bk’需求量bk’，Bk”的需求量bk”-bk’2/6/202341浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系例：設(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)方案？B1B2B3B4產(chǎn)量A11613221750A21413191560A3192023M50最低需求3070010最高需求507030不限2/6/202342浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系B1B2B3B4產(chǎn)量A11613221750A21413191560A3192023M50最低需求3070010最高需求507030不限B1’B1’’B2B3B4’B4’’銷量302070301050A1A2A3A4產(chǎn)量50605050161419M1614190131320M22192301715MM1715M02/6/202343浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系4、缺貨損失問(wèn)題

如下表，設(shè)銷地1不允許缺貨；銷地2缺貨，單位損失費(fèi)3元；銷地3缺貨，單位損失費(fèi)2元，問(wèn)如何處理？B1B2B3產(chǎn)量A151710A264680A332515銷量655525B1B2B3產(chǎn)量A151710A264680A332515銷量655525A440M323、指定銷售問(wèn)題如規(guī)定銷地1的需求量必須由產(chǎn)地4供應(yīng)，如何處理？1）直接令x41=b12)令c41=-M，或者c11=c21=c31=M這樣銷地1的需求量肯定是由產(chǎn)地1供應(yīng)了。2/6/202344浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系三、生產(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)用的總和最少？季度工廠生產(chǎn)能力（臺(tái)/季）成本（萬(wàn)元/臺(tái)）交貨量（臺(tái)）12510.81023511.101533011.002541011.30202/6/202345浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系發(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)（j>i）12345發(fā)量（臺(tái)）125235330410收量（臺(tái)）101525203010.8010.9511.1011.25