运输问题新演示文稿

运输问题新演示文稿目前一页\总数四十一页\编于十九点（优选）运输问题新.目前二页\总数四十一页\编于十九点运输问题数学模型例：某公司经销甲产品，下设3个加工厂4个销售点，其加工厂产量，销售地销量以及各工厂到各销售点单位运价见表，如何调运，总运费最小206563销量951047A348291A27103113A1产量B4B3B2B1销地产地目前三页\总数四十一页\编于十九点设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目前四页\总数四十一页\编于十九点上述问题可以扩展为m个产地n个销地的运输问题，设ai为Ai产量，bj为Bj销地销量，Ai到Bj单位运价Cij，则产销平衡的运输问题其数学模型为i=1，2，…,mj=1，2，…nXij≥0，i=1，2，…,mj=1，2，…n目前五页\总数四十一页\编于十九点模型特点：◆模型有m×n个变量，m+n个方程◆对产销平衡问题∑ai=∑bj◆运输问题（产销平衡）总存在可行解和最优解

1、∵cij≥0Xij≥0∴cijXij≥0∴运输问题一定有界2、一定有可行解Xij=aibj∑ai3、有界且有可行解，所以一定有最优解◆约束方程系数矩阵具有稀疏结构（见下页），秩r（A）=m+n-1

目前六页\总数四十一页\编于十九点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目前七页\总数四十一页\编于十九点表上作业法步骤：1.确定初始基本可行解：有三种方法：①最小元素法②西北角法③伏格尔法2.求非基变量检验数，进行最优解判别，若最优，停止，否则进行下一步3.确定进基、离基变量，找新的基本可行解，返回2，重复2、3，直到得到最优解。目前八页\总数四十一页\编于十九点最小元素法基本思想：步骤：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，当填入最后一个元素时，同时划去一行一列。目前九页\总数四十一页\编于十九点6563销量951047A348291A27103113A1产量B4B3B2B1

销地产地B1B2B3B4销量A17A24A39产量3656314633注意：★最小运价有多个时，可任选一个★保证数字格数量为（m+n-1）个产销平衡表中填入数字的格为数字格，其余格为空格。目前十页\总数四十一页\编于十九点伏格尔法思路：步骤：1.计算各行各列最小元素与次最小元素Cij的差，分别填在最右一列和最下面一行2.选差最大的行（或列），根据该行（列）最小元素Cij确定调运量目前十一页\总数四十一页\编于十九点B1B2B3B4A1A2A3销量产量

311310

1928

74105

365674

9列差额011251360123213012123125212

行差额76目前十二页\总数四十一页\编于十九点最优解判别：两种方法:①闭回路法②位势法1.闭回路法：闭回路：互不相同的2k个变量X11X21X22…………XkkX1k（其下标交错相等,在表中表现为相临的两个变量，同行或同列）组成一个闭回路。X11X12X22X21●●●●●●●●●●●●●●目前十三页\总数四十一页\编于十九点闭回路求法：在给出调运方案的产销平衡表上，从某一空格（k，t）格出发，沿水平或竖直方向前进，遇到一个合适的数字格转弯90°继续前进，再遇到一个合适的数字格再转弯90°，继续前进，……，最后又回到原来的出发点（k，t）格，称这样走过的一条路线为从（k，t）格出发的闭回路。注：以空格为起点，以某些数字格为转折点，最终返回起点，所构成的一个路线称为闭回路。闭回路是惟一的！每一个空格点都能构成一条闭回路！65639A34A27A1B4B3B2B1311310192874105314633目前十四页\总数四十一页\编于十九点检验数求法：对从（k，t）格出发的闭回路各顶点依次编号,（k，t）格为第一顶点，对所经过的其它各顶点顺序编号，依次为第二、第三顶点，则闭回路上所有奇数点单位运价之和减偶数点单位运价之和所得的差，即为（k，t）格的检验数kt65639A34A27A1B4B3B2B1311310192874105314633+1-1+1-111=（C11+C23）

-（C13+C21）=（3+2）-（3+1）=1目前十五页\总数四十一页\编于十九点位势法设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目前十六页\总数四十一页\编于十九点同理：对一般运输问题数学模型设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目前十七页\总数四十一页\编于十九点设基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分解为对应的行位势和列位势两部分目前十八页\总数四十一页\编于十九点续上页：由于基变量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目前十九页\总数四十一页\编于十九点上述计算过程可在表中进行，其中基变量Cij=Ui+Vj

非基变量检验数ij==Cij-Ui-Vj方法：1.在产销平衡表分别增加一行、一列2.计算行位势和列位势,分别填入最右一列、最后一行对应位置VjA3A2A1UiB4B3B2B13113104331631928741050310-12-59注：上表中右上角数字为单位运价，左下角红色数字为非基变量检验数，中间兰色数字为调运量上表中有负检验数，说明不是最优解121-11012┓┓┓┓┓┓目前二十页\总数四十一页\编于十九点位势法步骤：已知基可行解{Xij}1、对基变量Xij，解方程Cij=Ui+Vj，得到Ui，Vj2、对非基变量Xij计算ij=Cij-Ui-Vj，若ij全≥0，停。否则，转33、方案调整。目前二十一页\总数四十一页\编于十九点调运方案的改进——闭回路调整法1、确定进基格（进基变量）Min={σij

∣σij

＜0}=ktXkt为进基格2、作出从进基格（k，t）格出发的闭回路，对各顶点顺序编号3、确定调整量和离基格调整量Q=min{偶数点调运量}4、闭回路调整：闭回路上：奇数顶点调运量+Q偶数顶点调运量-Q其余格运量不变VjA3A2A1UiB4B3B2B13113104331631928741050310-12-59121-11012目前二十二页\总数四十一页\编于十九点VjA3A2A1UiB4B3B2B13113101928741055231630310-59-230221912表中解为最优解非基变量X11检验数11=0，所以该运输问题有无穷多解11=0，作出（1，1）格的闭回路，进行最优解调整，则得另一最优方案。VjA3A2A1UiB4B3B2B1311310192874105563213033-210-592021912目前二十三页\总数四十一页\编于十九点运输问题的解的情况：1、无穷多最优解：A3A2A1B4B3B2B1311310192874105UiVj563213033-210-592021912目前二十四页\总数四十一页\编于十九点2、退化解：有基变量取值为零的情况。B1B2B3B4aiA17A24A39bi365631145773812106364160目前二十五页\总数四十一页\编于十九点B1B2B3B4aiA17A24A39bi365631145773812106360416目前二十六页\总数四十一页\编于十九点1）在用表上作业法求初始调运方案时，第（k，t）格的调运量Xkt=minak´

bt´当ak´´=

bt´时，有两种处理方法：◆划去第k行或第t列，继续找其它数字格◆同时划去第k行和第t列，在划去的行或列的某个空格处填上一个零作为数字格2）在用闭回路法对调运方案改进时：在闭回路顶点出现两个以上最小运量，调整后，这些偶数顶点减去调整量后，运量为零，这时，只能把其中的一个数字格作为出基格，其余仍为运量为零的数字格当出现退化解后再作调整时，有可能在闭回路的偶数顶点上出现运量为零的数字格，这时调整量为零。目前二十七页\总数四十一页\编于十九点产销不平衡运输问题及其求解方法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目前二十八页\总数四十一页\编于十九点6432销量7A35A27A1产量B4B3B2B121134103597812B500044233322uivj0240-230380825772目前二十九页\总数四十一页\编于十九点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目前三十页\总数四十一页\编于十九点例2:设有3个化肥厂供应4个地区的农用化肥,假定等量化肥在这些地区使用效果相同,各化肥厂年产量,各地区年需求量、各化肥厂到各地区运送单位化肥的运价如下表,试求出总运费最小的化肥调拨方案ⅠⅡⅢⅣ产量ABC161322175014131915601920231550最低需求3070010最高需求507030不限目前三十一页\总数四十一页\编于十九点Ⅰ´ⅡⅢⅣ´产量ABC16132217501413191560192023-50Ⅰ″161419Ⅳ″1715-DM0M0M050307030102050目前三十二页\总数四十一页\编于十九点Ⅰ´Ⅰ″ⅡⅢⅣ´Ⅳ″ABCD5050201030603020050302050302070301050用表上作业法求得最优方案为：目前三十三页\总数四十一页\编于十九点例3：某调运问题，其产地产量、销地销量及单位产品获利情况见下表，已知丙销地至少保证供应C产品1000，而因某种原因，该地不经销A产品，求使得总销售收入最大的调运方案及相应利润。甲乙丙产量A5481000B16892000C1210112000销量150015001500目前三十四页\总数四十一页\编于十九点50015001500销量1000C2000B1000A产量丙乙甲5401689121011丁0005001500500500500500500uiVj00465412-7-50-4-6-6目前三十五页\总数四十一页\编于十九点VjA3A2A1uiB4B3B2B1101201112C2292021416