运输问题表上作业法.pptVIP

7.4表上作业法

1表上作业法迭代步骤

2按某种规则找出一个初始基可行解；

对现行解作最优性判断，即求各非基变量的检验数，判别是否达到最优解，如已是最

3优解，则停止计算，如不是最优解，则进行下一步骤；

在表上对初始方案进行改进，找出新的基可行解，再按第二步进行判别，直至找出最

4优解。

是

确定初始方案判定是否

结束

(初始最优？

基本可行解)

否

最优方案

改进调整

（换基迭代）

图1运输问题求解思路图

01初始基本可行解的确02例2：甲、乙两个煤矿

定供应A、B、C三个城

市用煤，各煤矿产量

及各城市需煤量、各

煤矿到各城市的运输

单价见表所示，求使

总运输费用最少的调

运方案。

例题有关信息表

运距城市日产量

（供应量）

煤矿ABC

甲9070100200

乙806575250

日销量

（需求量）100150200450

例题数学模型

minZ90x1170x12100x1380x2165x2275x23总运输量

x11x12x13200

日产量约束

x21x22x23250

x11x21100

s.t.

需求约束

x12x22150

xx200

1323



xij0,i1,2;j1,2,3;

最小元素法：从运价最小的格开始，在格

内的标上允许取得的最大数。然后按运价

从小到大顺序填数。若某行（列）的产量

（销量）已满足，则把该行（列）的其他

格划去。如此进行下去，直至得到一个基

本可行解。

用最小元素法确定初始调运方案

调销地

运量产B1B2B3产量

地

100100100

9070100

A200

1150100100

XX

1112X13

806575

A2100250