线性规划LP
适用条件
- 解满足一定的约束条件
- 在所有满足约束的可能解中，根据某个定义良好的评判标准，该解是最优的
- 约束条件和优化准则都可以表示为线性函数
线性约束条件可以转换为矩阵和向量的形式
例外
- 约束条件过紧，导致所有约束不能同时满足
- 约束条件过松，导致可行区域无界
单纯形法
该方法沿着凸可行区域的表面移动，不断改进目标函数值，最终找到最优解
归约
如果解决某个计算任务Q的算法可以用于求解计算任务P，则我们说P可被归约到Q。归约增强了算法的能力，对于线性规划而言这一点尤为重要。
线性规划
线性规划形式上自由度很大
- 可能是最大化问题也可能是最小化问题
- 约束条件可能是等式也可能是不等式
- 变量可以具有任意符号
但这些不同形式的线性规划都可以通过简单的归约实现相互转化
- 目标函数两边同时乘以-1，可将最大值问题转变为最小值问题（或者反之）
- 引入新的参数（例如s），将条件中的不等式转变为等式，其中s成为不等式的松弛变量
- 对于不确定符号的变量x，引入两个非负的变量,用替代x
因此我们可以将任意LP归约到具有某种特定形式的LP。这种形式成为LP的标准型，其中所有的变量非负，采用等式约束条件，并且都以目标函数最小化为目标
网络流问题
LP解法
给定有向图G=(V, E)，其边容量为
，使其满足如下约束：
-
不超过边的容量，
- 对于s和t之外的任意节点u，流入u的流量等于流出u的流量
同时，使如下线性目标函数取值最大：
-
起点出发的所有总和最大或者至终点出发的所有总和最大
最大流问题被归约成了一个线性规划问题
最小分割最大流定理
若将网络流中的节点分为两个不相交的集合L和R，并使s和t分别属于L和R。由于网络流必须经过L到达R，因此，没有哪个流的规模能够超过L到R的边的总容量。
网络图中最大流的规模等于其中(s, t)分割的最小容量
应用：完美匹配
对偶
在网络流中流的规模总是小于分割的容量，只有最大流和最小分割完全一致，并且相互确保了对方的最优性。实际上，每个线性的最大化问题都有一个对偶的最小问题，而且前后两个问题之间的关系非常类似于流与分割之间的关系。
构造对偶问题
- 为每个约束条件指定一个乘法因子
- 对原问题目标函数中的每个变量，写出对偶问题中相应的约束，使得不等式约束的右侧值总是大于原问题目标函数中该变量的系数
- 以原问题约束条件右侧值为系数的对偶问题目标函数求最优解
原问题
即
对偶问题
矩阵转置即是把矩阵的行列互换
如果一个线性规划的最优目标函数值有界，则其对偶的最优目标函数值也有界，并且二者相等
