數(shù)學(xué)建模MATLAB之線性規(guī)劃

1、編輯課件1 線性規(guī)劃線性規(guī)劃數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)編輯課件2實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容2. 掌握用數(shù)學(xué)軟件包求解線性規(guī)劃問題掌握用數(shù)學(xué)軟件包求解線性規(guī)劃問題.1. 了解線性規(guī)劃的基本內(nèi)容了解線性規(guī)劃的基本內(nèi)容.2. 用數(shù)學(xué)軟件包用數(shù)學(xué)軟件包MATLAB求解線性規(guī)劃問題求解線性規(guī)劃問題.5. 實(shí)驗(yàn)作業(yè)實(shí)驗(yàn)作業(yè). .3. 用數(shù)學(xué)軟件包用數(shù)學(xué)軟件包LINDO、LINGO求解線性規(guī)劃問題求解線性規(guī)劃問題.1. 兩個(gè)引例兩個(gè)引例.4. 建模案例：投資的收益與風(fēng)險(xiǎn)建模案例：投資的收益與風(fēng)險(xiǎn).編輯課件3問題一問題一 ： 任務(wù)分配問題：某車間有甲、乙兩臺(tái)機(jī)床，可用于加工三種工件.假定這兩臺(tái)

2、車床的可用臺(tái)時(shí)數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺(tái)時(shí)數(shù)和加工費(fèi)用如下表.問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費(fèi)用最低？ 單位工件所需加工臺(tái)時(shí)數(shù) 單位工件的加工費(fèi)用 車床類 型 工件1 工件2 工件3 工件1 工件2 工件3 可用臺(tái)時(shí)數(shù) 甲 0.4 1.1 1.0 13 9 10 800 乙 0.5 1.2 1.3 11 12 8 900 兩個(gè)引例兩個(gè)引例編輯課件4解解 設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6,可建立

3、以下線性規(guī)劃模型： 解答編輯課件5問題二：?jiǎn)栴}二： 某廠每日8小時(shí)的產(chǎn)量不低于1800件.為了進(jìn)行質(zhì)量控制，計(jì)劃聘請(qǐng)兩種不同水平的檢驗(yàn)員.一級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度25件/小時(shí)，正確率98%，計(jì)時(shí)工資4元/小時(shí)；二級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度15件/小時(shí)，正確率95%，計(jì)時(shí)工資3元/小時(shí).檢驗(yàn)員每錯(cuò)檢一次，工廠要損失2元.為使總檢驗(yàn)費(fèi)用最省，該工廠應(yīng)聘一級(jí)、二級(jí)檢驗(yàn)員各幾名？解解 設(shè)需要一級(jí)和二級(jí)檢驗(yàn)員的人數(shù)分別為x1、x2人,則應(yīng)付檢驗(yàn)員的工資為：212124323848xxxx因檢驗(yàn)員錯(cuò)檢而造成的損失為：21211282)%5158%2258(xxxx編輯課件6故目標(biāo)函數(shù)為：故目標(biāo)函數(shù)為：2121

4、213640)128()2432(minxxxxxxz約束條件為：0, 0180015818002581800158258212121xxxxxx編輯課件7線性規(guī)劃模型：線性規(guī)劃模型：213640minxxz12121253459s.t. 150,0 xxxxxx 解答返 回編輯課件8線性規(guī)劃模型的一般形式線性規(guī)劃模型的一般形式11min,1,2,., .s.t.0,1,2,., .ni iinik kikiucxa xb inxin 目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量的線性函數(shù)的線性函數(shù).min. s.tucxAxbvlbxvub矩矩陣陣形形式式：編輯課

5、件9實(shí)際問題中實(shí)際問題中的優(yōu)化模型的優(yōu)化模型T1min(max)( ),(,)s.t.( )0,1,2,nizf xxxxg xim或x是決策變量是決策變量f(x)是目標(biāo)函數(shù)是目標(biāo)函數(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ī)劃 優(yōu)化模型的分類優(yōu)化模型的分類編輯課件10用用MATLAB優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃min z=cX s.t.AXb1. 模

6、型：命令：x=linprog（c, A, b） 2. 模型：min z=cX s.t.AXbbeqXAeq命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式： 存在，則令A(yù)= ，b= .bAX 編輯課件113. 模型：min z=cX s.t.AXbbeqXAeqVLBXVUB命令：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表示初始點(diǎn) beqXAeq4. 命令：x,fval=linprog(

7、)返回最優(yōu)解及處的目標(biāo)函數(shù)值fval.編輯課件12解解 編寫編寫M文件文件xxgh1.m如下：如下：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 (xxgh1)編輯課件13解解: 編寫編寫M文件文

8、件xxgh2.m如下：如下： 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編輯課件14s.t.Xz8121110913min 9008003 . 12 . 15 . 000000011 . 14 . 0X改寫為：例例3 問題一的解答 問題問題編輯課件15編寫編寫M文件文件xxgh3.m如下如下:

9、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)編輯課件16結(jié)果結(jié)果:x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004 即在甲機(jī)床上加工600個(gè)工件2

10、,在乙機(jī)床上加工400個(gè)工件1、500個(gè)工件3，可在滿足條件的情況下使總加工費(fèi)最小為13800.編輯課件17例例2 問題二的解答 問題問題 213640minxxz s.t. )45(3521xx改寫為：編輯課件18編寫編寫M文件文件xxgh4.m如下：如下：c = 40;36;A=-5 -3;b=-45;Aeq=;beq=;vlb = zeros(2,1);vub=9;15; %調(diào)用linprog函數(shù)：x,fval = linprog(c,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh4)編輯課件19結(jié)果為：結(jié)果為：x = 9.0000 0.0000fval =360

11、即只需聘用9個(gè)一級(jí)檢驗(yàn)員. 注：注：本問題應(yīng)還有一個(gè)約束條件：x1、x2取整數(shù).故它是一個(gè)整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃問題.這里把它當(dāng)成一個(gè)線性規(guī)劃來解，求得其最優(yōu)解剛好是整數(shù)：x1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解.若用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專門的方法求解.返 回編輯課件20用用LINDO、LINGO優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃編輯課件21一、一、LINDO軟件包軟件包 下面我們通過一個(gè)例題來說明下面我們通過一個(gè)例題來說明LINDO軟件包的使用方法軟件包的使用方法.編輯課件22LINDOLINDO和和LIN

12、GOLINGO軟件能求解的優(yōu)化模型軟件能求解的優(yōu)化模型 LINGO LINDO優(yōu)化模型優(yōu)化模型線性規(guī)劃線性規(guī)劃(LP)非線性規(guī)劃非線性規(guī)劃(NLP)二次規(guī)劃二次規(guī)劃(QP)連續(xù)優(yōu)化連續(xù)優(yōu)化整數(shù)規(guī)劃整數(shù)規(guī)劃(IP)編輯課件231桶牛奶 3千克A1 12小時(shí) 8小時(shí) 4千克A2 或獲利24元/千克 獲利16元/千克 50桶牛奶桶牛奶 時(shí)間時(shí)間: 480小時(shí)小時(shí) 至多加工至多加工100千克千克A1 制訂生產(chǎn)計(jì)劃，使每天獲利最大制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)

13、工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到的獲利增加到 30元元/千克，是否應(yīng)改變生產(chǎn)計(jì)劃？千克，是否應(yīng)改變生產(chǎn)計(jì)劃？ 每天：每天：例例1 加工奶制品的生產(chǎn)計(jì)劃加工奶制品的生產(chǎn)計(jì)劃編輯課件24x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動(dòng)時(shí)間勞動(dòng)時(shí)間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 12max7264zxx每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)建立模型建立模型編輯課件25max

14、72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS

15、? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤(rùn)，利潤(rùn)3360元元. 模型求解模型求解編輯課件26 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000原料無(wú)剩余原料無(wú)剩余時(shí)間無(wú)剩余時(shí)間無(wú)剩余加工能力剩余加工能力剩余40m

16、ax 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 結(jié)果解釋結(jié)果解釋編輯課件27模型求解模型求解 reduced cost值表值表示當(dāng)該非基變量示當(dāng)該非基變量增加一個(gè)單位時(shí)增加一個(gè)單位時(shí)（其他非基變量（其他非基變量保持不變）保持不變）,目標(biāo)目標(biāo)函數(shù)減少的量函數(shù)減少的量(對(duì)對(duì)max型問題型問題) . OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0

17、.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2也可理解為：也可理解為：為了使該非基變?yōu)榱耸乖摲腔兞孔兂苫兞?，量變成基變量，目?biāo)函數(shù)中對(duì)應(yīng)目標(biāo)函數(shù)中對(duì)應(yīng)系數(shù)應(yīng)增加的量系數(shù)應(yīng)增加的量編輯課件28 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.

18、000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000結(jié)果解釋結(jié)果解釋 最優(yōu)解下最優(yōu)解下“資源資源”增加增加1單位時(shí)單位時(shí)“效益效益”的增量的增量 原料增原料增1單位單位, 利潤(rùn)增利潤(rùn)增48 時(shí)間增時(shí)間增1單位單位, 利潤(rùn)增利潤(rùn)增2 能力增減不影響利潤(rùn)能力增減不影響利潤(rùn)影子價(jià)格影子價(jià)格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？35 ”（或（或“=”（或（或“=”）功能相同）功能相同變量

19、與系數(shù)間可有空格變量與系數(shù)間可有空格(甚至回車甚至回車), 但無(wú)運(yùn)算符但無(wú)運(yùn)算符變量名以字母開頭，不能超過變量名以字母開頭，不能超過8個(gè)字符個(gè)字符變量名不區(qū)分大小寫（包括變量名不區(qū)分大小寫（包括LINDO中的關(guān)鍵字）中的關(guān)鍵字）目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件行號(hào)行號(hào)(行名行名)自動(dòng)產(chǎn)生或人為定義自動(dòng)產(chǎn)生或人為定義.行名以行名以“）”結(jié)束結(jié)束行中注有行中注有“!”符號(hào)的后面部分為注釋符號(hào)的后面部分為注釋.如如: ! Its Comment.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE” 對(duì)模型命名對(duì)模型命名（最多（最多72個(gè)字

20、符），如：個(gè)字符），如： TITLE This Model is only an Example編輯課件32變量不能出現(xiàn)在一個(gè)約束條件的右端變量不能出現(xiàn)在一個(gè)約束條件的右端表達(dá)式中不接受括號(hào)表達(dá)式中不接受括號(hào)“( )”和逗號(hào)和逗號(hào)“,”等任何符號(hào)等任何符號(hào), 例例: 400(X1+X2)需寫為需寫為400X1+400X2表達(dá)式應(yīng)化簡(jiǎn)，如表達(dá)式應(yīng)化簡(jiǎn)，如2X1+3X2- 4X1應(yīng)寫成應(yīng)寫成 -2X1+3X2缺省假定所有變量非負(fù)；可在模型的缺省假定所有變量非負(fù)；可在模型的“END”語(yǔ)句后語(yǔ)句后用用“FREE name”將變量將變量name的非負(fù)假定取消的非負(fù)假定取消可在可在 “END”后用后用“S

21、UB” 或或“SLB” 設(shè)定變量上下設(shè)定變量上下界界 例如：例如： “sub x1 10”的作用等價(jià)于的作用等價(jià)于“x1=345.5 x1+x2=345.5; ; x1=98; x1=98; 2 2* *x1+x2=600 x1+x2=345.5 x1+x2=345.5 x1=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.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)