线性规划与目标规划¶
约 7000 个字 1 张图片 预计阅读时间 23 分钟
线性规划与单纯形法¶
| 内容 | 重要性 | 描述和注 |
|---|---|---|
| 单纯形表(单纯形法) | ⭐⭐⭐⭐⭐ | 整个线性规划问题的核心，剩余的方法都建立在这之上 |
| 对偶问题转换 | ⭐⭐⭐ | 注意变量约束和条件约束的符号变化即可 |
| 利用对偶原理快速计算最优解 | ⭐⭐⭐⭐ | 主要掌握对偶定理和互补松弛性 |
| 对偶单纯形法 | ⭐⭐⭐⭐ | 与单纯形表极其类似所以前面掌握的好会比较容易掌握 |
| 灵敏度分析 | ⭐⭐⭐ | 改变原本的一些参数判断最优解的变化 |
线性规划问题及其数学模型¶
目标
- 了解线性规划模型的提出和背景
- 能够使用图解法求解线性规划问题
参考资料：如何理解线性规划中的单纯形法和单纯形表？
问题提出¶
简单来说就是约束条件为线性函数，并且想要求解某个函数(目标函数)的最值的优化问题，从实际问题中抽象出线性规划模型.
图解法¶
非常的容易，实际上就是利用图形解决二维的线性规划问题，我们曾经在小学二年级学习过这种方法.
主要的聚焦点在于这个简单的二维情形给出的一些启发:
- 解的情况
- 无穷多最优解
- 无界解
- 无可行解
- 唯一最优解
线性规划问题的标准形式¶
可以使用向量表示也可以使用矩阵
将多种情况化归为简单的一种情况讨论是数学上常用的思想，我们在这里也可以将多种情况都归结于标准形式的线性规划问题的解决：
- 目标函数(最大化)
- 如果是最小化，则加负号即可
- 约束条件(不等式)
- 如果是\(\leqslant\)形式，可以采取在左边加入松弛变量的方法
- 相反是\(\geqslant\)形式，则采用在左边减去一个松弛变量的做法
- 如果是无约束的变量可以使用两个非负变量相减代替
线性规划问题的解概念¶
可行解
满足约束条件的解称为可行解，使目标函数达到最大值的可行解称为最优解
基，基向量，基变量
\(B\)是系数矩阵\(A\)中的\(m\times m\)阶非奇异子矩阵(\(\lvert B \rvert\neq 0\))，则称\(B\)为基
\(P_{j}(j=1,2\dots,m)\)为基向量
\(x_{j}(j=1,2\dots,m)\)为基变量
基解
\(m\)个方程,\(n\)个变量(n>m)，选择其中\(\binom{n}{n-m}\)个为0，求出基解:max=\(\binom{n}{m}\)
由于选取的矩阵是非异阵所以满秩，也就是线性无关
基可行解，可行基
满足非负条件的基解也称为基可行解，对应基可行解的基，称为可行基
线性规划问题的几何意义¶
目标
- 了解解的概念
- 理解部分基本定理
- 理解单纯形法迭代原理
基本概念¶
- 凸集
- 凸组合
- 顶点
利用顶点的定义
顶点的定义是无法用凸集中不同两点进行线性组合得到，本节的部分定理用到了这一定义进行反证.
几个定理¶
Theorem 1
若线性规划问题存在可行域，则可行域为凸集
Proof is easy
Lemma 1
线性规划问题的可行解为基可行解\(\iff\)\(X\)的正分量对应的系数列向量是线性无关的
Proof.
\(\implies\)
由定义可以知道，基可行解的基变量对应系数列向量组成一个基(线性无关的向量组的子集仍然线性无关)，基是系数矩阵的满秩子矩阵，所以各系数列向量必线性独立
\(\impliedby\)
不妨设出k个正分量且线性独立，必有\(k\leqslant m\)，相等时构成基，显然成立，否则可以使用基扩张定理构造出新的基，使其为X
Theorem 2
线性规划问题的基可行解\(X\)对应于可行域\(D\)的顶点
Proof.
反证法，转而证明非可行域顶点\(\iff\)非基可行解
\(\impliedby\)
构造\(X=\left( X_{1},X_{2},\dots,X_{k},0,\dots,0 \right)\)，前k个系数列向量线性相关(利用引理)，得到一个零元，利用零元构造两个可行解，对其进行线性表出，证明X不是顶点
\(\implies\)
利用不是顶点，就可以用顶点线性表出，构造出线性相关即可
Lemma 2
若\(K\)是有界闭凸集，则任何一点\(X\in K\)可表示为\(K\)的顶点的凸组合
Theorem 3
若是可行域有界，线性规划问题的目标函数一定可以在可行域顶点上达到最优
换言之，若线性规划问题有最优解，一定存在一个基可行解为最优解
假设最优解，利用定理2，反证不是顶点，构造\(X_{0}+\mu\delta,X_{0}-\mu\delta\)，得到无穷多个最优解(那么可以移动至顶点，有界性保证了一定可以取到)
基本结论
线性规划问题所有的可行解构成一个凸集，或者无界域，有限多个顶点，每个基可行解对应可行域的一个顶点
若是有最优解，一定可以在顶点上得到，而顶点数目有限那么全部遍历后一定就可以得到最优解，但是如果\(m,n\)较大，全部遍历是不太现实的，所以提出了单纯形法
如果在一个顶点上的值优于周围顶点，一定是最优解
单纯形法¶
目标
- 掌握单纯形法的计算步骤
- 利用单纯形法判别解的形式
- 掌握单纯形法的几种变形
- 了解修正单纯形法的改进
1947年在美国五角大楼工作，Dantzig常常被空军要求去解实际的计划问题：分配空军的人力、经费、飞机和其它资 源。他给这些问题建立了线性规划模型，并提出著名的单纯形法(Simplex Method)。
粗糙过程¶
基本思路：从线性方程组中找出一个个单纯形，每个单纯形可以求得一组解，然后判断该解使目标函数变大或变小，决定下一步的单纯形，也就是迭代的过程，直到实现了最大值或最小值为止.
要想更好的掌握这种方法最好是选取两三个例子自己进行迭代，这里只是给出普通的理论方法
- 先化为标准形式
- 找出一组基(base，通常为单位阵)，用非基变量表示基变量
- 将目标函数化为非基变量的组合
- 取非基变量为0，得到一个基可行解
- 判定：如果目标函数中还有正系数的非基变量就可以更换(如果是求最大值)
- 迭代4,5
这里就涉及到换入换出变量的确定问题
- 选择正系数最大的非基变量为换入变量(直观上这使得增速最大)，然后找出换出变量
- 让非基变量中的不换入变量为0，就可以得出一个用换入变量表示原基变量的线性方程组，为了满足非负的要求，选取先接触到极限也就是0的那个变量
确定换入换出变量后就可以重新构建方程组和基变量了，再使所谓的非基变量为0(重复4)，得到另一个基可行解，如果非基变量的系数还是正的，说明可以继续迭代，重复上述过程，确认换入换出变量，然后取0，得到新的基可行解，当所有的非基变量系数为负数时，说明达到了最大值.
初始基可行解的确定¶
对于上面给出的做法，我们发现首先要确定初始的基可行解，方法如下
1. 直接观察
2. 加入松弛变量
3. 加入非负人工变量
加入人工变量的方法
实际上是为了构造出类似松弛变量那样的单位矩阵，采用人造基的方法，可以使用大\(M\)法，\(M\)是相当大的正数(可以理解为正无穷),对人工变量起到惩罚的作用,逼迫辅助线性规划的最优解中人工变量均为0
这里给出一个矩阵方法的简单推导：
还需要一个单纯形乘子的定义\(w=c_{B}B^{-1},z_{i}=wp_{i}\)
最优性检验与解的判别¶
由于线性规划问题求解过程中解的多样性，我们需要建立解的判别准则
- 最优解的判别定理
由此可得最优解判定定理，若\(X_{0}\)代表一个基可行解，而且对于一切的\(j=m+1,\dots,n，\sigma_{j}\leqslant 0\)，则称为最优解，其中\(\sigma_{j}\)为检验数.
- 无穷多最优解判别定理
同样符合1中的条件，检验数均非正，如果存在某个非基变量的检验数为0，那么线性规划问题有无穷多最优解
- 无界解判别定理
基变换¶
针对初始基可行解不是最优解也不能判别无界时，需要找新的基可行解
方法是从原本的可行解基中更换一个列向量，并且保证线性独立，得到新的可行基，称为基变换.
涉及到前面的一些规则再次阐述，尤其是\(\theta\)规则的部分，选择最小的换出
迭代(旋转)¶
由于原本是单位阵，那么逆阵应该也是单位阵，进行主元消去恰好是进行逆变换也就是乘上逆矩阵的做法，得到的下一个矩阵也是单位阵，于是可以一直使用主元消去的方法.
单纯形法的计算步骤¶
综合上方的矩阵做法和理论推导，将运算简化为表格计算，得到下方的单纯形表
单纯形表¶
为了便于理解计算关系，设计一种表用于计算，称为单纯形表，功能与增广矩阵相似，可以将线性约束关系与目标函数组成\(m+1 \times n+1\)的方程组
给出一个矩阵的表示：
| f | \(x_{B}\) | \(x_{N}\) | 右端 | |
|---|---|---|---|---|
| \(x_{B}\) | 0 | \(I_{m}\) | \(B^{-1}N\) | \(B^{-1}b\) |
| f | 1 | 0 | \(c_{B}B^{-1}N-c_{N}\) | \(c_{B}B^{-1}b\) |
这是一种展开的表示方法，其中第一行不是表的一部分，只是表头
计算步骤¶
第二张表称为初始单纯形表，每迭代一次就构造一个新的单纯形表
- 先建立初始单纯形表
- 检查检验数，如果没有得到最优解，转入下一步
- 在检验数为正的列向量中确认最大的为换入向量
- 找到出基变量，方法是\(\theta\)检验法
- 高斯消去法得到新的单纯形表
- 重复2-5
只需要一个例子就可以明白了.
| \(c_{j}\) | \(\to\) | 2 | 3 | 0 | 0 | 0 | ||
|---|---|---|---|---|---|---|---|---|
| \(C_{B}\) | \(X_{B}\) | b | x1 | x2 | x3 | x4 | x5 | \(\theta\) |
| 0 | X3 | 8 | 1 | 2 | 1 | 0 | 0 | 4 |
| 0 | X4 | 16 | 4 | 0 | 0 | 1 | 0 | - |
| 0 | X5 | 12 | 0 | [4] | 0 | 0 | 1 | 3 |
| - | z | 0 | 2 | 3 | 0 | 0 | 0 |
可知x2为换入变量，再计算\(\theta\)，得到最小值是3，它所在行对应的x5是换出变量，所在行和所在列交叉处的[4]称为主元素或枢元素(pivot element)
利用主元素将所在列变为\((0,0,1)^{T}\)，然后将\(x_{2}\to x_{5}\)
| \(c_{j}\) | \(\to\) | 2 | 3 | 0 | 0 | 0 | ||
|---|---|---|---|---|---|---|---|---|
| \(C_{B}\) | \(X_{B}\) | b | x1 | x2 | x3 | x4 | x5 | \(\theta\) |
| 0 | X3 | 2 | [1] | 0 | 1 | 0 | \(-\frac{1}{2}\) | 2 |
| 0 | X4 | 16 | 4 | 0 | 0 | 1 | 0 | 4 |
| 3 | X2 | 3 | 0 | 1 | 0 | 0 | \(\frac{1}{4}\) | - |
| - | z | -9 | 2 | 0 | 0 | 0 | \(-\frac{3}{4}\) |
发现有\(c_{1}-z_{1}=2>0\)，说明x1为换入变量，换出变量是x3
| \(c_{j}\) | \(\to\) | 2 | 3 | 0 | 0 | 0 | ||
|---|---|---|---|---|---|---|---|---|
| \(C_{B}\) | \(X_{B}\) | b | x1 | x2 | x3 | x4 | x5 | \(\theta\) |
| 2 | X1 | 2 | 1 | 0 | 1 | 0 | \(-\frac{1}{2}\) | - |
| 0 | X4 | 8 | 0 | 0 | -4 | 1 | [2] | 4 |
| 3 | X2 | 3 | 0 | 1 | 0 | 0 | \(\frac{1}{4}\) | 12 |
| - | z | -13 | 0 | 0 | -2 | 0 | \(\frac{1}{4}\) |
x5为换入变量，换出变量是x4
| \(c_{j}\) \(\to\) | 2 | 3 | 0 | 0 | 0 | |||
|---|---|---|---|---|---|---|---|---|
| \(C_{B}\) | \(X_{B}\) | b | x1 | x2 | x3 | x4 | x5 | \(\theta\) |
| 2 | X1 | 4 | 1 | 0 | 1 | \(\frac{1}4\) | 0 | |
| 0 | X5 | 4 | 0 | 0 | -2 | \(\frac{1}{2}\) | 1 | |
| 3 | X2 | 2 | 0 | 1 | \(\frac{1}{2}\) | \(-\frac{1}{8}\) | 0 | |
| - | z | -14 | 0 | \(-\frac{3}{2}\) | \(-\frac{1}{8}\) | 0 | 0 |
单纯形法的进一步讨论¶
人工变量法¶
基本思想
原本的做法需要依靠加入松弛变量构造出初始的单位阵作为基向量，但是如果不是符合\(\leqslant\)的方程就无法按照原本的方法进行，这时候可以考虑人工变量法直接加入基变量构造出单位矩阵，仍然得到初始基可行解，但是如果不加以约束，这显然会出现不符合题设的解
- 由于人工变量是加入原本约束条件的虚拟变量，所以必须要将它们从基变量中逐个替换出来
- 基变量不再含有非零的人工变量表示有解，反之无可行解
- 大M法
思路：如果是求最小值，目标函数中给人工变量赋以很大的系数(惩罚函数)，那么如果要求最小值，就不可能仍然含有人工变量
- 两阶段法
- 第一阶段：不考虑原问题是否存在基可行解，加入人工变量，构造仅含人工变量的目标函数和要求实现最小化，如果最小值为0，则说明原问题存在基可行解，可以进行二阶段计算
- 第二阶段：第一阶段计算得到的最终表除去人工变量，将目标函数换回原问题的目标函数系数，然后以此作为初始表，启动单纯形法
退化¶
使用最小比值规则确定换出变量时发现存在两个以上相同的最小比值，下一次迭代中将出现一个或者几个基变量等于零，这就出现退化解，这时可以采用一些方法规避循环：“摄动法”，“字典序法”.
Remark：Bland规则
1. 选取检验数大于零中下标最小的非基变量为换入变量
2. 按照最小比值规则计算出现两个以上最小比值选取下标最小(或最大)的基变量为换出变量
3. 一定要统一规则
检验数的几种表示形式¶
最大值和最小值选择不同的方向
单纯形法的矩阵描述¶
在上文已提前给出，在此不再赘述(矩阵描述更加简洁但是可能会更依赖代数功底一些)
改进单纯形法¶
传统单纯形法的局限性，换基后新的基变量对应的原始矩阵求逆会造成无谓的计算浪费
求解线性规划问题的关键就是找到\(B^{-1}\)，如果能简化逆阵计算就可以大大缩短时间，做法也是比较固定的：找到主元素，计算新的向量，左乘得到逆阵后即可化为单位阵.
也就是将入基的向量化为出基向量的列向量的样子
- 锁定主元
- 非主元化为零
小结
实际上就是用简单的高斯消去法代替求逆阵的过程，如果是提取阅读了课本或是网上的一些资料可能会发现一开始用的就是改进后的方法.
笔者前面也是直接按照改进后方法计算和书写，老师的讲义中在3.5提到了这一点，也使用的是这一简单方法
单纯形法的小结¶
- 变量处理
- 约束条件处理
- 目标函数
- 大M法
- 两阶段法
大M法
如果需要使用计算机的机器语言进行求解，大M法中的M不够明确就有可能出现无法正确求解的问题，所以进一步讨论两阶段法，保证过程的明确且唯一。
对偶理论和灵敏度分析¶
目标
- 对偶问题
- 对偶的含义
- 对偶问题的一般形式
- 基本性质
- 单纯形法的矩阵描述
- 对偶问题的基本性质
- 影子价格
对偶问题的提出¶
网课中有一个例子笔者觉得不错，就是以两个公司相互交易的角度，原本是卖方而转换为买方，那么如何获利最大化就是将收购对方公司的资本降到最低，这也就是目标，然后就是对方凭什么让出资源，那么就需要约束，让出所得不低于原有盈利。这也就是经典的生产问题和资源收购问题。
注意：但是有些问题的对偶问题不一定有比较明确的现实意义，但是只要是线性规划问题一定有它对应的对偶问题。
简单来说就是最大和最小对偶，大于号和小于号调换，将\(C\iff b\)，系数矩阵转置(对调一下自变量)，这样就得到了原线性规划问题(LP)的对偶问题(DP)
转换为：
但是这种方程毕竟还是太简单和特殊了，我们最好还是给出对偶问题的一般形式-非对称形式的转化方法
注：由于对偶问题的对偶问题就是原问题所以可以只掌握最小化或是最大化问题的变化根据不同的原问题选择正推或者逆推进行检验，为了保险起见应当两个都学相互检验。
理论上都应该转化为标准形式然后再进行对偶问题的转换，但是下面给出了一种直接写出的方法。
关于非对称形式的详细解释
可以参考中山大学郭老师的讲解
线性规划的对偶理论¶
转换方法¶
对称的就按照之前的方法进行，如果是不对称的可以将等式分解为两个不等式，再通过加负号的方法转换为单边的不等式约束，然后按对称形式变换关系可写出它的对偶问题(不用那么麻烦直接转置了按照法则对应也可以)
- 目标函数符号相反：最大对偶最小，最小对偶最大(非常容易)
- 将原本的\(b\)系数对调目标函数的系数(也非常容易)
- 新的对偶问题系数矩阵是原矩阵的转置(同样非常容易)
- 下面是唯一具有难度的约束条件和变量的符号转换问题，笔者自己总结了一套规律
- 给出一组对应关系极小化问题对应\(\geqslant\)，极大化问题对应\(\leqslant\)，然后再看下面的问题
- 先看原问题的约束条件，如果符合上面的对应关系，变量约束为\(\geqslant 0\)，如果不符合则改为\(\leqslant 0\)，如果取等就是无约束情况反而简单了
- 再看原问题的变量约束，仍然是那条对应关系只不过以0为分界(极小化问题就是非负限制\(\geqslant 0\)，极大化问题就是非正的限制\(\leqslant 0\))，符合的话约束就是\(\leqslant\)，不符合就是\(\geqslant\)，无约束实际是最简单的直接取等
- 注意：这种对应关系是符合最初的优化生产问题的
复杂一点的例子
根据上面的法则写出对偶问题：
对偶问题的基本性质¶
- 对称性：
- 对偶问题的对偶是原问题
- 弱对偶性：每一个问题的可行解的目标函数值都给出对偶问题的目标函数的界
- \(\overline{X}\)为原问题可行解，\(\overline{Y}\)是对偶问题可行解，\(C \overline{X}\leqslant \overline{Y}b\)
- 无界性：
- 若是原问题为无界解，则对偶问题无可行解
- 最优性：
- \(C \overline{X}=\overline{Y}b\)，\(\overline{X},\overline{Y}\)是最优解
- 对偶定理：
- 两个问题均有可行解
- 若原问题有最优解，那么对偶问题也有最优解，且最优解目标函数值相等
- 互补松弛性：很重要，可以很好的简化得到对偶问题最优解的过程
- \(\overline{X},\overline{Y}\)为原问题和对偶问题可行解，\(\overline{Y}X_{S}=0,Y_{S}\overline{X}=0 \iff \overline{X},\overline{Y}\)最优解
- 以下是从课本(最优化理论与算法-陈宝林)中的摘取(感觉比Slides详细)
- 如果\(x^{(0)},w^{(0)}\)是原问题和对偶问题的可行解，那么两者均为最优解的充要条件是对于任意的\(i,j\)，满足
-
- 如果\(x_{j}^{(0)}>0\)，就有\(w^{(0)}p_{j}=c_{j}\)
-
- 如果\(w^{(0)}p_{j}<c_{j}\)，\(x_{j}^{(0)}=0\)
-
- 如果\(w_{j}^{(0)}>0\)，就有\(A_{i}x^{(0)}=b_{i}\)
-
- 如果\(A_{i}x^{(0)}>b_{i}\)，\(w_{j}^{(0)}=0\)
- 原问题检验数与对偶问题解的关系
补充互补松弛性的应用：
1. 对偶问题取到最优解中变量如果非零，它所对应的约束条件在原问题中取等；如果取零则忽略
2. 原问题也是同理，原因是如果没有办法取等那么松弛变量一定大于零
对偶问题的经济解释——影子价格¶
给出乘子，实际意义应当是其他条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化，本质上是对于具体工厂的具体产品而存在的特殊价格，在完全市场经济条件下，如果某种资源市场价格低于该厂影子价格就可以买进以扩大生产，如果高于企业影子价格则应当卖掉.
对偶单纯形法¶
目标
- 理解对偶单纯形法的基本思路，与普通的单纯形法对比
- 了解对偶单纯形法的计算步骤
根据对偶问题的对称性，可以这样考虑：若保持对偶问题的解是基可行解，即\(c_j−C_BB^{-1}P_j \leqslant 0\)，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代.
基本思路：
- 满足两条性质：可行性和最优性
- 单纯形法：先满足可行性再逐渐逼近最优性
- 对偶单纯形法：先满足最优性，再逐渐逼近可行性
这里的原理还需要了解一下，可以参考胡运权老师书的写法(实际主要就是利用了对偶定理)
计算步骤¶
- 检验数均小于零-对偶问题可行解
- 判断\(b\)列向量是否全部非负，若是，达到最优，停止迭代，否则进入3
- 决定出基变量，选取最小的一个(负值中绝对值最大的一个)
-
确定换入变量，找到主元素
-
确定出基变量
找到\(b\)列中小于零的一行(如果不止一个就选择最小的为出基变量) - 确定入基变量
确定行之后还需要寻找对应行中\(a_{rj}<0\)的非基变量考虑作为入基变量
注：为什么要找小于0的呢，因为换基之后需要化为1，如果是正数无法改变\(b\)的符号仍然为负相当于没有变化
灵敏度分析¶
讨论线性规划问题时其中的常数值实际往往是估计值和预测值，那么就会问
1. 已求得的线性规划问题的最优解有什么变化在系数变化时
2. 在什么范围变化，最优解不会发生什么变化
以下也是针对各种线性规划中常量值的变化进行分析讨论
资源数量变化的分析¶
也就是增加一个矩阵，将变化后的值加到\(b\)列上即可
目标函数中价值系数\(c_{j}\)的变化分析¶
不影响约束增广矩阵，直接在最终的单纯形表里改就可以了，其他的除了检验数应该都不变，也就是只需要重新计算检验数，那么就可以重新迭代。
如果最优解不变需要检验数仍然小于等于0，也就是不需要迭代了，只需要进行不等式组求解就可以了。
技术系数\(a_{ij}\)的变化¶
两种情况
- \(A\)的变化带来\(B\)的变化
过于复杂了，为什么不重做？类似不变化的操作步骤，然后将那一列修正为基向量的0、1形式，构造后可能发现可行性和最优性都发生了变化。 - \(A\)的变化不带来\(B\)的变化
体现在最终的单纯形表上也就是\(B^{-1}A+B^{-1}\Delta A\)
新增变量¶
直接在终表中左乘\(B^{-1}\)和它的系数后加上，但是还需要增加新的基变量，构造新的单位阵
决定是否继续迭代的总结¶
| 可行性 | 最优性 | 方法 |
|---|---|---|
| 不满足 | 满足 | 对偶单纯形法继续迭代 |
| 满足 | 不满足 | 单纯形法继续迭代 |
| 不满足 | 不满足 | 引进人工变量，重新计算 |
| 满足 | 满足 | 最优解不变，停止迭代 |
这里需要比较多的练习进行适应，这样才能确保能够快速选择合适的方法进行计算