【大學】數學建模與數學實驗 線性規(guī)劃

1、 線性規(guī)劃線性規(guī)劃數學建模與數學實驗數學建模與數學實驗整理課件實驗目的實驗目的實驗內容實驗內容2. 掌握用數學軟件包求解線性規(guī)劃問題掌握用數學軟件包求解線性規(guī)劃問題.1. 了解線性規(guī)劃的基本內容了解線性規(guī)劃的基本內容.2. 用數學軟件包用數學軟件包MATLAB求解線性規(guī)劃問題求解線性規(guī)劃問題.5. 實驗作業(yè)實驗作業(yè). .3. 用數學軟件包用數學軟件包LINDO、LINGO求解線性規(guī)劃問題求解線性規(guī)劃問題.1. 兩個引例兩個引例.4. 建模案例：投資的收益與風險建模案例：投資的收益與風險.整理課件問題一問題一 ： 任務分配問題：某車間有甲、乙兩臺機床，可用于加工三種工件.假定這兩臺車床的可用臺時

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

3、： 解答整理課件問題二：問題二： 某廠每日8小時的產量不低于1800件.為了進行質量控制，計劃聘請兩種不同水平的檢驗員.一級檢驗員的標準為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標準為：速度15件/小時，正確率95%，計時工資3元/小時.檢驗員每錯檢一次，工廠要損失2元.為使總檢驗費用最省，該工廠應聘一級、二級檢驗員各幾名？解解 設需要一級和二級檢驗員的人數分別為x1、x2人,則應付檢驗員的工資為：212124323848xxxx因檢驗員錯檢而造成的損失為：21211282)%5158%2258(xxxx整理課件故目標函數為：故目標函數為：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 目標函數和所有的約束條件都是設計變量目標函數和所有的約束條件都是設計變量的線性函數的線性函數.min. s.tucxAxbvlbxvub矩矩陣陣形形式式：整理課件實際問題中實際問題中的

5、優(yōu)化模型的優(yōu)化模型T1min(max)( ),(,)s.t.( )0,1,2,nizf xxxxg xim或x是決策變量是決策變量f(x)是目標函數是目標函數gi(x) 0是約束條件是約束條件數學規(guī)劃數學規(guī)劃線性規(guī)劃線性規(guī)劃(LP)二次規(guī)劃二次規(guī)劃(QP)非線性規(guī)劃非線性規(guī)劃(NLP)純整數規(guī)劃純整數規(guī)劃(PIP)混合整數規(guī)劃混合整數規(guī)劃(MIP)整數規(guī)劃整數規(guī)劃(IP)0-1整數規(guī)劃整數規(guī)劃一般整數規(guī)劃一般整數規(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）注意：若沒有不等式： 存在，則令A= ，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 若沒有等式約束: , 則令Aeq= , beq= . 2其中X0表示初始點 beqXAeq4. 命令：x,fval=linprog()返回最優(yōu)解及處的目標函數值fva

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

10、改寫為：整理課件編寫編寫M文件文件如下：如下：c = 40;36;A=-5 -3;b=-45;Aeq=;beq=;vlb = zeros(2,1);vub=9;15; %調用linprog函數：x,fval = linprog(c,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh4)整理課件結果為：結果為：x =fval =360即只需聘用9個一級檢驗員. 注：注：本問題應還有一個約束條件：x1、x2取整數.故它是一個整數線性規(guī)劃整數線性規(guī)劃問題.這里把它當成一個線性規(guī)劃來解，求得其最優(yōu)解剛好是整數：x1=9，x2=0，故它就是該整數規(guī)劃的最優(yōu)解.若用線性規(guī)劃解法求得的最

11、優(yōu)解不是整數，將其取整后不一定是相應整數規(guī)劃的最優(yōu)解，這樣的整數規(guī)劃應用專門的方法求解.返 回整理課件用用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)化整數規(guī)劃整數規(guī)劃(IP)整理課件1桶牛奶 3千克A1 12小時 8小時

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

13、獲利 243x1 獲利獲利 164 x2 原料供應原料供應 5021 xx勞動時間勞動時間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標函數目標函數 12max7264zxx每天獲利每天獲利約束條件約束條件非負約束非負約束 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桶牛奶生產桶牛奶生產A1, 30桶生產桶生產A2，利潤，利潤3360元元. 模型求解模型求解整理課件 OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES 原料無剩余原料無剩余時間無剩余時間無剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束

15、）剩余為零的約束為緊約束（有效約束） 結果解釋結果解釋整理課件模型求解模型求解 reduced cost值表值表示當該非基變量示當該非基變量增加一個單位時增加一個單位時（其他非基變量（其他非基變量保持不變）保持不變）,目標目標函數減少的量函數減少的量(對對max型問題型問題) . 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、變量，量變成基變量，目標函數中對應目標函數中對應系數應增加的量系數應增加的量整理課件 OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3) 0.000000 4) 40.000000 結果解釋結果解釋 最優(yōu)解下最優(yōu)解下“資源資源”增加增加1單位時單位時“效益效益”的增量的增量 原料增原料增1單位單位, 利潤增利潤增48 時間增時間增1單位單位, 利潤增利潤增2 能力增減不影響利潤能力增減不影響利潤影子價格影子價格 35元可買到元可買到1桶牛奶，要買

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

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

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