18.1.2 线性规划基本概念、规范形

现在考虑线性规划问题(18.5a,18.5b),相应的可行集为 $M$ .

18.1.2.1 极端点和基

1. 极端点的定义

点 $\underset{―}{x}\in M$ 称作 $M$ 的极端点或顶点,是指对于所有 ${\underset{―}{x}}_1,{\underset{―}{x}}_2\in M,{\underset{―}{x}}_1\ne {\underset{―}{x}}_2$ ,有

$$\begin{array}{}\text{(18.7)}& \underset{―}{\mathbf{x}}\ne \lambda {\underset{―}{\mathbf{x}}}_1+\left(1-\lambda \right){\underset{―}{\mathbf{x}}}_2,0<\lambda <1,\end{array}$$

即 $\underset{―}{x}$ 不在连接 $M$ 任意两不同点的线段的中间.

2. 关于极端点的定理

如果矩阵 $\mathbf{A}$ 中与 $\underset{―}{\mathbf{x}}\in M$ 的正分量有关的那些列向量是线性无关的,则点 $\underset{―}{\mathbf{x}}$ 是 $M$ 的极端点.

如果 $\mathbf{A}$ 的秩是 $m$ ,那么 $\mathbf{A}$ 中线性无关列的最大数是 $m$ . 因此一个极端点至多拥有 $m$ 个正分量,其分量等于零的数目至少是 $n-m$ 个. 在通常情形下,正好有 $m$ 个正分量. 如果正分量数小于 $m$ ,则就称其为退化极端点.

3. 基

对于每一个极端点,可以选定矩阵 $\mathbf{A}$ 的 $m$ 个线性无关的列向量,这些列对应于其正分量. 这一组线性无关列向量称作该极端点的基. 通常, 每一个极端点恰好有一个基. 然而,退化的极端点就可能选定几个基. 从 $\mathbf{A}$ 的 $n$ 列中选择 $m$ 个线性无关向量,至多有 $\left(\begin{array}{c}n\\ m\end{array}\right)$ 种可能性. 因此,不同基的数目,从而不同极端点的数目是 $\left(\begin{array}{c}n\\ m\end{array}\right)$ . 如果 $M$ 非空,则 $M$ 至少有一个极端点.

$◼\mathbf{OF}$ : $f\left(\underset{―}{\mathbf{x}}\right)=2x_1+3x_2+4x_3=max$ !

$\mathbf{CT}$ : $x_1+x_2+x_3\ge 1$ ,

$$\begin{array}{}\text{(18.8)}& x_2\le 2\end{array}$$$$-x_1+2x_3\le 2,$$$$2x_1-3x_2+2x_3\le 2.$$

由约束条件确定的可行集示于图 18.4. 引入松弛变量 $x_4,x_5,x_6,x_7$ 后得到

$$\text{CT:}{x}_1+x_2+x_3-x_4=1\text{,}$$$$x_2+x_5=2,$$$$-x_1+2x_3+x_6=2,$$$$2x_1-3x_2+2x_3+x_7=2.$$

多面体的极端点 $P_2=\left(0,1,0\right)$ 对应于扩展系统的点 $\left(x_1,x_2,x_3,x_4,x_5,x_6,x_7\right)=$ $\left(0,1,0,0,1,2,5\right).A$ 的2,5,6,7列构成相应的基. 退化的极端点 $P_1$ 对应于 (1,0,0,0,2,3,0). 这一极端点的基包含1,5,6列,以及2,4或 7 列中的一列.

注 这里第一个不等式带不等号 “ $\ge$ ”,从而 $x_4$ 前不是加号而是减号. 常常将带负号和相应 $b_i>0$ 的这种附加变量称作剩余变量,而非松弛变量. 如在第 1189 页 18.1.3.3 所见, 剩余变量的出现要在求解过程中倍加小心.

4. 目标函数取极大值的极端点

定理 如果 $M$ 非空,并且目标函数 $f\left(\underset{―}{\mathbf{x}}\right)={\underset{―}{\mathbf{c}}}^{\mathrm{T}}\underset{―}{\mathbf{x}}$ 在 $M$ 上有界,则 $M$ 至少有一个极端点使得目标函数取极大值.

于是线性规划问题的求解就是至少确定一个极端点使得目标函数在其上达到极大值. 通常在实际问题中, 极端点的数目是非常大的, 从而需要有一种方法能够在合理的时间内找到答案. 这样的方法就是单纯形法, 也称作单纯形算法或单纯形程序.

18.1.2.2 线性规划问题的规范形

1. 规范形和基本解

线性规划问题 (18.4a, 18.4b) 总能通过适当的变量重新排序转换成如下形式:

OF : $f\left(\underset{―}{\mathbf{x}}\right)=c_1{x}_1+\cdots +c_{n-m}{x}_{n-m}+c_0=max$ !(18.9a)

CT: $a_{1,1}{x}_1+\cdots +a_{1,n-m}{x}_{n-m}+x_{n-m+1}=b_1$ ,

$$\begin{array}{}\text{(18.9b)}& \text{注 2 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ..}\end{array}$$$$a_{m,1}{x}_1+\cdots +a_{m,n-m}{x}_{n-m}+x_n=b_m,$$$$x_1,\cdots ,x_{n-m},x_{n-m+1},\cdots ,x_n\ge 0.$$

系数矩阵的最后 $m$ 列显然是线性无关的,从而形成一个基. 基本解 $(x_1,x_2,\cdots$ , $x_{n-m},x_{n-m+1},\cdots ,x_n)=\left(0,\cdots ,0,b_1,\cdots ,b_m\right)$ 可以直接从该方程组确定,但如果 $\underset{―}{b}\ge \underset{―}{0}$ 不成立,则它不是可行解.

如果 $\underset{―}{b}\ge \underset{―}{0}$ ,则(18.9a,18.9b)称作线性规划问题的规范形或标准形. 在这种情形下,基本解也是可行解,即 $\underset{―}{\mathbf{x}}\ge \underset{―}{\mathbf{0}}$ ,并且是 $M$ 的极端点. 变量 $x_1,\cdots ,x_{n-m}$ 称作非基变量,而 $x_{n-m+1},\cdots ,x_n$ 称作基变量. 目标函数在该极端点上取值 $c_0$ ,因为非基变量等于零.

2. 规范形的确定

如果 $M$ 的极端点是已知的,则线性规划问题(18.5a,18.5b)的规范形可以按如下方式得到. 从 $\mathbf{A}$ 的列中选择对应于该极端点的一个基. 通常,通过极端点的正分量可以确定这些列. 假定基变量组成向量 ${\underset{―}{\mathbf{x}}}_B$ ,而非基变量组成 ${\underset{―}{\mathbf{x}}}_N$ . 与该基对应的列构成基矩阵 ${\mathbf{A}}_B$ ,其余列构成矩阵 ${\mathbf{A}}_N$ . 于是

$$\begin{array}{}\text{(18.10)}& \mathbf{A}\underset{―}{\mathbf{x}}={\mathbf{A}}_N{\underset{―}{\mathbf{x}}}_N+{\mathbf{A}}_B{\underset{―}{\mathbf{x}}}_B=\underset{―}{\mathbf{b}}.\end{array}$$

矩阵 ${\mathbf{A}}_B$ 是非奇异的,其逆 ${\mathbf{A}}_B^{-1}$ 即所谓的基逆. 用 ${\mathbf{A}}_B^{-1}$ 乘 (18.10),并根据非基变量适当调整目标函数, 就得到线性规划问题的标准形:

OF: $f\left(\underset{―}{\mathbf{x}}\right)={\underset{―}{\mathbf{c}}}_N^{\mathrm{T}}{\underset{―}{\mathbf{x}}}_N+c_0$ ,(18.11a)

CT: ${\mathbf{A}}_B^{-1}{\mathbf{A}}_N{\underset{―}{\mathbf{x}}}_N+{\underset{―}{\mathbf{x}}}_B={\mathbf{A}}_B^{-1}\underset{―}{\mathbf{b}},{\underset{―}{\mathbf{x}}}_N\ge \underset{―}{\mathbf{0}},{\underset{―}{\mathbf{x}}}_B\ge \underset{―}{\mathbf{0}}$ .(18.11b)

注 如果原始系统 (18.1b) 仅有 “ $\le$ ” 类约束,并且同时 $\underset{―}{b}\ge \underset{―}{0}$ ,那么扩展系统 (18.4b) 没有剩余变量 (参见第 1183 页 18.1.2.1). 在这种情形下, 立即可知规范形. 选择所有松弛变量作为基变量 ${\underset{―}{\mathbf{x}}}_B$ ,结果就是 ${\mathbf{A}}_B=\mathbf{I}$ ,而 ${\underset{―}{\mathbf{x}}}_B=\underset{―}{\mathbf{b}}$ ,且 ${\underset{―}{\mathbf{x}}}_N=\underset{―}{\mathbf{0}}$ 是可行极端点.

$◼$ 在上面的例子中, $\underset{―}{x}=\left(0,1,0,0,1,2,5\right)$ 是一个极端点. 因此,

$$\begin{array}{}\text{(18.12a)}& {\mathbf{A}}_B=\left(\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 0& 0\\ 0& 0& 1& 0\\ -3& 0& 0& 1\\ x_2& x_5& x_6& x_7\end{array}\right),{\mathbf{A}}_B^{-1}=\left(\begin{array}{cccc}1& 0& 0& 0\\ -1& 1& 0& 0\\ 0& 0& 1& 0\\ 3& 0& 0& 1\end{array}\right),{\mathbf{A}}_N=\left(\begin{array}{ccc}1& 1& -1\\ 0& 0& 0\\ -1& 2& 0\\ 2& 2& 0\\ x_1& x_3& x_4\end{array}\right),\end{array}$$$$\begin{array}{}\text{(18.12b)}& {\mathbf{A}}_B^{-1}{\mathbf{A}}_N=\left(\begin{array}{ccc}1& 1& -1\\ -1& -1& 1\\ -1& 2& 0\\ 5& 5& -3\\ x_1& x_3& x_4\end{array}\right),{\mathbf{A}}_B^{-1}\mathbf{b}=\left(\begin{array}{c}1\\ 1\\ 2\\ 5\end{array}\right).\end{array}$$$$\begin{array}{}\text{(18.13)}& \begin{array}{rlrl}{x}_1+x_2+x_3-x_4& & & =1,\\ -x_1-x_3+x_4+x_5& & & =1,\\ -x_1+2x_3+x_6& & =2,& \\ 5x_1+5x_3-3x_4+x_7& & =5.& \end{array}\}\end{array}$$

从 $f\left(\underset{―}{\mathbf{x}}\right)=2x_1+3x_2+4x_3$ ,减去第一个约束的 3 倍,得到变换后的目标函数为

$$\begin{array}{}\text{(18.14)}& f\left(\underset{―}{\mathbf{x}}\right)=-x_1+x_3+3x_4+3.\end{array}$$