數(shù)學(xué)軟件求解線性規(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í)數(shù)分別為800和

2、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ī)劃模型： 解答問(wèn)題二：?jiǎn)栴}二：

3、 某廠每日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()2432(minxxxxxxz約束條

4、件為：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)題中的優(yōu)化模型的優(yōu)化模型T1min(max)( ),(,)s.t.(

5、)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（c, A, b） 2. 模型：min z=cX s.t.AXbbeqXA

6、eq命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式： 存在，則令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 若沒有等式約束: , 則令A(yù)eq= , beq= . 2其中X0表示初始點(diǎn) beqXAeq4. 命令：x,fval=linprog()返回最優(yōu)解及處的目標(biāo)函數(shù)值fval.解解 編寫編寫M文件文件xxgh1.m如下：如下：c=-0.4 -0.28

7、-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)解解: 編寫編寫M文件文件xxgh2.m如下：如下： c=6 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30,0,2

8、0; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh2)123m in( 634 )xzxx32120030 xxx1231111 2 0s .t. 0105 0 xxxs.t.Xz8121110913min 9008003 . 12 . 15 . 000000011 . 14 . 0X改寫為：例例3 問(wèn)題一的解答 問(wèn)題問(wèn)題編寫編寫M文件文件xxgh3.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

9、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 = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =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(3

10、521xx改寫為：編寫編寫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)結(jié)果為：結(jié)果為：x = 9.0000 0.0000fval =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ī)

11、劃的最優(yōu)解.若用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專門的方法求解.返 回用用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

12、小時(shí) 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 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000

14、000 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? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤(rùn)，利潤(rùn)3360元元. 模型求解模型求解 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X

15、2 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ú)剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 結(jié)果解釋結(jié)果解釋模型求解模型求解 reduced cost值表值表示當(dāng)該非基變量示當(dāng)該非基變量增加一

16、個(gè)單位時(shí)增加一個(gè)單位時(shí)（其他非基變量（其他非基變量保持不變）保持不變）,目標(biāo)目標(biāo)函數(shù)減少的量函數(shù)減少的量(對(duì)對(duì)max型問(wèn)題型問(wèn)題) . 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= 2也可理解為：也可

17、理解為：為了使該非基變?yōu)榱耸乖摲腔兞孔兂苫兞浚孔兂苫兞?，目?biāo)函數(shù)中對(duì)應(yīng)目標(biāo)函數(shù)中對(duì)應(yīng)系數(shù)應(yīng)增加的量系數(shù)應(yīng)增加的量 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結(jié)果解釋結(jié)果解釋 最優(yōu)解下最優(yōu)解下“資源資源”增加增加1單位時(shí)單位

18、時(shí)“效益效益”的增量的增量 原料增原料增1單位單位, 利潤(rùn)增利潤(rùn)增48 時(shí)間增時(shí)間增1單位單位, 利潤(rùn)增利潤(rùn)增2 能力增減不影響利潤(rùn)能力增減不影響利潤(rùn)影子價(jià)格影子價(jià)格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？ 35 ”（或（或“=”（或（或“=”）功能相同）功能相同2. 變量與系數(shù)間可有空格變量與系數(shù)間可有空格(甚至回車甚至回車), 但無(wú)運(yùn)算符但無(wú)運(yùn)算符3. 變量名以字母開頭，不能超過(guò)變量名以字母開頭，不能超過(guò)8個(gè)字符個(gè)字符4. 變量名不區(qū)分大小寫（包括變量名不區(qū)分大小寫（包括LINDO中的關(guān)鍵字）中的關(guān)鍵字）5. 目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件目標(biāo)函數(shù)所在行是第一行

19、，第二行起為約束條件6. 行號(hào)行號(hào)(行名行名)自動(dòng)產(chǎn)生或人為定義自動(dòng)產(chǎn)生或人為定義.行名以行名以“）”結(jié)束結(jié)束7. 行中注有行中注有“!”符號(hào)的后面部分為注釋符號(hào)的后面部分為注釋.如如: ! Its Comment.8. 在模型的任何地方都可以用在模型的任何地方都可以用“TITLE” 對(duì)模型命名對(duì)模型命名（最多（最多72個(gè)字符），如：個(gè)字符），如： TITLE This Model is only an Example9. 變量不能出現(xiàn)在一個(gè)約束條件的右端變量不能出現(xiàn)在一個(gè)約束條件的右端10.表達(dá)式中不接受括號(hào)表達(dá)式中不接受括號(hào)“( )”和逗號(hào)和逗號(hào)“,”等任何符號(hào)等任何符號(hào), 例例: 400

20、(X1+X2)需寫為需寫為400X1+400X211.表達(dá)式應(yīng)化簡(jiǎn)，如表達(dá)式應(yīng)化簡(jiǎn)，如2X1+3X2- 4X1應(yīng)寫成應(yīng)寫成 -2X1+3X212.缺省假定所有變量非負(fù)；可在模型的缺省假定所有變量非負(fù)；可在模型的“END”語(yǔ)句語(yǔ)句后用后用“FREE name”將變量將變量name的非負(fù)假定取消的非負(fù)假定取消13.可在可在 “END”后用后用“SUB” 或或“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,v