生长法

根据生长法的基本原理，得以下计算表 .------（3分）

v2 v3 v4 v5 v6 {2} 6 3 {3} S1 v2 ? 8 8 5 5 ? 9 9 3 {3} ? ? ? ? ? 1 {1} S2 v3 S3 v5 ? 5 3 {3} S4 v6 S5 据此也得到与破圈法相同的最短树。 .------（6分）

五、简答题(每小题10分，共20分)

1．试述单纯形法的计算步骤，并说明如何在单纯形表上判断问题是具有唯一最优解、无穷多最优解和无有限最优解。 解：1：单纯形法的计算步骤

第一步：找出初始可行解，建立初始单纯形表。

第二步：判断最优，检验各非基变量若所有的

xj的检验数

?j?CBB?1Pj?Cj。

?j?0，则基B为最优基，相应的基可行解即为基本最优解，计算停止。

若所有的检验数

?j?0，又存在某个非基变量的检验数所有的

?k?0，则线性规划问

题有无穷多最优解。

若有某个非基变量的检验数

?j?0，并且所对应的列向量的全部分量都非正，则该线

性规划问题的目标函数值无上界，既无界解，停止计算。

第三步：换基迭代

当存在

?k?0，选xk进基来改善目标函数。若检验数大于0的非基变量不止一个，则

xkxr可以任选其中之一来作为进基变量。

进基变量

确定后，按最小比值原则选择出基变量

。若比值最小的不止一个，选择

其中之一出基。

做主元变换。

反复进行上述过程就可以找到最优解或判断出没有有限最优解。 ------（3分）

2．简述最小费用最大流问题的提法以及用对偶法求解最小费用最大流的原理和步骤。

解：2：最大流问题就是在一定条件下，要求流过网络的物流、能量流或信息流等流量最大的问题。如果已知流过弧

(vi,vj)的单位流量要发生

cij的费用，要求使总费用为最小的

最大流流量分配方法。即在上述最大流问题上还应增加关于费用的目标：种问题称为最小费用最大流问题。模型可以描述为：

min?xijcij。这

min?xijcijmaxf??f????xij??xji??0s.t.?jj??f???0?xij?bij?vsvti?si?s,ti?t

采用对偶法求解最大流最小费用问题，其原理为：用福德—富克逊算法求出网络的最大流量，然后用Ford算法找出从起点

到终点

的最短增广链。在该增广链上，找出最大调

整量?，并调整流量，得到一个可行流。则此可行流的费用最小。如果此时流量等于最大流量，则目前的流就是最小费用最大流，否则应继续调整。

对偶法的步骤归纳如下：

第0步：用最大流方法找出网络最大流量fmax，并以0流作为初始可行流。 第一步：对于当前可行流，绘制其扩展费用网络图。

第二步：用Ford算法求出扩展费用网络图中从vs到vt的最短路。

第三步：在最短路线对应的原网络中的增广链上，调整流量，得到新的可行流。 第四步：绘制可行流图。若可行流的流量等于最大流量流，算法结束；否则从第一步开始重复上述过程

fmax，则已找到最小费用最大