數(shù)學(xué)建模MATLAB之線性規(guī)劃學(xué)習(xí)教案

1、會計學(xué)1數(shù)學(xué)數(shù)學(xué)(shxu)建模建模MATLAB之線性規(guī)劃之線性規(guī)劃第一頁，共45頁。實驗實驗(shyn)目的目的實驗實驗(shyn)內(nèi)容內(nèi)容2. 掌握用數(shù)學(xué)掌握用數(shù)學(xué)(shxu)軟件包求解線性規(guī)劃問題軟件包求解線性規(guī)劃問題.1. 了解線性規(guī)劃的基本內(nèi)容了解線性規(guī)劃的基本內(nèi)容.2. 用數(shù)學(xué)軟件包用數(shù)學(xué)軟件包MATLAB求解線性規(guī)劃問題求解線性規(guī)劃問題.5. 實驗作業(yè)實驗作業(yè). .3. 用數(shù)學(xué)軟件包用數(shù)學(xué)軟件包LINDO、LINGO求解線性規(guī)劃問題求解線性規(guī)劃問題.1. 兩個引例兩個引例.4. 建模案例：投資的收益與風(fēng)險建模案例：投資的收益與風(fēng)險.第1頁/共45頁第二頁，共45頁。問題問題(wn

2、t)一一 ： 任務(wù)分配問題任務(wù)分配問題(wnt)：某車間有甲、乙：某車間有甲、乙兩臺機床，可用于加工三種工件兩臺機床，可用于加工三種工件.假定這兩臺車床的可用臺時假定這兩臺車床的可用臺時數(shù)分別為數(shù)分別為800和和900，三種工件的數(shù)量分別為，三種工件的數(shù)量分別為400、600和和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如下表數(shù)和加工費用如下表.問怎樣分配車床的加工任務(wù)，才能既滿問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費用最低？足加工工件的要求，又使加工費用最低？ 單位工件所需加工臺時數(shù) 單位工

3、件的加工費用 車床類 型 工件1 工件2 工件3 工件1 工件2 工件3 可用臺時數(shù) 甲 0.4 1.1 1.0 13 9 10 800 乙 0.5 1.2 1.3 11 12 8 900 兩個兩個(lin )引例引例第2頁/共45頁第三頁，共45頁。解解 設(shè)在甲車床上加工工件設(shè)在甲車床上加工工件1、2、3的數(shù)量的數(shù)量(shling)分別為分別為x1、x2、x3，在乙車床，在乙車床上加工工件上加工工件1、2、3的數(shù)量的數(shù)量(shling)分別分別為為x4、x5、x6,可建立以下線性規(guī)劃模型：可建立以下線性規(guī)劃模型： 解答(jid)第3頁/共45頁第四頁，共45頁。問題二：問題二： 某廠每日某廠

4、每日8小時小時(xiosh)的產(chǎn)量不低于的產(chǎn)量不低于1800件件.為了進行質(zhì)量控制，計劃聘請兩種不同水平的檢驗員為了進行質(zhì)量控制，計劃聘請兩種不同水平的檢驗員.一級檢驗員的標(biāo)準(zhǔn)為：速度一級檢驗員的標(biāo)準(zhǔn)為：速度25件件/小時小時(xiosh)，正確，正確率率98%，計時工資，計時工資4元元/小時小時(xiosh)；二級檢驗員的標(biāo)；二級檢驗員的標(biāo)準(zhǔn)為：速度準(zhǔn)為：速度15件件/小時小時(xiosh)，正確率，正確率95%，計時工，計時工資資3元元/小時小時(xiosh).檢驗員每錯檢一次，工廠要損失檢驗員每錯檢一次，工廠要損失2元元.為使總檢驗費用最省，該工廠應(yīng)聘一級、二級檢驗員為使總檢驗費用最省，

5、該工廠應(yīng)聘一級、二級檢驗員各幾名？各幾名？解解 設(shè)需要一級和二級檢驗員的人數(shù)分別為設(shè)需要一級和二級檢驗員的人數(shù)分別為x1、x2人人,則應(yīng)付則應(yīng)付(yng f)檢驗員的工資為：檢驗員的工資為：212124323848xxxx因檢驗員錯檢而造成(zo chn)的損失為：21211282)%5158%2258(xxxx第4頁/共45頁第五頁，共45頁。故目標(biāo)故目標(biāo)(mbio)函數(shù)為：函數(shù)為：2121213640)128()2432(minxxxxxxz約束條件為：0, 0180015818002581800158258212121xxxxxx第5頁/共45頁第六頁，共45頁。線性規(guī)劃線性規(guī)劃(xin

6、 xn u hu)模型：模型：213640minxxz12121253459s.t. 150,0 xxxxxx 解答(jid)返 回第6頁/共45頁第七頁，共45頁。11min,1,2,., .s.t.0,1,2,., .ni iinik kikiucxa xb inxin 目標(biāo)函數(shù)和所有目標(biāo)函數(shù)和所有(suyu)的約束條件都是設(shè)的約束條件都是設(shè)計變量計變量的線性函數(shù)的線性函數(shù).min. s.tucxAxbvlbxvub矩矩陣陣形形式式：第7頁/共45頁第八頁，共45頁。實際問題實際問題(wnt)中中的優(yōu)化模型的優(yōu)化模型T1min(max)( ),(,)s.t.( )0,1,2,nizf xx

7、xxg xim或x是決策是決策(juc)變量變量f(x)是目標(biāo)是目標(biāo)(mbio)函數(shù)函數(shù)gi(x) 0是約束條件是約束條件數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃線性規(guī)劃線性規(guī)劃(LP)二次規(guī)劃二次規(guī)劃(QP)非線性規(guī)劃非線性規(guī)劃(NLP)純整數(shù)規(guī)劃純整數(shù)規(guī)劃(PIP)混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃(MIP)整數(shù)規(guī)劃整數(shù)規(guī)劃(IP)0-1整數(shù)規(guī)劃整數(shù)規(guī)劃一般整數(shù)規(guī)劃一般整數(shù)規(guī)劃連續(xù)規(guī)劃連續(xù)規(guī)劃第8頁/共45頁第九頁，共45頁。用用MATLAB優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃(xin xn u hu)min z=cX s.t.AXb1. 模型：命令(mng lng)：x=linprog（c, A, b） 2. 模型：

8、min z=cX s.t.AXbbeqXAeq命令(mng lng)：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式： 存在，則令A(yù)= ，b= .bAX 第9頁/共45頁第十頁，共45頁。3. 模型：min z=cX s.t.AXbbeqXAeqVLBXVUB命令(mng lng)：1 x=linprog（c，A，b，Aeq,beq, VLB，VUB） 2 x=linprog（c，A，b，Aeq,beq, VLB，VUB, X0） 注意：1 若沒有等式約束: , 則令A(yù)eq= , beq= . 2其中X0表示初始點 beqXAeq4. 命令(mng lng)：x,fval=

9、linprog()返回最優(yōu)解及處的目標(biāo)函數(shù)值fval.第10頁/共45頁第十一頁，共45頁。解解 編寫編寫M文件文件(wnjin)如下：如下：c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08; b=850;700;100;900; Aeq=; beq=; vlb=0;0;0;0;0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub) To MATLAB (xxg

10、h1)第11頁/共45頁第十二頁，共45頁。解解: 編寫編寫M文件文件(wnjin)如下：如下： c=6 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30,0,20; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh2)123m in( 634 )xzxx32120030 xxx1231111 2 0s .t. 0105 0 xxx第12頁/共45頁第十三頁，共45頁。s.t.Xz8121110913min 9008003 . 12 . 15 . 000000011 . 14 . 0

11、X改寫為：例例3 問題問題(wnt)一的解答一的解答 問題(wnt)第13頁/共45頁第十四頁，共45頁。編寫編寫(binxi)M文件如下文件如下:f = 13 9 10 11 12 8;A = 0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3;b = 800; 900;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=400 600 500;vlb = zeros(6,1);vub=;x,fval = linprog(f,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh3)第14頁/共45頁第十五頁，共45頁。結(jié)果

12、結(jié)果(ji gu):x =fval =1.3800e+004 即在甲機床上加工即在甲機床上加工600個工件個工件2,在乙機床上加工在乙機床上加工400個工件個工件1、500個工件個工件3，可在滿足條件的情況下使總加工費最小為，可在滿足條件的情況下使總加工費最小為13800.第15頁/共45頁第十六頁，共45頁。例例2 問題問題(wnt)二的解答二的解答 問題(wnt) 213640minxxz s.t. )45(3521xx改寫為：第16頁/共45頁第十七頁，共45頁。編寫編寫(binxi)M文件如下：文件如下：c = 40;36;A=-5 -3;b=-45;Aeq=;beq=;vlb = z

13、eros(2,1);vub=9;15; %調(diào)用調(diào)用linprog函數(shù)：函數(shù)：x,fval = linprog(c,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh4)第17頁/共45頁第十八頁，共45頁。結(jié)果結(jié)果(ji gu)為：為：x =fval =360即只需聘用即只需聘用9個一級檢驗員個一級檢驗員. 注：本問題應(yīng)還有一個約束條件：注：本問題應(yīng)還有一個約束條件：x1、x2取整數(shù)取整數(shù).故它是一個整數(shù)線性規(guī)劃問題故它是一個整數(shù)線性規(guī)劃問題.這里這里把它當(dāng)成一個線性規(guī)劃來解，求得其最優(yōu)解把它當(dāng)成一個線性規(guī)劃來解，求得其最優(yōu)解剛好是整數(shù)：剛好是整數(shù)：x1=9，x2=0，故它

14、就是該整，故它就是該整數(shù)規(guī)劃的最優(yōu)解數(shù)規(guī)劃的最優(yōu)解.若用線性規(guī)劃解法求得的最若用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專門數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專門的方法的方法(fngf)求解求解.返 回第18頁/共45頁第十九頁，共45頁。用用LINDO、LINGO優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃(xin xn u hu)第19頁/共45頁第二十頁，共45頁。 下面我們通過一個例題來說明下面我們通過一個例題來說明(shumng)LINDO軟件包的使用方法軟件包的使用方法.第20頁/共45頁第二十一

15、頁，共45頁。 LINGO LINDO優(yōu) 化 模 型優(yōu) 化 模 型(mxng)線性規(guī)劃線性規(guī)劃( x i n xn u hu)(LP)非線性規(guī)劃非線性規(guī)劃(NLP)二 次 規(guī)二 次 規(guī)劃劃(QP)連續(xù)優(yōu)化連續(xù)優(yōu)化整數(shù)規(guī)劃整數(shù)規(guī)劃(IP)第21頁/共45頁第二十二頁，共45頁。1桶牛奶 3千克A1 12小時 8小時 4千克A2 或獲利24元/千克 獲利16元/千克 50桶牛奶桶牛奶(ni ni) 時間時間(shjin): 480小時小時 至多至多(zhdu)加工加工100千克千克A1 制訂生產(chǎn)計劃，使每天獲利最大制訂生產(chǎn)計劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多

16、少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到的獲利增加到 30元元/千克，是否應(yīng)改變生產(chǎn)計劃？千克，是否應(yīng)改變生產(chǎn)計劃？ 每天：每天：第22頁/共45頁第二十三頁，共45頁。x1桶牛奶桶牛奶(ni ni)生產(chǎn)生產(chǎn)A1 x2桶牛奶桶牛奶(ni ni)生產(chǎn)生產(chǎn)A2 獲利獲利(hu l) 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動時間勞動時間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 12max7264zxx每天獲利每天獲利約

17、束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)第23頁/共45頁第二十四頁，共45頁。max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)(shngchn)A1, 30桶生產(chǎn)桶生產(chǎn)(shngchn)A2，利潤，利潤3360元

18、元. 第24頁/共45頁第二十五頁，共45頁。 OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES 原料原料(yunlio)無剩余無剩余時間時間(shjin)無無剩余剩余加工能力剩余加工能力剩余(shngy)40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 第25頁/共45頁第二十六頁，共45頁。模型模型(mxng(mxng)

19、)求解求解 reduced cost值表值表示當(dāng)該非基變量增示當(dāng)該非基變量增加一個單位時（其加一個單位時（其他非基變量保持不他非基變量保持不變 ）變 ） , 目 標(biāo) 函 數(shù)目 標(biāo) 函 數(shù)(hnsh)減少的量減少的量(對對max型問題型問題) . OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST X1 20.000000 X2 30.000000 ROW SLACK OR SURPLUS DUAL PRICES NO. ITERATIONS= 2也可理解為：也可理解為：為了使該非基變量為了使該非基變量變成基變量，目標(biāo)變成基變量，目標(biāo)(mbi

20、o)函數(shù)中對函數(shù)中對應(yīng)系數(shù)應(yīng)增加的量應(yīng)系數(shù)應(yīng)增加的量第26頁/共45頁第二十七頁，共45頁。 OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3) 0.000000 4) 40.000000 結(jié)果結(jié)果(ji (ji gu)gu)解釋解釋 最優(yōu)解下最優(yōu)解下“資源資源”增加增加(zngji)1單位時單位時“效益效益”的增量的增量 原料增原料增1單位單位(dnwi), 利潤增利潤增48 時間增時間增1單位單位, 利潤增利潤增2 能力增減不影響利潤能力增減

21、不影響利潤影子價格影子價格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？35 ”（或（或“=”（或（或“=”）功能相同）功能相同變量與系數(shù)間可有空格變量與系數(shù)間可有空格(甚至回車甚至回車), 但無運算符但無運算符變量名以字母開頭，不能超過變量名以字母開頭，不能超過8個字符個字符變量名不區(qū)分大小寫（包括變量名不區(qū)分大小寫（包括LINDO中的關(guān)鍵字）中的關(guān)鍵字）目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件行號行號(行名行名)自動產(chǎn)生或人為定義自動產(chǎn)生或人為定義.行名以行名以“）”結(jié)束結(jié)束行中注有行中注有“!”符號的后面部分為注釋符號的后面部分為注釋

22、.如如: ! Its Comment.在模型的任何在模型的任何(rnh)地方都可以用地方都可以用“TITLE” 對模型命對模型命名（最多名（最多72個字符），如：個字符），如： TITLE This Model is only an Example第30頁/共45頁第三十一頁，共45頁。變量不能出現(xiàn)在一個約束條件的右端變量不能出現(xiàn)在一個約束條件的右端表達(dá)式中不接受括號表達(dá)式中不接受括號“( )”和逗號和逗號“,”等任何符號等任何符號, 例例: 400(X1+X2)需寫為需寫為400X1+400X2表達(dá)式應(yīng)化簡，如表達(dá)式應(yīng)化簡，如2X1+3X2- 4X1應(yīng)寫成應(yīng)寫成 -2X1+3X2缺省假定所有

23、變量非負(fù)；可在模型的缺省假定所有變量非負(fù)；可在模型的“END”語句后用語句后用“FREE name”將變量將變量name的非負(fù)假定取消的非負(fù)假定取消可在可在 “END”后用后用“SUB” 或或“SLB” 設(shè)定設(shè)定(sh dn)變量上下界變量上下界 例如：例如： “sub x1 10”的作用等價于的作用等價于“x1=98; x1=98; 2 2* *x1+x2=600 x1+x2=98 x1=98 2 2* *x1+x2=600 x1+x21 c=-0.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02 1.045 1.065; beq=1; A=0 0.

24、025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,vlb,vub); a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q)To MATLAB（xxgh5）第41頁/共45頁第四十二頁，共45頁。計算結(jié)果：計算結(jié)果：第42頁/共45頁第四十三頁，共45頁。五、五、 結(jié)果結(jié)果(ji gu)分析分析返 回4.4.在在a a附近有一個附近有一個(y )(y )轉(zhuǎn)折點，在這一點左邊，風(fēng)險增加很少時，利潤增長轉(zhuǎn)折點，在這一點左邊，風(fēng)險增加很少時，利潤增長 很快很快. .在這一點右邊，風(fēng)險增加很大時，利潤增長很緩慢，所以對于風(fēng)險和在這一點右邊，風(fēng)險增加很