第三章 特殊的线性规划问题
第一节 运 输 问 题
人员、物资的流动在社会生产实践中是极其频繁且普遍的. 我们经常需要把某些货物从一些地方运送到另一些地方，在制定运输方案时，考虑最多的是运输费用是否最低？例如：要从甲、乙两地向A、B运送100t药材，每吨运费（单位：百元）及供需情况见表3-1：
表3-1 药材供应、需求量和单位运价表
单 位 运 供 应 费 点 需 求 点 A城 B城 供应量（t） 甲地 乙地 需求量(t) 1 5 30 2 10 70 40 60 通常人们总是将单位运费最低的优先安排，其次考虑运费次低的线路. 这样从甲地运30t到A城，运10t到B城；从乙地运60t到B城，该方案的总费用为: 30×1+10×2+60×10=650（百元）.
值得注意的是，我们虽然每次都优先考虑运费最小的线路，但最终方案的总费用未必最少. 如上面问题可安排从甲地运40t给A城，乙地分别运30t给A、B两城，从而总费用为: 40×2+30×5+30×10=530（百元）．
出现这种现象主要是因为局部最优不等于全局最优，或者说局部最优的简单相加不等于全局最优，所以我们有必要研究运输问题. 事实上它属于线性规划问题的范畴，但由于其约束方程组的系数矩阵具有特殊的结构，可以找到一种比单纯形法更简便的求解方法——表上作业法.
一、运输问题的模型和特征
运输问题的一般提法是这样的：某种物资有m个产地：A1, A2, ??, Am.
- 1 -
需要运到n个销地B1, B2, ??, Bn；Ai的产量为ai ；Bj的销量为bj，并且
?a??b（即供需平衡． 若供需不平衡可以经过适当调整，转化为供需平衡
iji?1j?1mn问题来解决）．若已知货物从Ai运到Bj的单位运费为cij (i =1、2??m, j=1、2??n), 试问如何组织调运，既能满足供销需要，又能使总运费为最少？
令决策变量xij表示从Ai运到Bj的物资数量，则该问题为求解所有xij使总的运输费用??cijxij达到最少．该问题的数学模型可写为
i?1j?1mnMinZ???cijxij
i?1j?1mn?m??xij?bj,j??,?,?,n?i???ns.t.??xij?ai,i??,?,?,m
?j???x??,对所有的i,j?ij?很显然，运输问题是一个有m×n个变量、m +n个约束方程的线性规划问题，其系数矩阵A如下：
x11x12?x1nx21x22?x2n?xm1xm2?xmn
????m行???????n行????11?1???11?1???????11?1? A???1 1 1??? 1 1 1??? ? ? ???? 1 1 1????
与前面各节遇到的规划相比，运输问题的特征是：①在产销平衡时，运输问题一定有可行解，且有最优解. ②当产量与销量均为整数时，必存在决策变量为整数的最优解. ③决策变量的系数只有0和1，系数矩阵A有m +n行、m n列，秩为m+n-1，从而有m+n-1个基变量. ④运输问题的m+n-1个基变量不构成
- 2 -
闭回路.
所谓“闭回路”是指当运输问题用下面的表格形式（表3-2）给出时，一组变量能连成如下形式，如图3-1所示，我们就称该变量组构成闭回路.
其实闭回路就是一条封闭折线，每个顶点都是转角点. 设m =4,n =5,将变量组?x21,x22,x32,x35,x15,x13,x43,x41,x21?表示为图3-2. 显然，该变量组形成一闭回路.
表3-2 运 输 表
销地 产地 A1 ?? Am 销量 x11 xm1 b1 cm1 B1 c11 x12 xm2 b2 cm2 ?? B2 c12 ?? xmn bn ?? ?? x1n cmn Bn c1n 产量 a1 ?? am x11x12x11x12x22x23x31x13x14x34x21x22x31x33图3-1 闭回路类型图
x41x43
?x21 x41 ? ? x22 x32 ? x13 ? ?x43 ? x15 ?x35 图3-2 闭回路示意图
定理3-1 运输问题的m+n-1个变量构成基变量的充要条件是不含闭回
- 3 -
路．（证明略）．相应地从一个非基变量出发，存在且惟一存在一条闭回路．
二、用表上作业法求解运输问题
基于运输问题的上述特殊性，求解运输问题的单纯形法就可以大大简化，对求极小化问题来说，这种解法能在表上进行——表上作业法．其基本步骤是：
1．编制初始调运方案（即确定初始基本可行解） 常用的方法有西北角法和最小元素法；
2．最优性检验（即求出相应的检验数） 常用方法有闭回路法和位势法； 3．解的改进 根据检验数确定方案是否最优，是则终止，否则采用闭回路法调整，再返回到第2步，直至最优．
（一）编制初始调运方案
以一个实例介绍初始基本可行解的确定．
例3-1 某省医疗队从A1、 A2 、A3三所省级医院抽调骨干医护人员配备必要设备去B1、B2、B3、B4四个贫困县进行巡回医疗扶贫，各医院抽调的人数、各县需要人数、以及从医院到各县的人均（包括设备交通）费用如表3-3所示，问如何安排可使总费用最小？
表3-3 运输问题的人均费用表
B1 B2 B3 B4 人均费用（单位：百元）
A1 A2 A3 县需求人数
医院抽出人数
2 9 10 7 9 1 3 4 2 5 8 4 2 5 7 3 8 4 6
初始调运方案就是找到一组初始可行基，即找到m＋n－1=3＋4－1=6个正整数填入它的运输表3-4，使满足约束条件．
（1）西北角法 所谓西北角法就是从表3-4的左上角第一格开始安排运输计划． 方法是：取其对应医院抽出数与县城需要数的最小值作为初始基本可行解的第一个分量值（x11?min?a1,b1?）． 这样第一列的需求已经满足，用线划去第一列，再看第二列、第一行，由于抽出数还有9-3=6，与B2的需求数8比较，
- 4 -
取最小值6（x12?min?a1?x11,b2?）填入该格． 依此次序进行，即可得到第一个基本可行解，见表3-4．
表3-4 运输问题作业表——西北角法
县城 医院 A1 3 A2 A3 医院抽B1 2 1 8 3 8 2 4 6 3 1 4 B2 9 3 4 2 B3 10 6 B4 7 出人数 9 2 5 5 7 县需人数 6 （2）最小费用法 西北角法的优点是简单、易实现，但没有考虑最小费用． 可能要经过许多次迭代才能得到最优解． 而最小费用法的基本思想是就近供应， 优先考虑最小单位运费对应的xij， 这样得到的方案会更接近最优方案．以例3-1来说明具体步骤．
表3-5 运输问题作业表——最小费用法
县城 医院 A1 医院抽B1 2 1 8 ③ 3 8 4 ⑤ 3 ④ 4 B2 9 4 2 B3 10 ④ ② B4 7 出人数 9 2 5 5 7 A2 A3 ③ 县需人数 6 在运输表3-5中，单位运费cij最小的是c21?1. 这个格子处于A2行B1列，因而最多可供5人，但需求量为3人，于是，在这个格子里填上尽可能大的数是
- 5 -