第六章运输问题
1 第六章运输问题
运输问题的模型
2 运输问题的模型
运输问题的描述 运输问题的一般提法是这样的:某种物资 有若干个产地和销地,若已知各个产地 的产量、各个销地的销量以及各产地到 各销地的单位运价(或运输距离)。问 应如何组织调运,才能使总运费(或总 的运输量)最省? 将此问题更具体化,假定有m个产地,n 个销地
3 运输问题的描述 运输问题的一般提法是这样的：某种物资 有若干个产地和销地，若已知各个产地 的产量、各个销地的销量以及各产地到 各销地的单位运价（或运输距离）。问 应如何组织调运，才能使总运费（或总 的运输量）最省？ 将此问题更具体化，假定有m个产地，n 个销地
a1第i产地的供应量,i=1,2 b第销地的需求量,j=1,2,…,n Cn-从i产地到j销地的单位运费,i=1, 2,…,m,j=1,2,…,n xi产地到销地的调运数量。 则该问题为求解最佳调运方案,即求解所 有x的值,使总的运输费用m、达到 最少。决策变量为x1 ∑∑cnx i=1j=1
4 ai—第i产地的供应量，i=1，2，…，m。 bj—第j销地的需求量，j=1，2，…，n。 cij—从i产地到j销地的单位运费，i=1， 2，…，m，j=1，2，…，n。 xij—i产地到j销地的调运数量。 则该问题为求解最佳调运方案，即求解所 有xij的值，使总的运输费用 达到 最少。决策变量为xij 。 1 1 m n ij ij i j c x = =
般模型形式 minZ=∑∑c,x i=1j=1 ∑x≥b,j=1,2,…,n s. x≤a i=1.2 x≥0,所有的i,j
5 一般模型形式 1 1 min m n ij ij i j Z c x = = = 1 1 , 1,2, , . . , 1,2, , 0, m ij j i n ij i j ij x b j n s t x a i m x = = = = 所有的i，j