數學模組化--線性規劃

今天結束了為時兩周的數學模組化暑假教育訓練，打算重新整理一下課堂上的知識，并通過部落格做筆記，這是第一節課講的内容–線性規劃。

線性規劃（Linear programming,簡稱LP）屬于運籌學的重要分支，其目的在于合理利用有限資源進行最優決策。

建立線性規劃數學模型的基本步驟是

1.确定目标變量和決策變量，一般決策變量要求是非負的；

2.根據決策變量與變量的函數關系确定目标函數；

3.根據限制條件确定限制條件。

線性規劃的标準型

min f(x) = c’x

st.

Ax<=b

Aeq.x=beq

lb<=x<=ub

c為行向量。

一般來說，一個問題是否能化成線性規劃問題來求解，需符合如下4個假定：

1.比例性假定：決策變量的變化所引起的目标函數的改變量和決策變量的改變量成比例，同樣，每個決策變量的變化所引起的限制方程左端值的改變量和該變量的改變量成比例 ；

2.可加性假定：每個決策變量對目标函數和限制方程的影響是獨立于其他變量的，目标函數是每個決策變量對目标函數貢獻的總和；

3.連續性假定：線性規劃問題中的決策變量應取連續值；

4.确定性假定:線性規劃問題中的所有參數都是确定的參數，線性規劃問題不包含随機因素。

線性規劃問題的解有可能出現如下幾種情況：

1.有可行解

1)有唯一最優解 ；

2)有無窮多最優解；

3)無最優解。

2.無最優解。

線性規劃問的求解算法都是基于單純形法，單純形法的基本思路是：先找出可行域的一個極點，根據一定規則判斷是否最優，否則轉到與之相鄰的另一個極點，并使目标函數值最優；如此下去，直到找到某一最優解。

MATLAB中解決線性規劃的基本函數是linprog，基本調用格式如下：

x=linprog(c,A,b)

[x,y,exitflag]=linprog(c,A,b,Aeq,beq,lb,ub,x0,opt)

x為最優解列向量

y為目标函數最小值

exitflag為描述調用尋優函數時退出的狀态

（

1 表示函數收斂到解x

0 表示達到了函數最大評價次數或疊代次數

-2 表示沒有找到可行解

-3 表示所求解的線性規劃問題是無界的

-4 表示在執行算法的時候遇到了NaN

-5 表示原問題和對偶問題都是不可行的

-6 表示搜尋方向使得目标函數值下降得很少

）

例子

min z=2x1+3x2+x3

st.

x1+4x2+2x3>=8

3x1+2x2>=6

x1,x2,x3>=0

c=[2 3 1]'
A=[1 4 2;3 2 0]
b=[8;6]
[x y]=linprog(c,-a,-b,[],[],zeros(3,1))

x=
    0.8066
    1.7900
    0.0166
y=
    7.000