线性规划

框架图先放在这里

图片由知乎 @运筹说 提供，原文链接：https://zhuanlan.zhihu.com/p/382644742

线性规划模型标准型

标准型如上

• 目标函数求max；
• 约束条件两端用“=”连结；
• 右端常数项非负；
• 所有决策变量非负。（如有决策变量没有约束，则把该变量拆成两个正数变量之差）

图解法

画图然后求解，对二元的可用，多个变量就不好用了，无法用代码写，就不详述了

单纯形法

名词概念

基：B是线性规划问题的一个基，是满秩子矩阵。B中的每一个列向量称为基向量P(j=l,m)与基向量P对应的变量x(j=l···,m)称为基变量。线性规划中除基变量以外的变量X(j= m+1,n)称为非基变量

基解：除了基，其余的非基变量都为0，解得的解叫做基解

基可行解：满足非负约束条件的基解成为可行解

可行基：对应于基可行解的基称为可行基

退化解：非零基变量的个数小于m的基本解，即某个基变量取值为0

定理

• 定理1：若线性规划问题存在可行解，则问题的可行域是凸集。
• 引理：线性规划问题的可行解为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。
• 定理2：线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。
• 定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解。

基本原理

单纯形法迭代的基本思路是：先找到一个初始的基可行解，判定其是否为最优解，如为否，则转换到相邻的基可行解，并使目标函数值不断增大，一直找到最优解为止。

大M法和两阶段法

单纯形表发依靠画表求解，有两个进阶的方法，叫大M法和两阶段法

• 一些线性规划问题在化为标准形后约束条件系数矩阵不存在单位矩阵，就需要在约束条件中添加人工变量构造一个新的线性规划问题。叫做大M法
• 用大M法处理人工变量，在用电子计算机求解时，对M只能在计算机内输入一个机器最大字长的数字。如果线性规划问题中的参数值与这个代表M的数比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。第一阶段 先求解目标函数中只含有人工变量的线性规划问题。第二阶段 若第一阶段表明有可行解，则去除人工变量，目标函数回归标准型式，从第一阶段的最终单纯形表出发继续迭代。