最优化理论与算法第3章:单纯形方法

本文的内容主要来自陈宝林的《最优化理论与算法(第2版)》第3章《单纯形方法》和老师的PPT。

# 1 单纯形方法原理

# 1.1 基本可行解的转换

考虑问题:

formula

同时记:

formula

其中formulaformula分别是基本可行解formula的基矩阵和非基矩阵。则formula处的目标函数值为:

formula

我们的目标是从这个基本可行解出发,得到另一个目标函数值更小的。考虑任意可行解:

formula

注意,这里的formulaformula的基矩阵和非基矩阵是相对formula说的。这时候目标函数值为:

formula

注意到formula,所以此时若formula,则达到最优解条件。若此时存在formula,为了让formula下降得更快,所以我们会添加一个基formula,这个基对应的formula应当是最最大的。所以有:

formula

则此时:

formula

为了保证新的解是可行解,我们需要确保formula,即formula,所以我们应当取:

formula

formula,则问题无界。如果找到了,这时候formula,得到了一个新的可行解,接下来我们证明这是基本可行解,方法是证明formula线性无关。注意到formula是线性无关的,而formula,而formula,故formula可被formula线性标出,故formula线性无关。故:

formula

是新的更优的基本可行解。

定理 3.1.1 若在极小化问题中,对于某个基本可行解,所有formula,则这个基本可行解是最优解,这里:

formula

称为判别数检验数。注:如果formula是基的下标,则判别数为formula

# 1.2 单纯形方法计算步骤

首先要给定一个初始的基本可行解,假设初始基矩阵为formula,执行以下步骤:

  1. formula

  2. 求单纯形子formula,对于所有非基变量,计算判别数formula,令:

    formula

    formula,则找到最优解,退出。否则进入下一步;

  3. formula,若formula,则不存在有限最优解,退出,否则进入下一步;

  4. 确定下标formula,使:

    formula

    formula离基变量formula进基变量,用formula替换formula得到新的基矩阵,返回步骤1。

对于最大化问题,步骤2的formulaformula即可。

# 1.3 收敛性

所有迭代会出现下列情况:

  1. formula,当前解为最优解;
  2. formulaformula,问题无界;
  3. formulaformula,找到新基本可行解,非退化情况下目标函数下降。

定理 3.1.2 对于非退化问题,单纯形方法经过有限次迭代要么达到最优基本可行解,要么无界。

# 1.4 使用表格形式的单纯形方法

首先,对标准形式作变换可以得到:

formula

消去第一个等式中的formula,得到:

formula

将上式写在表格中就有了单纯形表

formula formula formula 右端
formula formula formula formula formula
formula formula formula formula formula

其中,formula的每一个分量即为判别数formulaformula的列分量就是formula。第一列通常省略。

初始的时候。我们已经有了一个可行解formula

formula,则找到了最优解。

formula,则需要用主元消去法。在表的最后一行中,寻找除右端外的最大值,它所在的一行称主列,从而确定了离基变量。这时候寻找主列上除最后一列外大于0的元素,且右端除以该元素值最小的,找到的该元素称为主元,它所在的行称为主行,再用主行加上初等行变换,消去主元所在列,并使主元为formula。循环此操作。

2016-2020 Ziping Sun
京ICP备 17062397号