运筹学运输问题

1、运筹学运输问题 诸如这类有多个不同的生产、消费者，如何合理不同的生产者和消费者之诸如这类有多个不同的生产、消费者，如何合理不同的生产者和消费者之间的分配关系，达到最小费用的问题也运筹学最重要的问题之一。我们把这种间的分配关系，达到最小费用的问题也运筹学最重要的问题之一。我们把这种分派问题称为运输问题。分派问题称为运输问题。 在运筹学中，运输问题是一个的在运筹学中，运输问题是一个的“运输运输”，即许多其它问题也可以通过适，即许多其它问题也可以通过适当的手段，把它们转化为运输问题加以解决。这部分也是我们这学期主要学习当的手段，把它们转化为运输问题加以解决。这部分也是我们这学期主要学习内容之一。内容

2、之一。运输问题运输问题 某种物品先存放在两个仓库某种物品先存放在两个仓库A1A1相相A2A2中，再运往三个使用地中，再运往三个使用地B1B1，B2B2和和B3B3，其间的其间的距离距离( (或单位运价或单位运价) )如下表小方格中的数据所示，各仓库的存量相使用地的需用量也如下表小方格中的数据所示，各仓库的存量相使用地的需用量也都示于下表中，试建立控总运输量都示于下表中，试建立控总运输量( (或总运费或总运费) )最小的运输问题数学模型。最小的运输问题数学模型。设：设： x xijij 从从A Ai i地运往地运往B Bj j地的货物数量地的货物数量运价运价 z= 3x z= 3x1111 +

3、4x + 4x12 12 + 2x+ 2x13 13 + + 3x3x2121 + 5x + 5x22 22 + 3x+ 3x2323x x1111 + x + x12 12 + x+ x13 13 = 10= 10约束约束条件条件st.st. x x2121 + x + x22 22 + x+ x23 23 = 4= 4x x1111 + x + x21 21 = 3= 3 x x1212 + x + x22 22 = 5= 5 x x1313 + x + x23 23 = 6= 6x xij ij 0 0产销运输问题的特点产销运输问题的特点x x1111 + x + x12 12 + x+

4、 x13 13 = 10= 10 x x2121 + x + x22 22 + x+ x23 23 = 4= 4x x1111 + x + x21 21 = 3= 3 x x1212 + x + x22 22 = 5= 5 x x1313 + x + x23 23 = 6= 61 1 1 101 1 1 10 1 1 1 4 1 1 1 41 1 31 1 3 1 1 5 1 1 5 1 1 6 1 1 6 1）运输问题最优解有界）运输问题最优解有界2）运输问题系数矩阵非常特殊）运输问题系数矩阵非常特殊3）运输问题约束都是等式约束）运输问题约束都是等式约束5）一般运输问题都是产销平衡的（不平衡

5、问题要化为平衡问题）一般运输问题都是产销平衡的（不平衡问题要化为平衡问题）4）一般运输问题约束有一个多余的约束）一般运输问题约束有一个多余的约束6）一般产）一般产m、销销n有（有（m*n）个变量和（个变量和（m+n）个约束（没有去掉多余）个约束（没有去掉多余）7）产）产m、销销n运输问题最多有（运输问题最多有（m+n-1）个值为非零的变量个值为非零的变量 因为有一个约束多余，既因为有一个约束多余，既R（A）= m+n-1运输问题求解方法：运输问题求解方法：表上作业法表上作业法例三例三 B1B2B3B4产量A116A210A322销量8141214484 412124 411112 210103

6、 39 98 85 511116 6最最小小元元素素法法 B1B2B3B4产量A116A210A322销量8141214484 412124 411112 210103 39 98 85 511116 6西西北北角角法法运价：运价：246运价：运价：372例三例三 B1B2B3B4产量A116A210A322销量8141214484 48 8505040402 210103 39 98 85 511116 6最最小小元元素素法法运价：运价：880运价：运价：456 B1B2B3B4产量A116A210A322销量8141214484 48 8505040402 210103 39 98 85

7、511116 6西西北北角角法法例三例三 B1B2B3B4产量A116A210A322销量8141214484 48 8505040402 210103 39 98 85 511116 6最最小小元元素素法法例三例三 B1B2B3B4产量A116A210A322销量8141214484 412124 411112 210103 39 98 85 511116 6运价：运价：244列列罚罚数数12345行罚数2513011213012212011276200运价：运价：246 （最小元素法）（最小元素法）运价：运价：372（西北角法）（西北角法）怎样的安排为怎样的安排为最优最优呢？呢？例三例三

8、B1B2B3B4产量A116A210A322销量8141214484 412124 411112 210103 39 98 85 511116 6 B1B2B3B4产量A116A210A322销量814121448afbcde cbjiahgfed例三例三 B1B2B3B4产量A116A210A322销量8141214484 412124 411112 210103 39 98 85 511116 6最最小小元元素素法法运价：运价：246b例三例三 B1B2B3B4产量A116A210A322销量8141214484 412124 411112 210103 39 98 85 511116 6

9、最最小小元元素素法法运价：运价：246b例三例三 B1B2B3B4产量A116A210A322销量8141214484 412124 411112 210103 39 98 85 511116 6最最小小元元素素法法运价：运价：246b例三例三 B1B2B3B4产量A116A210A322销量8141214484 412124 411112 210103 39 98 85 511116 6最最小小元元素素法法运价：运价：246b例三例三 B1B2B3B4产量A116A210A322销量8141214484 412124 411112 210103 39 98 85 511116 6最最小小元元

10、素素法法运价：运价：246b例三例三 B1B2B3B4产量A116A210A322销量8141214484 412124 411112 210103 39 98 85 511116 6最最小小元元素素法法运价：运价：246b例三例三 B1B2B3B4产量A116A210A322销量8141214484 412124 411112 210103 39 98 85 511116 6最最小小元元素素法法运价：运价：246244例三例三 B1B2B3B4产量A116A210A322销量8141214484 412124 411112 210103 39 98 85 511116 6b B1B2B3B4

11、产量A116A210A322销量8141214484 412124 411112 210103 39 98 85 511116 69-11+4-39-11+4-3=-1=-1 我们可以通过找出所有回路的方法来确定怎样调整运输计划，逐步使总运价降我们可以通过找出所有回路的方法来确定怎样调整运输计划，逐步使总运价降低。这种逐步调整运输计划直至达到最优解为止的方法称为低。这种逐步调整运输计划直至达到最优解为止的方法称为闭合回路法闭合回路法。它它的难点是每次找这些回路非常复杂。有更好的办法吗？的难点是每次找这些回路非常复杂。有更好的办法吗？ 运输问题的数学模型运输问题的数学模型（假定产销平衡）目标函数：目标函数：nmj=1 i=1min Z = Cij xijnj=1 xij = ai i=1,2,m产量约束：产量约束：销量约束：销量约束：mi=1 xij = bj j=1,2,n