单纯形法:格式与迭代

格式

  1. 目标函最大化
  2. 所有约束都是等式(变量的非负限制除外),并且具有非负右端项。
  3. 所有的变量都是非负的。

将不等式转化成带有非负右端项的等式约束 为了把(≤)不等式约束转换成等式约束,在约束的左端添加非负的松弛变量。为了把(≥)不等式约束转换成等式约束,在约束的右端添加非负的剩余变量。

e.g.
将约束6x_1+4x_2≤24转换成6x_1+4x_2+s_1=24,s_1≥0,其中s_1 是松弛变量。
将约束x_1+x_2≥800转换成x_1+x_2−s_2=800,s_2≥0,其中s_2 是剩余变量。

处理无限制变量 将无限制变量用两个非负变量替换。

e.g.
对于无限制变量s转换成s=s_1−s_2,s_1≥0,s_2≥0。

设方程个数为m,变量个数为n,并且m<n,基本解对应解空间中的一个角点,角点的最大数目是:

C_m^n=\frac{n!}{m!(n−m)!}

基本可行解完全确定了代数解空间中的最优解候选点。

设定n−m个变量为零,称为非基变量,剩下的变量称为基变量,解方程得到基本解。

单纯形法的迭代性质

线性规划的最优解只要存在,一定出现在在解空间的角点(corner point)。单纯性算法每次选择一个对目标函数值具有最大改善率的变量,进行迭代,每次迭代与解空间的一个角点对应,沿着解空间的边缘移动。单纯形法通过考查解空间中所有可能的基本可行解(角点)的一小部分,极大的减轻了计算负担。

e.g.

线性规划问题

标准化

标准化

从原点开始迭代,令x_1=0,x_2=0,即x_1,x_2 为非基变量,s_1,s_2,s_3 为基变量,单纯形表如下:

单纯形表1

z行由式z−2x_1−x_2+0s_1+0s_2+0s_3=0确定。

进基变量的确定(单纯性最优性条件) 进基变量将对应于目标方程中那些最大负值系数的变量。

离基变量的确定(单纯性可行性条件) 方程右端项(解列)与进基变量下方约束系数非负数比中最小的一项。

在上图中,进基变量为x_1,离基变量为s_2 (15/0>5/1>24/6)。

高斯-约当计算 在确定进基变量和离基变量后,进行高斯-约当计算。

  1. 在基列中,以进基变量取代离基变量。
  2. 新的枢纽行=当前枢纽行/枢纽元素。
  3. 除枢纽行,其他行新行=当前行-当前行枢轴列的系数x新的数轴行。

(其实就是枢纽元素变成1,该列其他元素变成0)

得到新的单纯形表:

单纯形表2

再次进行高斯、约当计算,得到:

单纯形表3

终止条件 目标函数中所有系数均大于0,目标函数达到了最优。

如下图所示,单纯形法每次迭代与解空间的一个角点对应(1->2->3),每次选择一个对目标函数值具有最大改善率的变量作为进基变量,沿着解空间的边缘移动。而离基变量的计算得到的非负比值实际上是这些约束关于进基变量轴的截距(4,5,∞)。

单纯形法的图形表示

发表评论

电子邮件地址不会被公开。 必填项已用*标注