线性规划

维基百科,自由的百科全书
跳转至: 导航搜索
线性规划

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

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

标准型[编辑]

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

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

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

这里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”来作为未知向量。

例子[编辑]

上述线性规划例子的对偶问题:

假如有一个种植园主缺少肥料和农药,他希望同这个农夫谈判付给农夫肥料和农药的价格。可以构造一个数学模型来研究如何既使得农夫觉得有利可图肯把肥料和农药的资源卖给他,又使得自己支付的金额最少?

问题可以表述如下

假设y1, y2分别表示每单位肥料和农药的价格,则所支付租金最小的目标函数可以表示为

min  E=F y_1 + P y_2
s.t.
 F_1 y_1 + P_1 y_2 \ge S_1 (控制购买价格使得农夫觉得有利可图)
 F_2 y_1 + P_2 y_2 \ge S_2 (同上)
 y_1 \ge 0,\, y_2 \ge 0 (不可以购买负数单位资源)

理論[编辑]

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

在兩種情況下線性規劃問題沒有最優解。其中一種是在約束條件相互矛盾的情況下(例如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發明的橢球法(ellip-soid method),該法又是Arkadi Nemirovski(2003年馮‧諾伊曼運籌學理論獎得主)和 D. Yudin凸集最優化橢球法的一般化。

理論上,「橢球法」在最惡劣的情況下所需要的計算量要比「單形法」增長的緩慢,有希望用之解決超大型線性規劃問題。但在實際應用上,Khachiyan的演算法令人失望:一般來說,單純形演算法比它更有效率。它的重要性在於鼓勵了對內點演算法的研究。內點演算法是針對單形法的「邊界趨近」觀念而改採「內部逼近」的路線,相對於只沿著可行域的邊沿進行移動的單純形演算法,內點演算法能夠在可行域內移動。

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

單形法沿著邊界由一個頂點移動到「相鄰」的頂點,內點演算法每一步的移動考量較周詳,「跨過可行解集合的內部」去逼近最佳解。當今的觀點是:對於線性規劃的日常應用問題而言,如果演算法的實現良好,基於單純形法和內點法的演算法之間的效率沒有太大差別,只有在超大型線性規劃中,頂點幾成天文數字,內點法有機會領先單形法。

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

线性规划理论中存在几个尚未解决的问题,这些开放问题的答案将会是数学运算中的根本突破,并且很可能是我们解决大规模线性规划问题的主要进展。

  • LP存在强多项式时间算法吗?
  • LP存在多项式时间算法以得到一个严格互补解吗?
  • LP在实数(单位成本)模型下存在多项式时间算法吗?

这些问题已经由Stephen Smale二十一世纪十八个尚未解决的最伟大的问题中应用。用Smale的话来说,“第三个问题是线性规划理论中最主要的尚未解决的问题”。然而,对于线性规划问题存在弱多项式时间算法,比如椭球算法内点算法,尚未发现限制在约束条件个数和变量个数的强多项式时间算法,此算法的发展将会带来理论上重大意义,或者是解决大规模线性规划上的实际收益。

   尽管赫尔希博士猜想进来被证明是错误的,但是它依旧留下下面的开放问题:
  • Are there pivot rules which lead to polynomial-time Simplex variants?
  • Do all polytopal graphs have polynomially-bounded diameter?

整數規劃[编辑]

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

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

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

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

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

参见[编辑]

参考[编辑]

外部連結[编辑]

求解軟件包