运筹学chap3_运输问题课件.ppt

《运筹学chap3_运输问题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章运输问题产销平衡运输问题及其数学模型产销平衡运输问题的表上作业法产销不平衡运输问题有转运运输问题2321341产销平衡运输问题网络图s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地6753842759106产销平衡运输问题模型供应地约束需求地约束2321341s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地6753842791065总运价产销平衡运输问题的数学模型产销平衡问题s.t.产销平衡运输问题的特点1.A矩阵Pij=[0

2、,…,0,1,0,…,0,1,0,…,0]T第i个第m+j个3.存在可行解2.冗余约束数=1产销平衡运输问题的特点5.存在有界最优解4.所有运输路径的运价等幅调整，最优解不变。产销平衡运输问题的单纯形法1.rank(A)=m+n-13.单纯形法变量数目：mn+(m+n-1)需要寻找新的方法2.基变量个数:m+n-1运输问题的表格表示销地产地产量销量一般运输问题的表格表示销地产地B1B2…Bn产量A1x11x12x1na1A2x21x22x2na2……Amxm1xm2xmnam销量b1b2…bnc11c12c1nc2nc22c21

3、cm1cm2cmn表上作业法的思路1.确定初始基可行解2.最优性判别迭代要求：保持基可行解3.迭代初始基础可行解—西北角法（1）813131466初始基础可行解—西北角法（2）0131914122最小元素法（1）最小元素法（2）最小元素法（3）最小元素法（4）最小元素法（5）最小元素法（6）初始基础可行解（3）—Vogel法不仅考虑最小单位运价，还考虑次小单位运价沃格尔法构造初始基可行解(1)B1B2B3B4产量A114A21327A319销量22131213675384275910611333234512345221沃格尔法构造

4、初始基可行解(2)B1B2B3B4产量A114A2131227A319销量22131213675384275910611333213334512345222511沃格尔法构造初始基可行解(3)B1B2B3B4产量A11314A2131227A319销量2213121367538427591061133321333134512345223251111沃格尔法构造初始基可行解(4)B1B2B3B4产量A111314A22131227A31919销量22131213675384275910611333213331345123452232

5、51111运输问题基的表示m个供应地、n个需求地的运输问题，任何一个基要满足以下三个条件：基变量的个数为m+n-1；同行同列的基变量不能形成回路；运输表的每一行和每一列中至少有一个基变量。运输问题基的表示123412312341231234123123412312341231234123运输表中同行同列组成回路的变量123412312341231234123123412312341231234123解的最优性检验（1）--闭回路法基本思路：非基变量对应的检验数ij0?5闭回路法(1)12=c12-c22+c21-c11=7-

6、4+8-6=55闭回路法(2)13=c13-c23+c21-c11=5-2+8-6=555闭回路法(3)14=c13-c34+c33-c23+c21–c11=3-6+10-2+8-6=7755闭回路法(4)24=c24-c34+c33-c23=7-6+10-2=99575闭回路法(5)31=c31-c21+c23-c33=5-8+2-10=-11-115795闭回路法(6)32=c32-c22+c23-c33=9-4+2-10=-3-3579-11解的最优性检验（2）--对偶变量法基本思路：利用对偶问题求解原问题的ij

7、s.t.ui,vj符号不限s.t.对偶变量法对应于基变量部分，有ij=0，则：共有m+n个变量，m+n-1个等式，故解不唯一，称为位势。根据位势求非基变量ij对偶变量法(1)v4=0对偶变量法(2)u3+v4=c34u3=6对偶变量法(3)u3+v3=c33v3=4对偶变量法(4)u2+v3=c23u2=-2对偶变量法(5)u2+v2=c22v2=6对偶变量法(6)u2+v1=c21v1=10对偶变量法(7)u1+v1=c11u1=-4对偶变量法(8)12=c12–(u1+v2)=7-(-4+6)=55对偶变量法(9)13

8、=c13–(u1+v3)=5-(-4+4)=555对偶变量法(10)14=c14–(u1+v4)=3-(-4+0)=7755对偶变量法(11)24=c24–(u2+v4)=7-(-2+0)=99557对偶变量法(12)31=c31–(u3+v