最优化理论与算法第2章:线性规划的基本性质

本文的内容主要来自陈宝林的《最优化理论与算法(第2版)》第2章《线性规划的基本性质》。

# 1 标准形式及图解法

# 1.1 标准形式

一般线性规划问题,可以写成下列标准形式

formula

其中formulaformulaformula。同时一般假定formula

极大化转换:若优化目标为formula,则另formula

约束方程常量为负:若formula,另formula

决策变量无非负限制:若formula无非负限制,可以另formula,其中formula

决策变量有上下界:若formula,另formula;若formula,另formula。注:此方法与约束方程为不等式类似,如果同时存在上下界,就引入松弛变量。

约束方程为不等式:若给定的问题为:

formula

可以引入松弛变量formula,化为下列标准式:

formula

类似地,对于formula,可以引入剩余变量

含有绝对值:若给定的问题为(这里使用formula表示逐个元素的绝对值):

formula

可以引入formula,于是我们有formula,化为下列标准式:

formula

TODO: 写个程序演示一下?

# 1.2 图解法

线性不等式的几何意义是半平面,因此对于两变量线性规划,可以使用图解法

  1. 作出线性规划问题的可行域;
  2. 作出目标函数的等值线;
  3. 移动等值线到可行域边界得到最优点。

注意,目标函数的梯度指向目标函数增大的方向。

线性规划可能存在无穷多个最优解,这些解组成了可行域的一条边;线性规划可行域为空集,则线性规划无解。若可行域无界,则该线性规划可能无界,即不存在有限最优值(这种情况也是无最优解)。

formula

# 2 基本性质

# 2.1 可行域

定理2.2.1 约束条件为线性等式或者不等式的线性规划的可行域是凸集。

注:由凸集的有限交是凸集即可得证。

# 2.2 最优极点

考虑标准形式的可行域,其极点为formula,极方向为formula,由表示定理可以知道,可行点formula可以表示为:

formula

代入标准形式:

formula

若某个formula,则formula可以取很大,问题成为了无界。所以有界的充要条件是所有formula。有界的最优解一定有formula。所以对于有界的问题,简化成了:

formula

这时,令:

formula

则:

formula

定理2.2.2 设标准形式的线性规划可行域非空,则有下列结论:

  1. 存在最优解(这里的存在是指有限的)的充要条件是formula,其中formula为可行域极方向;
  2. 若存在最优解,则最优解可在某个极点上达到。

# 2.3 最优基本可行解

对标准形式的线性规划,若formula,可将formula列调换后,得到矩阵formula,其中formula为满秩方阵。formula进行对应的行变换,可以得到formula,于是约束条件可以写为:

formula

其中formula的分量是自由分量,令formula,可得到一个解:

formula

定义2.2.1 对于:

formula

称为方程formula的一个基本解formula称为基矩阵,简称为formula的各分量称为基变量,基变量全体称为一组基formula的各分量称为非基变量。若formula,则formula称为基本可行解formula称为可行基矩阵,基变量全体称为一组可行基。若formula称基本可行解是非退化的,否则称为退化的

由于基矩阵只有有限个(formula),基本解也只有有限个,基本可行解也为有限个。

定理2.2.3 极点的代数含义formula的极点集与formula基本可行解集等价。

注:其实线性规划的标准形式可以看作超平面与第一象限(闭集)的交,所有变量的个数formula就是整个空间的维度,而非基变量的个数formula是超平面的维度。与坐标轴、坐标平面之类的东西(这些东西的维度为formula)交点就是那些非基变量为formula的点,这些交点如果分量都大于formula,那么就位于第一象限内,也就是极点。退化的基本可行解是指基本可行解本来交于类似坐标平面的高维事物,却交于类似于坐标轴的低维事物,即同时交于两个坐标平面,这种情况会出现重复的基本解。

引理 基本可行解的代数含义 对于可行解formulaformula是基本可行解formula formula的非零分量对应的formula的列向量线性无关。

证:“formula”,由于formula是基本可行解,它取正值的分量必为基变量,对应的列向量是基矩阵的一部分,基矩阵可逆,所以对应的列向量必线性无关。“formula”,这里只需要证明它是基变量,由于formula行满秩,formula非零分量对应的列向量,一定可以扩充成formula个线性无关的列向量,由定义知formula为基本解。

复述定理:令formulaformula是极点formula formula是基本可行解。

定理2.2.3 证:不妨假设formula的前formula个分量大于formula,余下的formula个分量为formula,即formula

formula”。由反证法,接下来证明,若formula是极点,且formula不是基本可行解,即formulaformula个正分量formula对应的formula的列向量formula线性相关,会推导出矛盾。

存在不全为零的formula,满足formula,取formula满足formula,令:

formula

则我们有formula,且由formulaformula。但formula,且formula与极点定义矛盾。

formula”。已知formula,其中formulaformula对应的基矩阵。假设存在formula,满足formula。我们将formula也按前formula个分量和后formula个分量拆分,即formula

formula

由于formula同时formula,所以formula。又由于formulaformula,所以我们有formula。故formulaformula为极点。

定理 极方向的代数含义formula的极方向formulaformula个非零分量, formulaformula的极方向formula formula的非零分量对应的formula的列向量组的秩为formula

证:

formula”。formula为行满秩矩阵,故formula。不妨假设formulaformula个非零分量分别是formulaformula,并且formula对应的列向量的一个极大线性无关组是formula。这formula个线性无关向量可以在formula的列向量中扩充成formula个线性无关的向量,formula

假设存在formulaformulaformula的方向(即formulaformulaformula)且存在formula,满足formula。则formulaformula均为formula。因而formula可以记为:

formula

故:

formula

formulaformula,则formula不是方向,故formula,同理formula,所以有formula,故formula是极方向。

formula”。不妨设formula。若formula,则formulaformula,结论成立。若formula,设formula,可以知道formula线性相关,故对应的列向量组秩formula。假设formula线性相关,则存在不全为零的formula,满足formula,取formula满足formula,令:

formula

则我们有formula,且formula,且formula。由于formula,且formula,所以formula不是极方向,故对应的列向量组秩formula

# 2.4 基本可行解的存在问题

定理2.2.4 如果formula有可行解,则一定存在基本可行解。

证:证明思路是不断构造更多formula分量的可行解,直到可行解对应的向量组线性无关。设formulaformula是一个可行解,且formula。若formula线性无关,则由引理,formula为基本可行解。若formula线性相关,则存在不全为formula,且至少有一个正数的formula(如果都是负的,等式同时取相反数即可),满足:

formula

formula,定义formula。则我们有formulaformulaformula,故formula是可行解,且正分量减少了,不断重复这个步骤,就可以获得基本可行解。

定理 若LP有最优解,则存在一个基本可行解是最优解。定理2.2.2与定理2.2.4的推论。

定理 若LP问题有最优解,则要么最优解唯一,要么有无 穷多最优解。

证明思路是如果存在两个不同的最优解,它们的正线性组合也是最优解。

2016-2020 Ziping Sun
京ICP备 17062397号