Optimization in Computer Engineering

线性规划

模型：

$\begin{aligned} \max z &= 2x + y \\ \text{s.t.}\quad 5y &\leq 15 \\ 6x + 2y &\leq 24 \\ x + y &\leq 5 \\ x, y &\geq 0 \end{aligned}$

略，见ppt。

单纯形法要求：

$\max/\min\ z=c^{T}x\qquad \text{s.t.}\quad Ax=b,\ \ b\ge0,\ \ x\ge0$

即：约束全为等式、右端项非负、变量非负。

基：从 $A$ 中取 $m$ 个线性无关列组成的方阵 $B$ ；对应变量为基变量 $x_B$ ，其余为非基变量；
基本解：令非基变量 $=0$ ，解 $Bx_B=b$ 得 $x_B=B^{-1}b$ ；若 $x_B\ge0$ 则为基本可行解，对应可行域的一个顶点（角点）；
基本解总数 $\le C_n^m=\dfrac{n!}{m!\,(n-m)!}$ ，规模稍大即无法枚举 → 单纯形法只考察其中一小部分。

基	$z$	各变量列	解（右端项）
$z$ 行	1	目标行系数（约化成本）	$-z$ 或 $z$ 的当前值
各基变量行	0	约束系数（枢轴运算后为单位阵结构）	基变量当前值

step 1 确定初始基本可行解。

step 2（最优性条件） 在 $z$ 行中检查非基变量系数：

step 3（可行性条件） 对进基列计算比值 $\dfrac{\text{解列}}{\text{进基列系数}}$ ，只取分母严格为正的行；取最小非负比值对应的基变量离基。

step 4（枢轴运算 / Gauss–Jordan）

其实step4就是把枢轴列变为单位正交向量的线性变换

返回第 2 步。

（1）大 M 法

化标准型；对没有松弛/剩余变量可作初始基的每个等式，加入人工变量 $R_i$ ；
目标函数中对人工变量施加巨额惩罚：最大化取系数 $-M$ ，最小化取 $+M$ （ $M\to\infty$ ）；
一致性调整：因 $R_i$ 在目标行有非零系数，须用行变换把 $R_i$ 从 $z$ 行消去，使 $z$ 行右端项与当前基取值一致（否则后续判据失效）；
按主流程迭代；
判别：迭代结束时若人工变量仍取正值 → 原问题无可行解；若人工变量全部归零 → 所得即最优解。

（2）两阶段法

阶段 I：加入人工变量，构造辅助目标 $r=\sum_i R_i$ $r = \sum_{i} R_{i}$ （无论原问题是 max 还是 min，一律最小化人工变量之和），按主流程迭代：
- 若 $\min r>0$ → 原问题无可行解，结束；
- 若 $\min r=0$ → 得到原问题的一个基本可行解，转阶段 II。
阶段 II：删去人工变量列，恢复原目标函数；先用行变换把目标行调整为与当前基一致，再按 2.4 迭代至最优。

情形	判别准则	说明	处理
退化	可行性条件出现最小比值并列；迭代后某基变量取 0	存在多余约束；理论上可能循环	任选其一离基继续；检查模型冗余
无穷多最优解	最优表中某非基变量在 $z$ 行的系数为 0	目标等值线平行于紧约束	令该变量进基可得另一最优顶点；可按其他偏好选解
无界解	进基列所有系数 $\le0$ （无非正分母，无离基变量）而 $z$ 行仍有改进系数	模型漏约束或参数错误	可能是模型缺陷
不可行解	用大 M/两阶段后，最优表中人工变量仍为正	约束不相容	可能是约束冲突

对标准型 $\max z=c^{T}x,\ Ax=b,\ x\ge0$ ，取基 $B$ ：

$x_B=B^{-1}b,\qquad z=c_Bx_B=c_BB^{-1}b$

任意迭代步的单纯形表可整体写成

	$z$	原变量	松弛变量	右端
$z$ 行	1	$c_BB^{-1}A-c$	$c_BB^{-1}$	$c_BB^{-1}b$
约束行	0	$B^{-1}A$	$B^{-1}$	$B^{-1}b$

绝对值最小化 $\min\sum_j c_j|x_j|$ ：令 $x_j=x_j^{+}-x_j^{-}$ ， $|x_j|=x_j^{+}+x_j^{-}$ ，化为 LP；最优时 $x_j^{+},x_j^{-}$ 至少一个为 0。
min–max（最大成本最小化） $\min\ \max_{k}\sum_j c_{kj}x_j$ ：引入标量 $z$ ，改为 $\min z$ s.t. $\sum_j c_{kj}x_j\le z\ (\forall k)$ ，其余约束不变。
曲线拟合的误差度量：最小二乘（平方和，非线性）／最小绝对偏离（绝对值和，可写 LP）／最小最大偏离（ $\max|e_i|$ ，可写 LP）。选不同度量即得不同模型。