運輸問題新演示文稿當前第1頁\共有41頁\編于星期五\15點（優選）運輸問題新.當前第2頁\共有41頁\編于星期五\15點運輸問題數學模型例：某公司經銷甲產品，下設3個加工廠4個銷售點，其加工廠產量，銷售地銷量以及各工廠到各銷售點單位運價見表，如何調運，總運費最小206563銷量951047A348291A27103113A1產量B4B3B2B1銷地產地當前第3頁\共有41頁\編于星期五\15點設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當前第4頁\共有41頁\編于星期五\15點上述問題可以擴展為m個產地n個銷地的運輸問題，設ai為Ai產量，bj為Bj銷地銷量，Ai到Bj單位運價Cij，則產銷平衡的運輸問題其數學模型為i=1，2，…,mj=1，2，…nXij≥0，i=1，2，…,mj=1，2，…n當前第5頁\共有41頁\編于星期五\15點模型特點：◆模型有m×n個變量，m+n個方程◆對產銷平衡問題∑ai=∑bj◆運輸問題（產銷平衡）總存在可行解和最優解

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

當前第6頁\共有41頁\編于星期五\15點P11P12……P1nP21P22……P2n……Pm1Pm2……Pmn

11……1a111……1a2

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

……:

11……1bmm行n行

0

0

0

:

::

110Pij=

:=:+:

101

:

:

:

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

根據Ckt對應的產地產量ak、銷地銷量bt確定調運量調運量Xkt=min{ak，bt

}

，將Xkt填在產銷平衡表第（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.從未被劃去元素中再找最小元素，重復1、2，當填入最后一個元素時，同時劃去一行一列。當前第9頁\共有41頁\編于星期五\15點6563銷量951047A348291A27103113A1產量B4B3B2B1

銷地產地B1B2B3B4銷量A17A24A39產量3656314633注意：★最小運價有多個時，可任選一個★保證數字格數量為（m+n-1）個產銷平衡表中填入數字的格為數字格，其余格為空格。當前第10頁\共有41頁\編于星期五\15點伏格爾法思路：步驟：1.計算各行各列最小元素與次最小元素Cij的差，分別填在最右一列和最下面一行2.選差最大的行（或列），根據該行（列）最小元素Cij確定調運量當前第11頁\共有41頁\編于星期五\15點B1B2B3B4A1A2A3銷量產量

311310

1928

74105

365674

9列差額011251360123213012123125212

行差額76當前第12頁\共有41頁\編于星期五\15點最優解判別：兩種方法:①閉回路法②位勢法1.閉回路法：閉回路：互不相同的2k個變量X11X21X22…………XkkX1k（其下標交錯相等,在表中表現為相臨的兩個變量，同行或同列）組成一個閉回路。X11X12X22X21●●●●●●●●●●●●●●當前第13頁\共有41頁\編于星期五\15點閉回路求法：在給出調運方案的產銷平衡表上，從某一空格（k，t）格出發，沿水平或豎直方向前進，遇到一個合適的數字格轉彎90°繼續前進，再遇到一個合適的數字格再轉彎90°，繼續前進，……，最后又回到原來的出發點（k，t）格，稱這樣走過的一條路線為從（k，t）格出發的閉回路。注：以空格為起點，以某些數字格為轉折點，最終返回起點，所構成的一個路線稱為閉回路。閉回路是惟一的！每一個空格點都能構成一條閉回路！65639A34A27A1B4B3B2B1311310192874105314633當前第14頁\共有41頁\編于星期五\15點檢驗數求法：對從（k，t）格出發的閉回路各頂點依次編號,（k，t）格為第一頂點，對所經過的其它各頂點順序編號，依次為第二、第三頂點，則閉回路上所有奇數點單位運價之和減偶數點單位運價之和所得的差，即為（k，t）格的檢驗數kt65639A34A27A1B4B3B2B1311310192874105314633+1-1+1-111=（C11+C23）

-（C13+C21）=（3+2）-（3+1）=1當前第15頁\共有41頁\編于星期五\15點位勢法設Xij為Ai到Bj的運量，根據例1運輸問題數學模型

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設U1，U2，U3

，V1，V2，V3，V4為對應3+4個約束方程的對偶變量，則其對偶問題為Max=∑Uiai+∑Vjbj

Ui+Vj≤CijUi，Vj無約束i=1,2,3j=1,2,3,4當前第16頁\共有41頁\編于星期五\15點同理：對一般運輸問題數學模型設U1，U2，……Um

，V1，V2，……Vn為對應運輸問題m+n個約束方程的對偶變量對偶問題數學模型：Max=∑Uiai+∑Vjbj

Ui+Vj≤CijUi，Vj無約束Ui，Vj又分別稱為對應于發點（產地）i和收點（銷地）j的位勢i=1,2,…,m

Ui

j=1,2,…,nVjXij≥0，i=1，2，…,mj=1，2，…n當前第17頁\共有41頁\編于星期五\15點設基B為運輸問題的一個可行基，則對偶變量Y=CBB-1

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

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

Cij-Ui-Vj=0

Cij=Ui+VjXij∈XB即：我們可以把某一調運方案中所有基變量的運價Cij分解為對應的行位勢和列位勢兩部分當前第18頁\共有41頁\編于星期五\15點續上頁：由于基變量Cij=Ui+Vj

非基變量檢驗數ij=Cij-Ui-Vj只要求出Ui、Vj，則可求出ij例：例1初始調運表見下表該例：m=3，n=4，基變量有6個，對應的Cij方程也有6個，而位勢量(對偶變量)有7個，6個方程解出7個位勢有很多解，把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將位勢量填入調運方案表中，計算非基變量的檢驗數ij=Cij-Ui-VjVjA3A2A1UiB4B3B2B1311310④③③①⑥③192874105U1V3V4U2V1U3V2當前第19頁\共有41頁\編于星期五\15點上述計算過程可在表中進行，其中基變量Cij=Ui+Vj

非基變量檢驗數ij==Cij-Ui-Vj方法：1.在產銷平衡表分別增加一行、一列2.計算行位勢和列位勢,分別填入最右一列、最后一行對應位置VjA3A2A1UiB4B3B2B13113104331631928741050310-12-59注：上表中右上角數字為單位運價，左下角紅色數字為非基變量檢驗數，中間蘭色數字為調運量上表中有負檢驗數，說明不是最優解121-11012┓┓┓┓┓┓當前第20頁\共有41頁\編于星期五\15點位勢法步驟：已知基可行解{Xij}1、對基變量Xij，解方程Cij=Ui+Vj，得到Ui，Vj2、對非基變量Xij計算ij=Cij-Ui-Vj，若ij全≥0，停。否則，轉33、方案調整。當前第21頁\共有41頁\編于星期五\15點調運方案的改進——閉回路調整法1、確定進基格（進基變量）Min={σij

∣σij

＜0}=ktXkt為進基格2、作出從進基格（k，t）格出發的閉回路，對各頂點順序編號3、確定調整量和離基格調整量Q=min{偶數點調運量}4、閉回路調整：閉回路上：奇數頂點調運量+Q偶數頂點調運量-Q其余格運量不變VjA3A2A1UiB4B3B2B13113104331631928741050310-12-59121-11012當前第22頁\共有41頁\編于星期五\15點VjA3A2A1UiB4B3B2B13113101928741055231630310-59-230221912表中解為最優解非基變量X11檢驗數11=0，所以該運輸問題有無窮多解11=0，作出（1，1）格的閉回路，進行最優解調整，則得另一最優方案。VjA3A2A1UiB4B3B2B1311310192874105563213033-210-592021912當前第23頁\共有41頁\編于星期五\15點運輸問題的解的情況：1、無窮多最優解：A3A2A1B4B3B2B1311310192874105UiVj563213033-210-592021912當前第24頁\共有41頁\編于星期五\15點2、退化解：有基變量取值為零的情況。B1B2B3B4aiA17A24A39bi365631145773812106364160當前第25頁\共有41頁\編于星期五\15點B1B2B3B4aiA17A24A39bi365631145773812106360416當前第26頁\共有41頁\編于星期五\15點1）在用表上作業法求初始調運方案時，第（k，t）格的調運量Xkt=minak′

bt′當ak′′=

bt′時，有兩種處理方法：◆劃去第k行或第t列，繼續找其它數字格◆同時劃去第k行和第t列，在劃去的行或列的某個空格處填上一個零作為數字格2）在用閉回路法對調運方案改進時：在閉回路頂點出現兩個以上最小運量，調整后，這些偶數頂點減去調整量后，運量為零，這時，只能把其中的一個數字格作為出基格，其余仍為運量為零的數字格當出現退化解后再作調整時，有可能在閉回路的偶數頂點上出現運量為零的數字格，這時調整量為零。當前第27頁\共有41頁\編于星期五\15點產銷不平衡運輸問題及其求解方法1、產＞銷：∑ai＞∑bj∑Xij≤aii=1，2……m∑Xij=bjj=1，2……n松弛變量Xi，n+1（I=1，2……m）表示Ai的庫存量，增加銷地Bn+1,銷量∑ai-∑bj，對應運價Ci，n+1=0i=1，2……mj=1，2……n，n+1當前第28頁\共有41頁\編于星期五\15點6432銷量7A35A27A1產量B4B3B2B121134103597812B500044233322uivj0240-230380825772當前第29頁\共有41頁\編于星期五\15點2.銷＞產：∑bj＞∑ai增加虛產地Am+１，產量am+1=∑bj-∑ai，對應運價Cm+1，j=0Minz=∑∑CijXiji=1j=1m+1n∑Xij=aiｉ＝1,2……ｍ+1j=1n∑Ｘij=bjj=1,2

……ni=1m+1當前第30頁\共有41頁\編于星期五\15點例2:設有3個化肥廠供應4個地區的農用化肥,假定等量化肥在這些地區使用效果相同,各化肥廠年產量,各地區年需求量、各化肥廠到各地區運送單位化肥的運價如下表,試求出總運費最小的化肥調撥方案ⅠⅡⅢⅣ產量ABC161322175014131915601920231550最低需求3070010最高需求507030不限當前第31頁\共有41頁\編于星期五\15點Ⅰ′ⅡⅢⅣ′產量ABC16132217501413191560192023-50Ⅰ″161419Ⅳ″1715-DM0M0M050307030102050當前第32頁\共有41頁\編于星期五\15點Ⅰ′Ⅰ″ⅡⅢⅣ′Ⅳ″ABCD5050201030603020050302050302070301050用表上作業法求得最優方案為：當前第33頁\共有41頁\編于星期五\15點例3：某調運問題，其產地產量、銷地銷量及單位產品獲利情況見下表，已知丙銷地至少保證供應C產品1000，而因某種原因，該地不經銷A產品，求使得總銷售收入最大的調運方案及相應利潤。甲乙丙產量A5481000B16892000C1210112000銷量150015001500當前第34頁\共有41頁\編于星期五\15點50015001500銷量1000C2000B1000A產量丙乙甲5401689121011丁0005001500500500500500500uiVj00465412-7-50-4-6-6當前第35頁\共有41頁\編于星期五\15點VjA3A2A1uiB4B3B2B1101201112C2292021416