运筹学公式的几何解释（1）

阅读本文需要一定的线性代数知识基础

基本概念

假设有这样一个线性规划问题：

max{Z}=C_1x_1+C_2x_2+\ldots+C_nx_n

\begin{cases} a_{11}x_1+a_{12}x_2+⋯+a_{1n}x_n=b_1\\[2ex] a_{21}x_1+a_{22}x_2+⋯+a_{2n}x_n=b_2\\[2ex] …\\[2ex] a_{m1}x_1+a_{m2}x_2+⋯+a_{mn}x_n=b_m\\[2ex] x_j≥0,j=1,2,…,n\\[2ex] \end{cases}

我们将之化为矩阵形式，可以得到：

max{Z}=CX

\begin{cases} AX=bX≥0 \\[2ex] X\geq0 \end{cases}

其中

A_{m\times n}

且

r\left(A\right)=m

，

C=\left(C_1,C_2\cdots C_n\right)

，

x = \left\lbrack \begin{array}{l} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \\ \end{array} \right\rbrack

,

A = \left\lbrack \begin{array}{llll} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \cdots & \cdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{array} \right\rbrack

,

b = \left\lbrack \begin{array}{l} b_{1} \\ b_{2} \\ \vdots \\ b_{n} \\ \end{array} \right\rbrack

。

观察

{\mathit{\max}Z} = CX

，你会发现Z是行向量C与列向量X的点积，也就是：

{\mathit{\max}Z} = C^{T} \cdot X

我们都知道，点乘的几何意义是一个向量在另一个向量上的投影长度乘上另一个向量的长度；这意味着从几何上来看，最优值Z表示的是向量C在X上的投影乘上X的长度。为了方便表示，我们假设

C^{T}

和

X

都是二维向量，将

C^{T}

和

X

放到一张图上：

由于点乘又可以写作

Z = \left| c \right| \cdot \left| x \right| \cdot {\mathit{\cos}\theta}

，对于题目中的求解Z的最大值，实际上我们只需要使向量x尽量大，夹角θ尽量小。对于相反的最小化问题，我们就使向量x尽量小，夹角θ尽量大。

现在我们已经在几何上表现出了最优值Z，现在来看最优解X。先从解的几种不同情况入手：

1. 唯一解

这种情况最好理解，即在约束范围内，我们只能找到一个向量x使得最优值Z达到最优条件。

2. 多重解

即在约束范围内，我们只能找到多个向量x使得最优值Z达到最优条件。不妨计算一下：

设C为二维向量

\left( {c_{1},c_{2}} \right)

，设多重解为二维向量

X\left( {x_{1},x_{2}} \right)

，则有：

\left( {c_{1},c_{2}} \right) \cdot \left( {x_{1},x_{2}} \right)~ = ~c_{1}x_{1} + c_{2}x_{2}~ = ~Z

整理可得：

x_{2} = \frac{Z - c_{1} \cdot x_{1}}{c_{2}} = \frac{Z}{c_{2}} - \frac{c_{1}}{c_{2}}x_{1}

即：X的多个最优解都位于直线

y = \frac{z}{c_{2}} - \frac{c_{1}}{c_{2}}x

上。

3. 无界解

根据上文我们可以推测，当向量c与向量x点乘结果可取到无穷时，无界解就产生了。根据

Z = \left| c \right| \cdot \left| x \right| \cdot {\mathit{\cos}\theta}

，由于

{\mathit{\cos}\theta}\epsilon\left\lbrack {- 1,1} \right\rbrack

，因此只有x的长度能决定Z取到无穷。因此可以知道，无界解即在x的约束区域内存在至少一个方向可使向量x无限延伸。

4. 无可行解

这种情况也比较容易理解，即x的约束区域自相矛盾，找不到满足情况的向量x。