05运筹学-运输问题.ppt

主讲教师季敏,联系电话虚拟网：6000442430）,E-mail:jimin,清华大学出版社,运筹学教程（第二版）,运筹学基础,胡运权主编,教材,诸如这类有多个不同的生产、消费者，如何合理不同的生产者和消费者之间的分配关系，达到最小费用的问题也运筹学最重要的问题之一。我们把这种分派问题称为运输问题。在运筹学中，运输问题是一个广义的“运输”，即许多其它问题也可以通过适当的手段，把它们转化为运输问题加以解决。这部分也是我们这学期主要学习内容之一。,运输问题,某种物品先存放在两个仓库A1相A2中，再运往三个使用地B1，B2和B3，其间的距离(或单位运价)如下表小方格中的数据所示，各仓库的存量相使用地的需用量也都示于下表中，试建立控总运输量(或总运费)最小的运输问题数学模型。,设：xij从Ai地运往Bj地的货物数量,运价minz=3x11+4x12+2x13+3x21+5x22+3x23,x11+x12+x13=10,x21+x22+x23=4,x11+x21=3,x12+x22=5,x13+x23=6,xij0,产销运输问题的特点,x11+x12+x13=10 x21+x22+x23=4x11+x21=3x12+x22=5x13+x23=6,111101114113115116,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,例三,最小元素法,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,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,我们可以通过找出所有回路的方法来确定怎样调整运输计划，逐步使总运价降低。这种逐步调整运输计划直至达到最优解为止的方法称为闭合回路法。它的难点是每次