線性規(guī)劃概述

1、線性規(guī)劃1.簡介在數(shù)學中，線性規(guī)劃(Linear Programming,簡稱LP)問題是目標函數(shù)和約 束條件都是線性的最優(yōu)化問題。線性規(guī)劃是最優(yōu)化問題中的重要領(lǐng)域之一。很多運籌學中的實際問題都可以 用線性規(guī)劃來表述。線性規(guī)劃的某些特殊情況，例如網(wǎng)絡(luò)流、多商品流量等問題， 都被認為非常重要，并有大量對其算法的專門研究。很多其他種類的最優(yōu)化問題 算法都可以分拆成線性規(guī)劃子問題，然后求得解。在歷史上，由線性規(guī)劃引申出 的很多概念，啟發(fā)了最優(yōu)化理論的核心概念，諸如“對偶”、“分解”、“凸性” 的重要性及其一般化等。同樣的，在微觀經(jīng)濟學和商業(yè)管理領(lǐng)域，線性規(guī)劃被大 量應(yīng)用于解決收入極大化或生產(chǎn)過程的成

2、本極小化之類的問題。喬治丹齊格被 認為是線性規(guī)劃之父。10 30 50 70 W JIO L30 IS。2.標準型描述線性規(guī)劃問題的常用和最直觀形式是標準型。標準型包括以下三個部分: 一個需要極大化的線性函數(shù)，例如!國1 + C皿以下形式的問題約束，例如：血m +曲匝和非負變量，例如:1 00線性規(guī)劃問題通?？梢杂镁仃囆问奖磉_成:maximize C Xsubject to Ax 上 I). * * 其他類型的問題，例如極小化問題，不同形式的約束問題，和有負變量的問題，都可以改寫成其等價問題的標準型。3.例子以下是一個線性規(guī)劃的例子。假設(shè)一個農(nóng)夫有一塊A平方千米的農(nóng)地，打算種植小麥或大麥或是兩

3、者依某一比例混合種植。該農(nóng)夫只可以使用有限數(shù)量的肥料F和農(nóng)藥P，而單位面積的小麥和大麥都需要不同數(shù)量的肥料和農(nóng)藥，小麥以（七P表示，貝U小麥與大麥的種植面積問題可以表示為以下的線性規(guī)劃問題:大麥以 電，P2）表示。設(shè)小麥和大麥的售出價格分別為S1和max（最大化利潤-目標函數(shù)）（Ti+T2 APiii + 0這里xs是新引入的松弛變量，Z需要極大化的變量.5.例子以上例子的轉(zhuǎn)換成增廣矩陣:maximize subject to .廠| - .七 -: 一 iF1S += FPlTi +產(chǎn)魂+購=P這里.i七 是（非負）松弛變量.寫成矩陣形式：z-1 -S1 & 0 0 0-Hl01110 0A

4、0 F10 1 0旬F0 Pl 耳 0 0 1X-4P_5_Maximize Z in:6.對偶每個線性規(guī)劃問題，稱為原問題，都可以變換為一個對偶問題。我們可將“原 問題”表達成矩陣形式：maximize C Xsubject to Ax 上 I）. * * 而相應(yīng)的對偶問題就可以表達成以下矩陣形式：minimize V subject to這里用“y”來作為未知向量。7.理論幾何上，線性約束條件的集合相當于一個凸包或凸集，叫做可行域。因為目 標函數(shù)亦是線性的，所以其極值點會自動成為最值點。線性目標函數(shù)亦暗示其最 優(yōu)解只會出現(xiàn)在其可行域的邊界點中。在兩種情況下線性規(guī)劃問題沒有最優(yōu)解。其中一種是

5、在約束條件相互矛盾的 情況下（例如x2和x W 1），其可行域?qū)兂煽占?，問題沒有解，因 此亦沒有最優(yōu)解。在這種情況下，該線性規(guī)劃問題會被稱之為“不可行”。另一種情況是，約束條件的多面體可以在目標函數(shù)的方向無界（例如：max z=x + 3 x s.t. x0, x0, x + x10），目標函數(shù)可以取得任意121212大的數(shù)值，所以沒有最優(yōu)解。除了以上兩種病態(tài)的情況以外（問題通常都會受到資源的限制，如上面的例 子），最優(yōu)解永遠都能夠在多面體的頂點中取得。但最優(yōu)解未必是唯一的：有可 能出現(xiàn)一組最優(yōu)解，覆蓋多面體的一條邊、一個面、甚至是整個多面體（最后一 種情況會在目標函數(shù)只能等于0的情況下出

6、現(xiàn)）。兩個變量的線性規(guī)劃問題中，一組線性約束條件劃定了對兩個變量的解的可 行域。可解的問題會有一個簡單多邊形的可行域。單純形算法利用多面體的頂點構(gòu)造一個可能的解，然后沿著多面體的邊走到 目標函數(shù)值更高的另一個頂點，直至到達最優(yōu)解為止。雖然這個算法在實際上很 有效率，在小心處理可能出現(xiàn)的“循環(huán)”的情況下，可以保證找到最優(yōu)解，但它 的最壞情況可以很壞：可以構(gòu)筑一個線性規(guī)劃問題，單純形算法需要問題大小的 指數(shù)倍的運行時間才能將之解出。事實上，有一段時期內(nèi)人們曾不能確定線性規(guī) 劃問題是NP完全問題還是可以在多項式時間里解出的問題。第一個在最壞情況具有多項式時間復雜度的線性規(guī)劃算法在1979年由前蘇 聯(lián)

7、數(shù)學家Leonid Khachiyan提出。這個算法建基于非線性規(guī)劃中Naum Shor發(fā) 明的橢球法(ellip-soid method)，該法又是 Arkadi Nemirovski (2003 年馮 諾伊曼運籌學理論獎 得主)和D. Yudin的凸集最優(yōu)化橢球法的一般化。理論上，“橢球法”在最惡劣的情況下所需要的計算量要比“單形法”增長 的緩慢，有希望用之解決超大型線性規(guī)劃問題。但在實際應(yīng)用上，Khachiyan的 算法令人失望：一般來說，單純形算法比它更有效率。它的重要性在于鼓勵了對 內(nèi)點算法的研究。內(nèi)點算法是針對單形法的“邊界趨近”觀念而改采“內(nèi)部逼近” 的路線，相對于只沿著可行域的

8、邊沿進行移動的單純形算法，內(nèi)點算法能夠在可 行域內(nèi)移動。1984年，貝爾實驗室印度裔數(shù)學家卡馬卡(Narendra Karmarkar)提出了投 影尺度法(又名Karmarkars algorithm)o這是第一個在理論上和實際上都表 現(xiàn)良好的算法：它的最壞情況僅為多項式時間，且在實際問題中它比單純形算法 有顯著的效率提升。自此之后，很多內(nèi)點算法被提出來并進行分析。一個常見的內(nèi)點算法為Mehrotra predictor-corrector method。盡管在理論上對它所知甚 少，在實際應(yīng)用中它卻表現(xiàn)出色。單形法沿著邊界由一個頂點移動到“相鄰”的頂點，內(nèi)點算法每一步的移動 考量較周詳，“跨過

9、可行解集合的內(nèi)部”去逼近最佳解。當今的觀點是：對于線 性規(guī)劃的日常應(yīng)用問題而言，如果算法的實現(xiàn)良好，基于單純形法和內(nèi)點法的算 法之間的效率沒有太大差別，只有在超大型線性規(guī)劃中，頂點幾成天文數(shù)字，內(nèi) 點法有機會領(lǐng)先單形法。線性規(guī)劃的求解程式在各種各樣的工業(yè)最優(yōu)化問題里被廣泛使用，例如運輸 網(wǎng)絡(luò)的流量的最優(yōu)化問題，其中很多都可以不太困難地被轉(zhuǎn)換成線性規(guī)劃問題。有待解決的問題LP 一種強多項式時間(polynomial-time)算法嗎？Does LP admit a strongly polynomial algorithm to find a strictly complementary sol

10、ution?Does LP admit a polynomial algorithm in the real number (unit cost) model of computation?解第一提。polynomial-time，多項式成長，指的是數(shù)學問題會呈現(xiàn)多項式 成長，隨變量越多，限制越多，成長越快。當然越大的問題越難求解。另外還 有指數(shù)成長(exponential-time)，簡單說明，數(shù)學問題的成長速度，會是多項式 成長的倍數(shù)。此類問題，更難求解。整數(shù)規(guī)劃要求所有的未知量都為整數(shù)的線性規(guī)劃問題叫做整數(shù)規(guī)劃(integer programming, IP)或整數(shù)線性規(guī)劃(integer linear programming, ILP)問題。 相對于即使在最壞情況下也能有效率地解出的線性規(guī)劃問題，整數(shù)規(guī)劃問題的最 壞情況是不確定的，在某些實際情況中(有約束變量的那些)為NP困難問題。0-1整數(shù)規(guī)劃是整數(shù)規(guī)劃的特殊情況，所有的變量都要是0或1(而非任意整數(shù))。這類問題亦被分類為NP困難問題。只要求當中某幾個未知數(shù)為整數(shù)的線性規(guī)劃問題叫做混合整數(shù)