线性规划

维基百科，自由的百科全书

在數學中，線性規劃 (Linear Programming，簡稱LP) 問題是目標函數和約束條件都是線性的最優化問題。

線性規劃是最優化問題中重要的領域之一。很多運籌學中的實際問題都可以用線性規劃問題來表述。線性規劃的某些特殊情況，例如網路流問題和多商品流量問題，都被認為很重要，以致產生出對其專門的算法的大量研究。很多的其他種類最優化問題算法中，都用到了將問題分拆成線性規劃子問題，然後求解的方法。歷史上，線性規劃引申出的很多概念，啟發了最優化理論的核心概念，諸如「對偶」、「分解」、「凸性」的重要性及其一般化等。同样地，在微观经济学和商业管理领域，线性规划被大量应用地于收入极大化或生产过程的成本极小化。乔治·丹齐格被認爲是线性规划之父。

线性规划正在翻译。欢迎您积极翻译与修订。
目前已翻译99%，原文在en:Linear Programming。

註：未完成的主要是專有名詞和人名的翻譯。

[编辑] 标准型

描述线性规划问题的常用和最直观形式是标准型。标准型包括以下三个部分：

一个需要极大化的线性函数, 例如

c 1 x 1 + c 2 x 2

以下形式的问题约束，例如:

$a_{11} x_1 + a_{12} x_2 \le b_1$

$a_{21} x_1 + a_{22} x_2 \le b_2$

$a_{31} x_1 + a_{32} x_2 \le b_3$

和非负变量，例如:

$x_1 \ge 0$

$x_2 \ge 0$

线性规划问题通常可以用矩阵形式表达成：

maximize $\mathbf{c}^T \mathbf{x}$

subject to $\mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0$

其他类型的问题，例如极小化问题，不同形式的约束问题，和有负变量的问题，都可以改写成其等价问题的标准型。

[编辑] 例子

以下是一個線性規劃的例子。假設一個農夫有一塊A平方千米的農地，打算種植小麥或大麥，或是兩者依某一比例混合種植。該農夫只可以使用有限數量的肥料F和農藥P，而單位面積的小麥和大麥都需要不同數量的肥料和農藥，小麥以(F₁, P₁) 表示，大麥以 (F₂, P₂) 表示。設小麥和大麥的售出價格分別為 S₁ 和 S₂，則小麥與大麥的種植面積問題可以表示為以下的線性規劃問題：

max $P = S 1 x 1 + S 2 x 2$		（最大化利潤 - 目標函數）
s.t.	$x_1 + x_2 \le A$	（種植面積的限制）
	$F_1 x_1 + F_2 x_2 \le F$	（肥料數量的限制）
	$P_1 x_1 + P_2 x_2 \le P$	（農藥數量的限制）
	$x_1 \ge 0,\, x_2 \ge 0$	（不可以栽種負數的面積）

[编辑] 增广矩阵（松弛型）

在用单纯型法求解线性规划问题之前，必须先把线性规划问题转换成增广矩阵形式。增广矩阵形式引入非负松弛变量将不等式约束变成等式约束。问题就可以写成以下形式：

Maximize Z in:

$\begin{bmatrix} 1 & -\mathbf{c}^T & 0 \\ 0 & \mathbf{A} & \mathbf{I} \end{bmatrix} \begin{bmatrix} Z \\ \mathbf{x} \\ \mathbf{x}_s \end{bmatrix} = \begin{bmatrix} 0 \\ \mathbf{b} \end{bmatrix}$

$\mathbf{x}, \, \mathbf{x}_s \ge 0$

这里 x_s 是新引入的松弛变量, Z 需要极大化的变量.

[编辑] 例子

以上例子的转换成增广矩阵:

maximize $S_1 x_1 + S_2 x_2\,$		(目标函数)
subject to	$x_1 + x_2 + x_3 = A\,$	(augmented constraint)
	$F_1 x_1 + F_2 x_2 + x_4 = F\,$	(augmented constraint)
	$P_1 x_1 + P_2 x_2 + x_5 = P\,$	(augmented constraint)
	$x_1,x_2,x_3,x_4,x_5 \ge 0$

这里 $x_3,x_4,x_5\,$ 是(非负)松弛变量.

写成矩阵形式:

Maximize Z in:

$\begin{bmatrix} 1 & -S_1 & -S_2 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & F_1 & F_2 & 0 & 1 & 0 \\ 0 & P_1 & P_2 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} Z \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} 0 \\ A \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} \ge 0$

[编辑] 对偶

每个线性规划问题，称为原问题，都可以变换为一个对偶问题。我们可将“原问题”表达成矩阵形式：

maximize $\mathbf{c}^T \mathbf{x}$

subject to $\mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0$

而相应的对偶问题就可以表达成以下矩阵形式：

minimize $\mathbf{y}^T \mathbf{b}$

subject to $\mathbf{y}^T \mathbf{A} \ge \mathbf{c}^T, \, \mathbf{y} \ge 0$

这里用“y”来作为未知向量。

[编辑] 理論

幾何上，線性約束條件的集合相當於一個凸包或凸集，叫做可行域。因為目標函數亦是線性的，所以其極值點會自動成為最值點。線性目標函數亦暗示其最優解只會出現在其可行域的邊界點中。

在兩種情況下線性規劃問題沒有最優解。其中一種是在約束條件相互矛盾的情況下（例如 x ≥ 2 和 x ≤ 1），其可行域將會變成空集，問題沒有解，因此亦沒有最優解。在這種情況下，該線性規劃問題會被稱之為「不可行」。

另一種情況是，約束條件的多面體可以在目標函數的方向無界（例如： max z=x₁ + 3 x₂ s.t. x₁ ≥ 0, x₂ ≥ 0, x₁ + x₂ ≥ 10），目標函數可以取得任意大的數值，所以沒有最優解。

除了以上兩種病態的情況以外（問題通常都會受到資源的限制，如上面的例子），最優解永遠都能夠在多面體的頂點中取得。但最優解未必是唯一的：有可能出現一組最優解，覆蓋多面體的一條邊、一個面、甚至是整個多面體（最後一種情況會在目標函數只能等於0的情況下出現）。

[编辑] 算法

兩個變量的線性規劃問題中，一組線性約束條件劃定了對兩個變量的解的可行域。可解的問題會有一個簡單多邊形的可行域。

單純形演算法利用多面體的頂點構造一個可能的解，然後沿著多面體的邊走到目標函數值更高的另一個頂點，直至到達最優解為止。雖然這個演算法在實際上很有效率，在小心處理可能出現的「迴圈」的情況下，可以保證找到最優解，但它的最壞情況可以很壞：可以構築一個線性規劃問題，單純形演算法需要問題大小的指數倍的運行時間才能將之解出。当前，線性規劃問題是NP完全問題還是可以在多項式時間裏解出的問題，人們尚無定論。

第一個在最壞情況具有多項式時間複雜度的線性規劃算法在1979年由 Leonid Khachiyan 提出。這個算法建基於非線性規劃中 Naum Shor 發明的橢球法，該法又是 Arkadi Nemirovski（2003年馮‧諾伊曼運籌學理論獎得主）和 D. Yudin 的凸集最優化橢球法的一般化。

但在實際應用上，Khachiyan的演算法令人失望：一般來說，單純形演算法比它更有效率。它的重要性在於鼓勵了對內點演算法的研究。相對於只沿著可行域的邊沿進行移動的單純形演算法，內點演算法能夠在可行域內移動。

1984年，Narendra Karmarkar（卡馬卡）提出了投影尺度法。這是第一個在理論上和實際上都表現良好的算法：它的最壞情況僅為多項式時間，且在實際問題中它比單純形演算法有顯著的效率提升。自此之後，很多內點演算法被提出來並進行分析。一個常見的內點演算法為 Mehrotra predictor-corrector method。儘管在理論上對它所知甚少，在實際應用中它卻表現出色。

當今的觀點是：對於線性規劃的日常應用問題而言，若果演算法的實現良好，基於單純形法和內點法的演算法之間的效率沒有太大差別。

線性規劃的求解程式在各種各樣的工業最優化問題裡被廣泛使用，例如運輸網路的流量的最優化問題，其中很多都可以不太困難地被轉換成線性規劃問題。

[编辑] 有待解决的问题

[编辑] 整數規劃

要求所有的未知量都為整數的線性規劃問題叫做整數規劃 (integer programming, IP) 或整數線性規劃 (integer linear programming, ILP) 問題。相對於即使在最壞情況下也能有效率地解出的線性規劃問題，整數規劃問題的最壞情況是不確定的，在某些實際情況中（有約束變量的那些）為指數型困難問題。

0-1 整數規劃是整數規劃的特殊情況，所有的變量都要是0或1（而非任意整數）。這類問題亦被分類為指數型困難問題。

只要求當中某幾個未知數為整數的線性規劃問題叫做混合整數規劃 (mixed integer programming, MIP) 問題。這類問題通常亦被分類為指數型困難問題。

存在著幾類 IP 和 MIP 的子問題，它們可以被有效率地解出，最值得注意的一類是具有完全單位模約束矩陣，和約束條件的右邊全為整數的一類。

一個解決大型整數線性規劃問題的先進演算法為 delayed column generation。

[编辑] 参见

单纯型法, used to solve LP problems
Leonid Kantorovich was one of founders of linear programming
影子价格
MPS file format
LP example, Job Shop problem

[编辑] 参考

Alexander Schrijver: "Theory of Linear and Integer Programming". John Wiley and Sons. 1998.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Chapter 29: Linear Programming, pp.770–821.
Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman. ISBN 0716710455. A6: MP1: INTEGER PROGRAMMING, pg.245.

[编辑] 外部連結

求解軟件包

AIMMS — include linear programming in industry solutions (free trial license available);
COIN-OR — COmputational INfrastructure for Operations Research, open-source library
Cplex — Commercial library for linear programming
HOPDM — Higher Order Primal Dual Method
LINDO — LP, IP, Global solver/modeling language
lp_solve
MOSEK — Optimization software for LP, QP, MIP, SOCP and more
Premium Solver — Spreadsheet add-in
What's Best! — Spreadsheet add-in
Xpress-MP — Optimization software free to students
GIPALS — Linear programming environment and dynamic link library (DLL)
DecisionPro Linear Programming Optimization Software
QSopt Optimization software for LP (free for research purposes).
Microarray Data Classification Server (MDCS) based on linear programming
Linear programming and linear goal programming A freeware program for MS-DOS
Simplex Method Tool A quick-loading web page

来自“http://zh.wikipedia.org../../../%E7%BA%BF/%E6%80%A7/%E8%A7%84/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92.html”

页面分类: 翻譯請求 | 應用數學

线性规划

维基百科，自由的百科全书

目录

[编辑] 标准型

[编辑] 例子

[编辑] 增广矩阵（松弛型）

[编辑] 例子

[编辑] 对偶

[编辑] 理論

[编辑] 算法

[编辑] 有待解决的问题

[编辑] 整數規劃

[编辑] 参见

[编辑] 参考

[编辑] 外部連結

Views

导航

帮助

搜索

其他语言