优化理论之线性规划的初始基本可行解.md

线性规划的初始基本可行解

我们使用单纯形法的时候，需要一个初始基本可行解来开始迭代优化，求出其他改进的基本可行解。下面我们介绍两个求初始基本可行解的方法。

• 两阶段法
• 两阶段法核心思想
• 大M法
• 大M法核心思想
• 单个人工变量技巧
• 注意：人工变量vs松弛变量

两阶段法

两阶段法核心思想

第一阶段：每个方程增加一个系数为1的非负人工变量，这些人工变量组成单位矩阵，可求出一组拓展的基本可行解。接下来用消主元法消去所有添加的人工变量（使人工变量都是非基变量取0，不必遵守单纯形法的主元选择规则），剩下的就是一个初始基本可行解。

第二阶段：根据第一阶段得到的初始基本可行解，用一般单纯形法求解问题。

总的来说，第一阶段问题要让人工变量为0，第二阶段正常解原问题。

大M法

大M法核心思想

类似于惩罚函数法。在约束中增加非负人工变量,\(\boldsymbol{x_a}\)，同时修改目标函数，增加惩罚项\(M\boldsymbol{e^Tx_a}\)，其中\(M\)是一个很大的正数，这样由于极小化目标函数的过程中，必然要优化\(M\)，将迫使人工变量离基。

具体方式：目标函数加上带\(M\)的人工变量，限制条件中增加非负人工变量，再用一般单纯形法求解。

由于添加的非负人工变量的系数为1，能够组成单位阵，因此很容易获得初始基本可行解。

单个人工变量技巧

处理\(\boldsymbol{\bar b=B^{-1}b}\)存在负数项情形，引入一个标量\(x_a\)，转换为 \[ \boldsymbol{x_B}+\boldsymbol{B^{-1}N x_N}-x_a \boldsymbol{e}=\boldsymbol{\bar b}\\ \boldsymbol{x}=\begin{bmatrix}\boldsymbol{x_B} \\ \boldsymbol{x_N}\end{bmatrix}≥\boldsymbol{0},x_a≥0 \] 其中，\(\boldsymbol{e}=\{1,1,\dotsb,1\}^T\)是m维列向量。为了消除\(\boldsymbol{]\bar b}\)中的所有负数，可以借以将\(x_a\)引入基变量来实现。令 \[ b_r = \min\{b_i\}<0 \] 以\(x_a\)所在列为主列，第r行为主行进行主元消去（\(x_a\rightarrow x_r\)）。此时，约束方程右端变为 \[ \begin{cases} \bar b_r' = -\bar b_r >0 \\ \bar b_i' = \bar b_i - \bar b_r ≥0, i\neq r \end{cases} \] 于是，我们得到了一个关于添加单个人工变量的一个基本可行解（\(\boldsymbol{\bar b}≥0\)）。再由此基本可行解出发，用两阶段法或大M法求解。

注意：人工变量vs松弛变量

人工变量与前面介绍过的松弛变量是两个不同的概念。松弛变量的作用是把不等式约束改写成等式约束，改写前后的两个问题是等价的。松弛变量的取值能够表达现行的可行点是在可行域的内部还是在其边界，也就是说，在此可行解处，原来的约束是成立严格不等式还是等式。因此，松弛变量是“合法”的变量。而人工变量的引入，改变了原来的约束条件，从这个意义上讲，它们是“不合法”的变量。这两种变量不可混为一谈。