https://pan.baidu.com/s/1YBqXVaUImGS1ZJcxPa9HCw

Linear Program(LP)

线性规划是一个优化问题：

• 待优化的目标是一个线性函数，要么是求最小要么是求最大
• 有可行解（可行空间由一系列不等式）

标准形式

• 所有不等式不等号相同
• 所有变量非负
• 一个没有被约束的变量，被两个非负变量代替

• 一个非正数$x_1 \leq 0$ 被 $x_2 = -x_1 \geq 0$

• 等式可以用两个不等式代替

$x_1 - x_2 = 100 \Longleftrightarrow x_1 - x_2 \leq 100 and x_1 - x_2 \geq 100$