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 術語進行交叉引用。