數(shù)學(xué)軟件求解線性規(guī)劃數(shù)學(xué)建模論文學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1數(shù)學(xué)軟件數(shù)學(xué)軟件(run jin)求解線性規(guī)劃數(shù)學(xué)建求解線性規(guī)劃數(shù)學(xué)建模論文模論文第一頁(yè)，共45頁(yè)。問(wèn)題一問(wèn)題一 ： 任務(wù)分配問(wèn)題：某車間有甲、乙兩臺(tái)機(jī)任務(wù)分配問(wèn)題：某車間有甲、乙兩臺(tái)機(jī)床，可用于加工三種工件床，可用于加工三種工件.假定這兩臺(tái)車床的可用臺(tái)假定這兩臺(tái)車床的可用臺(tái)時(shí)數(shù)分別為時(shí)數(shù)分別為800和和900，三種工件的數(shù)量分別為，三種工件的數(shù)量分別為400、600和和500，且已知用三種不同車床加工單位數(shù)量不，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺(tái)時(shí)數(shù)和加工費(fèi)用如下表同工件所需的臺(tái)時(shí)數(shù)和加工費(fèi)用如下表.問(wèn)怎樣分配問(wèn)怎樣分配車床的加工任務(wù)，才能既滿足車床的加工任務(wù)，才能既滿

2、足(mnz)加工工件的要加工工件的要求，又使加工費(fèi)用最低？求，又使加工費(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è)(lin )引例引例第2頁(yè)/共45頁(yè)第二頁(yè)，共45頁(yè)。解解 設(shè)在甲車床上加工工件設(shè)在甲車床上加工工件1、2、3的數(shù)量分的數(shù)量分別別(fnbi)為為x1、x2、x3，在乙車床上加工工，在乙車床上加工工件件1、2、3的數(shù)量分別的數(shù)量分別(fnbi)為為x4、x5、x6,可建立以下線性規(guī)劃模型：

3、可建立以下線性規(guī)劃模型： 解答(jid)第3頁(yè)/共45頁(yè)第三頁(yè)，共45頁(yè)。問(wèn)題二：?jiǎn)栴}二： 某廠每日某廠每日8小時(shí)的產(chǎn)量不低于小時(shí)的產(chǎn)量不低于1800件件.為了進(jìn)行質(zhì)量為了進(jìn)行質(zhì)量控制，計(jì)劃聘請(qǐng)兩種不同水平的檢驗(yàn)員控制，計(jì)劃聘請(qǐng)兩種不同水平的檢驗(yàn)員.一級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：一級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度速度(sd)25件件/小時(shí)，正確率小時(shí)，正確率98%，計(jì)時(shí)工資，計(jì)時(shí)工資4元元/小時(shí)；二級(jí)小時(shí)；二級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度檢驗(yàn)員的標(biāo)準(zhǔn)為：速度(sd)15件件/小時(shí)，正確率小時(shí)，正確率95%，計(jì)時(shí)，計(jì)時(shí)工資工資3元元/小時(shí)小時(shí).檢驗(yàn)員每錯(cuò)檢一次，工廠要損失檢驗(yàn)員每錯(cuò)檢一次，工廠要損失2元元.為使總檢驗(yàn)為使總

4、檢驗(yàn)費(fèi)用最省，該工廠應(yīng)聘一級(jí)、二級(jí)檢驗(yàn)員各幾名？費(fèi)用最省，該工廠應(yīng)聘一級(jí)、二級(jí)檢驗(yàn)員各幾名？解解 設(shè)需要一級(jí)和二級(jí)檢驗(yàn)員的人數(shù)分別為設(shè)需要一級(jí)和二級(jí)檢驗(yàn)員的人數(shù)分別為x1、x2人人,則應(yīng)付則應(yīng)付(yng f)檢驗(yàn)員的工資為：檢驗(yàn)員的工資為：212124323848xxxx因檢驗(yàn)員錯(cuò)檢而造成(zo chn)的損失為：21211282)%5158%2258(xxxx第4頁(yè)/共45頁(yè)第四頁(yè)，共45頁(yè)。故目標(biāo)故目標(biāo)(mbio)函數(shù)為：函數(shù)為：2121213640)128()2432(minxxxxxxz約束條件為：0, 0180015818002581800158258212121xxxxxx第5頁(yè)/

5、共45頁(yè)第五頁(yè)，共45頁(yè)。線性規(guī)劃線性規(guī)劃(xin xn u hu)模型：模型：213640minxxz12121253459s.t. 150,0 xxxxxx 解答(jid)返 回第6頁(yè)/共45頁(yè)第六頁(yè)，共45頁(yè)。11min,1,2,., .s.t.0,1,2,., .ni iinik kikiucxa xb inxin 目標(biāo)目標(biāo)(mbio)函數(shù)和所有的約束條件都是設(shè)計(jì)變函數(shù)和所有的約束條件都是設(shè)計(jì)變量量的線性函數(shù)的線性函數(shù).min. s.tucxAxbvlbxvub矩矩陣陣形形式式：第7頁(yè)/共45頁(yè)第七頁(yè)，共45頁(yè)。實(shí)際問(wèn)題實(shí)際問(wèn)題(wnt)中中的優(yōu)化模型的優(yōu)化模型T1min(max)(

6、),(,)s.t.( )0,1,2,nizf xxxxg xim或x是決策是決策(juc)變量變量f(x)是目標(biāo)是目標(biāo)(mbio)函數(shù)函數(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ī)劃第8頁(yè)/共45頁(yè)第八頁(yè)，共45頁(yè)。用用MATLAB優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃(xin xn u hu)min z=cX s.t.AXb1. 模型：命令(mng lng)：

7、x=linprog（c, A, b） 2. 模型：min z=cX s.t.AXbbeqXAeq命令(mng lng)：x=linprog（c，A，b，Aeq,beq）注意：若沒(méi)有不等式： 存在，則令A(yù)= ，b= .bAX 第9頁(yè)/共45頁(yè)第九頁(yè)，共45頁(yè)。3. 模型：min z=cX s.t.AXbbeqXAeqVLBXVUB命令(mng lng)：1 x=linprog（c，A，b，Aeq,beq, VLB，VUB） 2 x=linprog（c，A，b，Aeq,beq, VLB，VUB, X0） 注意：1 若沒(méi)有等式約束: , 則令A(yù)eq= , beq= . 2其中X0表示初始點(diǎn) beqX

8、Aeq4. 命令：x,fval=linprog()返回(fnhu)最優(yōu)解及處的目標(biāo)函數(shù)值fval.第10頁(yè)/共45頁(yè)第十頁(yè)，共45頁(yè)。解解 編寫編寫(binxi)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; vub=;x,fval=linprog(c,A,b,Aeq

9、,beq,vlb,vub) To MATLAB (xxgh1)第11頁(yè)/共45頁(yè)第十一頁(yè)，共45頁(yè)。解解: 編寫編寫M文件文件(wnjin)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第12頁(yè)/共45頁(yè)第十二頁(yè)，共45頁(yè)。s.t.Xz8121110913min改寫為：

10、例例3 問(wèn)題問(wèn)題(wnt)一的解答一的解答 問(wèn)題(wnt)第13頁(yè)/共45頁(yè)第十三頁(yè)，共45頁(yè)。編寫編寫(binxi)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)第14頁(yè)/共45頁(yè)第十四頁(yè)，共45頁(yè)。

11、結(jié)果結(jié)果:x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004 即在甲機(jī)床上加工即在甲機(jī)床上加工600個(gè)工件個(gè)工件(gngjin)2,在乙機(jī)床上加在乙機(jī)床上加工工400個(gè)工件個(gè)工件(gngjin)1、500個(gè)工件個(gè)工件(gngjin)3，可在滿，可在滿足條件的情況下使總加工費(fèi)最小為足條件的情況下使總加工費(fèi)最小為13800.第15頁(yè)/共45頁(yè)第十五頁(yè)，共45頁(yè)。例例2 問(wèn)題問(wèn)題(wnt)二的解答二的解答 問(wèn)題(wnt)改寫為：第16頁(yè)/共45頁(yè)第十六頁(yè)，共45頁(yè)。編寫編寫M文件文件xxgh4.m如下：如下：c =

12、 40;36;A=-5 -3;b=-45;Aeq=;beq=;vlb = zeros(2,1);vub=9;15; %調(diào)用調(diào)用(dioyng)linprog函數(shù)：函數(shù)：x,fval = linprog(c,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh4)第17頁(yè)/共45頁(yè)第十七頁(yè)，共45頁(yè)。結(jié)果結(jié)果(ji gu)為：為：x = 9.0000 0.0000fval =360即只需聘用即只需聘用9個(gè)一級(jí)檢驗(yàn)員個(gè)一級(jí)檢驗(yàn)員. 注：本問(wèn)題應(yīng)還有一個(gè)約束條件：注：本問(wèn)題應(yīng)還有一個(gè)約束條件：x1、x2取整取整數(shù)數(shù).故它是一個(gè)整數(shù)線性規(guī)劃問(wèn)題故它是一個(gè)整數(shù)線性規(guī)劃問(wèn)題.這里把它當(dāng)成

13、這里把它當(dāng)成一個(gè)線性規(guī)劃來(lái)解，求得其最優(yōu)解剛好是整數(shù)：一個(gè)線性規(guī)劃來(lái)解，求得其最優(yōu)解剛好是整數(shù)：x1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解，故它就是該整數(shù)規(guī)劃的最優(yōu)解.若若用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用的整數(shù)規(guī)劃應(yīng)用(yngyng)專門的方法求解專門的方法求解.返 回第18頁(yè)/共45頁(yè)第十八頁(yè)，共45頁(yè)。用用LINDO、LINGO優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃(xin xn u hu)第19頁(yè)/共45頁(yè)第十九頁(yè)，共45頁(yè)。 下面我們通過(guò)一

14、個(gè)例題來(lái)說(shuō)明下面我們通過(guò)一個(gè)例題來(lái)說(shuō)明(shumng)LINDO軟件包的使用方法軟件包的使用方法.第20頁(yè)/共45頁(yè)第二十頁(yè)，共45頁(yè)。 LINGO LINDO優(yōu) 化 模 型優(yōu) 化 模 型(mxng)線性規(guī)劃線性規(guī)劃(xin xn u hu)(LP)非線性規(guī)劃非線性規(guī)劃(NLP)二次規(guī)劃二次規(guī)劃(QP)連續(xù)優(yōu)化連續(xù)優(yōu)化整數(shù)規(guī)劃整數(shù)規(guī)劃(IP)第21頁(yè)/共45頁(yè)第二十一頁(yè)，共45頁(yè)。1桶牛奶 3千克A1 12小時(shí) 8小時(shí) 4千克A2 或獲利24元/千克 獲利16元/千克 50桶牛奶桶牛奶(ni ni) 時(shí)間時(shí)間(shjin): 480小時(shí)小時(shí) 至多至多(zhdu)加工加工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ì)劃？ 每天：每天：第22頁(yè)/共45頁(yè)第二十二頁(yè)，共45頁(yè)。x1桶牛奶桶牛奶(ni ni)生產(chǎn)生產(chǎn)A1 x2桶牛奶桶牛奶(ni ni)生產(chǎn)生產(chǎn)A2 獲利獲利(hu l) 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動(dòng)時(shí)間勞動(dòng)時(shí)間 48081221 xx

16、加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 12max7264zxx每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)第23頁(yè)/共45頁(yè)第二十三頁(yè)，共45頁(yè)。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 PRIC

17、ES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶桶牛奶(ni ni)生產(chǎn)生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤(rùn)，利潤(rùn)3360元元. 第24頁(yè)/共45頁(yè)第二十四頁(yè)，共45頁(yè)。 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW

18、 SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000原料原料(yunlio)無(wú)剩余無(wú)剩余時(shí)間時(shí)間(shjin)無(wú)剩余無(wú)剩余加工能力剩余加工能力剩余(shngy)40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 第25頁(yè)/共45頁(yè)第二十五頁(yè)，共45頁(yè)。模型模型(mxng)(mxng)求解求解 reduced cos

19、t值表示值表示當(dāng) 該 非 基 變 量當(dāng) 該 非 基 變 量(binling)增加一增加一個(gè)單位時(shí)（其他非個(gè)單位時(shí)（其他非基變量基變量(binling)保持不變）保持不變）,目標(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.0000

20、00 4) 40.000000 0.000000 NO. ITERATIONS= 2也可理解為：也可理解為：為了使該非基變?yōu)榱耸乖摲腔兞孔兂苫兞?，量變成基變量，目?biāo)函數(shù)中對(duì)應(yīng)目標(biāo)函數(shù)中對(duì)應(yīng)(duyng)系數(shù)應(yīng)系數(shù)應(yīng)增加的量增加的量第26頁(yè)/共45頁(yè)第二十六頁(yè)，共45頁(yè)。 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.00000

21、0 3) 0.000000 2.000000 4) 40.000000 0.000000結(jié)果結(jié)果(ji (ji gu)gu)解釋解釋 最優(yōu)解下最優(yōu)解下“資源資源”增加增加(zngji)1單位時(shí)單位時(shí)“效益效益”的增量的增量 原料增原料增1單位單位(dnwi), 利利潤(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ù)間可有空格(甚至甚至(shnzh)回車回車), 但無(wú)運(yùn)算但無(wú)運(yùn)算符符3.變量名以

22、字母開(kāi)頭，不能超過(guò)變量名以字母開(kāi)頭，不能超過(guò)8個(gè)字符個(gè)字符4.變量名不區(qū)分大小寫（包括變量名不區(qū)分大小寫（包括LINDO中的關(guān)鍵字）中的關(guān)鍵字）5.目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件6.行號(hào)行號(hào)(行名行名)自動(dòng)產(chǎn)生或人為定義自動(dòng)產(chǎn)生或人為定義.行名以行名以“）”結(jié)束結(jié)束7.行中注有行中注有“!”符號(hào)的后面部分為注釋符號(hào)的后面部分為注釋.如如: 8. ! Its Comment.9.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE” 對(duì)模型命名（最多對(duì)模型命名（最多72個(gè)字符），如：個(gè)字符），如：10. TITLE This Mode

23、l is only an Example第30頁(yè)/共45頁(yè)第三十頁(yè)，共45頁(yè)。9.變量不能出現(xiàn)在一個(gè)約束條件的右端變量不能出現(xiàn)在一個(gè)約束條件的右端10. 表達(dá)式中不接受括號(hào)表達(dá)式中不接受括號(hào)“( )”和逗號(hào)和逗號(hào)“,”等任何符號(hào)等任何符號(hào), 例例: 400(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ǔ)句(yj)后用后用“FREE name”將變量將變量name的非負(fù)假定的非負(fù)假定取消取消13. 可在可在 “END

24、”后用后用“SUB” 或或“SLB” 設(shè)定變量設(shè)定變量上下界上下界14. 例如：例如： “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

25、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）第41頁(yè)/共45頁(yè)第四十一頁(yè)，共45頁(yè)。計(jì)算結(jié)果：計(jì)算結(jié)果：第42頁(yè)/共45頁(yè)第四十二頁(yè)，共45頁(yè)。五、五、 結(jié)果結(jié)果(ji gu)分分析析返 回4.4.在在a=0.006a=0.006附近有一個(gè)轉(zhuǎn)折點(diǎn)，在這一點(diǎn)左邊，風(fēng)險(xiǎn)增加很少時(shí)，利潤(rùn)增長(zhǎng)附近有一個(gè)轉(zhuǎn)折點(diǎn)，在這一點(diǎn)左邊，風(fēng)險(xiǎn)增加很少時(shí)，利潤(rùn)增長(zhǎng)(zngzhng)(zngzhng) 很快很快. .在這一點(diǎn)右邊，風(fēng)險(xiǎn)增加很大時(shí)，利潤(rùn)增長(zhǎng)在這一點(diǎn)右邊，風(fēng)險(xiǎn)增加很