數(shù)學(xué)軟件求解線性規(guī)劃

1、 線性規(guī)劃線性規(guī)劃數(shù)學(xué)建模與數(shù)學(xué)實驗數(shù)學(xué)建模與數(shù)學(xué)實驗實驗?zāi)康膶嶒災(zāi)康膶嶒瀮?nèi)容實驗內(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. 實驗作業(yè)實驗作業(yè). .3. 用數(shù)學(xué)軟件包用數(shù)學(xué)軟件包LINDO、LINGO求解線性規(guī)劃問題求解線性規(guī)劃問題.1. 兩個引例兩個引例.4. 建模案例：投資的收益與風(fēng)險建模案例：投資的收益與風(fēng)險.問題一問題一 ： 任務(wù)分配問題：某車間有甲、乙兩臺機床，可用于加工三種工件.假定這兩臺車床的可用臺時數(shù)分別為800和

2、900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如下表.問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費用最低？ 單位工件所需加工臺時數(shù) 單位工件的加工費用 車床類 型 工件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 兩個引例兩個引例解解 設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6,可建立以下線性規(guī)劃模型： 解答問題二：問題二：

3、 某廠每日8小時的產(chǎn)量不低于1800件.為了進行質(zhì)量控制，計劃聘請兩種不同水平的檢驗員.一級檢驗員的標(biāo)準(zhǔn)為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標(biāo)準(zhǔn)為：速度15件/小時，正確率95%，計時工資3元/小時.檢驗員每錯檢一次，工廠要損失2元.為使總檢驗費用最省，該工廠應(yīng)聘一級、二級檢驗員各幾名？解解 設(shè)需要一級和二級檢驗員的人數(shù)分別為x1、x2人,則應(yīng)付檢驗員的工資為：212124323848xxxx因檢驗員錯檢而造成的損失為：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è)計變量目標(biāo)函數(shù)和所有的約束條件都是設(shè)計變量的線性函數(shù)的線性函數(shù).min. s.tucxAxbvlbxvub矩矩陣陣形形式式：實際問題中實際問題中的優(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表示初始點 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 問題一的解答 問題問題編寫編寫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 即在甲機床上加工600個工件2,在乙機床上加工400個工件1、500個工件3，可在滿足條件的情況下使總加工費最小為13800.例例2 問題二的解答 問題問題 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個一級檢驗員. 注：注：本問題應(yīng)還有一個約束條件：x1、x2取整數(shù).故它是一個整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃問題.這里把它當(dāng)成一個線性規(guī)劃來解，求得其最優(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軟件包軟件包 下面我們通過一個例題來說明下面我們通過一個例題來說明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小時 8

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

13、 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動時間勞動時間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 12max7264zxx每天獲利每天獲利約束條件約束條件非負約束非負約束 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，利潤，利潤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原料無剩余原料無剩余時間無剩余時間無剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 結(jié)果解釋結(jié)果解釋模型求解模型求解 reduced cost值表值表示當(dāng)該非基變量示當(dāng)該非基變量增加一

16、個單位時增加一個單位時（其他非基變量（其他非基變量保持不變）保持不變）,目標(biāo)目標(biāo)函數(shù)減少的量函數(shù)減少的量(對對max型問題型問題) . 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ù)中對應(yīng)目標(biāo)函數(shù)中對應(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單位時單位

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

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

20、(X1+X2)需寫為需寫為400X1+400X211.表達式應(yīng)化簡，如表達式應(yīng)化簡，如2X1+3X2- 4X1應(yīng)寫成應(yīng)寫成 -2X1+3X212.缺省假定所有變量非負；可在模型的缺省假定所有變量非負；可在模型的“END”語句語句后用后用“FREE name”將變量將變量name的非負假定取消的非負假定取消13.可在可在 “END”后用后用“SUB” 或或“SLB” 設(shè)定變量上下設(shè)定變量上下界界 例如：例如： “sub x1 10”的作用等價于的作用等價于“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