运 筹 学作 业
一、填空题
1． 有m 个供应点、n 个需求点的运输问题是 m*n 个变量的线性规划 问
题的一种特殊情况。

当这个运输问题是供需平衡问题时，任一基解中基变量的个数为
＿
m+n-1 _ 。

2. 运输问题中求初始基本可行解的方法通常有 最小元素法 _、 西北角法 、
＿
沃格尔法 三种方法。

3.求解不平衡的运输问题的基本思想是 将产销不平衡问题化产销平衡问题
4.若运输问题已求得最优解，此时所求出的检验系数一定全部 大于等于
0 .
5．运输问题的检验数ij σ与对偶变量u i 、v j 之间存在关系
)
(j i ij ij v u c +-=σ
二、单项选择题
1、一个线性规划问题（P ）与它的对偶问题（D ）有关系（ B ）。

A 、（P ）求最大则（D ）求最小；
B 、（P ）、（D ）均有可行解则都有最优解；
C 、（P ）的约束均为等式，则（
D ）的所有变量均无非负限制； 2．若运输问题在总供应量大于总需要量，( C )。

A.必须用线性规划单纯形法求最优解; B .不存在可行解
C. 虚设一个需求点;
D. 虚设一个供应点
3．有6 个产地4个销地的平衡运输问题模型具有特征 ( B )。

A ．有10个变量24个约束;
B ．有24个变量10个约束
C ．有24个变量9个约束;
D ．有9个基变量10个非基变量
4. m+n －1个变量构成一组基变量的充要条件是( B )。

A ．m+n －1个变量恰好构成一个闭回路;
B ．m+n －1个变量不包含任何闭回路
C ．m+n －1个变量中部分变量构成一个闭回路;
D ．m+n －1个变量对应的系数列向量线性相关
5.有m 个产地n 个销地的平衡运输问题模型具有特征( c )。

A ．有mn 个变量m+n 个约束;
B ．有m+n 个变量mn 个约束
C ．有mn 个变量m+n －1约束;
D ．有m+n －1个基变量，mn －m －n －1个非基变量
3、请将下面线性规划问题化为对偶问题。

123412341342341234min 235352 24.. 60,,0,z x x x x x x x x x x x s t x x x x x x x =+-++-+≥⎧
⎪+-≤⎪⎨
++=⎪⎪≤≥⎩取值无约束
解：根据线性规划原问题同对偶问题的对应关系，可以很容易的得到下列的结果：
⎪⎪⎪⎩⎪
⎪⎪
⎨⎧≤≥=+--≤++-≤+≥+++=无约束
，，3213
2132131
2
13
21001
523322..645max y y y y y y y y y y y y y t s y y y ω
4、（15）某糖果经销公司的3个加工厂A 1、A 2、A 3每天产量分别为7吨、4吨、9吨；这些产品要运往4处经销点B 1、B 2、B 3、B 4，每天的销量为3吨、6吨、5吨、6吨；产销地点之间距离不同等因素形成的运价如下表：
1．请列出该问题的产销平衡表（问题2可在该表上分析）。

2．请采用表上作业法的最小元素法求出初始分配方案？该方法有何需要加以改进之处？
3．请采用闭回路法进行最优性检验，并求出最佳总费用。

2．用最小元素法，在产销平衡表上求出初始分配方案如下：
销地
1
B
2
B
3
B
4
B 产量
产地
A 1 3
11
(+1) 4
3
3 (-1) 10
7 A 2 3 1
9
(-1) 1
2
(+1)
8
4
A 3 7
6
4
10 3 5
9
销量 3 6 5 6 20
用最小元素法时，由于前面都是选择的最小的运价，未考虑后面的剩余物质运输的价格，不得不以更大的运价去安排运输业务。

造成局部的运价最优，而全局运价可能不是最优的情况。

应用沃格尔法法进行改进。

用闭回路法进行检验，在图中可找出如图中虚线表示的闭回路。

由于检验数1413232424c c c c ++-=∂= -1,0≤故知表中的解不是最优解，要进行解的改进。

该闭合回路的偶数顶点位于格（A 1，B 4）和（A 2，B 4），由于
{m i n },m i n 2314=x x {3，1}=1
故应对解作如下调整：124：加x ， 114：减x 113：加x ， 123：减x
再用闭回路法进行检验，结果示于下表中空格的小括号内。

由于所有非基变量的检验数全非负，故这个解为最优解。

销地
B 1 B 2 B 3 B 4 产量
产地
A 1 （0） 3
（4）
11
5
3
2 10
7
A 2 3 1
（2） 9 （1）
2
1 8 4
A 3 （27） 7
6
4
（36）
10
3
5
9
销量
3 6 5 6 20
此时，基变量个数仍为6个，这时的目标函数值等于
=Z m i n 3+24+15+20+8+15=85。