运筹学 - 线性规划的基本概念、图解法

线性规划的基本概念

线性规划

我们在运筹学当中首先讨论在一些约束条件下的最大化问题：

$$\begin{array}{rl}& \max (\min )f(x)\\ & s.t.\{\begin{array}{l}{f}_1(x)⩽a_1\\ f_2(x)⩾a_2\\ ⋮\end{array}\end{array}$$

我们可以看到有三个要素：

• 决策变量：指决策者为实现规划目标的方案，措施，是问题中要 确定的未知量
• 目标函数：指问题要达到的目的要求，表示为决策变量的函数.
• 约束条件：指决策变量取值时受到的各种可用资源的限制，表示 为含决策变量的等式或不等式.

由此我们导出线性规划的概念.

定义：线性规划

线性规划是目标函数、约束条件均为线性的规划问题.

线性规划一般而言写为：

$$\begin{array}{rl}& \max (\min )z=\sum _{j=1}^n{c}_j{x}_j\\ & s.t.\{\begin{array}{l}\sum _{j=1}^n{a}_{ij}{x}_j⩽(=,⩾)b_i\\ x_j⩾(⩽)0,j=1,2,\cdots ,n\end{array}\end{array}$$

我们可以看到，由于线性性，可以考虑将其写为矩阵形式.

$$\begin{array}{rl}& \max (\min )z={\mathbf{c}}^{\mathrm{T}}\mathbf{x}\\ & s.t.\{\begin{array}{l}\mathbf{Ax}⩽(=,⩾)\mathbf{b}\\ \mathbf{x}⩾(⩽)0\end{array}\end{array}$$

其中 $\mathbf{c},\mathbf{b},\mathbf{x}$ 均为列向量，$\mathbf{A}$ 为常数矩阵，但通常不为方阵. 我们通常也分块写为 $\mathbf{A}=({\mathbf{P}}_1,\cdots ,{\mathbf{P}}_n)$ .

线性规划的标准形式

我们定义线性规划的标准形式为：

$$\begin{array}{rl}& \max z={\mathbf{c}}^{\mathrm{T}}\mathbf{x}\\ & s.t.\{\begin{array}{l}\mathbf{Ax}=\mathbf{b}\\ \mathbf{x}⩾0\end{array}\end{array}$$

换言之，保证：

• 问题为极大化问题.
• 所有约束条件为等于常数.
• 变量的约束均为非负.

标准化问题是我们找出通用解法的开始，接下来我们讨论如何进行标准化.

一、极小化变为极大化.

这个比较简单，如果问题形如

$$\min z=2x+y$$

那么我们取负号即可：

$$\max z=-2x-y$$

二、约束条件均化为等于.

小于等于和大于等于均类似，如果形如：

$$x_1+x_2⩽3$$

我们就引入一个松弛变量，令：

$$x_3=3-x_1-x_2⩾0$$

那么就有

$$x_1+x_2+x_3=3$$

三、约束条件化为非负.

如果有约束，但是形如：

$$x_1⩽-3$$

令 $x_1^{\prime }=-3-x_1$ 即可. 则可得到 $x_1^{\prime }⩾0$ .

如果无约束，例如 $x_2$ 无约束，则设

$$x_2=x_2^{\prime }-x_2^{\prime \prime }$$

其中 $x_2^{\prime },x_2^{\prime \prime }$ 均非负，那么我们同样化为了有约束问题.

线性规划问题的解

设线性规划问题：

$$\begin{array}{rl}& \max z={\mathbf{c}}^{\mathrm{T}}\mathbf{x}\\ & s.t.\{\begin{array}{ll}\mathbf{Ax}=\mathbf{b}& (1.1)\\ \mathbf{x}⩾0& (1.2)\end{array}\end{array}$$

我们接下来讨论它的解，引入如下概念.

定义：可行解

满足约束条件 $(1.1),(1.2)$ 的所有解称为可行解，可行解全体构成可行域： $\mathbb{S}=\left\{\mathbf{x}\in {\mathbb{R}}^n\mid \mathbf{Ax}=\mathbf{b},\mathbf{x}⩾0\right\}$

定义：最优解

可行解中达到最大值的解称为最优解.

我们在线性规划当中寻求的就是最优解，最优解的寻找是线性规划当中核心的问题. 在之后我们将会逐步讨论.

然后接下来我们来看其中的约束条件，我们不难发现其中有线性方程组：

$$\mathbf{Ax}=\mathbf{b}$$

这启发我们使用线性代数的方法来考虑其中的问题，其中 $\mathbf{A}$ 是 $m\times n$ 阶矩阵，$m$ 为约束条件个数，$n$ 为决策变量个数，在多数的情况下，$m<n$ 都是必然的，若 $m⩾n$ ，通常可以直接解出有限的解. 我们接下来只讨论行满秩的情形. （不满秩说明约束条件部分可以相互抵消）

令

$$\mathbf{A}=({\mathbf{P}}_1,\cdots ,{\mathbf{P}}_n)$$

由于行满秩，这说明列空间维数也为 $m$ ，不妨设前 $m$ 个就是线性无关的：$\mathbf{B}=({\mathbf{P}}_1,\cdots ,{\mathbf{P}}_m)$ ，那么有

$$\mathbf{A}=\left(\begin{array}{cc}\mathbf{B}& \mathbf{N}\end{array}\right)$$

就有如下概念：

• $\mathbf{B}$ 为基向量. （任意 $m$ 个线性无关的都能组成基向量）
• $\mathbf{N}$ 为非基向量.
• 基向量对应的变量称为基变量：${\mathbf{x}}_B=(x_1,\cdots ,x_m)$ .
• 除基变量之外的变量称为非基变量.

定义：基解、基可行解

将非基变量全部赋予 $0$ ，解 $\mathbf{Ax}=\mathbf{b}$ 得到的解称为基解. 如果基解同时也是可行解，则称为基可行解.

接下来通过简单的问题来讨论上述概念.

例：线性规划基本概念

$$\begin{array}{rl}& \max (\min )z=2x_1+3x_2\\ & s.t.\{\begin{array}{l}2x_1+2x_2+x_3=12\\ x_1+2x_2+x_4=8\\ 4x_1+x_5=16\\ 4x_2+x_6=12\\ x_i⩾0\end{array}\end{array}$$

针对上述的线性规划问题，说明基、基变量、基解、基可行解的概念.

写出其系数矩阵：

$$\mathbf{A}=\left(\begin{array}{cccccc}2& 2& 1& 0& 0& 0\\ 1& 2& 0& 1& 0& 0\\ 4& 0& 0& 0& 1& 0\\ 0& 4& 0& 0& 0& 1\end{array}\right)$$

我们容易知道后四个向量线性无关：$({\mathbf{P}}_3,{\mathbf{P}}_4,{\mathbf{P}}_5,{\mathbf{P}}_6)$ ，它是基，因此 $(x_3,x_4,x_5,x_6)$ 为基变量，我们代入 $x_1=x_2=0$ 进行求解有：

$$\{\begin{array}{l}{x}_3=12\\ x_4=8\\ x_5=16\\ x_6=12\end{array}$$

它是基解，根据约束条件，它也是基可行解. $\square$

图解法

这个比较简单，可以直接看书（老高考地区应该还在高中就包含了这部分），需要注意的就是图解法给了我们一些直接的灵感：

1. 线性规划问题的解有四种：
   1. 有唯一解.
   2. 有无穷多有界解.
   3. 有无界解.
   4. 无解.
2. 如果线性规划存在有界解，那么应该在凸可行域的顶点处.

这些结论将会在下一节当中证明.