解线性规划问题的内生典式单纯形法

An Endogenous Typical form Simplex Method for Solving Linear Programming Problems

摘要: 对于线性规划问题的约束方程组对应的系数矩阵中没有子矩阵为单位矩阵，如大M法、两阶段法、对偶单纯形法等，都是采取“凑一个单位矩阵”出来，然后进行求解，过程繁琐、迭代次数较多。针对这一问题，采用实验法、分析法和比较法，对线性规划问题的求解过程进行研究，根据约束方程组的内在联系，利用消元法，从系数矩阵中推导出一个单位矩阵，从而使问题得以解决，因此提出了求解线性规划问题的内生典式单纯形法。实验结果显示，内生典式单纯形法适用题型多，求解快捷，迭代次数平均为0.75次。

Abstract: There is no sub matrix in the coefficient matrix corresponding to the constraint equations of the linear programming problem as the unit matrix, such as the large M method, the two-stage method, the dual simplex method, etc., which are all “gathered together a unit matrix” and then solved. The process is cumbersome and the number of iterations is large. In order to solve this problem, ex-perimental method, analytical method and comparative method are used to study the solution process of the linear programming problem. According to the internal relationship of the constraint equations, a unit matrix is derived from the coefficient matrix by elimination method, so that the problem can be solved. Therefore, an endogenous typical form simplex method for solving the line-ar programming problem is proposed. The experimental results show that the endogenous typical form simplex method is applicable to many types of questions, fast in solving, and the average number of iterations is 0.75.

1. 引言

单纯形法解线性规划问题，常常遇到约束方程组的系数矩阵中没有单位向量，或单位向量的个数不够，需要补充所缺的单位向量，因而产生了大M法、两阶段法、对偶单纯形法等。然而，约束方程组的系数矩阵中是存在基矩阵的 [1]。能不能在这些基矩阵中经过方程组的行初等变换，化出一个单位矩阵来呢？经过不断的实践，反复的演算 [2]，终于找到了解决这一问题的方法——内生典式单纯形法。

2. 基础理论知识

线性规划问题的一般模型为 [3]

$\begin{array}{c}\max 或\min z=CX\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}AX\le \left(或=,\ge \right)b\\ X\ge 0\end{array}\end{array}\stackrel{其标准型为}{\to }\begin{array}{c}\max z=CX\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}AX=b\\ X\ge 0\end{array}\end{array}$。

现在设 $A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right]=\left(P_1,P_2,\cdots ,P_m,P_{m+1},\cdots ,P_n\right)=\left(B,N\right)$。

其中 $B=\left(P_1,P_2,\cdots ,P_m\right)$， $N=\left(P_{m+1},\cdots ,P_n\right)$. $P_1,P_2,\cdots ,P_m$ 为基向量， $P_{m+1},\cdots ,P_n$ 为非基向量。

$X=\left[\begin{array}{c}{X}_B\\ X_N\end{array}\right]$，其中 $X_B={\left(x_1,x_2,\cdots ,x_m\right)}^{\text{T}}$， $X_N={\left(x_{m+1},x_{m+2},\cdots ,x_n\right)}^{\text{T}}$。

因此， $AX=b$ 等价于 $B{X}_B+N{X}_N=b$，则 $X_B=B^{-1}\left(b-N{X}_N\right)$。令 $X_N=0$，且 $B^{-1}b\ge 0$ 时，基可行解为 $X^{*}=B^{-1}b$， $b={\left(b_1,b_2,\cdots ,b_m\right)}^{\text{T}}$。

以往对于线性规划问题的约束方程组对应的系数矩阵中没有子矩阵为单位矩阵，如大M法、两阶段法、对偶单纯形法等，都是采取“凑一个单位矩阵”出来，然后进行求解。这些解法，过程繁琐、迭代次数较多。

根据线性方程组的消元解法，一般地，标准型线性规划的约束方程组 $AX=b$ 经过行初等变换,总可以化为如下典式方程组：

$\begin{array}{ccccccc}{x}_1& & & & +a_{1m+1}{x}_{m+1}+\cdots +a_{1n}{x}_n& =& b_1\\ & x_2& & & +a_{2m+1}{x}_{m+1}+\cdots +a_{2n}{x}_n& =& b_2\\ & & \ddots & & & & ⋮\\ & & & x_m& +a_{mm+1}{x}_{m+1}+\cdots +a_{mn}{x}_n& =& b_n\end{array}$ (1)

这样，就能从系数矩阵中推导出一个单位矩阵 $I_{m\times m}$，就不用额外去增加人工变量 [4]，从而增加单位向量而使用大M法、两阶段法、对偶单纯形法等来求解线性规划问题 [5] [6] [7]。现由(1)式立即可列出第一张单纯形表，就能进行迭代求解了。这样可以大大减少迭代次数，从而快速求解线性规划问题。这种先通过行初等变换化约束方程组为典式方程组来求解线性规划问题的方法，就称为内生典式单纯形法，简称内生典式法。

内生典式单纯形法解题步骤如下：

第一步：根据线性规划约束方程组 $AX=b$ 的特点，应用消元法，将约束方程组化为 $I_{m\times m}{X}_B+B^{-1}N{X}_N=B^{-1}b$，其中 $I_{m\times m}$ 为m阶单位矩阵。

第二步：列出第一张单纯形表，确定中心元(转轴元)、进基变量、出基变量。以下与单纯形法步骤一致。对应各变量 $x_j$ 的检验数为 ${\sigma }_j=c_j-{\displaystyle \underset{i=1}{\overset{m}{\sum }}{c}_i{a}_{ij}}\left(j=1,2,3,\cdots ,n\right)$。

下面举例来验证其效果。

3. 实例验证

3.1. 实例1

求解线性规划问题

分析：这个问题，通常用大M法迭代求解，需要进行3次迭代。用两阶段法来求解，需要进行4次迭代。这两种解法，计算量都较大。下面用内生典式单纯形法来求解。

解：先把原规划化为标准形式，得

$\begin{array}{l}\max z=2x_1+5x_2+0x_3+0x_4+0x_5\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1+2x_2+x_3=8\\ x_1+x_2-x_4=2\\ x_2+x_5=3\\ x_1,x_2,x_3,x_4,x_5\ge 0\end{array}\end{array}$

对上述约束方程组进行行初等变换，化为典式方程组

$\begin{array}{l}\max z=2x_1+5x_2+0x_3+0x_4+0x_5\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1+2x_2+x_3=8\\ x_2+x_3+x_4=6\\ x_2+x_5=3\\ x_1,x_2,x_3,x_4,x_5\ge 0\end{array}\end{array}$

列出单纯形表，见表1。

Table 1. Example 1 iteration operation table

表1. 实例1迭代运算表

最优解为 $x^{*}={\left(2,3\right)}^{\text{T}}$，最优值 $z^{*}=19$。

从以上解题过程可以看出，只需要进行1次迭代，就能求出最优解。

3.2. 实例2

求解线性规划问题 [3]

$\begin{array}{l}\min w=-3x_1+x_2+x_3\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1-2x_2+x_3\le 11\\ -4x_1+x_2+2x_3\ge 3\\ -2x_1+x_3=1\\ x_1,x_2,x_3\ge 0\end{array}\end{array}$

分析：这个问题，通常采用大M法、两阶段法来求解。用大M法、两阶段法，都需要进行3次迭代，计算量很大。现用内生典式单纯形法来求解。

解：设 $z=-w$，则可把原规划化为标准形式，得

$\begin{array}{l}\max z=3x_1-x_2-x_3+0x_4+0x_5\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1-2x_2+x_3+x_4=11\\ -4x_1+x_2+2x_3-x_5=3\\ -2x_1+x_3=1\\ x_1,x_2,x_3,x_4,x_5\ge 0\end{array}\end{array}$

现在对约束方程组进行行初等变换，化为典式方程组

$\{\begin{array}{l}3x_1+x_4=12\\ x_2-x_5=1\\ -2x_1+x_3=1\\ x_i\ge 0\left(i=1,2,3,4,5\right)\end{array}$

列出单纯形表，见表2。

Table 2. Example 2 iteration operation table

表2. 实例2迭代运算表

最优解为 $x^{*}={\left(4,1,9\right)}^{\text{T}}$，最优值 $w^{*}=-z^{*}=-2$。

从以上解题过程可以看出，只需要1次迭代，就能求出最优解。

3.3. 实例3

求解线性规划问题 [3]

$\begin{array}{l}\min w=2x_1+3x_2+4x_3\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1+2x_2+x_3\ge 3\\ 2x_1-x_2+3x_3\ge 4\\ x_1,x_2,x_3\ge 0\end{array}\end{array}$

分析：这个问题，通常用对偶单纯形法来求解比较快捷，需要进行2次迭代。用大M法、两阶段法，都需要进行3次迭代，计算量很大。现用内生典式单纯形法来求解。

解：设 $z=-w$，则可把原规划化为标准形式，得

$\begin{array}{l}\max z=-2x_1-3x_2-4x_3+0x_4+0x_5\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1+2x_2+x_3-x_4=3\\ 2x_1-x_2+3x_3-x_5=4\\ x_1,x_2,x_3,x_4,x_5\ge 0\end{array}\end{array}$

现在对约束方程组进行行初等变换，化为典式方程组

$\begin{array}{l}\max z=-2x_1-3x_2-4x_3+0x_4+0x_5\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1+2x_2+x_3-x_4=3\\ 5x_2-x_3-2x_4+x_5=2\\ x_1,x_2,x_3,x_4,x_5\ge 0\end{array}\end{array}$

列出单纯形表，见表3。

Table 3. Example 3 iteration operation table

表3. 实例3迭代运算表

最优解为 $x^{*}={\left(11/5,2/5,0\right)}^{\text{T}}$，最优值 $w^{*}=-z^{*}=28/5$。

从以上解题过程可以看出，只需要1次迭代，就能求出最优解。

3.4. 实例4

求解线性规划问题

$\begin{array}{l}\min w=2x_1+x_2+5x_3\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1-x_2+x_3\ge 4\\ x_1+3x_2+4x_3\le 12\\ x_2-x_3\ge 2\\ x_1,x_2,x_3\ge 0\end{array}\end{array}$

分析：这个问题，通常采用对偶单纯形法、大M法、两阶段法来求解。用对偶单纯形法，需要进行3次迭代，用大M法，需要进行3次迭代。用两阶段法来求解，需要进行4次迭代。计算量很大。现用内生典式单纯形法来求解。

解：设 $z=-w$，则可把原规划化为标准形式，得

$\begin{array}{l}\max z=-2x_1-x_2-5x_3+0x_4+0x_5+0x_6\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1-x_2+x_3-x_4=4\\ x_1+3x_2+4x_3+x_5=12\\ x_2-x_3-x_6=2\\ x_i\ge 0\left(i=1,2,3,4,5,6\right)\end{array}\end{array}$

现在对约束方程组进行行初等变换，化为典式方程组

$\begin{array}{l}\max z=-2x_1-x_2-5x_3+0x_4+0x_5+0x_6\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{x}_1-x_4-x_6=6\\ 7x_3+x_4+x_5+4x_6=0\\ x_2-x_3-x_6=2\\ x_i\ge 0\left(i=1,2,3,4,5,6\right)\end{array}\end{array}$

列出单纯形表，见表4。

Table 4. Example 4 iteration operation table

表4. 实例4迭代运算表

最优解为 $x^{*}={\left(6,2,0\right)}^{\text{T}}$，最优值 $w^{*}=-z^{*}=14$。

从以上解题过程可以看出，由内生典式方程组列出单纯形表，就得出了最优解，无需迭代。

4. 解法效果比较

对以上4个实例使用大M法、两阶段法、对偶单纯形法、内生典式法来求解的迭代次数进行比较，见表5。

Table 5. Comparison of iteration times of various solutions for linear programming problems

表5. 线性规划问题的各种解法迭代次数比较

由表5知，大M法平均迭代次数为2.75次；两阶段法平均迭代次数为3次；对偶单纯形法平均迭代次数为2次；内生典式法适用题型多，平均迭代次数仅为0.75次。

5. 结语

对线性规划问题的求解过程进行研究，根据约束方程组的内在联系，利用消元法，施行行初等行变换，从系数矩阵中推导出一个单位矩阵出来，不需要增加条件来凑配单位矩阵，从而使问题得以解决，提出了内生典式单纯形法。通过4个实例使用大M法、两阶段法、对偶单纯形法、内生典式法来求解线性规划问题的迭代次数并进行比较，得出内生典式单纯形法适应题型多，运算快捷，平均迭代次数仅为0.75次。这证明，内生典式单纯形法行之有效。正所谓，大道至简。但是，对于一些约束方程组化为典式约束方程组的过程中，遇到约束矩阵中各元素的值较大时，施行行初等行变换时，计算量较大。化约束方程组为典式方程组的技巧，即如何快捷的通过消元法推导出一个单位矩阵出来，还可以进行深入研究。如果能从一个可行基开始迭代，就求出线性规划问题的最优解，是今后改进的方向。

致谢

感谢遵义师范学院基金的支持。对文中引用参考文献的作者表示衷心感谢！

基金项目

遵义师范学院基金(KCSZPY019)。