重慶工商大學(xué)數(shù)學(xué)模型與數(shù)學(xué)實驗課件第12講 約束優(yōu)化

1、大學(xué)數(shù)學(xué)實驗Experiments in Mathematics實驗8 約束優(yōu)化數(shù)學(xué)建模與數(shù)學(xué)實驗- 李煥榮 實 驗 8優(yōu)化問題三要素：決策變量；目標函數(shù)；約束條件約束條件決策變量優(yōu)化問題的一般形式當最優(yōu)解在可行域邊界上取得時不能用無約束優(yōu)化方法求解目標函數(shù) 實 驗 8 實 驗 89/8/20222約束優(yōu)化的分類 線性規(guī)劃(LP) 目標和約束均為線性函數(shù) 非線性規(guī)劃(NLP) 目標或約束中存在非線性函數(shù) 二次規(guī)劃(QP) 目標為二次函數(shù)、約束為線性 整數(shù)規(guī)劃(IP) 決策變量(部分)為整數(shù) 整數(shù)線性規(guī)劃(ILP) 整數(shù)非線性規(guī)劃(INLP) 0-1規(guī)劃整數(shù)決策變量只取或連續(xù)優(yōu)化離散優(yōu)化 實 驗

2、 8 實 驗 8本實驗基本內(nèi)容2. 基本原理和算法3. MATLAB實現(xiàn)1. 問題與模型NLPLPQP 實 驗 8 實 驗 89/8/202241桶牛奶 3千克A1 12小時 8小時 4千克A2或獲利12元/千克獲利8元/千克 0.8千克B12小時,1.5元1千克獲利22元/千克 0.75千克B22小時,1.5元1千克獲利16元/千克 制訂生產(chǎn)計劃，使每天凈利潤最大 15元可增加1桶牛奶，應(yīng)否投資？50桶牛奶, 480小時 至多100公斤A1 B1，B2的獲利經(jīng)常有10%的波動，對計劃有無影響？實例1: 奶制品生產(chǎn)銷售計劃 聘用臨時工人增加勞動時間，工資最多每小時幾元？ 實 驗 8 實 驗 8

3、1桶牛奶 3千克 A1 12小時 8小時 4千克 A2 或獲利12元/千克 獲利8元/千克 0.8千克 B12小時,1.5元1千克獲利22元/千克 0.75千克 B22小時,1.5元1千克獲利16元/千克 出售x1 千克 A1, x2 千克 A2， x3千克 B1, x4千克 B2原料供應(yīng) 勞動時間 加工能力 決策變量 目標函數(shù) 利潤約束條件非負約束 x5千克 A1加工B1， x6千克 A2加工B2附加約束 LP 實 驗 8 實 驗 8求解線性規(guī)劃(LP)的基本原理基本模型二維線性規(guī)劃的圖解法一般線性規(guī)劃的單純形算法一般線性規(guī)劃的內(nèi)點算法 實 驗 8 實 驗 8x,fval,exitflag,

4、output,lambda =linprog(c,A1,b1,A2,b2,v1,v2,x0,opt)MATLAB 求解 LP輸入：x0初始解(缺省時為0)opt MATLAB控制參數(shù)中間所缺參數(shù)項補輸出：lambda Lagrange乘子，維數(shù)等于約束個數(shù)，非零分量對應(yīng)于起作用約束 lambda.ineqlin: 對應(yīng) A1xb1 lambda. eqlin : 對應(yīng) A2x = b2 lambda. lower : 對應(yīng) v1 x lambda. upper : 對應(yīng) x v2Exam0802.m 實 驗 8 實 驗 8MATLAB 求解 LPopt MATLAB控制參數(shù):三種算法選擇 缺省

5、時采用大規(guī)模算法（是一種內(nèi)點算法）； 當opt中“LargeScale”參數(shù)設(shè)置為“off”時，采用中規(guī)模算法，該模式下缺省的算法是二次規(guī)劃的算法（一種有效集方法）； 當opt中“LargeScale”參數(shù)設(shè)置為“off”，并且“Simplex”參數(shù)設(shè)置為“on”時，采用單純形算法。只有有效集方法可以由用戶提供初始解x0，其他兩個算法則不需要（即使提供了也會被MATLAB忽略）。 Exam0801.mx,fval,exitflag,output,lambda =linprog(c,A1,b1,A2,b2,v1,v2,x0,opt) 實 驗 8 實 驗 8c=12 8 22 16 -1.5 -1

6、.5;A1=4 3 0 0 4 3;2 1 0 0 3 2;1 0 0 0 1 0;b1=600 240 100;A2=0 0 1 0 -0.8 0;0 0 0 1 0 -0.75;b2=0 0;v1=0 0 0 0 0 0; x,z0,ef,out,lag=linprog(-c,A1,b1,A2,b2,v1)lag.ineqlin, lag.eqlin 實例1: 奶制品生產(chǎn)銷售計劃x=(0,168,19.2,0,24,0) ; z = -z0 =1730.4; lag.ineqlin =(1.58;3.26; 0.00) ; 實 驗 8 實 驗 8 15元可增加1桶牛奶，應(yīng)否投資？實例1:

7、奶制品生產(chǎn)銷售計劃x=(0,168,19.2,0,24,0) ; z = -z0 =1730.4lag.ineqlin =(1.58;3.26; 0.00) ; 601z1=1731.98z1-z = 1731.98-1730.4=1.58z1=lag.ineqlin(1) z1*12=1.58*12= 18.9615應(yīng)該投資！ “影子價格” 實 驗 8 實 驗 8實例1: 奶制品生產(chǎn)銷售計劃 聘用臨時工人增加勞動時間，工資最多每小時幾元？x=(0,168,19.2,0,24,0) ; z = -z0 =1730.4 lag.ineqlin =(1.58;3.26; 0.00) ; lag.ineqlin(2)=3.26，所以1小時勞動時間的影子價格應(yīng)為3.26/2=1.63，即單位勞動時間增加的利潤是1.63(元) 實 驗 8 實 驗 8 B1，B2的獲利經(jīng)常有10%的波動，對計劃有無影響？實例1: 奶制品生產(chǎn)銷售計劃x=(0,168,19.2,0,24,0) ; z = -z0 =1730.4 lag.ineqlin =(1.58;3.26; 0.00) ;若每公斤B1的獲利下降10%,應(yīng)將目標函數(shù)中x3的系數(shù)改為19.8，重新計算發(fā)現(xiàn)最優(yōu)解和最優(yōu)值均發(fā)生了變化若B2的獲利向上波動10%，原計劃也不再是最優(yōu)的MATLAB沒有給出這種