线性规划 (一) 线性规划的基本形式及各种概念

2019-12-07 本文已影响0人小小何先生

在最优化中，目标函数和约束函数皆为线性函数的优化问题称为线性规划（LP），它是相对简单的最优化问题。

标准形式

线性规划：

如下形式的线性规划记2-1：
$\left.\begin{array}{ll}{\min \sum_{j=1}^{n} c_{j} x_{j}} \\ {\text { s.t. } \sum_{j=1}^{n} a_{i j} x_{j}=b_{i},} & {i=1,2, \cdots, m} \\ {x_{j} \geq 0,} & {j=1,2, \cdots, n}\end{array}\right\}$

称为线性规划的标准形式。其中 $c_{j}$ 称为价格系数， $b_{i}$ 称为右端项。

采用向量－矩阵表示法，标准形式可以简写为如下形式，记为2-2:

$\left.\begin{array}{c}{\min c^{T} x} \\ {\text {s.t. } A x=b} \\ {x \geq 0}\end{array}\right\}$

其中 $A=(a_{ij})_{m \times n}$ ， $b=(b_{1}, \cdots, b_{m})^{T}$ ， $c=(c_{1}, \cdots , c_{n})^{T}$ ， $x=(x_{1}，\cdots , x_{n})^{T}$ 。

典范形式：

在下面进行理论分析时，经常把 $A$ 看作由 $n$ 个列向量构成的，即：

$A=[a_{1}，a_{2}，\cdots ，a_{n}]$

其中第 $j$ 列向量是 $a_{j}=[a_{1j}，a_{2j}，\cdots ，a_{mj}]^{T}$ 。于是，2-2中的 $Ax=b$ 可写成：

$\sum_{j=1}^{n}x_{j}a_{j}=b$

若 $A$ 中有 $m$ 个列向量可以合并成单位矩阵，且 $b \geq 0$ ，则此时的2-2称为线性规划的典范形式。

一般形式化标准形

对于一般形式的线性规划，比如标准形式中是求极小，而有时候给出的是求极大，所以我们需要将其化成标准形，然后对标准形做研究，得到通用的解法。

那么实际问题中出现的非标准形式如何处理呢？有三个基本原则：

(1) 极大化极小：

如求 $max \sum_{j=1}^{n}c_{j}x_{j}$ ，可变为 $min \sum_{j=1}^{n}(-c_{j})x_{j}$ 。

(2) 松弛变量和剩余变量：
如约束中出现 $\leq$ ，则在该约束中加上一个变量（称为松弛变量），并要求该变量非负；如出现 $\geq$ ，则在该约束中减去一个变量（称为剩余变量）。

注意：新引入变量的价格系数全部设为零，因此目标函数中没有出现新变量。

(3) 自由变量：
以上讨论都考虑变量的取值是非负的。实际中，如果某些变量没有这种约束，也就是说，某些变量可以任意取值，那么这些变量称为自由变量。自由变量可以通过以下两种方法把它消除。
- 第一种方法：引入两个非负变量 $x_{1}^{+}$ 和 $x_{1}^{-}$ ，令 $x_{1}=x_{1}^{+}-x_{1}^{-}$ 。将其代入到线性规划的目标函数和约束函数中，自由变量 $x_{1}$ 就消除了。注意，求出新线性规划的最优点后，再利用 $x_{1}=x_{1}^{+}-x_{1}^{-}$ 便可以定出 $x_{1}$ 。
- 第二种方法：取一个包含 $x_{1}$ 的等式约束，例如 $a_{i1}x_{1}+a_{i2}x_{2}+ \cdots + a_{im}x_{n}=b_{i}$ 由此解出：
  $x_{1}=\frac{b_{i}}{a_{i1}}-\frac{a_{i2}}{a_{i1}}x_{2} - \cdots - \frac{a_{in}}{a_{i1}}x_{n}$

第一种方法将增加变量的数目，导致问题的维数增大。第二种方法正好相反。

解的性质

在介绍解的性质之前，先需要了解一下各种各样的解的概念。

满足 $Ax=b$ 的 $x$ 称为方程组 $Ax=b$ 的解，而满足 $Ax=b$ ， $x \geq 0$ 的 $x$ 称为线性规划2-2的容许解。现在要定义一种特殊的容许解-基本容许解，而在介绍基本容许解之前需要介绍另一个概念：基。

定义： $A$ 的 $m$ 个线性无关列向量称为基。基中的每个列向量称为基向量，而 $A$ 中的其余列向量称为非基向量。由全体基向量合成的矩阵称为基矩阵，也简称为基。若基是单位矩阵，则称为标准基。

定义： 在约束 $\sum_{j=1}^{n}x_{j}a_{j}=b$ 中，确定一个基后，与基向量对应的变量称为基变量，与非基向量对应的变量称为非基变量。

定义： 设 $x_{0}$ 是 $Ax=b$ 的一个解。若它有 $m$ 个分量所对应的 $A$ 的列向量构成基 $B$ ,而其余 $n-m$ 个分量全部为0，则 $x_{0}$ 称为约束 $Ax=b$ 关于基 $B$ 的基本解。若 $x_{0}$ 还满足 $x_{0} \geq 0$ 则 $x_{0}$ 称为约束 $Ax=b$ ， $x \geq 0$ 关于基 $B$ 的基本容许解，也称为线性规划2-2关于基 $B$ 的基本容许解。