-
線性規劃
(運籌學術語)
鎖定
- 中文名
- 線性規劃
- 外文名
- linear programming
- 所屬學科
- 運籌學
- 研究內容
- 線性最優化問題
- 應用學科
- 高中數學必修5
線性規劃線性規劃簡介
數學模型
(2)畫出約束條件所表示的可行域
(3)在可行域內求目標函數的最優解及最優值
線性規劃標準型
描述線性規劃問題的常用和最直觀形式是標準型。標準型包括以下三個部分:
以下形式的問題約束:
和非負變量:
其它類型的問題,例如極小化問題,不同形式的約束問題,和有負變量的問題,都可以改寫成其等價問題的標準型。
線性規劃模型建立
從實際問題中建立數學模型一般有以下三個步驟;
1.根據影響所要達到目的的因素找到決策變量;
3.由決策變量所受的限制條件確定決策變量所要滿足的約束條件。
所建立的數學模型具有以下特點:
1、每個模型都有若干個決策變量(x1,x2,x3……,xn),其中n為決策變量個數。決策變量的一組值表示一種方案,同時決策變量一般是非負的。
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個以上的線性規劃問題。為了提高解題速度,又有改進單純形法、對偶單純形法、原始對偶方法、分解算法和各種多項式時間算法。對於只有兩個變量的簡單的線性規劃問題,也可採用圖解法求解。這種方法僅適用於只有兩個變量的線性規劃問題。它的特點是直觀而易於理解,但實用價值不大。通過圖解法求解可以理解線性規劃的一些基本概念。
S.T.
AX =b
X>=0
其中A為一個m*n矩陣。
若A行滿秩
則可以找到基矩陣B,並尋找初始基解。
用N表示對應於B的非基矩陣。則規劃問題1可化為:
規劃問題2:
Min z=CB XB+CNXN
XB >= 0, XN >= 0 (2)
(1)兩邊同乘B-1,得
XB + B-1 N XN = B-1 b
同時,由上式得XB = B-1 b - B-1 N XN,也代入目標函數,問題可以繼續化為:
規劃問題3:
Min z=CB B-1 b + ( CN - CB B-1 N ) XN
S.T.
XB+B-1N XN = B-1 b (1)
XB >= 0, XN >= 0 (2)
令N:=B-1N,b:= B-1 b,ζ= CB B-1b,σ= CN - CB B-1 N,則上述問題化為規劃問題形式4:
Min z= ζ + σ XN
S.T.
XB+ N XN = b (1)
XB >= 0, XN >= 0 (2)
在上述變換中,若能找到規劃問題形式4,使得b>=0,稱該形式為初始基解形式。
上述的變換相當於對整個擴展矩陣(包含C及A) 乘以增廣矩陣 。所以重在選擇B,從而找出對應的CB。
若存在初始基解
若σ>= 0
若σ >= 0不成立
可以採用單純形表變換。
若Pj <=0不成立
則Pj至少存在一個分量ai,j為正。在規劃問題4的約束條件(1)的兩邊乘以矩陣T。
T=
l ai,j>0。
l βq+βi*(-aq,j/ai,j)>=0,其中q!=i。即βq>=βi/ ai,j * aq,j。
n 若aq,j<=0,上式一定成立。
n 若aq,j>0,則需要βq / aq,j >=βi/ ai,j。因此,要選擇i使得βi/ ai,j最小。
如果這種方法確定了多個下標,選擇下標最小的一個。
轉換後得到規劃問題4的形式,繼續對σ進行判斷。由於基解是有限個,因此,一定可以在有限步跳出該循環。
若對於每一個i,ai,j<=0
最優值無解。
若不能尋找到初始基解
無解。
若A不是行滿秩
化簡直到A行滿秩,轉到若A行滿秩。
線性規劃發展
1947年美國數學家G.B.Dantzing提出求解線性規劃的單純形法,為這門學科奠定了基礎。
1951年美國經濟學家T.C.庫普曼斯把線性規劃應用到經濟領域,為此與康託羅維奇一起獲1975年諾貝爾經濟學獎。
50年代後對線性規劃進行大量的理論研究,並湧現出一大批新的算法。例如,1954年C.萊姆基提出對偶單純形法,1954年S.加斯和T.薩迪等人解決了線性規劃的靈敏度分析和參數規劃問題,1956年A.塔克提出互補鬆弛定理,1960年G.B.丹齊克和P.沃爾夫提出分解算法等。
線性規劃的研究成果還直接推動了其他數學規劃問題包括整數規劃、隨機規劃和非線性規劃的算法研究。由於數字電子計算機的發展,出現了許多線性規劃軟件,如MPSX,OPHEIE,UMPIRE等,可以很方便地求解幾千個變量的線性規劃問題。
1984年美國貝爾電話實驗室的印度數學家N.卡馬卡提出解線性規劃問題的新的多項式時間算法。用這種方法求解線性規劃問題在變量個數為5000時只要單純形法所用時間的1/50。現已形成線性規劃多項式算法理論。50年代後線性規劃的應用範圍不斷擴大。 建立線性規劃模型的方法
線性規劃應用
在企業的各項管理活動中,例如計劃、生產、運輸、技術等問題,線性規劃是指從各種限制條件的組合中,選擇出最為合理的計算方法,建立線性規劃模型從而求得最佳結果。