GLPK/背景理论

有时，为此维基教科书中其他地方的材料提供背景理论可能会有用。此页面提供了一个位置。但此页面不应用于盲目复制官方 GLPK 手册中的基础材料，也不应用于撰写关于线性规划的一般条目。

方向

寻求方向的读者可以参考以下维基百科页面

• 线性规划 (LP)
• 混合整数规划 (MIP)（一种线性规划）
• 纯整数规划 (IP)（其中一部分适合线性规划）
• 网络流（通常是线性规划的专门化）
• 图论和组合优化（其中一部分适合线性规划）

另请注意，混合整数规划 (MIP) 和混合整数线性规划 (MILP) 在这里被视为同义词。并且术语纯线性规划用于排除混合整数问题。

卡罗什-库恩-塔克 (KKT) 最优性条件

在非线性规划 (NLP) 的一般情况下，卡罗什-库恩-塔克 最优性条件 (KKT) 为解是局部最优的提供了必要的充要条件（以及必须满足的某些正则性条件）。线性规划 (LP) 是 NLP 的一个特例，其中可行域和目标函数都是凸的。在这种情况下，KKT 条件本身对于解是全局最优的既是必要条件又是充分条件。 KKT 条件可以应用于任何 LP 问题的基本解和内点解，但不能应用于混合整数线性规划 (MIP) 的解。也就是说，前两个 KKT 条件可以应用于混合整数规划以确认解是可行的。

此维基教科书还描述了GLPK 报告 KKT 的具体细节，并提供了一个典型示例.

KKT 最优性条件

以标准形式取一个原始 LP 问题：

最小化	$z=\mathbf {c} ^{\top }\mathbf {x}$
受制于	${\begin{aligned}A\mathbf {x} &=\mathbf {b} \\\mathbf {x} &\geq \mathbf {0} \end{aligned}}$

其中$\mathbf {x}$是原始变量的向量。对偶 LP 问题变为

最大化	$p=\mathbf {b} ^{\top }\pi +\mathbf {0} ^{\top }\lambda$
受制于	${\begin{aligned}A^{\top }\mathbf {\pi } +\lambda &=\mathbf {c} \\\mathbf {\lambda } &\geq \mathbf {0} \\\pi &\quad {\text{of any sign}}\end{aligned}}$

其中 $(\pi \,|\,\lambda )\,\!$ 是对偶变量的向量， $\pi \,\!$ 是等式约束 $A\mathbf {x} =\mathbf {b}$ 的拉格朗日（或单纯形）乘数（影子价格）向量，而 $\lambda \,\!$ 是不等式约束 $\mathbf {x} \geq \mathbf {0}$ 的拉格朗日乘数（折算成本）向量。

卡鲁什-库恩-塔克（KKT）最优性条件利用了原始和对偶公式中的所有约束，并包含一个互补松弛条件。五个 KKT 最优性条件是

KTT.PE	$A\mathbf {x} =\mathbf {b}$
KTT.PB	$\mathbf {x} \geq \mathbf {0}$
KTT.DE	$A^{\top }\mathbf {\pi } +\lambda =\mathbf {c}$
KTT.DB	$\lambda \geq \mathbf {0}$
KTT.CS	$x_{j}=0\ {\text{or}}\ \lambda _{j}=0\ {\text{for all}}\ j\ {\text{(or both)}}$

TheKKT.CS条件可以改写为 $x_{j}\lambda _{j}=0\,\!$ 或 $\lambda ^{\top }\mathbf {x} =\mathbf {0}$，意味着向量 $\mathbf {x}$ 和 $\lambda \,\!$ 必须是正交的。

KKT 条件在 GLPK 中的实现稍微复杂一些，因为 GLPK 支持具有较低 $l_{j}\,\!$ 和上限 $u_{j}\,\!$ 边界的变量，这也意味着没有边界。一般来说

最小化或最大化	$z=\mathbf {c} ^{\top }\mathbf {x}$
受制于	${\begin{aligned}&(I\;|\;-\!A)\mathbf {x} =\mathbf {0} \\&\mathbf {l} \leq \mathbf {x} \leq \mathbf {u} \end{aligned}}$

其中$\mathbf {x}$（如前所述）是结构和辅助变量的向量，而$I\,\!$是一个单位矩阵。尽管如此，GLPK中使用的条件等同于上面显示的条件，并且具有相同的含义。

最后，请注意，KKT条件KKT.PE和KTT.PB可以针对MIP解决方案计算，而GLPK将根据请求执行此操作。在这种情况下，这两个条件被描述为“整数可行性条件”，而不是“卡罗什-库恩-塔克最优性条件”。

另请参见

Tommi Sottinen 的关于运筹学 的课程笔记提供了 KKT 条件的 LP 证明，并将这些结果与 GLPK 术语进行交叉引用。