【大學(xué)】數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn) 線性規(guī)劃

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

2、數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺(tái)時(shí)數(shù)和加工費(fèi)用如下表.問(wèn)怎樣分配車床的加工任務(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è)引例整理課件解解 設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6,可建立以下線性規(guī)劃模型

3、： 解答整理課件問(wèn)題二：?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整理課件故目標(biāo)函數(shù)為：故目標(biāo)函數(shù)為：2121213640)128

4、()2432(minxxxxxxz約束條件為：0, 0180015818002581800158258212121xxxxxx整理課件線性規(guī)劃模型：線性規(guī)劃模型：213640minxxz12121253459s.t. 150,0 xxxxxx 解答返 回整理課件線性規(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矩矩陣陣形形式式：整理課件實(shí)際問(wèn)題中實(shí)際問(wèn)題中的

5、優(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)化模型的分類整理課件用用MATLAB優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃min z=cX s.t.AXb1. 模型：命令：x=linprog（

6、c, A, b） 2. 模型：min z=cX s.t.AXbbeqXAeq命令：x=linprog（c，A，b，Aeq,beq）注意：若沒(méi)有不等式： 存在，則令A(yù)= ，b= .bAX 整理課件3. 模型：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 若沒(méi)有等式約束: , 則令A(yù)eq= , beq= . 2其中X0表示初始點(diǎn) beqXAeq4. 命令：x,fval=linprog()返回最優(yōu)解及處的目標(biāo)函數(shù)值fva

7、l.整理課件解解 編寫(xiě)編寫(xiě)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)整理課件解解: 編寫(xiě)編寫(xiě)M文件文件如下：如下： c=6 3 4; A=0 1 0; b=

8、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整理課件s.t.Xz8121110913min 9008003 . 12 . 15 . 000000011 . 14 . 0X改寫(xiě)為：例例3 問(wèn)題一的解答 問(wèn)題問(wèn)題整理課件編寫(xiě)編寫(xiě)M文件文件如下如下:f = 13 9 10 11 12 8;A = 0.4 1.1 1 0 0 0 0 0 0

9、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)整理課件結(jié)果結(jié)果:x =fval =1.3800e+004 即在甲機(jī)床上加工600個(gè)工件2,在乙機(jī)床上加工400個(gè)工件1、500個(gè)工件3，可在滿足條件的情況下使總加工費(fèi)最小為13800.整理課件例例2 問(wèn)題二的解答 問(wèn)題問(wèn)題 213640minxxz s.t. )45(3521xx

10、改寫(xiě)為：整理課件編寫(xiě)編寫(xiě)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)整理課件結(jié)果為：結(jié)果為：x =fval =360即只需聘用9個(gè)一級(jí)檢驗(yàn)員. 注：注：本問(wèn)題應(yīng)還有一個(gè)約束條件：x1、x2取整數(shù).故它是一個(gè)整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃問(wèn)題.這里把它當(dāng)成一個(gè)線性規(guī)劃來(lái)解，求得其最優(yōu)解剛好是整數(shù)：x1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解.若用線性規(guī)劃解法求得的最

11、優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專門(mén)的方法求解.返 回整理課件用用LINDO、LINGO優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃整理課件一、一、LINDO軟件包軟件包 下面我們通過(guò)一個(gè)例題來(lái)說(shuō)明下面我們通過(guò)一個(gè)例題來(lái)說(shuō)明LINDO軟件包的使用方法軟件包的使用方法.整理課件LINDOLINDO和和LINGOLINGO軟件能求解的優(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)整理課件1桶牛奶 3千克A1 12小時(shí) 8小時(shí)

12、 4千克A2 或獲利24元/千克 獲利16元/千克 50桶牛奶桶牛奶 時(shí)間時(shí)間: 480小時(shí)小時(shí) 至多加工至多加工100千克千克A1 制訂生產(chǎn)計(jì)劃，使每天獲利最大制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到的獲利增加到 30元元/千克，是否應(yīng)改變生產(chǎn)計(jì)劃？千克，是否應(yīng)改變生產(chǎn)計(jì)劃？ 每天：每天：例例1 加工奶制品的生產(chǎn)計(jì)劃加工奶制品的生產(chǎn)計(jì)劃整理課件x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利

13、獲利 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)建立模型建立模型整理課件max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES NO.

14、ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤(rùn)，利潤(rùn)3360元元. 模型求解模型求解整理課件 OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES 原料無(wú)剩余原料無(wú)剩余時(shí)間無(wú)剩余時(shí)間無(wú)剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束

15、）剩余為零的約束為緊約束（有效約束） 結(jié)果解釋結(jié)果解釋整理課件模型求解模型求解 reduced cost值表值表示當(dāng)該非基變量示當(dāng)該非基變量增加一個(gè)單位時(shí)增加一個(gè)單位時(shí)（其他非基變量（其他非基變量保持不變）保持不變）,目標(biāo)目標(biāo)函數(shù)減少的量函數(shù)減少的量(對(duì)對(duì)max型問(wèn)題型問(wèn)題) . OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST X1 20.000000 X2 30.000000 ROW SLACK OR SURPLUS DUAL PRICES NO. ITERATIONS= 2也可理解為：也可理解為：為了使該非基變?yōu)榱耸乖摲腔兞孔兂苫?/p>

16、變量，量變成基變量，目標(biāo)函數(shù)中對(duì)應(yīng)目標(biāo)函數(shù)中對(duì)應(yīng)系數(shù)應(yīng)增加的量系數(shù)應(yīng)增加的量整理課件 OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3) 0.000000 4) 40.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桶牛奶，要買

17、嗎？桶牛奶，要買嗎？35 ”（或（或“=”（或（或“=”）功能相同）功能相同2. 變量與系數(shù)間可有空格變量與系數(shù)間可有空格(甚至回車甚至回車), 但無(wú)運(yùn)算符但無(wú)運(yùn)算符3. 變量名以字母開(kāi)頭，不能超過(guò)變量名以字母開(kāi)頭，不能超過(guò)8個(gè)字符個(gè)字符4. 變量名不區(qū)分大小寫(xiě)（包括變量名不區(qū)分大小寫(xiě)（包括LINDO中的關(guān)鍵字）中的關(guān)鍵字）5. 目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件6. 行號(hào)行號(hào)(行名行名)自動(dòng)產(chǎn)生或人為定義自動(dòng)產(chǎn)生或人為定義.行名以行名以“）”結(jié)束結(jié)束7. 行中注有行中注有“!”符號(hào)的后面部分為注釋符號(hào)的后面部分為注釋.如如: ! Its Co

18、mment.8. 在模型的任何地方都可以用在模型的任何地方都可以用“TITLE” 對(duì)模型命名對(duì)模型命名（最多（最多72個(gè)字符），如：個(gè)字符），如： TITLE This Model is only an Example整理課件9. 變量不能出現(xiàn)在一個(gè)約束條件的右端變量不能出現(xiàn)在一個(gè)約束條件的右端10.表達(dá)式中不接受括號(hào)表達(dá)式中不接受括號(hào)“( )”和逗號(hào)和逗號(hào)“,”等任何符號(hào)等任何符號(hào), 例例: 400(X1+X2)需寫(xiě)為需寫(xiě)為400X1+400X211.表達(dá)式應(yīng)化簡(jiǎn)，如表達(dá)式應(yīng)化簡(jiǎn)，如2X1+3X2- 4X1應(yīng)寫(xiě)成應(yīng)寫(xiě)成 -2X1+3X212.缺省假定所有變量非負(fù)；可在模型的缺省假定所有變量非

19、負(fù)；可在模型的“END”語(yǔ)句后語(yǔ)句后用用“FREE name”將變量將變量name的非負(fù)假定取消的非負(fù)假定取消13.可在可在 “END”后用后用“SUB” 或或“SLB” 設(shè)定變量上下設(shè)定變量上下界界 例如：例如： “sub x1 10”的作用等價(jià)于的作用等價(jià)于“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.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)，ho