运筹学之运输问题

运输问题 案例

运 输 问题 (Transportation Problem)

运输问题 案例

一、运输问题的数学模型例：某运输问题的资料如下：单位 销地 运价 产地

B1 B2 B3 B42 1 8 3 9 3 4 8 10 4 2 4 2 2 5 6

产量

A1 A2 A3销量

9 5 7

运输问题 案例

设xij为运量 目标函数： Z 2 x11 9 x12 10x13 7 x14 x21 3 x22 min 4 x 23 2 x24 8 x31 4 x32 2 x33 5 x 34 x11 x12 x13 x14 9 x21 x22 x23 x 24 5 x31 x32 x33 x 34 7 x11 x21 x31 3 约束条件： x12 x22 x32 8 x13 x23 x33 4 x14 x24 x34 6 x 0 ( i 1.2.3, j 1.2.3.4) ij

运输问题 案例

数学模型的一般形式

已知资料如下：单 产地 销 产 量

B1

Bn

产 量

A1 Am销 量

c11 c1n cm1 cmn

a1 am

b bn 1

运输问题 案例

当产销平衡时，其模型如下：

minZ cij xiji 1 j 1

m

n

xij ai xij b j x 0 ij

( ai b j )

运输问题 案例

当产大于销时，其模型是：

minZ cij xiji 1 j 1

m

n

xij ai xij b j x 0 ij

( ai b j )

运输问题 案例

当产小于销时，其模型是：

m inZ c ij x ij x ij a i x ij b j ( a i b j ) x ij 0 并假设：a ij 0, b j 0, c ij 0

运输问题 案例

特征： 1、平衡运输问题必有可行解，也 必有最优解； 2、运输问题的基可行解中应包括 m+n-1 个基变量。

运输问题 案例

这是平衡的运输问题的数学模型，包含m×n个变量， m×n个约束方程。系数矩阵如下：x11 x12 x1n x21 x22 x2 n xm1 xm 2 xmn

1 1

1

1 1 1 1 1 1 1 1 1 1 1 1

1

1 1

m 行 n 行

运输问题 案例

二、表上作业法步骤：

⑴.找出初始基本可行解(初始调运方案，一 般m+n-1个数字格),用西北角法、最小元素法、 伏格尔法(Vogel) ; ⑵.求出各非基变量的检验数，判别是否达到 最优解。如果是停止计算，否则转入下一步，用 位势法计算； ⑶.改进当前的基本可行解(确定换入、换 出变量),用闭合回路法调整； ⑷.重复⑵. ⑶,直到找到最优解为止。

运输问题 案例

1、求初始方案：例一、某运输资料如下表所示：单位 销地 运价 产地

B1 B2 B3 B43 1 7 3 11 9 4 6 3 2 10 5 10 8 5 6

产量

A1 A2 A3销量

7 4 9

运输问题 案例

西北角法(或左上角法)此法是纯粹的人为的规定，没有理论依据 和实际背景，但它易操作，特别适合在计算机 上编程计算，因而受欢迎。

运输问题 案例

西北角法(或左上角法)1、先确定左上角变量的值，令它取尽可能的值。将 这个值填入该变量对应位置，并在该数字上画上圈。 画圈格子的对应的变量是基变量。

2、在画

圈格子所在的行或列应取0值的变量处填上× 号。当画圈格子所在行和列的其余变量都应取0时， 则或者只对行打×,不能同时对行或列都打×。打× 格子对应的变量是非基变量。3、对表中尚未画圈和打×的部分，重复1、2的手续。 若遇左上角变量取0值，则在该位置填0,并且同样画 上圈，对应变量仍是基变量。

运输问题 案例

⑵.最小元素法： 基本思想是就近供应，即从运价最小的地方开始供 应(调运),然后次小，直到最后供完为止。B1 A13 11

B23

B3 4

B410

产量 7

38

A2A3 销量

1

9

2

49

37 4 10

15

63 6 5

3 6

总的运输费用=(3×1)+(6×4) +(4×3)+(1×2)+(3×10)+(3×5)=86元

运输问题 案例

最小元素法 1、先确定运价最小的格子所对应的变量值。若有几 个格子同时达到最小运价，则可任取一个。令该变 量取尽可能大的值。将此值填入该变量对应位置并 画圈。画圈的格子对应的变量是基变量。2、在画圈格子所在的行或列应取0值的变量处填上 ×号。当画圈格子所在行和列的其余变量都应取0时， 则或者只对行打×,不能同时对行或列都打×。打 ×格子对应的变量是非基变量。 3、对表中尚未画圈和打×的部分，重复1、2的手续。 当表剩余部分仅是一行或一列时，确定其最小运价 对应变量后，不管其余元素是否取零值，都不能打 ×,应作剩余部分处理。

运输问题 案例

闭回路

集合{xi1 j1 , xi1 j2 , xi2 j2 , xi2 j3 , , xis js , xis j1 } (i1 , i2 , , is ; j1 , j2 , , js互不相同) 为一个闭回路。集合中的变量称为闭回路的顶点，相邻两个变量的 连线为闭回路的边。 性质：回路中的顶点必是偶数，在运输表中，回路 遇到顶点必须转90度与另一顶点连接。