運(yùn)輸問(wèn)題新演示文稿

運(yùn)輸問(wèn)題新演示文稿目前一頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)（優(yōu)選）運(yùn)輸問(wèn)題新.目前二頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)運(yùn)輸問(wèn)題數(shù)學(xué)模型例：某公司經(jīng)銷甲產(chǎn)品，下設(shè)3個(gè)加工廠4個(gè)銷售點(diǎn)，其加工廠產(chǎn)量，銷售地銷量以及各工廠到各銷售點(diǎn)單位運(yùn)價(jià)見表，如何調(diào)運(yùn)，總運(yùn)費(fèi)最小206563銷量951047A348291A27103113A1產(chǎn)量B4B3B2B1銷地產(chǎn)地目前三頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)設(shè)Xij為Ai到Bj的銷量Minz=3X11+11X12+3X13

+

10X14+…+7X31+4X32+10X33+

5X34

X11+X12+X13+X14=7←a1X21+X22+X23+X24

=4←a2X31+X32+X33+X34=9←a3該模型又可表示為i=1，2，3j=1，2，3，4Xij≥0，i=1，2，3j=1，2，3，4

X11+X21+X31=3←b1X12+X22+X32=6←b2X13+X23+X33=5←b3X14+X24+X34=9←b4Xij≥0，i=1，2，3；j=1，2，3，4目前四頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)上述問(wèn)題可以擴(kuò)展為m個(gè)產(chǎn)地n個(gè)銷地的運(yùn)輸問(wèn)題，設(shè)ai為Ai產(chǎn)量，bj為Bj銷地銷量，Ai到Bj單位運(yùn)價(jià)Cij，則產(chǎn)銷平衡的運(yùn)輸問(wèn)題其數(shù)學(xué)模型為i=1，2，…,mj=1，2，…nXij≥0，i=1，2，…,mj=1，2，…n目前五頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)模型特點(diǎn)：◆模型有m×n個(gè)變量，m+n個(gè)方程◆對(duì)產(chǎn)銷平衡問(wèn)題∑ai=∑bj◆運(yùn)輸問(wèn)題（產(chǎn)銷平衡）總存在可行解和最優(yōu)解

1、∵cij≥0Xij≥0∴cijXij≥0∴運(yùn)輸問(wèn)題一定有界2、一定有可行解Xij=aibj∑ai3、有界且有可行解，所以一定有最優(yōu)解◆約束方程系數(shù)矩陣具有稀疏結(jié)構(gòu)（見下頁(yè)），秩r（A）=m+n-1

目前六頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)P11P12……P1nP21P22……P2n……Pm1Pm2……Pmn

11……1a111……1a2

:11……1am11……1b111……1b2

……:

11……1bmm行n行

0

0

0

:

::

110Pij=

:=:+:

101

:

:

:

000第i個(gè)分量第m+j個(gè)分量▲系數(shù)矩陣pij除了第i和第m+j個(gè)分量為1外，其余分量全為0▲A的前m行之和減去后n行之和得到的是零向量，即A的行向量線性相關(guān)，其不等于零的子式的最大階數(shù)為m+n-1目前七頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)表上作業(yè)法步驟：1.確定初始基本可行解：有三種方法：①最小元素法②西北角法③伏格爾法2.求非基變量檢驗(yàn)數(shù)，進(jìn)行最優(yōu)解判別，若最優(yōu)，停止，否則進(jìn)行下一步3.確定進(jìn)基、離基變量，找新的基本可行解，返回2，重復(fù)2、3，直到得到最優(yōu)解。目前八頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)最小元素法基本思想：步驟：1.從單位運(yùn)價(jià)表中找最小元素Ckt=min{Cij}2.

根據(jù)Ckt對(duì)應(yīng)的產(chǎn)地產(chǎn)量ak、銷地銷量bt確定調(diào)運(yùn)量調(diào)運(yùn)量Xkt=min{ak，bt

}

，將Xkt填在產(chǎn)銷平衡表第（k，t）格若ak＞

bt，Xkt=bt

，劃去第t列，置ak′=ak-

bt若ak＜bt，Xkt=

ak

，劃去第k行，置bt′=bt-ak

若ak=

bt劃去第k行或第t列，置bt′=0或

ak′=03.從未被劃去元素中再找最小元素，重復(fù)1、2，當(dāng)填入最后一個(gè)元素時(shí)，同時(shí)劃去一行一列。目前九頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)6563銷量951047A348291A27103113A1產(chǎn)量B4B3B2B1

銷地產(chǎn)地B1B2B3B4銷量A17A24A39產(chǎn)量3656314633注意：★最小運(yùn)價(jià)有多個(gè)時(shí)，可任選一個(gè)★保證數(shù)字格數(shù)量為（m+n-1）個(gè)產(chǎn)銷平衡表中填入數(shù)字的格為數(shù)字格，其余格為空格。目前十頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)伏格爾法思路：步驟：1.計(jì)算各行各列最小元素與次最小元素Cij的差，分別填在最右一列和最下面一行2.選差最大的行（或列），根據(jù)該行（列）最小元素Cij確定調(diào)運(yùn)量目前十一頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)B1B2B3B4A1A2A3銷量產(chǎn)量

311310

1928

74105

365674

9列差額011251360123213012123125212

行差額76目前十二頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)最優(yōu)解判別：兩種方法:①閉回路法②位勢(shì)法1.閉回路法：閉回路：互不相同的2k個(gè)變量X11X21X22…………XkkX1k（其下標(biāo)交錯(cuò)相等,在表中表現(xiàn)為相臨的兩個(gè)變量，同行或同列）組成一個(gè)閉回路。X11X12X22X21●●●●●●●●●●●●●●目前十三頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)閉回路求法：在給出調(diào)運(yùn)方案的產(chǎn)銷平衡表上，從某一空格（k，t）格出發(fā)，沿水平或豎直方向前進(jìn)，遇到一個(gè)合適的數(shù)字格轉(zhuǎn)彎90°繼續(xù)前進(jìn)，再遇到一個(gè)合適的數(shù)字格再轉(zhuǎn)彎90°，繼續(xù)前進(jìn)，……，最后又回到原來(lái)的出發(fā)點(diǎn)（k，t）格，稱這樣走過(guò)的一條路線為從（k，t）格出發(fā)的閉回路。注：以空格為起點(diǎn)，以某些數(shù)字格為轉(zhuǎn)折點(diǎn)，最終返回起點(diǎn)，所構(gòu)成的一個(gè)路線稱為閉回路。閉回路是惟一的！每一個(gè)空格點(diǎn)都能構(gòu)成一條閉回路！65639A34A27A1B4B3B2B1311310192874105314633目前十四頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)檢驗(yàn)數(shù)求法：對(duì)從（k，t）格出發(fā)的閉回路各頂點(diǎn)依次編號(hào),（k，t）格為第一頂點(diǎn)，對(duì)所經(jīng)過(guò)的其它各頂點(diǎn)順序編號(hào)，依次為第二、第三頂點(diǎn)，則閉回路上所有奇數(shù)點(diǎn)單位運(yùn)價(jià)之和減偶數(shù)點(diǎn)單位運(yùn)價(jià)之和所得的差，即為（k，t）格的檢驗(yàn)數(shù)kt65639A34A27A1B4B3B2B1311310192874105314633+1-1+1-111=（C11+C23）

-（C13+C21）=（3+2）-（3+1）=1目前十五頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)位勢(shì)法設(shè)Xij為Ai到Bj的運(yùn)量，根據(jù)例1運(yùn)輸問(wèn)題數(shù)學(xué)模型

X11+X12+X13+X14=7←U1X21+X22+X23+X24

=4←U2X31+X32+X33+X34=9←U3

X11+X21+X31=3←V1X12+X22+X32=6←V2X13+X23+X33=5←V3X14+X24+X34=9←V4Xij≥0，i=1，2，3；j=1，2，3，4設(shè)U1，U2，U3

，V1，V2，V3，V4為對(duì)應(yīng)3+4個(gè)約束方程的對(duì)偶變量，則其對(duì)偶問(wèn)題為Max=∑Uiai+∑Vjbj

Ui+Vj≤CijUi，Vj無(wú)約束i=1,2,3j=1,2,3,4目前十六頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)同理：對(duì)一般運(yùn)輸問(wèn)題數(shù)學(xué)模型設(shè)U1，U2，……Um

，V1，V2，……Vn為對(duì)應(yīng)運(yùn)輸問(wèn)題m+n個(gè)約束方程的對(duì)偶變量對(duì)偶問(wèn)題數(shù)學(xué)模型：Max=∑Uiai+∑Vjbj

Ui+Vj≤CijUi，Vj無(wú)約束Ui，Vj又分別稱為對(duì)應(yīng)于發(fā)點(diǎn)（產(chǎn)地）i和收點(diǎn)（銷地）j的位勢(shì)i=1,2,…,m

Ui

j=1,2,…,nVjXij≥0，i=1，2，…,mj=1，2，…n目前十七頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)設(shè)基B為運(yùn)輸問(wèn)題的一個(gè)可行基，則對(duì)偶變量Y=CBB-1

=(U1,U2,……,Um,V1,V2,……,Vn)決策變量Xij的系數(shù)列向量Pij=ei+em+j=0：1：1：0檢驗(yàn)數(shù)ij=Cij-CBB-1Pij

=Cij-(U1,U2,……,Um,V1,V2,……,Vn)=Cij-Ui-Vj由單純形法原理可知基變量檢驗(yàn)數(shù)為零即

Cij-Ui-Vj=0

Cij=Ui+VjXij∈XB即：我們可以把某一調(diào)運(yùn)方案中所有基變量的運(yùn)價(jià)Cij分解為對(duì)應(yīng)的行位勢(shì)和列位勢(shì)兩部分目前十八頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)續(xù)上頁(yè)：由于基變量Cij=Ui+Vj

非基變量檢驗(yàn)數(shù)ij=Cij-Ui-Vj只要求出Ui、Vj，則可求出ij例：例1初始調(diào)運(yùn)表見下表該例：m=3，n=4，基變量有6個(gè)，對(duì)應(yīng)的Cij方程也有6個(gè)，而位勢(shì)量(對(duì)偶變量)有7個(gè)，6個(gè)方程解出7個(gè)位勢(shì)有很多解，把U1作為自由變量，令U1=0C13=U1+V3=3V3=3C14=U1+V4=10V4=10C23=U2+V3=2U2=-1C21=U2+V1=1V1=2C34=U3+V4=5U3=-5C32=U3+V2=4V2=9將位勢(shì)量填入調(diào)運(yùn)方案表中，計(jì)算非基變量的檢驗(yàn)數(shù)ij=Cij-Ui-VjVjA3A2A1UiB4B3B2B1311310④③③①⑥③192874105U1V3V4U2V1U3V2目前十九頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)上述計(jì)算過(guò)程可在表中進(jìn)行，其中基變量Cij=Ui+Vj

非基變量檢驗(yàn)數(shù)ij==Cij-Ui-Vj方法：1.在產(chǎn)銷平衡表分別增加一行、一列2.計(jì)算行位勢(shì)和列位勢(shì),分別填入最右一列、最后一行對(duì)應(yīng)位置VjA3A2A1UiB4B3B2B13113104331631928741050310-12-59注：上表中右上角數(shù)字為單位運(yùn)價(jià)，左下角紅色數(shù)字為非基變量檢驗(yàn)數(shù)，中間蘭色數(shù)字為調(diào)運(yùn)量上表中有負(fù)檢驗(yàn)數(shù)，說(shuō)明不是最優(yōu)解121-11012┓┓┓┓┓┓目前二十頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)位勢(shì)法步驟：已知基可行解{Xij}1、對(duì)基變量Xij，解方程Cij=Ui+Vj，得到Ui，Vj2、對(duì)非基變量Xij計(jì)算ij=Cij-Ui-Vj，若ij全≥0，停。否則，轉(zhuǎn)33、方案調(diào)整。目前二十一頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)調(diào)運(yùn)方案的改進(jìn)——閉回路調(diào)整法1、確定進(jìn)基格（進(jìn)基變量）Min={σij

∣σij

＜0}=ktXkt為進(jìn)基格2、作出從進(jìn)基格（k，t）格出發(fā)的閉回路，對(duì)各頂點(diǎn)順序編號(hào)3、確定調(diào)整量和離基格調(diào)整量Q=min{偶數(shù)點(diǎn)調(diào)運(yùn)量}4、閉回路調(diào)整：閉回路上：奇數(shù)頂點(diǎn)調(diào)運(yùn)量+Q偶數(shù)頂點(diǎn)調(diào)運(yùn)量-Q其余格運(yùn)量不變VjA3A2A1UiB4B3B2B13113104331631928741050310-12-59121-11012目前二十二頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)VjA3A2A1UiB4B3B2B13113101928741055231630310-59-230221912表中解為最優(yōu)解非基變量X11檢驗(yàn)數(shù)11=0，所以該運(yùn)輸問(wèn)題有無(wú)窮多解11=0，作出（1，1）格的閉回路，進(jìn)行最優(yōu)解調(diào)整，則得另一最優(yōu)方案。VjA3A2A1UiB4B3B2B1311310192874105563213033-210-592021912目前二十三頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)運(yùn)輸問(wèn)題的解的情況：1、無(wú)窮多最優(yōu)解：A3A2A1B4B3B2B1311310192874105UiVj563213033-210-592021912目前二十四頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)2、退化解：有基變量取值為零的情況。B1B2B3B4aiA17A24A39bi365631145773812106364160目前二十五頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)B1B2B3B4aiA17A24A39bi365631145773812106360416目前二十六頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)1）在用表上作業(yè)法求初始調(diào)運(yùn)方案時(shí)，第（k，t）格的調(diào)運(yùn)量Xkt=minak′

bt′當(dāng)ak′′=

bt′時(shí)，有兩種處理方法：◆劃去第k行或第t列，繼續(xù)找其它數(shù)字格◆同時(shí)劃去第k行和第t列，在劃去的行或列的某個(gè)空格處填上一個(gè)零作為數(shù)字格2）在用閉回路法對(duì)調(diào)運(yùn)方案改進(jìn)時(shí)：在閉回路頂點(diǎn)出現(xiàn)兩個(gè)以上最小運(yùn)量，調(diào)整后，這些偶數(shù)頂點(diǎn)減去調(diào)整量后，運(yùn)量為零，這時(shí)，只能把其中的一個(gè)數(shù)字格作為出基格，其余仍為運(yùn)量為零的數(shù)字格當(dāng)出現(xiàn)退化解后再作調(diào)整時(shí)，有可能在閉回路的偶數(shù)頂點(diǎn)上出現(xiàn)運(yùn)量為零的數(shù)字格，這時(shí)調(diào)整量為零。目前二十七頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)產(chǎn)銷不平衡運(yùn)輸問(wèn)題及其求解方法1、產(chǎn)＞銷：∑ai＞∑bj∑Xij≤aii=1，2……m∑Xij=bjj=1，2……n松弛變量Xi，n+1（I=1，2……m）表示Ai的庫(kù)存量，增加銷地Bn+1,銷量∑ai-∑bj，對(duì)應(yīng)運(yùn)價(jià)Ci，n+1=0i=1，2……mj=1，2……n，n+1目前二十八頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)6432銷量7A35A27A1產(chǎn)量B4B3B2B121134103597812B500044233322uivj0240-230380825772目前二十九頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)2.銷＞產(chǎn)：∑bj＞∑ai增加虛產(chǎn)地Am+１，產(chǎn)量am+1=∑bj-∑ai，對(duì)應(yīng)運(yùn)價(jià)Cm+1，j=0Minz=∑∑CijXiji=1j=1m+1n∑Xij=aiｉ＝1,2……ｍ+1j=1n∑Ｘij=bjj=1,2

……ni=1m+1目前三十頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)例2:設(shè)有3個(gè)化肥廠供應(yīng)4個(gè)地區(qū)的農(nóng)用化肥,假定等量化肥在這些地區(qū)使用效果相同,各化肥廠年產(chǎn)量,各地區(qū)年需求量、各化肥廠到各地區(qū)運(yùn)送單位化肥的運(yùn)價(jià)如下表,試求出總運(yùn)費(fèi)最小的化肥調(diào)撥方案ⅠⅡⅢⅣ產(chǎn)量ABC161322175014131915601920231550最低需求3070010最高需求507030不限目前三十一頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)Ⅰ′ⅡⅢⅣ′產(chǎn)量ABC16132217501413191560192023-50Ⅰ″161419Ⅳ″1715-DM0M0M050307030102050目前三十二頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)Ⅰ′Ⅰ″ⅡⅢⅣ′Ⅳ″ABCD5050201030603020050302050302070301050用表上作業(yè)法求得最優(yōu)方案為：目前三十三頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)例3：某調(diào)運(yùn)問(wèn)題，其產(chǎn)地產(chǎn)量、銷地銷量及單位產(chǎn)品獲利情況見下表，已知丙銷地至少保證供應(yīng)C產(chǎn)品1000，而因某種原因，該地不經(jīng)銷A產(chǎn)品，求使得總銷售收入最大的調(diào)運(yùn)方案及相應(yīng)利潤(rùn)。甲乙丙產(chǎn)量A5481000B16892000C1210112000銷量150015001500目前三十四頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)50015001500銷量1000C2000B1000A產(chǎn)量丙乙甲5401689121011丁0005001500500500500500500uiVj00465412-7-50-4-6-6目前三十五頁(yè)\總數(shù)四十一頁(yè)\編于十九點(diǎn)VjA3A2A1uiB4B3B2B1101201112C2292021416