《运筹学运输问题.ppt》由会员分享，可在线阅读，更多相关《运筹学运输问题.ppt（17页珍藏版）》请在三一文库上搜索。
1、主讲教师 季敏,联系电话：13282105582（虚拟网：6000442430）,E-mail: ,清华大学出版社,运筹学教程（第二版）,运筹学基础,胡运权 主编,教材,诸如这类有多个不同的生产、消费者，如何合理不同的生产者和消费者之间的分配关系，达到最小费用的问题也运筹学最重要的问题之一。我们把这种分派问题称为运输问题。 在运筹学中，运输问题是一个广义的“运输”，即许多其它问题也可以通过适当的手段，把它们转化为运输问题加以解决。这部分也是我们这学期主要学习内容之一。,运输问题,某种物品先存放在两个仓库A1相A2中，再运往三个使用地B1，B2和B3，其间的 距离(或单位运价)如下表小方格中的数
2、据所示，各仓库的存量相使用地的需用量也 都示于下表中，试建立控总运输量(或总运费)最小的运输问题数学模型。,设： xij 从Ai地运往Bj地的货物数量,运价 min z= 3x11 + 4x12 + 2x13 + 3x21 + 5x22 + 3x23,x11 + x12 + x13 = 10,x21 + x22 + x23 = 4,x11 + x21 = 3,x12 + x22 = 5,x13 + x23 = 6,xij 0,产销运输问题的特点,x11 + x12 + x13 = 10 x21 + x22 + x23 = 4 x11 + x21 = 3 x12 + x22 = 5 x13 +
3、x23 = 6,1 1 1 10 1 1 1 4 1 1 3 1 1 5 1 1 6,1）运输问题最优解有界,2）运输问题系数矩阵非常特殊,3）运输问题约束都是等式约束,5）一般运输问题都是产销平衡的（不平衡问题要化为平衡问题）,4）一般运输问题约束有一个多余的约束,6）一般产m、销n有（m*n）个变量和（m+n）个约束（没有去掉多余）,7）产m、销n运输问题最多有（m+n-1）个值为非零的变量 因为有一个约束多余，既R（A）= m+n-1,运输问题求解方法： 表上作业法,例三,最小元素法,8,2,10,14,8,6,8,8,6,4,8,14,西北角法,运价：246,运价：372,例三,最小元
4、素法,8,2,14,8,6,10,8,8,6,4,8,14,运价：880,运价：456,西北角法,有没有搞错！,例三,最小元素法,8,2,14,问题就在这里 ！,沃格尔提出一种新的解决问题的方法,思路,例三,4,12,4,11,2,10,3,9,8,5,11,6,14,运价：244,8,12,8,2,5,1,3,0,1,1,2,运价：246 （最小元素法）,运价：372（西北角法）,怎样的安排为最优呢？,例三,a,b,c,d,闭回路检验法,例三,最小元素法,8,2,10,14,8,6,运价：246,b,例三,最小元素法,8,2,10,14,8,6,运价：246,b,0,例三,最小元素法,8,2
5、,10,14,8,6,运价：246,b,2,例三,最小元素法,8,2,10,14,8,4,运价：246,b,2,例三,最小元素法,8,2,12,14,8,4,运价：246,b,2,例三,最小元素法,8,0,12,14,8,4,运价：246,b,2,例三,最小元素法,8,12,14,8,4,运价：246,2,例三,8,0,12,14,8,4,b,9-11+4-3 =-1,-1,我们可以通过找出所有回路的方法来确定怎样调整运输计划，逐步使总运价降低。这种逐步调整运输计划直至达到最优解为止的方法称为闭合回路法。它的难点是每次找这些回路非常复杂。有更好的办法吗？,运输问题的数学模型（假定产销平衡）,目标函数：,产量约束：,销量约束：,xij 0,基变量对应的 应该等于零,