线性规划——1
1. 线性规划的标准形式
①目标函数的优化方向都是求,可以通过将取反转化
②为了使非平凡约束中的关系始终为等号:
- 松弛变量:引入新变量,使小于等于号变等号
- 剩余变量:引入新变量,使大于等于号变等号
③为了使平凡约束中的关系始终大于等于0(即消除*变量):
2. 线性规划的基本概念
对于标准线性规划:
①基: 中列向量组成的线性无关的矩阵(矩阵可逆),叫线性规划式的基
②基向量: 基中任意一个列向量为一个基向量
③基变量: 基向量对应原线性规划的变量为基变量,其余为非基变量
④基本解: 方程组的解,,其余非基变量全部为0,这样基变量的值和非基变量的值构成原线性规划的解,叫基本解。若基变量都非0,即基本解中非0个数为,则为非退化的基本解,否则为退化的基本解。
⑤可行解: 在约束域S中的向量:
⑥基本可行解: 既是基本解又是可行解的向量,即所有分量非负的基本解,因为基本解已经满足非平凡约束了
⑦最优基可行解: 所有基本可行解中,目标函数值最优的,叫最优基可行解。最优基可行解对应的基叫最优基
⑧顶点、极点: 设,是凸集,如果不能表示为中其它任 意两个不同点的凸组合,则称为的顶点或极点
3. 解的基本性质
①设是标准线性规划的可行解,则是基可行解的充要条件是的非零分量在中所对应的列向量组线性无关
说明:可行解保证了,因此要保证是基可行解,只需保证对应的向量组为基即可,即的非零分量在中所对应的列向量组线性无关。
②标准线性规划的可行解是可行集的顶点的充要条件是是基可行解
说明:主要告诉我们是基可行解则是可行集的顶点
③若标准线性规划有最优解,则必在其可行集S的顶点处取得
4. 单纯形法
方法背景: 找出标准线性规划所有的基可行解很困难,尤其当时,指数时间
基本思想: 从线性规划的某一个顶点出发,沿着使目标函数值下降的方向寻找下一个顶点
前提假设: 我们在原线性规划中能找到一个单位矩阵的基,设
原线性规划可以转化为如下形式
①最优解判别准则(如何判断我们得到的解是否是最优解,然后终止迭代):
上述的一个基可行解为,目标函数值为:
设是任意一个可行解,用非基变量表示,目标函数值为:
当对于任意一个可行解,都有时,此时的基可行解为最优解,即
因为,若,则有
结论:对于存在单位矩阵基的线性规划,当时,即所有判别数则就是这个线性规划的最优解
用分量形式表示,是一个单位向量,基变量和非基变量的判别数表示如下(基变量的判别数为0,实际其对应的可以看作单位矩阵,不用算一定为0):
结论: 若线性规划的某个判别数,而相应的列向量,则线性规划无最优解。由于基变量的判别数一定为0,因此可以缩小范围。若非基变量的判别数,而相应的列向量(所有分量小于等于0),则线性规划无最优解