建模、化归

建模技巧

分段线性凸的目标函数可以转化为线性规划 绝对值目标函数可以转化为线性规划

标准形式

$\begin{array}{rl} \text{min} & c^Tx\\ \text{s.t.} & Ax=b\\ & x \succeq 0 \end{array}$ 任意形式的线性规划转化为标准形式的方法： 1. 无约束变量：转化为两个非负变量之差 2. 不等式约束：添加松弛变量变等式约束 3. max 目标：minimize 其相反数

最简形式

$\begin{array}{rl} \text{min} & c^Tx\\ \text{s.t.} & Ax \succeq b \end{array}$ 任意形式的线性规划转化为最简形式的方法： 1. 等式约束：等价于 $\ge$ $\le$ 两个不等式约束 2. $\le$ 约束：取负号变 $\ge$ 约束 3. max 目标：minimize 其相反数

单纯形算法

对偶问题

敏感性分析