最优化方法

很多工程及管理学科中的问题都可以归结于优化数学模型。因而对优化问题的研究成为数学的重要分支之一。在本章中我们将介绍线性规划、非线性无约束规划、非线性约束规划及组合优化等问题的一些基本概念和经典算法。

§1线性规划与单纯型法* §2非线性规划的最优性条件# §3无约束非线性优化算法 §4罚函数法* §5组合最优化问题 §6智能优化算法* 6.1模拟退火算法 6.2遗传算法

线性规划问题

线性规划问题常见于工程和管理科学中。对线性规划问题的可解性，算法设计已有很好的研究。本小节主要讲述对线性规划的几个基本概念。本节知识点有线性规划的标准形转化、基本可行解、最有基本可行解。重点为将各形式线性规划转化为标准形。

线性规划是目标函数与约束函数都是线性函数的优化问题

线性规划的标准形式：

\[\begin{aligned} \text{min} \quad & \boldsymbol{c}^T\boldsymbol{x} \\ \text{s.t.} \quad & \boldsymbol{Ax} = \boldsymbol{b} \\ & \boldsymbol{x} \ge 0 \end{aligned} \tag{1}\]

其中 \(\boldsymbol{A}\) 为 \(m \times n\) 矩阵，并且 \(m < n\) (矮宽)，\(\text{rank} \boldsymbol{A} = m\) (列满秩)。\(\boldsymbol{c}\) 为 \(n\) 维列向量， \(\boldsymbol{b}\) 为 \(m\) 维列向量且 \(\boldsymbol{b} \ge \boldsymbol{0}\)。

如果不是标准形，有一些转换方法：

• 对于 \(\text{max} \quad \boldsymbol{c}^T\boldsymbol{x}\)，目标函数可以乘以 \(-1\) ，转化为 \(\text{min} \quad -\boldsymbol{c}^T\boldsymbol{x}\)
• 如果 \(\boldsymbol{b}\) 中的第 \(i\) 个元素是负的，则在第 \(i\) 个约束方程边同乘 \(-1\)
• 如果约束方程为不等式，转换为等式约束
  • 对于 \(\le\) 的不等式，左边可以加上非负松弛变量
  • 对于 \(\ge\) 的不等式，左边可以减去非负剩余变量
• 如果变量 \(x_i\) 没有非 \(0\) 限制，可引入两个非负变量 \(x^{'}_i , x^{''}_i\)，使得 \(x_i = x^{'}_i - x^{''}_i\)

对于系数矩阵为宽矩阵的方程组，从 \(\boldsymbol{A}\) 的一部分列向量入手。重新排列列向量为线性无关的在前面，即把 \(\boldsymbol{A}\) 写成分块矩阵 \(\boldsymbol{A} = \left [ \begin{array} {c:c} \boldsymbol{B} & \boldsymbol{N} \end{array} \right ]\)

其中 \(\boldsymbol{B}\) 为一个基(满秩)，\(\boldsymbol{N}\) 为剩余列向量组成的矩阵。

此时

\[\boldsymbol{x} = \left [ \begin{array} {c} \boldsymbol{x_B} \\ \boldsymbol{x_N} \end{array} \right ]\]

则约束方程可写为

\(\boldsymbol{Ax} = \left [ \begin{array} {c:c} \boldsymbol{B} & \boldsymbol{N} \end{array} \right ] \left [ \begin{array} {c} \boldsymbol{x_B} \\ \boldsymbol{x_N} \end{array} \right ] = \boldsymbol{Bx_B} + \boldsymbol{Nx_N} = \boldsymbol{b}\)，

可以得到 \(\boldsymbol{x_B} = \boldsymbol{B}^{-1}\boldsymbol{b} - \boldsymbol{B}^{-1}\boldsymbol{Nx_N}\)

令 \(\boldsymbol{x_N} = 0\)，得到 \(\boldsymbol{Ax} = \boldsymbol{b}\) 的一个解

\[\boldsymbol{x} = \left [ \begin{array} {c} \boldsymbol{B}^{-1}\boldsymbol{b} \\ 0 \end{array} \right ]\]

满足 \([\boldsymbol{x}_B^T, \boldsymbol{0}^T ]\) 是 \(\boldsymbol{Ax} = \boldsymbol{b}\) 在基 \(\boldsymbol{B}\) 下的基本解。

满足 \(\boldsymbol{Ax} = \boldsymbol{b} , \boldsymbol{x} \ge \boldsymbol{0}\) 的解向量称为可行解。

如果可行解是基本解，则称之为基本可行解。

满足 \(\boldsymbol{Ax} = \boldsymbol{b}\) 并且使得 \(\boldsymbol{c}^T \boldsymbol{x}\) 取得最小值的解向量称为最优可行解。

如果最优可行解是基本解，则称为最优基本可行解。

线性规划基本定理把线性规划问题的求解转换为在有限数量的基本可行解上进行搜索。只需要检验基本可行解的最优性即可。

线性规划的几何视角

约束集的极点和基本可行解是等价的。(证明很长)

约束集的极点是不在集合中其他两点连线上的点，换言之，几何图形的顶点。因此在求解线性规划问题时，只需要检查约束集的极点就行。

来看一个小例子

单纯形方法

求解线性规划问题的算法有很多种，本节主要讲述便于实现的单纯形表格法。本节知识点有单纯形数据表格、判别数或检验数、停机准则、改进基本可行解、初始数据设定。难点为初始表格的计算、进基变量和出基变量的更新、主元变化。

单纯形法的基本思想：线性规划问题归结为寻找最优基本可行解。从一个基本可行解出发，找一个使目标函数减少的基本可行解。不断改进基本可行解，最终得到最优基本可行解。

当前的基本可行解 \(\boldsymbol{x}^{(k)}\)，当前点的目标值函数值为 \(f_k = f(\boldsymbol{x}^{(k)})\)

\[\boldsymbol{x}^{(k)} = \left [ \begin{array}{} \boldsymbol{x}_B^{(k)} \\ \boldsymbol{0} \end{array} \right ] = \left [ \begin{array}{} \boldsymbol{B}_k^{-1} \boldsymbol{b} \\ \boldsymbol{0} \end{array} \right ]\] \[x^{(k)} =\]

两阶段法和大M法

对于约束中含有等式约束或者大于号约束的线性规划问题，我们很难确定一个基本初始可行解，需要其他方法来处理。本节主要讲述求解此类问题的两阶段法和大M法。 本节主要内容有两阶段法的第一阶段和第二阶段的模型建立和求解、大M法的模型建立和求解。难点为各方法的模型构造，两阶段法第二阶段的判别数及最优值的重新计算。