资源描述：
《运筹学运输问题(3).ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第七章运输问题7.1运输问题的数学模型7.2表上作业法7.3产销不平衡问题5.1运输问题的数学模型(1)运输问题的引入例1有一个地区有两个产棉区A1,A2向三个纺织厂B1B2,B3供应棉花,产棉区每年的供应量分别为70kt和50kt;纺织厂每年的需求量分别为50kt,40kt和30kt.已知各产棉区到各纺织厂的单位运价如左表,问如何安排运输方案,使总运费最小.设由Ai运往Bj的棉花的运量为xij(kt),如右表:销地产地B1B2B3A1A2586438销地产地B1B2B3产量A1A2x11x12x13x21x22x237050销
2、量5040301205.1运输问题的数学模型(1)运输问题的引入由于各个产棉区Ai运往各个纺织厂Bj的总量应该等于它的产量，所以x11+x12+x13=70x21+x22+x23=50另外,由于各个纺织厂收到各个产棉区运输的总量应该等于它的需求量x11+x21=50x12+x22=40x13+x23=30目标是总运费最小，即minz=5x11+8x12+6x13+4x21+3x22+8x23销地产地B1B2B3产量A1A2x11x12x13x21x22x237050销量5040301205.1运输问题的数学模型(1)运输问题的引
3、入此运输问题的数学模型为:minz=5x11+8x12+6x13+4x21+3x22+8x23x11+x12+x13=70x21+x22+x23=50x11+x21=50x12+x22=40x13+x23=30xij≥0(i=1,2;j=1,2,3)5.1运输问题的数学模型(2)运输问题的一般数学模型运输问题的一般描述:m个产地Ai,I=1,2..,m,产量分别为ai个单位,n个产地Bj,j=1,2..,n,产量分别为bj个单位;Ai与Bj之间的单位运价爲Cij,问如何安排运输方案,使总运费最少?销地产地B1B2…Bn产量A1A
4、2…Amc11c12…c1nc21c22…c2n……………………………cm1cm2…cmna1a2…am销量b1b2…bn∑ai=∑bj5.1运输问题的数学模型(2)运输问题的一般数学模型此问题的数学模型:minz=∑∑cijxijs.t∑xij=ai(i=1,2..m)∑xij=bj(j=1,2..n)xij≥0(i=1,2..m,j=1,2..n)i＝1j＝1mn5.2表上作业法模型的矩阵表述表上作业法的计算步骤确定初始基可行解最优解的判别闭回路调整法对于平衡运输问题化成矩阵形式:minz=CX;AX=b;X≥0其中C=(c
5、11,c12,...,C1n,...,cm1,cm2,…,cmn)，b=(a1,a2,…,am,b1,b2,…,bn)T,X=(x11,x12,…,x1n,…,xm1,xm2,…,xmn)T。11…111…1…A=11…111…1111………111R(A)=m+n-15.2.1模型的矩阵表示该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1外，其余的都为零。即Pij＝(0,0,…,0,1,0,…,0,1,0,…,0)T＝ei+em+j对产销平衡的运输问题，由于有以下关系式存在：∑bj=∑(∑xij)=
6、∑(∑xij)=∑ai所以模型最多只有m+n-1个独立约束方程。即系数矩阵的秩≤m+n-1。5.2.1模型的矩阵表示表上作业法的实质是单纯形法。其计算步骤为：（1）找出初始基可行解。即在（m×n）产销平衡表上给出（m+n—1）个数字格。（2）求各非基变量的检验数。在表上即是空格的检验数。判别是否达到最优解。如果已经是最优解，则停止计算，否则转到下一步。（3）确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。（4）重复（2），（3）直到得到最优解(肯定存在)为止。以上运算都可以在表上进行。5.2.2表上作业法的矩阵表
7、示步骤详解（例2）例2设某物资从A1,A2,A3处运往B1,B2,B3,B4处,各处供应量,需求量及单位运价见下表。问如何安排运输方案,才能使总运费最少?销地产地B1B2B3B4供应量A137645A224322A343853需求量323210最小元素法伏格尔（Vogel）法5.2.3确定初始基可行解最小元素法根据单位运价最低处优先供应的原则依次安排运输量最小元素法销地产地B1B2B3B4供应量A137645A224322A343853需求量323210单位运价最小元素法销地产地B1B2B3B4供应量A137645A222432
8、2A343853需求量323210最小元素法销地产地B1B2B3B4供应量A1317645A2224322A343853需求量323210最小元素法销地产地B1B2B3B4供应量A1317645A2224322A3432853需求量323210最小元素法销地产地
