线性规划

线性规划的定义

线性规划（英语：Linear Programming，简称LP）是一种数学方法，通过线性方程或不等式描述问题的约束条件和目标，以实现最佳结果（例如利润最大化或成本最小化）。作为最优化的一种特例，线性规划在许多领域都有重要应用。

那一堆概念就不学了（？），主打一个会算就行。

线性规划 维基百科

图解法

画图，获得一个有界凸多边形

上例中求解得到问题的最优解是唯一的。
但对一般线性规划问题, 求解结果还可能出现以下几种情况:

1. 无穷多最优解(多重最优解)，见图2-4。（目标函数直线最终与约束条件边界线重合）
2. 无界解，见图2-5。（可行域无界, 目标函数值可以增大到无穷大）（模型有误，缺乏必要的约束条件）
3. 无可行解，见图2-6。（可行域为空集）（模型有误，有矛盾的约束条件）

• 当线性规划问题的可行域非空时, 它是有界或无界凸多边形。
• 若线性规划问题存在最优解, 它一定在有界可行域的某个顶点得到;
• 若在两个顶点同时得到最优解, 则它们连线上的任意一点都是最优解, 即有无穷多最优解。

图解法只适合变量数为2的情况。

单纯型法

概念是不懂的，但是我算算算。

线性规划的标准型

规则：

1. 目标函数：若为最小化（），左右取负转化为最大化（）
2. 约束方程：加/减松弛变量，然后不等式变等式
   1. 约束方程为“”不等式，则可在“”不等式的左端加入非负松弛变量，把原“”不等式变为等式；
   2. 约束方程为“”不等式，则可在“”不等式的左端减去一个非负剩余变量(也可称松弛变量)，把原“”不等式变为等式。
   3. 若存在取值无约束的变量，可令，其中

其中，松弛变量表示没有被利用的资源

例1：

变为：

例2：

变为

单纯形表

例1：

								(分母为零)

列表方法：

1. 将目标函数和约束条件填入表中。 分别为约束条件右侧的常数， 是对应 的价值变量（初始都为0，是 乘上目标函数的对应系数）。
2. 看最后一行[2,3,0,0,0]，其中最大的是 列的 ，即
3. 对于第 行，若 ，求 （ 时不算）
4. 取 的最小值，对应 出基。
5. 以 为主元素进行初等行变换（旋转或迭代），使第 列变换为 ，在 列用 行 替换 行

第5步，具体的：

首先， 对应行进行初等行变换 ，将 化为

状态
第3行变换前
第3行变换后

接着，其它行进行初等行变换的倍加操作，将 列的数化 0。

变换前
变换后
						变换
						无
					无

这一轮变化下来，求得新表

最后一行的检验数依然有正数，取最大正数。
重复第5步的换入变量和初等行变换，并求新的 ，得到

								分母为负

最后一行的检验数依然有正数，取最大正数。
重复第5步的换入变量和初等行变换，并求新的 ，得到

最后一行的检验数已经没有正数了

解得最优解
目标函数的最大值

参考❀华科mooc

此博客后面修改了计算错误（应该是从纸到电子稿，表格抄错了）