1、 數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)后勤工程學(xué)院數(shù)學(xué)教研室第第4 4講講 線性規(guī)劃線性規(guī)劃 實(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ī)劃問題。5、實(shí)驗(yàn)作業(yè)。、實(shí)驗(yàn)作業(yè)。3、用數(shù)學(xué)軟件包、用數(shù)學(xué)軟件包lindo、lingo求解線性規(guī)劃問題。求解線性規(guī)劃問題。1、兩個(gè)引例。、兩個(gè)引例。4、建模案例：投資的收益與風(fēng)險(xiǎn)、建模案例：投資的收益與風(fēng)險(xiǎn) 問題一問題一 ： 任務(wù)分配問題：某車間有甲、乙兩臺(tái)機(jī)床，可用于加工三種

2、工件。假定這兩臺(tái)車床的可用臺(tái)時(shí)數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺(tái)時(shí)數(shù)和加工費(fèi)用如下表。問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費(fèi)用最低？ 兩個(gè)引例兩個(gè)引例 解解 設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6?？山⒁韵戮€性規(guī)劃模型： 解答 問題二：?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)員

3、的標(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約束條件為：0, 0180015818002581800158258212121xxxxxx 線性規(guī)劃模型：線性規(guī)劃模型：213640minxxz0, 01594535 .

4、.212121xxxxxxts 解答返 回 線性規(guī)劃模型的一般形式線性規(guī)劃模型的一般形式.,.,.,.,.minnixnibxat sxcuinkikikniii2102111 目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量的線性函數(shù)。的線性函數(shù)。min. . ucxAxbstvlbxvub矩矩陣陣形形式式： 實(shí)際問題中實(shí)際問題中的優(yōu)化模型的優(yōu)化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x決策變量決策變量f(x)目標(biāo)函數(shù)目標(biāo)函數(shù)gi(x) 0約束條件約束條件數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃線性規(guī)劃線性規(guī)劃(LP)二次規(guī)劃二次規(guī)劃(

5、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)化模型的分類 min z=cX bAXts. .1、模型：命令：x=linprog（c，A，b） 2、模型：min z=cX bAXts. .beqXAeq命令：x=linprog（c，A，b，Aeq,beq） 或或 x=linprog（c，A，b，Aeq,beq,x0）或或 x,fval=linprog（c，A，b，Aeq,beq）注意注意：若沒有不等式： 存在，則令A(yù)= ，b= .bAX

6、用用MATLAB優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃 3、模型：min z=cX bAXts. .beqXAeqVLBXVUB 命令：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)解返回最優(yōu)解及及處的目標(biāo)函數(shù)值處的目標(biāo)函數(shù)值fval. 321436minxxxz 1231231232380120. .3005020 xxxxxxstxx

7、x 解解: 編寫編寫M文件文件xxgh1.m如下：如下： c=6 3 4; A=1,2,-3;0 1 0; b=80;50; Aeq=1 1 1; beq=120; vlb=30,0,20; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)To Matlab (xxgh1)123123123123min(6 3 4)1238001050. . 1 1 112030020 xzxxxxxxstxxxxx 例例1 解解 編寫編寫M文件文件xxgh2.m如下：如下：c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0.01

8、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 (xxgh2)max 6543216 . 064. 072. 032. 028. 04 . 0 xxxxxxz 85003. 003. 003. 001. 001. 001. 0. .654321xxxxxxts 70005. 002. 041xx

9、 10005. 002. 052xx 90008. 003. 063xx 6, 2 , 10jxj 例例2 S.t.Xz8121110913min 9008003 . 12 . 15 . 000000011 . 14 . 0X500600400100100010010001001X ，0654321xxxxxxX改寫為： 問題問題例例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 1 0 0 0 1 0 0 1 0 0 0

10、 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 = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004計(jì)算結(jié)果：計(jì)算結(jié)果： 即在甲機(jī)床上加工600個(gè)工件2,在乙機(jī)床上加工400個(gè)工件1、500個(gè)工件3，可在滿足條件的情況下使總加工費(fèi)最小為13800。 問題問題 213640minxxz s.t. )45(3521xx改寫為：例例2 問題二的解答 編寫編寫M

11、文件文件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.0000 fval =360即只需聘用9個(gè)一級(jí)檢驗(yàn)員。 注：注：本問題應(yīng)還有一個(gè)約束條件：x1、x2取整數(shù)。故它是一個(gè)整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃問題。這里把它當(dāng)成一個(gè)線性規(guī)劃來解，求得其最優(yōu)解剛好是整數(shù)：x1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解。若用線性規(guī)

12、劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專門的方法求解。返 回 用用LINGO優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃 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) LINGO模型的優(yōu)點(diǎn)模型的優(yōu)點(diǎn)1. LINGO軟件簡(jiǎn)介軟件簡(jiǎn)介(2) 對(duì)簡(jiǎn)單的對(duì)簡(jiǎn)單的LINGO程序程序 LINGO也可以也可以LINDO一樣編程一樣編程但但LINGO與與LINDO語法有差異語法有差異提供

13、了靈活的編程語言（矩陣生成器）提供了靈活的編程語言（矩陣生成器）包含了包含了LINDO的全部功能的全部功能 2.Lingo軟件包使用軟件包使用程序程序：minmin=7=7* *x1+3x1+3* *x2x2; ; x1+x2=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+x2=600 x1 x1，x2x2 為整數(shù)為整數(shù) 3. lingo軟件包的變量界定軟件包的變量界定bin(x) 限制限制x 為為0 0 或或1;1;bnd(L,

14、x,U) 限制限制LxU;free(x) 取消對(duì)變量取消對(duì)變量x 的默認(rèn)下界為的默認(rèn)下界為0 0 的限制，的限制， 即即x 可以取任意實(shí)數(shù)可以取任意實(shí)數(shù); ;gin(x) 限制限制x 為為整數(shù)整數(shù). .在默認(rèn)情況下，在默認(rèn)情況下，LINGO 規(guī)定變量是非負(fù)的，也規(guī)定變量是非負(fù)的，也就是說下界為就是說下界為0 0，上界為，上界為+。變量界定函數(shù)變量界定函數(shù)實(shí)現(xiàn)對(duì)變量取值范圍的限制實(shí)現(xiàn)對(duì)變量取值范圍的限制, ,共共4種：種： 1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 制訂生

15、產(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ì)劃 1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動(dòng)時(shí)

16、間勞動(dòng)時(shí)間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472xxzMax每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天建立模型建立模型 Model:Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;end Global optimal solution found. Objective value: 3360.000 Infeasibilities: 0.000000

17、Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.00000020桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤(rùn)利潤(rùn)3360元。元。 模型求解模型求解 Global optimal solution found. Objective va

18、lue: 3360.000 Infeasibilities: 0.000000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000原料無剩余原料無剩余時(shí)間無剩余時(shí)間無剩余加工能力剩余加工能力剩余40Model:Max=72*x1+64

19、*x2;x1+x250;12*x1+8*x2480;3*x1100;end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 結(jié)果解釋結(jié)果解釋 模型求解模型求解 reduced cost值表值表示當(dāng)該非基變量示當(dāng)該非基變量增加一個(gè)單位時(shí)增加一個(gè)單位時(shí)（其他非基變量（其他非基變量保持不變）目標(biāo)保持不變）目標(biāo)函數(shù)減少的量函數(shù)減少的量(對(duì)對(duì)max型問題型問題) Global optimal solution found. Objective value: 3360.000 Infeasibilities: 0.000000 Total solver i

20、terations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000也可理解為：也可理解為：為了使該非基變?yōu)榱耸乖摲腔兞孔兂苫兞?，量變成基變量，目?biāo)函數(shù)中對(duì)應(yīng)目標(biāo)函數(shù)中對(duì)應(yīng)系數(shù)應(yīng)增加的量系數(shù)應(yīng)增加的量 Global optimal solution found. Object

21、ive value: 3360.000 Infeasibilities: 0.000000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000結(jié)果解釋結(jié)果解釋 最優(yōu)解下最優(yōu)解下“資源資源”增增加加1單位時(shí)單位時(shí)“效益效益”的的增量增量

22、 原料增原料增1單位單位, 利潤(rùn)增利潤(rùn)增48 時(shí)間加時(shí)間加1單位單位, 利潤(rùn)增利潤(rùn)增2 能力增減不影響利潤(rùn)能力增減不影響利潤(rùn)影子價(jià)格影子價(jià)格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？ 35 48, 應(yīng)該買！應(yīng)該買！ 聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？ 2元！元！ Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 7

23、2.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 50.00000 10.00000 6.666667 3 480.0000 53.33333 80.00000 4 100.0000 INFINITY 40.00000最優(yōu)解不變時(shí)目標(biāo)最優(yōu)解不變時(shí)目標(biāo)系數(shù)允許變化范圍系數(shù)允許變化范圍 x1系數(shù)范圍系數(shù)范圍(64,96) x2系數(shù)范圍系數(shù)范圍(48,72) A1獲利增加到獲利增加到

24、30元元/千克，應(yīng)否改變生產(chǎn)計(jì)劃千克，應(yīng)否改變生產(chǎn)計(jì)劃 x1系數(shù)由系數(shù)由24 3= 72 增加增加為為30 3= 90，在在允許范圍內(nèi)允許范圍內(nèi) 不變不變！( (約束條件不變約束條件不變) )結(jié)果解釋結(jié)果解釋( (靈敏度分析靈敏度分析) ) 結(jié)果解釋結(jié)果解釋 Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 6

25、4.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 50.00000 10.00000 6.666667 3 480.0000 53.33333 80.00000 4 100.0000 INFINITY 40.00000影子價(jià)格有意義影子價(jià)格有意義時(shí)約束右端的允時(shí)約束右端的允許變化范圍許變化范圍 原料最多增加原料最多增加10 時(shí)間最多增加時(shí)間最多增加53 35元可買到元可買到1桶牛奶，每天最多買多少？桶牛奶，每天最多買多少？最多買最多買10

26、桶桶(目標(biāo)函數(shù)不變目標(biāo)函數(shù)不變)注意注意: 充分但充分但可能不必要可能不必要 1桶桶牛奶牛奶 3千克千克A1 12小時(shí)小時(shí) 8小時(shí)小時(shí) 4公斤公斤A2 或或獲利獲利24元元/公斤公斤 獲利獲利16元元/公斤公斤 0.8千克千克B12小時(shí)小時(shí),3元元1千克千克獲利獲利44元元/千克千克 0.75千克千克B22小時(shí)小時(shí),3元元1千克千克獲利獲利32元元/千克千克 制訂生產(chǎn)計(jì)劃，使每天凈利潤(rùn)最大制訂生產(chǎn)計(jì)劃，使每天凈利潤(rùn)最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小時(shí)時(shí)間，應(yīng)否投小時(shí)時(shí)間，應(yīng)否投資？現(xiàn)投資資？現(xiàn)投資150元，可賺回多少？元，可賺回多少？50桶牛奶桶牛奶, 480小

27、時(shí)小時(shí) 至多至多100公斤公斤A1 B1，B2的獲利經(jīng)常有的獲利經(jīng)常有10%的波動(dòng)，對(duì)計(jì)劃有無影響？的波動(dòng)，對(duì)計(jì)劃有無影響？例例2 奶制品的生產(chǎn)銷售計(jì)劃奶制品的生產(chǎn)銷售計(jì)劃 1桶桶牛奶牛奶 3千克千克 A1 12小時(shí)小時(shí) 8小時(shí)小時(shí) 4千克千克 A2 或或獲利獲利24元元/千克千克 獲利獲利16元元/kg 0.8千克千克 B12小時(shí)小時(shí),3元元1千克千克獲利獲利44元元/千克千克 0.75千克千克 B22小時(shí)小時(shí),3元元1千克千克獲利獲利32元元/千克千克 出售出售x1 千克千克 A1, x2 千克千克 A2， x3千克千克 B1, x4千克千克 B2原料原料供應(yīng)供應(yīng) 勞動(dòng)勞動(dòng)時(shí)間時(shí)間 加工能

28、力加工能力 決策決策變量變量 目標(biāo)目標(biāo)函數(shù)函數(shù) 利潤(rùn)利潤(rùn)約束約束條件條件非負(fù)約束非負(fù)約束 0,61xx x5千克千克 A1加工加工B1， x6千克千克 A2加工加工B26543213332441624xxxxxxzMax50436251xxxx48022)(2)(4656251xxxxxx10051 xx附加約束附加約束 5380 x.x64750 x.x 50桶牛奶桶牛奶, 480小時(shí)小時(shí) 至多至多100公斤公斤A1 所以模型為所以模型為: :5043) 26251xxxx48022)(2)(4) 3656251xxxxxx600334) 26521xxxx44804624) 36521xxxx約束條件恒等變形：約束條件恒等變形：1234561256125615354616241644323343436004264480100. .0.80.75,0Max zxxxxxxxxxxxxxxxxstxxxxxx Lingo程序程序Model:Max=24*x1+16*x2+44*x3 +32*x4 -3*x5-3*x6;4*x1+3*x2+4*x5