大学精品课件：3-运输问题.ppt

1、一、运输问题的数学模型一、运输问题的数学模型231运输问题的提出运输问题的提出2341d1=22d2=13d3=12d4=13s2=27s3=19s1=14供应地供应地运价运价需求地需求地6753482759106供应量供应量需求量需求量总供应量总供应量60吨吨总需求量总需求量60吨吨供求平衡的运输问题供求平衡的运输问题0131213221927146109572483576min343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211=+=+=+=+=+=+

2、=+=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxs.t.xxxxxxxxxxxxz问题的线性规划模型问题的线性规划模型供应地约束供应地约束需求地约束需求地约束ijx表示从表示从供应地供应地 i 运往运往需求地需求地 j 的运量的运量运输问题的一般形式运输问题的一般形式bnb2b1xmnxm2xm1amcmncm2cm1m x2nx22x21a2c2nc22c212x1nx12x11a1c1nc12c111n21产地产地产产量量销地销地销量销量xij,cij 分别表示从产地分别表示从产地 i 销往销往 j 地的运量及单位运价地的运量及单位运价试确定总费用最低的调运方

3、案试确定总费用最低的调运方案数学模型数学模型0)2.3(,.,2,1,)1.3(,.,2,1,.min1111 ijjmiijinjijminjijijxnjbxmiaxtsxcznmA 111111111111111111x11 x12 x1m x21 x22 x2m xm1 xm2 xmn1)(,111111 nmArankbxxanjjnjmiijminjijmii关于运输问题数学模型的几点说明关于运输问题数学模型的几点说明rank(A)=m+n-1，于是其基变量的个数为，于是其基变量的个数为 m+n-1 icolumnEenmi 记记 njmijnikwhereeekcolumnAPj

4、mik,.,2,1;,.,2,1,1,则则 miPnjPnij,.,2,.,2,1,11 这这 m+n-1个列向量线性无关个列向量线性无关运输问题的可行解总存在，因而存在有限最优解运输问题的可行解总存在，因而存在有限最优解 njjmiijiijbaQwhereQbax11,0取取此地此地 Pk=ei+e m+j(或或Pij)，事实上，是变量，事实上，是变量 xij 对应的列向量对应的列向量jnjijnijiniijinjjinjjinjijbaQbQbaxabQaQbax 111111,则则二、表上作业法二、表上作业法表上作业法是单纯形法在求解运输问题时的一种简表上作业法是单纯形法在求解运输问

5、题时的一种简化方法，其实质是单纯形法，但其求解是在二维表化方法，其实质是单纯形法，但其求解是在二维表上完成的，求解步骤归纳为：上完成的，求解步骤归纳为：1)找出初始基可行解，即在找出初始基可行解，即在 m n产销平衡表上给出产销平衡表上给出 m+n-1个个(非负非负)数字格；数字格；2)求各非基变量的检验数，即在表上计算空格的检验数，判求各非基变量的检验数，即在表上计算空格的检验数，判断是否达到最优解，若已是最优解，则停止计算，否则转断是否达到最优解，若已是最优解，则停止计算，否则转入下一步；入下一步；3)确定进基变量和出基变量，找出新的基可行解，在表上用确定进基变量和出基变量，找出新的基可行

6、解，在表上用闭回路闭回路法调整；法调整；4)重复重复2),3)直到求得最优解。直到求得最优解。闭回路闭回路定义定义：在运输问题的调运表中，凡能排成：在运输问题的调运表中，凡能排成 xi1j1,xi1j2,xi2j2,xisjs,xisj1 形式的变量集合，称为一个闭回形式的变量集合，称为一个闭回路，其中诸变量称为该闭回路的顶点。路，其中诸变量称为该闭回路的顶点。特点：特点：1)每个顶点都是转角；每个顶点都是转角；2)每行或每列有且仅有两个顶点；每行或每列有且仅有两个顶点；3)相临顶点的连线都是水平或垂直的。相临顶点的连线都是水平或垂直的。B1B2B3B4B5B6B7A1x11x12x13x14

7、x15x16x17A2x21x22x23x24x25x26x27A3x31x32x33x34x35x36x37闭回路闭回路1：x11,x12,x22,x23,x33,x31,x11闭回路闭回路2：x15,x16,x36,x37,x27,x25,x15闭回路的代数表示闭回路的代数表示在运输问题的调运表中，在运输问题的调运表中，xi1j1,xi1j2,xi2j2,xisjs,xisj1，这，这s个顶点构成闭回路，个顶点构成闭回路，则这些顶点对应的系数列向量则这些顶点对应的系数列向量Pi1j1,Pi1j2,Pi2j2,Pisjs,Pisj1，成立着，成立着 Pi1j1Pi1j2Pi2j2PisjsP

8、isj1 0。闭回路闭回路1：x11,x12,x22,x23,x33,x31,x11 P11P12P22P23P33 P31 0闭回路闭回路2：x15,x16,x36,x37,x27,x25,x15P15P16P36P37P27P250 7,2,1;3;3,2,1 jmieePjmiij闭回路的一个性质闭回路的一个性质定理定理：运输问题的：运输问题的 m+n-1 个变量个变量 xi1j1,xi2j2,xisjs(s=m+n-1)构成某一基可构成某一基可行解的基变量的充分必要条件是：不存行解的基变量的充分必要条件是：不存在以这些变量为顶点的闭回路。在以这些变量为顶点的闭回路。作用：作用：1)较简

9、便地求出基可行解；较简便地求出基可行解；2)判断某一可行解是否为基可行解。判断某一可行解是否为基可行解。2.1、初始基可行解的确定、初始基可行解的确定西北角法西北角法最小元素法最小元素法Vogel法法西北角法西北角法直观法直观法 1 2 3 4 6 7 5 3 1 14 8 4 2 7 2 27 5 9 10 6 3 19 22 13 12 13 813131466最小元素法最小元素法基本思想基本思想：就近供应，即从单位运价最：就近供应，即从单位运价最小者开始确定供销关系，然后次小，小者开始确定供销关系，然后次小，直至给出初始基可行解为止。直至给出初始基可行解为止。1 2 3 4 6 7 5

10、3 1 14 8 4 2 7 2 27 5 9 10 6 3 19 22 13 12 13 最小元素法最小元素法求求初始基可行解初始基可行解121313(0)(0)(15)(1)(0)(2)19(3)(0)1(0)(2)2(0)(0)Vogel法法基本思想基本思想：一产地的产品假如不能按最小运：一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。应当采用最小运费调运。Vo

11、gel法的步骤：法的步骤：1)计算出各行、各列的最小运费和次最小运费的差计算出各行、各列的最小运费和次最小运费的差额，并填入调运表的最右行和最下行；额，并填入调运表的最右行和最下行；2)从行或列差额中选出最大者，选择它所在行或列从行或列差额中选出最大者，选择它所在行或列中的最小元素，确定最大调运量，并划去相应的中的最小元素，确定最大调运量，并划去相应的行或列；行或列；3)对未划去的行列重新实施对未划去的行列重新实施 1),2)直到求得初始解。直到求得初始解。Vogel法法求求初始基可行解初始基可行解 1 2 3 4 3 11 3 10 1 7 1 9 2 8 2 4 7 4 10 5 3 9

12、3 6 5 6 01125136012333212317652122三种方法的合理性分析三种方法的合理性分析用西北角法、最小元素法、用西北角法、最小元素法、VogelVogel法得到的法得到的初始解为基可行解？初始解为基可行解？用三法填入调运表的数字格个数为用三法填入调运表的数字格个数为 m+n-1，且这些数字非负，即得到运输问题的可行解。且这些数字非负，即得到运输问题的可行解。调运表为调运表为 m 行，行，n 列的矩形表格，行数与列数的列的矩形表格，行数与列数的和为和为 m+n；用三法填入调运表的每一个数用三法填入调运表的每一个数(除最后一个除最后一个)，将，将划去该数字格所在的行或列划去该

13、数字格所在的行或列(行列其一行列其一)；当表中只剩一个元素时，填入最后一数，同时划当表中只剩一个元素时，填入最后一数，同时划去该数字格所在的行与列；去该数字格所在的行与列；三种方法的合理性分析三种方法的合理性分析(续续)这些数字格对应变量的系数列向量这些数字格对应变量的系数列向量 Pikjk(k=1,2,m+n-1)线性无关，进一步得到该线性无关，进一步得到该可行解为基可行解。可行解为基可行解。1)记填入调运表的第一个数字格位置为记填入调运表的第一个数字格位置为(i1,j1)，对应的变量为对应的变量为 xi1j1,Pi1j1=ei1+em+j1,并划去第并划去第i1行或第行或第j1列，意味着，

14、以后填入数字格对应变量列，意味着，以后填入数字格对应变量的系数列向量，将不出现的系数列向量，将不出现ei1 或或 em+j1；所以；所以Pi1j1 不能由不能由Pikjk(k=2,m+n-1)线性表示；线性表示；2)一般地，一般地，Pikjk 不能由其后的不能由其后的Pirjr(r=k+1,m+n-1)线性表示；线性表示；3)所以，所以，Pikjk(k=1,2,m+n-1)线性无关。线性无关。2.2、最优解的判别、最优解的判别方法：计算非基变量方法：计算非基变量(空格空格)的检验数的检验数计算计算 cij CBB-1 Pij,(i,j)N对于所有非基指标对于所有非基指标(i,j)N，有，有 c

15、ij CBB-1 Pij 0，则已得最优解；则已得最优解；否则，为非否则，为非最优解，并最优解，并确定进基变量和出基变量确定进基变量和出基变量非基变量检验数计算非基变量检验数计算闭回路法闭回路法位势法位势法2.2.1、闭回路法闭回路法定理：从每一空格定理：从每一空格(非基变量非基变量)出发，经数字格出发，经数字格(基变量基变量)一定存在闭回路，且这样的闭回路是一定存在闭回路，且这样的闭回路是唯一的。唯一的。分析：分析：存在性：存在性：对于对于Pij(i,j)为非基指标，存在为非基指标，存在Pi1j1,Pi2j2,Pisjs(ik,jk)为基指标，使得为基指标，使得Pij=1Pi1j1+2Pi2

16、j2+sPisjs(k 0)由由Pij=ei+em+j及基向量的线性无关性和向量的内积及基向量的线性无关性和向量的内积计算，可得计算，可得 k=1或或 k=-1唯一性：唯一性：由基向量的线性无关性，直接得到。由基向量的线性无关性，直接得到。闭回路法闭回路法(续续)1 2 3 4 6 7 5 3 1 14 8 4 2 7 2 27 5 9 10 6 3 19 22 13 12 13 8131314665579-11-3 12=c12-c22+c21-c11=5,13=c13-c23+c21-c11=5,14=c14-c34+c33-c23+c21-c11=7,24=c24-c34+c33-c23

17、=9 31=c31-c21+c23-c33=-11 0 32=c32-c22+c23-c33=-3 02.2.2、位势法位势法(对偶变量法对偶变量法)0,.,2,1,.,2,1,.min1111 ijjjmiijiinjijminjijijxvnjbxumiaxtsxcz运输问题原问题运输问题原问题对偶问题对偶问题unrvunjmicvutsvbuajiijjiminjjjii:,.,2,1;,.,2,1,.max11 nmBvvvuuuBC,;,21211 jiijijBijijvucPBCc 1单纯形乘子单纯形乘子检验数检验数 Bjivucjiij ),(,0对于基变量指标对于基变量指标(

18、i,j)，有，有位势法计算检验数的步骤位势法计算检验数的步骤对于基变量对于基变量(i,j)B，列出位势方程组，列出位势方程组ui+vj=cij取取 u1=0，求解位势方程组，求解位势方程组根据公式根据公式 ij=cij (ui+vj)，计算非基变量的计算非基变量的检验数检验数位势法计算检验数位势法计算检验数 1 2 3 4 6 7 5 3 1 14 8 4 2 7 2 27 5 9 10 6 3 19 22 13 12 13 813131466u1+v1=c11=6,u2+v3=c23=2 u2+v1=c21=8,u3+v3=c33=10u2+v2=c22=4,u3+v4=c34=6令令 u1

19、=0,得得u2=2,u3=10v1=6,v2=2,v3=0,v4=-4位势方程位势方程5579-11-3 jiijijvuc 2.3 2.3 基可行解的改进基可行解的改进闭回路调整法闭回路调整法当表格中空格处出现负检验数时，表明未得当表格中空格处出现负检验数时，表明未得最优解；最优解；选择最小负检验数所在的空格为调入格，即以它对应选择最小负检验数所在的空格为调入格，即以它对应的非基变量为进基变量的非基变量为进基变量 1 2 3 4 6 7 5 3 1 14 14 8 4 2 7 2 8 13 6 27 5 9 10 6 3 6 13 19 22 13 12 13 -11+6-6-6+6调入量及

20、出基变量的确定，选择闭回路上具有调入量及出基变量的确定，选择闭回路上具有“”项的数字格的最小者对应的基变量出基，项的数字格的最小者对应的基变量出基，=min(6,8)=6调整前调整前：z=350z=350调整后：调整后：z=284z=284 1 2 3 4 6 7 5 3 1 14 14 8 4 2 7 2 2 13 12 27 5 9 10 6 3 6 13 19 22 13 12 13 +13-13-13+13闭回路调整法闭回路调整法(续续)55-4-2118 1 2 3 4 6 7 5 3 1 1 13 14 8 4 2 7 2 2 13 12 27 5 9 10 6 3 19 19 2

21、2 13 12 13 闭回路调整法闭回路调整法(续续2)5542118Min z=232,x11=1,x14=13,x21=2,x22=13,x23=12,x31=19,其他其他 xij=0确定初始基础可行解确定初始基础可行解西北角法西北角法求非基变量的检验数求非基变量的检验数闭回路法闭回路法位势法位势法确定进基变量确定进基变量确定出基变量确定出基变量得到新的基可行解得到新的基可行解沿回路调整运量沿回路调整运量Vogel法法最小元素法最小元素法2.4、运输问题解的讨论、运输问题解的讨论对于产销平衡的运输问题，必存在对于产销平衡的运输问题，必存在最优解；最优解；唯一最优解唯一最优解:非基变量非基

22、变量(空格空格)的检验数均大于的检验数均大于0;无穷多最优解无穷多最优解:非基变量的检验数均非基变量的检验数均 0且其中某个且其中某个=0;退化退化:求解运输问题时，数字格的数目求解运输问题时，数字格的数目m+n-1,则需在相应空格填入则需在相应空格填入0,以确保基变量的个数为以确保基变量的个数为m+n-1,最终求出问题的解。最终求出问题的解。确定初始解时确定初始解时用闭回路法调整时用闭回路法调整时确定初始解时，产生退化确定初始解时，产生退化 1 2 3 4 3 11 4 5 1 7 7 7 3 8 2 4 1 2 10 6 3 9 3 6 5 6 63(6)(0)0416用闭回路调整时，产生

23、退化用闭回路调整时，产生退化在闭回路上出现两个或两个以上的具有在闭回路上出现两个或两个以上的具有“-”标标记的相等的最小值。这时只能选择其一为调出记的相等的最小值。这时只能选择其一为调出格格(空格空格)，其它变为，其它变为0的填入的填入0,以确保数字格以确保数字格(基变量基变量)的个数为的个数为m+n-1,最终求出问题的解。最终求出问题的解。1 2 3 4 6 7 5 3 1 13 13 8 4 2 7 2 2 13 12 27 5 9 10 6 3 6 13 19 21 13 12 13 +13-13-1355-4+13-2118 0思考与判断思考与判断为什么用为什么用Vogel法给出的初始

24、解，比最小元素法更接近法给出的初始解，比最小元素法更接近于于最优解？最优解？运输问题是一种特殊的线性规划，因而它的解可能出运输问题是一种特殊的线性规划，因而它的解可能出现下列四种情况之一现下列四种情况之一:唯一解，无穷多解，无界解，无唯一解，无穷多解，无界解，无可行解可行解?运输问题中，只要给出运输问题中，只要给出m+n-1非零的非零的xij满足约束方程，满足约束方程，就可作为一个初始可行解？就可作为一个初始可行解？运输问题单位运价表的某一行运输问题单位运价表的某一行(列列)元素分别加上常数元素分别加上常数k，最优调运方案不变？最优调运方案不变？运输问题单位运价表的某一行运输问题单位运价表的某

25、一行(列列)元素分别乘上常数元素分别乘上常数k，最优调运方案不变？最优调运方案不变？当所有产地产量和销地的销量均为整数值时，该运输当所有产地产量和销地的销量均为整数值时，该运输问题的最优解也为整数？问题的最优解也为整数？三、产销不平衡的运输问题三、产销不平衡的运输问题 njjnjmiijminjijmiibxxa1111110)2.3(,.,2,1,)1.3(,.,2,1,.min1111 ijjmiijinjijminjijijxnjbxmiaxtsxcz产销平衡产销平衡产销不平衡产销不平衡 njjmiiba11产大于销产大于销转化成产销平衡转化成产销平衡 njjmiimininbaxb11

26、11,10)2.3(,.,2,1,)1.3(,.,2,1,.min1111 ijjmiijinjijminjijijxnjbxmiaxtsxcz数学模型数学模型产大于销产大于销 njjmiiba11多余物资的处理：就地存储。产地多余物资的处理：就地存储。产地 Ai 的存储量为的存储量为 xi,n+1，实施存，实施存储的单位费用储的单位费用 ci,n+1=0，并将这些不同的存储地统一为一假想的销，并将这些不同的存储地统一为一假想的销地地 Bn+1，该销地的销量为，该销地的销量为产大于销产大于销转化成产销平衡转化成产销平衡(续续)1,.,2,1;,.,2,10)2.3(1,.,2,1,)1.3(,

27、.,2,1,.min11111111 nnjmixnnjbxmiaxtsxcxczijjmiijinjijminjijijminjijij数学模型数学模型销大于产销大于产转化成产销平衡转化成产销平衡 miinjjnjjmmabxa111,110,.,2,1,.,2,1,.min1111 ijjmiijinjijminjijijxnjbxmiaxtsxcz数学模型数学模型销大于产销大于产 njjmiiba11处理方式：增加一个假想的产地处理方式：增加一个假想的产地 Am+1，运往，运往 Bj的量为的量为 xm+1,j，运，运输单价输单价 cm+1,j=0，该，该假想的产地假想的产地 Am+1产地的产量为产地的产量为0,.,2,1,1,.,2,1,.min111111 ijjmiijinjijminjijijxnjbxmiaxtsxcz