數學模組化：matlab解決線性規劃問題

在人們的生産實踐中,經常會遇到如何利用現有資源來安排生産,以取得最大經濟效

益的問題。此類問題構成了運籌學的一個重要分支一數學規劃,而線性規劃(Linear

Programming, LP)則是數學規劃的一個重要分支。自從1947年G. B. Dantzig 提出求解線

性規劃的單純形方法以來,線性規劃在理論上趨向成熟,在實用中日益廣泛與深入。特别

是在計算機能處理成千上萬個限制條件和決策變量的線性規劃問題之後，線性規劃的适

用領域更為廣泛了,已成為現代管理中經常采用的基本方法之一。

例如，給定m個資料點(xi,yi),i=1,2,…,m，拟合一條直線y=ax+b(即确定參數a、b)，使得所有資料點(xi,yi)和拟合直線上對應的點(xi,axi+b)之間距離的最大值rmax最小。也就是說，對整個這組資料點而言，最大絕對偏差r=max{ | yi-y(xi) | }最小。這種準則實際上定義了如下優化問題：

M i n      r Min\;\;r Minr

s . t . s.t. s.t.

f ( n ) = { r − r i ≥ 0 , r + r i ≥ 0 , i = 1 , 2 , . . . , m f(n)= \begin{cases}r-r_i\geq0, \\ r+r_i\geq0, \end{cases} \\ i=1,2,...,m f(n)={r−ri​≥0,r+ri​≥0,​i=1,2,...,m

這是一個線性規劃問題，具有很廣泛的應用。

木匠問題

木匠銷售桌子和書架的機關淨利潤分别為25美元和30美元，他希望确定每周生産的桌子數量x和書架數量y。他每周最多有690 張木闆和120小時的勞動時間可以利用，如果木闆和工時不用于生産桌子和書架，他能夠将它們有效地使用在其他方面。他估計，生産一張桌子需要20張木闆和5小時勞動時間，生産一個書架需要30張木闆和4小時勞動時間。模型為

M a x    25 x + 30 y Max\;25x+30y Max25x+30y

s . t . s.t. s.t.

20 x + 30 y ≤ 690 ( 木 闆 ) 5 x + 4 y ≤ 120 ( 勞 動 時 間 ) x , y ≥ 0 ( 非 勞 動 性 ) 20x+30y\leq690\qquad(木闆)\\ 5x+4y\leq120\qquad(勞動時間)\\ x,y\geq0\qquad(非勞動性) 20x+30y≤690(木闆)5x+4y≤120(勞動時間)x,y≥0(非勞動性)

木匠問題中的限制所代表的凸集在圖中用多邊形ABCD表示。請注意，限制所代表的直線有6個交點，但隻有四個交點（即A—D）滿足所有限制進而屬于該凸集。點A—D是該多邊形的極點。

如果一個線性規劃存在最優解，它必然也會出現在限制所形成的凸集的某個極點上，極點上目标函數的值（木匠問題的利潤）是

極點	目标函數值（美元）
A(12,15)	750
B(0,23)	690
C(0,0)
D(24,0)	600

是以，木匠每周應該制作12張桌子和15個支架，每周最大利潤為750美元。

木匠問題(線性規劃)的matlab解法

線性規劃的目标函數可以是求最大值,也可以是求最小值,限制條件的不等号可以是

小于等号也可以是大于等号。為了避免這種形式多樣性帶來的不便, Matlab中規定線性

規劃的标準形式為

m i n    f T x min\;f^Tx minfTx

s . t . = { A ⋅ x ≤ 0 , A e q ⋅ x = b e q ≥ 0 , l b ≤ x ≤ u b s.t.= \begin{cases}A·x\leq0, \\ Aeq·x=beq\geq0, \\lb\leq x\leq ub \end{cases} s.t.=⎩⎪⎨⎪⎧​A⋅x≤0,Aeq⋅x=beq≥0,lb≤x≤ub​

式中:f,x ,b ,beq,lb, ub為列向量,其中f稱為價值向量,b稱為資源向量;A , Aeq為矩陣。

Matlab中求解線性規劃的指令為

[x,fval] = linprog(f,A,b)

[x,fval] = linprog( f,A,b,Aeq, beq)

[x,fval] = linprog( f ,A, b,Aeq , beq,1b,ub)

式中:x傳回決策向量的取值;fval傳回目标函數的最優值;f為價值向量;A和b對應線性

不等式限制;Aeq和beq對應線性等式限制;lb和ub分别對應決策向量的下界向量和上

界向量。

例如,線性規劃

m a x    c T x , s . t .      A x ≥ b max\;c^Tx, \\s.t.\;\;Ax\geq b maxcTx,s.t.Ax≥b

的matlab标準型為

m i n    − c T x , s . t .      − A x ≤ − b min\;-c^Tx, \\s.t.\;\;-Ax\leq -b min−cTx,s.t.−Ax≤−b

附上木桶問題的matlab代碼

f=[ -25; -30];
a=[ 20,30;5,4]; b=[690;120];
[x,y] =linprog( f ,a,b,[], [], zeros(2,1));
x,y=-y

           

x =
   12.0000
   15.0000
y =
   750
           

轉載請标明出處，謝謝！。

如果感覺本文對您有幫助，請留下您的贊，您的支援是我堅持寫作最大的動力，謝謝！