開啟主選單

求真百科

線性規劃

來自 原創力文檔 的圖片

中文名:線性規劃

外文名:linear programming

所屬學科:運籌學

研究內容:線性最優化問題

線性規劃(Linear programming,簡稱LP),是運籌學中研究較早、發展較快、應用廣泛、方法較成熟的一個重要分支,是輔助人們進行科學管理的一種數學方法,是研究線性約束條件線性目標函數極值問題的數學理論和方法。

線性規劃是運籌學的一個重要分支,廣泛應用於軍事作戰經濟分析經營管理工程技術等方面。為合理地利用有限的人力、物力、財力等資源作出的最優決策,提供科學的依據。

目錄

線性規劃簡介

數學模型

(1)列出約束條件及目標函數

(2)畫出約束條件所表示的可行域

(3)在可行域內求目標函數的最優解及最優值

標準型

描述線性規劃問題的常用和最直觀形式是標準型。標準型包括以下三個部分:

一個需要極大化的線性函數:

以下形式的問題約束:

和非負變量:

其它類型的問題,例如極小化問題,不同形式的約束問題,和有負變量的問題,都可以改寫成其等價問題的標準型。

模型建立

從實際問題中建立數學模型一般有以下三個步驟:

1.根據影響所要達到目的的因素找到決策變量;

2.由決策變量和所在達到目的之間的函數關係確定目標函數;

3.由決策變量所受的限制條件確定決策變量所要滿足的約束條件。

所建立的數學模型具有以下特點:

1、每個模型都有若干個決策變量(x1,x2,x3……,xn),其中n為決策變量個數。決策變量的一組值表示一種方案,同時決策變量一般是非負的。

2、目標函數是決策變量的線性函數,根據具體問題可以是最大化(max)或最小化(min),二者統稱為最優化(opt)。

3、約束條件也是決策變量的線性函數。

當我們得到的數學模型的目標函數為線性函數,約束條件為線性等式或不等式時稱此數學模型為線性規劃模型。

例:

生產安排模型:某工廠要安排生產Ⅰ、Ⅱ兩種產品,已知生產單位產品所需的設備台時及A、B兩種原材料的消耗,如表所示,表中右邊一列是每日設備能力及原材料供應的限量,該工廠生產一單位產品Ⅰ可獲利2元,生產一單位產品Ⅱ可獲利3元,問應如何安排生產,使其獲利最多?

解:

1、確定決策變量:設x1、x2分別為產品Ⅰ、Ⅱ的生產數量;

2、明確目標函數:獲利最大,即求2x1+3x2最大值;

3、所滿足的約束條件:

設備限制:x1+2x2≤8

原材料A限制:4x1≤16

原材料B限制:4x2≤12

基本要求:x1,x2≥0

用max代替最大值,s.t.(subject to 的簡寫)代替約束條件,則該模型可記為:

max z=2x1+3x2

s.t. x1+2x2≤8

4x1≤16

4x2≤12

x1,x2≥0

解法

求解線性規劃問題的基本方法是單純形法,已有單純形法的標準軟件,可在電子計算機上求解約束條件和決策變量數達 10000個以上的線性規劃問題。為了提高解題速度,又有改進單純形法、對偶單純形法原始對偶方法分解算法和各種多項式時間算法。對於只有兩個變量的簡單的線性規劃問題,也可採用圖解法求解。這種方法僅適用於只有兩個變量的線性規劃問題。它的特點是直觀而易於理解,但實用價值不大。通過圖解法求解可以理解線性規劃的一些基本概念。

發展

法國數學家J.- B.- J.傅里葉和C.瓦萊-普森分別於1832和1911年獨立地提出線性規劃的想法,但未引起注意。

1939年蘇聯數學家Л.В.康托羅維奇在《生產組織與計劃中的數學方法》一書中提出線性規劃問題,也未引起重視。[1]

1947年美國數學家G.B.Dantzing提出求解線性規劃的單純形法,為這門學科奠定了基礎。

1947年美國數學家J.von[[諾伊曼提出對偶理論,開創了線性規劃的許多新的研究領域,擴大了它的應用範圍和解題能力。

1951年美國經濟學家T.C.庫普曼斯把線性規劃應用到經濟領域,為此與康托羅維奇一起獲1975年諾貝爾經濟學獎

50年代後對線性規划進行大量的理論研究,並湧現出一大批新的算法。例如,1954年C.萊姆基提出對偶單純形法,1954年S.加斯和T.薩迪等人解決了線性規劃的靈敏度分析和參數規劃問題,1956年A.塔克提出互補鬆弛定理,1960年G.B.丹齊克和P.沃爾夫提出分解算法等。

線性規劃的研究成果還直接推動了其他數學規劃問題包括整數規劃、隨機規劃和非線性規劃的算法研究。由於數字電子計算機的發展,出現了許多線性規劃軟件,如MPSX,OPHEIE,UMPIRE等,可以很方便地求解幾千個變量的線性規劃問題。 1979年蘇聯數學家L. G. Khachian提出解線性規劃問題的橢球算法,並證明它是多項式時間算法。

1984年美國貝爾電話實驗室的印度數學家N.卡馬卡提出解線性規劃問題的新的多項式時間算法。用這種方法求解線性規劃問題在變量個數為5000時只要單純形法所用時間的1/50。現已形成線性規劃多項式算法理論。50年代後線性規劃的應用範圍不斷擴大。 建立線性規劃模型的方法

應用

在企業的各項管理活動中,例如計劃、生產、運輸、技術等問題,線性規劃是指從各種限制條件的組合中,選擇出最為合理的計算方法,建立線性規劃模型從而求得最佳結果。

視頻

線性規劃問題

參考資料