延續上一篇 [最佳化] 淺談線性規劃(0)- Standard form of Linear Programming ,這次要跟大家介紹 線性規劃(LP)問題的求解。由先前介紹我們知道,對任意含有線性不等式拘束的LP問題都可以將其轉換成標準型式的LP問題。亦即含有 等式拘束的LP問題。 \[\begin{array}{l} \min {c^T}x\\ s.t.\\ \left\{ \begin{array}{l} Ax = b,\\ x \ge 0 \end{array} \right. \end{array}\]其中 $A$ 為 $m \times n$ 矩陣且 $n>m$, $rank(A) = m$,$A$ 沒有全為零的column$;b \geq 0$, 在介紹之前要先介紹兩種解的概念 ============================ Definition: (Feasible solution and Basic solution) 一個向量 $x \in \mathbb{R}^n$ 稱作 可行解(Feasible solution) ,如果其滿足拘束條件,亦即 $x \geq 0$ 且 $Ax=b$ 一個向量 $x \in \mathbb{R}^n$ 稱作對 $Ax=b$ 的 基本解( Basic Solution) ,若 $x$中 nonzero component 對應到$A$矩陣的線性獨立 Columns。 ============================ 先給個例子看看這兩種解有甚麼不同 Example 考慮下列拘束條件 $Ax=b$: \[\left[ {\begin{array}{*{20}{c}} 1&2&{ - 2}\\ 1&3&{ - 2} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{x_1}}\\ {{x_2}}\\ {{x_3}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 1\\ 1 \end{array}} \right]\] 觀察上式,為三個變數兩個拘束條件,故可以任意其中
If you can’t solve a problem, then there is an easier problem you can solve: find it. -George Polya