線性規(guī)劃的求解與靈敏度問題

1、第第1頁頁第第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ī)劃問題.3. 用數(shù)學(xué)軟件包用數(shù)學(xué)軟件包LINDO、LINGO求解線性規(guī)劃問題求解線性規(guī)劃問題.1. 兩個引例兩個引例.4. 建模案例：投資的收益與風(fēng)險建模案例：投資的收益與風(fēng)險.第第3頁頁問題一問題一 ： 任務(wù)分配問題：某車間有甲、乙兩臺機(jī)床，可用任務(wù)分配問題：某車間有甲、乙兩臺機(jī)床，可用于加工三種工件于加工三種工件.假定這兩臺車床的可用臺時數(shù)分別為假定

2、這兩臺車床的可用臺時數(shù)分別為800和和900，三種工件的數(shù)量分別為，三種工件的數(shù)量分別為400、600和和500，且已知用三種，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費(fèi)用如不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費(fèi)用如下表下表.問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費(fèi)用最低？求，又使加工費(fèi)用最低？ 單位工件所需加工臺時數(shù) 單位工件的加工費(fèi)用 車床類 型 工件1 工件2 工件3 工件1 工件2 工件3 可用臺時數(shù) 甲 0.4 1.1 1.0 13 9 10 800 乙 0.5 1.2 1.3 11 1

3、2 8 900 兩個引例兩個引例第第4頁頁解解 設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6,可建立以下線性規(guī)劃模型： 解答第第5頁頁問題二：問題二： 某廠每日8小時的產(chǎn)量不低于1800件.為了進(jìn)行質(zhì)量控制，計劃聘請兩種不同水平的檢驗(yàn)員.一級檢驗(yàn)員的標(biāo)準(zhǔn)為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗(yàn)員的標(biāo)準(zhǔn)為：速度15件/小時，正確率95%，計時工資3元/小時.檢驗(yàn)員每錯檢一次，工廠要損失2元.為使總檢驗(yàn)費(fèi)用最省，該工廠應(yīng)聘一級、二級檢驗(yàn)員各幾名？解解 設(shè)需要一級和二級檢驗(yàn)員的人數(shù)分別為x1、x2人,則應(yīng)

4、付檢驗(yàn)員的工資為：212124323848xxxx因檢驗(yàn)員錯檢而造成的損失為：21211282)%5158%2258(xxxx第第6頁頁故目標(biāo)函數(shù)為：故目標(biāo)函數(shù)為：2121213640)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

5、inxin 目標(biāo)函數(shù)和所有的約束條件都是設(shè)計變量目標(biāo)函數(shù)和所有的約束條件都是設(shè)計變量的線性函數(shù)的線性函數(shù).min. s.tucxAxbvlbxvub矩矩陣陣形形式式：第第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ī)劃一般整

6、數(shù)規(guī)劃一般整數(shù)規(guī)劃連續(xù)規(guī)劃連續(xù)規(guī)劃 優(yōu)化模型的分類第第10頁頁用用MATLAB優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃min z=cX s.t.AXb1. 模型：命令：x=linprog（c, A, b） 2. 模型：min z=cX s.t.AXbbeqXAeq命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式： 存在，則令A(yù)= ，b= .bAX 第第11頁頁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，V

7、UB, X0） 注意：1 若沒有等式約束: , 則令A(yù)eq= , beq= . 2其中X0表示初始點(diǎn) beqXAeq4. 命令：x,fval=linprog()返回最優(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;

8、 vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub) To MATLAB (xxgh1)第第13頁頁解解: 編寫編寫M文件文件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第第14頁頁s.t.Xz8121110913min 900800

9、3 . 12 . 15 . 000000011 . 14 . 0X改寫為：例例3 問題一的解答 問題問題第第15頁頁編寫編寫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 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

10、.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004 即在甲機(jī)床上加工600個工件2,在乙機(jī)床上加工400個工件1、500個工件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(

11、c,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh4)第第19頁頁結(jié)果為：結(jié)果為：x = 9.0000 0.0000fval =360即只需聘用9個一級檢驗(yàn)員. 注：注：本問題應(yīng)還有一個約束條件：x1、x2取整數(shù).故它是一個整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃問題.這里把它當(dāng)成一個線性規(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頁頁一、LIND

12、O軟件包 下面我們通過一個例題來說明下面我們通過一個例題來說明LINDO軟件包的使用方法軟件包的使用方法.第第22頁頁LINDO和LINGO軟件能求解的優(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)第第23頁頁1桶牛奶 3千克A1 12小時 8小時 4千克A2 或獲利24元/千克 獲利16元/千克 50桶牛奶桶牛奶 時間時間: 480小時小時 至多加工至多加工100千克千克A1 制訂生產(chǎn)計劃，使每天獲利最大制訂生產(chǎn)計劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買

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

14、束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)建立模型第第25頁頁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.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. ITERAT

15、IONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤利潤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原料

16、無剩余原料無剩余時間無剩余時間無剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 結(jié)果解釋第第27頁頁模型求解模型求解 reduced cost值表值表示當(dāng)該非基變量示當(dāng)該非基變量增加一個單位時增加一個單位時（其他非基變量（其他非基變量保持不變）保持不變）,目標(biāo)目標(biāo)函數(shù)減少的量函數(shù)減少的量(對對max型問題型問題) . OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALU

17、E 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也可理解為：也可理解為：為了使該非基變?yōu)榱耸乖摲腔兞孔兂苫兞?，量變成基變量，目?biāo)函數(shù)中對應(yīng)目標(biāo)函數(shù)中對應(yīng)系數(shù)應(yīng)增加的量系數(shù)應(yīng)增加的量第第28頁頁 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE

18、 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單位時單位時“效益效益”的增量的增量 原料增原料增1單位單位, 利潤增利潤增48 時間增時間增1單位單位, 利潤增利潤增2 能力增減不影響利潤能力增減不影響利潤影子價格影子價格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？

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

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

21、END”語句語句后用后用“FREE name”將變量將變量name的非負(fù)假定取消的非負(fù)假定取消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;

22、 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)，hold on a=a+0.001;end xlabel(a),ylabel(Q)To MATLAB（xxgh5）第第43頁頁計算結(jié)果：計算結(jié)果：第第44頁頁五、五、 結(jié)果分析結(jié)果分析返 回4 4.在a=0.006附近有一個轉(zhuǎn)折點(diǎn)，在這一點(diǎn)左

23、邊，風(fēng)險增加很少時，利潤增長 很快.在這一點(diǎn)右邊，風(fēng)險增加很大時，利潤增長很緩慢，所以對于風(fēng)險和 收益沒有特殊偏好的投資者來說，應(yīng)該選擇曲線的拐點(diǎn)作為最優(yōu)投資組合， 大約是a*=0.6%，Q*=20% ，所對應(yīng)投資方案為: 風(fēng)險度 收益 x0 x1 x2 x3 x4 0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212 3.3.曲線上的任一點(diǎn)都表示該風(fēng)險水平的最大可能收益和該收益要求的最小風(fēng)險.對于不同風(fēng)險的承受能力，選擇該風(fēng)險水平下的最優(yōu)投資組合.2 2.當(dāng)投資越分散時，投資者承擔(dān)的風(fēng)險越小，這與題意一致.即: 冒險的投資者會出現(xiàn)集中投資的情況，保守的投資者則盡量分散投資.1.1.風(fēng)險大，收益也大.第第45頁頁實(shí)驗(yàn)作業(yè)實(shí)驗(yàn)作業(yè) 某廠生產(chǎn)甲乙兩種口味的飲料,每百箱甲飲料需用原料6千克,工人10名,可獲利10萬元;每百箱乙飲料需用原料5千克,工人20名,可獲利9萬元.今工廠共有原料60千克,工人150名,又由于其他條件所限甲飲料產(chǎn)量不超過800箱.問如何安排生產(chǎn)計劃,即兩種飲料各生產(chǎn)多少使獲利最大.進(jìn)一步討論: 1)若投資0.8萬元可增加原料1千克,問應(yīng)否作這項(xiàng)投資. 2)若每100箱甲飲料獲利可增加1萬元,問應(yīng)否改變生產(chǎn)計劃.返 回第第46頁頁MATLAB優(yōu)化工