第3章+运输问题-第1,2节

第3章

运输问题

第1节运输问题的数学模型第2节表上作业法第3节产销不平衡的运输问题及其求解方法第4节应用举例

第1节运输问题的数学模型 已知有m个生产地点Ai,i=1,2,…,m。可供应某种物资，其供应量(产量)分别为 ai,i=1,2,…,m,有n个销地Bj, j=1,2,…,n,其需要量分别为bj, j=1,2,…,n,从Ai到Bj运输单位物资的运价(单价)为cij,这些数据可汇总于产销平衡表和单位运价表中，见表3-1,表3-2。有时可把这两表合二为一。

表3-1产销平衡表销地产地

1 2… n

产量 a1 a2┆ am

1 2┆ m销量 b1 b2… bn

表3-2单位运价表销地产地

1

2┉

n

1 2┆ m

c11 c12┈ c1n c21 c22┈ c2n┇ cm1 cm2┈ cmn

产销平衡表和单位运价表销地产地

1

2

… n

产量 a1 a2┆ am

1 2┆ m销量

c11 c12┈ c1n c21 c22┈ c2n┇ cm1 cm2┈ cmnb1 b2… bn

若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型

min z=∑∑ cij xiji=1 j= 1

m

n

m ( 3 1) ∑ xij= b j j= 1, 2,, n i=1 n s.t . ∑ xij= ai i= 1, 2,, m ( 3 2) j=1 x≥ 0 ij m×n个变量，(m+n)个约束方程

其系数矩阵的结构比较松散，且特殊x11 x12 x1n x21 x22 x2 n 1 1 1 1 1 1 xm 1 xm 2 xmn 1 1 m行 n行 u1 1 1 1 u2 1 1 i um m+j v1 1 1 v2 1 1 vn 1

该系数矩阵中对应于变量xij的系数向量Pij,其分量中除第i个和第m+j个为1以外，其余的都为零。即 Pij=(0,…,1,0,…,0,1,0,…,0)T=ei+em+j

对产销平衡的运输问题，有以下关系式存在： n m ∑ b j=∑ ∑ xij =∑ ∑ xij =∑ ai j=1 j=1 i=1 i=1 j=1 i=1n n m m

模型最多只有n+m-1个独立约束方程系数矩阵的秩≤n+m-1

第2节表上作业法 表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为： (1)找出初始基可行解。即在(m×n)产销平衡表上用西北角法或最小元素法，Vogel法给出m+n-1个数字，称为数字格。它们就是初始基变量的取值。 (2)求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。 (3)确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。 (4)重复(2),(3)直到得到最优解为止。

例1某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2

为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价为表33所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少

解:作出这问题的产销平衡表和单位运价表表3-3单位运价表销地加工厂 B1 B2 B3 B4

A1 A2 A3

3 1 7

11 9 4

3 2 10

10 8 5

表3-4销地加工厂 B1

产销平衡表B2 B3 B4产量

A1 A2 A3销量

7 4 9 3 6 5 6

2.1

确定初始基可行解

这与一般线性规划问题不同。 产销平衡的运输问题总是存在可行解。 m n因有∑ ai=∑ b j= di=1 j=1

必存在xij≥0,i=1,…,m,j=1,…,n这就是可行解 又因0≤xij≤min(ai,bj)故运输问题必存在最优解。

确定初始基可行解的方法 西北角法 最小元素法 伏格尔(Vogel)法 一般希望的方法是既简便，又尽可能接近最优解

1.

最小元素法

这方法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基可行解为止 以例1进行讨论。第一步：从表3-3中找出最小运价为1,这表示先将A2的产品供应给B1。因a2>b1,A2除满足B1的全部需要外，还可多余1吨产品。在表3-4的(A2,B1)的交叉格处填上3。得表3-5。并将表3-3的B1列运价划去。得表3-6。

表 3-5 .表3-6销地加工厂 A1 A2 A3销量销地加工厂 A1 A2 A3

B1

B2

B3

B4

3 3B1 3 1 7

产量 7 4 9

6B2 11 9 4

5B3 3 2 10

6B4 10 8 5

第二步：在表3-6未划去的元素中再找出最小运价2,确定A2多余的1吨供应B3销地加工厂 B1 B2 B3 B4产量

表3-7

A1 A2 A3销量销地

3 3 B1 3 1 7 6 B2 11 9 4

1 5 B3 3 2 10 6 B4 10 8 5

7 4 9

表3-8

加工厂 A1 A2 A3

第三步：在表未划去的元素中再找出最小运价3,确定A1的4吨供应B3销地加工厂 B1 B2 B3 B4产量

A1 A2 A3销量销地加工厂 A1 A2 A3

3 3 B1 3 1 7 6 B2 11 9 4

4 1 5 B3 3 2 10 6 B4 10 8 5

7 4 9

本文来源：https://www.bwwdw.com/article/mzri.html