首页 | 主题 | 图库 | 问答 | 文摘 | 原创 | 百科

历史 | 地理 | 人物 | 艺术 | 体育 | 科学 | 音乐 | 电影 | 信息技术 | 世界遗产

 开放、中立，源自维基百科

个人工具


线性规划

维库，知识与思想的自由文库

(重定向自整数规划)
跳转到: 导航, 搜索

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

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

翻譯標記 本條目仍然有文字尚未被翻譯成中文，條目是根據en:Linear Programming進行翻譯。
歡迎您積極參與翻譯與修訂，目前翻譯的進度為99%。

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


目录

[编辑] 标准型

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

  • 一个需要极大化的线性函数, 例如
c1x1 + c2x2
  • 以下形式的问题约束，例如:
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，而單位面積的小麥和大麥都需要不同數量的肥料和農藥，小麥以(F1, P1) 表示，大麥以 (F2, P2) 表示。設小麥和大麥的售出價格分別為 S1 和 S2，則小麥與大麥的種植面積問題可以表示為以下的線性規劃問題：

max P = S1x1 + S2x2 （最大化利潤 - 目標函數）
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

这里 xs 是新引入的松弛变量, 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=x1 + 3 x2 s.t. x1 ≥ 0, x2 ≥ 0, x1 + x2 ≥ 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) 問題。 相對於即使在最壞情況下也能有效率地解出的線性規劃問題，整數規劃問題的最壞情況是不確定的，在某些實際情況中（有約束變量的那些）為NP困難問題。

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

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

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

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

[编辑] 参见

[编辑] 参考

A6: MP1: INTEGER PROGRAMMING, pg.245.


[编辑] 外部連結

求解軟件包

来自“http://www.wikilib.net/wiki/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92”
导航
其它语言
AD Links