第二章-运输问题

1、2.4 运输问题2.4.1 运输问题的一般模型2.4.2 表上作业法2.4.3 产销不平衡问题 2.4.1 运输问题的一般模型运输问题的一般模型一、一般提法一、一般提法1、产销平衡问题、产销平衡问题 A1（a1） A2（a2） 产地：产地： . . . Am（am） B1（b1） B2（b2） 销地：销地： . . . Bn（bn）已知从已知从Ai到到Bj的单位运价为的单位运价为cij,且且njjmiiba11问题：如何制定最合理的物资调运方案，问题：如何制定最合理的物资调运方案， 使总运费最低？使总运费最低？ 2、产销不平衡问题、产销不平衡问题（化为产销平衡问题来 解决）供不应求：供大于求：

2、njjmiiba11njjmiiba11 例：某食品公司下设3个加工厂和4个门市部，各加工厂每天的产量和各门市部每天的销量及运价如表： 门市部加工厂B1B2B3B4产量A13113107A219284A3741059销量365620A2A3B2A1B3B4B1运输问题网络图a2=4a3=9b1=3b2=6b3=5b4=6a1=7供应量供应地运价需求量需求地311310192874105二、模型设从设从Ai 到Bj的运量是xij(i=1,2,3;j=1,2,3,4),z为总费用。min z =3x11+11x12+3x13+10 x14 +x21+ 9x22+ 2x23+ 8x24 +7x31+

3、4x32+10 x33+5x34 x11+ x12+ x13+ x14=7 x21+ x22+ x23+ x24=4 x31+ x32+ x33+ x34=9 x11+ x21 + x31 =3 x12 + x22+ x32 =6 x13 + x23 + x33 =5 x14 + x24+ x34 =6 xij0 (i=1,2,3 ; j=1,2,3,4) 运输问题的一般模型运输问题的一般模型 有有m m个产地生产某种物资，有个产地生产某种物资，有n n个地区需要个地区需要该类物资。该类物资。 令令a a1 1, , a a2 2, , , , a am m表示各产地产量，表示各产地产量，b

4、b1 1, , b b2 2, , , , b bn n表示各销地的销量，表示各销地的销量， a ai i= = b bj j 称为产销平衡。称为产销平衡。 设设x xijij表示产地表示产地 i i 运往销地运往销地 j j 的物资量，的物资量，c cijij表示对应的单位运费，则我们有运输表示对应的单位运费，则我们有运输问题的数学模型如下：问题的数学模型如下： 0 ,2, 1 ,2, 1min1111ijjmiijnjiijminjijijxnjbxmiaxxcZ销量约束产量约束u运输问题有运输问题有m n个决策变量，个决策变量，m+n个约束个约束条件。由于有产销平衡条件，只有条件。由于有

5、产销平衡条件，只有m+n1个个约束相互独立，因此，运输问题的基变量只约束相互独立，因此，运输问题的基变量只有有m+n1 个个.模型特点：（1）有有限最优解）有有限最优解（2）系数矩阵中每列只有两个）系数矩阵中每列只有两个1，其余全，其余全 为为0。（3）基变量的个数）基变量的个数=m+n-1运输问题的表格表示2.4.2 表上作业法表上作业法运输问题的求解步骤运输问题的求解步骤确定初始可行方案（最小元素法）确定初始可行方案（最小元素法）最优性检验（闭回路法）最优性检验（闭回路法）调整新方案调整新方案方法：最先满足最小的运费安排调运。方法：最先满足最小的运费安排调运。 总是从运价表中找最小元，优先

6、满足供应，填上总是从运价表中找最小元，优先满足供应，填上相应运量后划去一线（最后划两线）。相应运量后划去一线（最后划两线）。一、确定初始可行方案-最小元素法314336初始解：初始解：x13 =4 ，x14 =3 ，x21=3，x23 =1，x32 =6，x34 =3，其余，其余xij=0相应的运费为：相应的运费为：Z0=34+103+13+21+46+53=86v方法评价：优点：较简便易行，方法评价：优点：较简便易行， 有目标观念。有目标观念。 缺点：只从单一格出发，缺点：只从单一格出发， 无全局观念。无全局观念。u注：注：（1）有数字格表示基变量，）有数字格表示基变量，其个数为其个数为m+

7、n-1，空格表示非基变量。，空格表示非基变量。（2）每填上一个数后，则只能划去一行（）每填上一个数后，则只能划去一行（或一列）。或一列）。（3）若中间过程填上一个数后，同时划去一）若中间过程填上一个数后，同时划去一行和一列，有数字格的个数将少行和一列，有数字格的个数将少1个，这时，个，这时，要在所划去的该行（或该列）上任意一格填要在所划去的该行（或该列）上任意一格填一个一个0，此格当有数格对待。，此格当有数格对待。二、最优性检验二、最优性检验-（计算空格检验数）（计算空格检验数）要求：除此空格外，其余顶点均为有要求：除此空格外，其余顶点均为有数格。数格。方法：方法： 找出每个空格的闭回路。找出

8、每个空格的闭回路。闭回路：由水平或垂直线组成的闭合闭回路：由水平或垂直线组成的闭合图形。图形。314336（2）计算每个空格的检验数。）计算每个空格的检验数。 等于其闭回路上由此空格起奇数顶点运价与偶数等于其闭回路上由此空格起奇数顶点运价与偶数顶点运价的负值之和。顶点运价的负值之和。31433611=3-3+2-1=112=11-10+5-4=222=9-2+3-10+5-4=124=8-10+3-2=-131=7-5+10-3+2-1=1033=10-3+10-5=12（3）若所有）若所有ij0，则当前方案是最优方，则当前方案是最优方案，否则转第三步调整新方案。案，否则转第三步调整新方案。注

9、：运输问题检验数的经济意义：注：运输问题检验数的经济意义： 当该空格增运当该空格增运1单位时引起的总运单位时引起的总运费的增量。费的增量。本例中由于本例中由于24=-1销销1、模型、模型 0 ,2, 1 ,2, 1min1111ijjmiijnjiijminjijijxnjbxmiaxxcZ2、方法、方法增加一个虚设的销地，其销量为增加一个虚设的销地，其销量为ai-bj。例：求解下面的运输问题。例：求解下面的运输问题。虚拟一个销地8145411=2-4+3-1=023=6-5+4-3=224=0-0+4-3=1所有所有ij0,得到最优解。得到最优解。最优解：最优解：x12* *=1，x13 * *=4， x14* * =5 ，x21* *=8， x22* *=4，其，其余余xij* *=