數(shù)學(xué)規(guī)劃模型實(shí)驗(yàn)

1、1/22數(shù)學(xué)規(guī)劃模型實(shí)驗(yàn)數(shù)學(xué)規(guī)劃模型實(shí)驗(yàn) 數(shù)學(xué)教研組數(shù)學(xué)教研組 盧鵬盧鵬 2015.7.23 2/22優(yōu)化問題及其一般模型： 引引 言言 優(yōu)化問題是人們在工程技術(shù)、經(jīng)濟(jì)管理和科學(xué)研究等領(lǐng)域中最常遇到的問題之一。例如：l 設(shè)計師要在滿足強(qiáng)度要求等條件下選擇材料的尺寸， 使 結(jié)構(gòu)總重量最輕；l 公司經(jīng)理要根據(jù)生產(chǎn)成本和市場需求確定產(chǎn)品價格，使所獲 利潤最高；l 調(diào)度人員要在滿足物質(zhì)需求和裝載條件下安排從各供應(yīng)點(diǎn) 到需求點(diǎn)的運(yùn)量和路線，使運(yùn)輸總費(fèi)用最低；l 投資者要選擇一些股票,債券下注,使收益最大,而風(fēng)險最小l 3/22一般地，優(yōu)化模型可以表述下： min( ). .( )01 2izf xs t

2、g xim , , = = , , , , , 這是一個多元函數(shù)的條件極值問題，其中這是一個多元函數(shù)的條件極值問題，其中 . 許多實(shí)際問題歸結(jié)出的這種優(yōu)化模型，若決策變量個數(shù)許多實(shí)際問題歸結(jié)出的這種優(yōu)化模型，若決策變量個數(shù)較少可用較少可用微分法微分法求解求解; ;但是其決策變量個數(shù)但是其決策變量個數(shù) n n 和約束條件個和約束條件個數(shù)數(shù) m m 較大，并且最優(yōu)解往往在可行域的邊界上取得，較大，并且最優(yōu)解往往在可行域的邊界上取得，數(shù)學(xué)規(guī)數(shù)學(xué)規(guī)劃劃就是解決這類問題的有效方法。就是解決這類問題的有效方法。 12,nxxxx 4/22數(shù)學(xué)規(guī)劃模型分類數(shù)學(xué)規(guī)劃模型分類： “數(shù)學(xué)規(guī)劃是運(yùn)籌學(xué)和管理科學(xué)中應(yīng)

3、用及其數(shù)學(xué)規(guī)劃是運(yùn)籌學(xué)和管理科學(xué)中應(yīng)用及其廣泛的分支。數(shù)學(xué)規(guī)劃包括廣泛的分支。數(shù)學(xué)規(guī)劃包括線性規(guī)劃線性規(guī)劃、非線性規(guī)非線性規(guī)劃劃、整數(shù)規(guī)劃整數(shù)規(guī)劃、幾何規(guī)劃、多目標(biāo)規(guī)劃等，用數(shù)、幾何規(guī)劃、多目標(biāo)規(guī)劃等，用數(shù)學(xué)規(guī)劃方法解決實(shí)際問題，就要將實(shí)際問題經(jīng)過學(xué)規(guī)劃方法解決實(shí)際問題，就要將實(shí)際問題經(jīng)過抽象、簡化、假設(shè)，確定變量與參數(shù)，建立適當(dāng)抽象、簡化、假設(shè)，確定變量與參數(shù)，建立適當(dāng)層次上的數(shù)學(xué)模型，并求解。層次上的數(shù)學(xué)模型，并求解。 5/22建立數(shù)學(xué)規(guī)劃模型的步驟建立數(shù)學(xué)規(guī)劃模型的步驟: :Step 1. Step 1. 尋求決策，即回答什么？必須清楚，無歧義。尋求決策，即回答什么？必須清楚，無歧義。

4、閱讀完題目的第一步不是尋找答案或者解法，而是閱讀完題目的第一步不是尋找答案或者解法，而是Step 2. Step 2. 確定決策變量確定決策變量 第一來源：第一來源：Step 1Step 1的結(jié)果，用變量固定需要回答的決策的結(jié)果，用變量固定需要回答的決策 第二來源：由決策導(dǎo)出的變量（具有派生結(jié)構(gòu)）第二來源：由決策導(dǎo)出的變量（具有派生結(jié)構(gòu)） 其它來源：輔助變量（聯(lián)合完成更清楚的回答）其它來源：輔助變量（聯(lián)合完成更清楚的回答）Step 3. Step 3. 確定優(yōu)化目標(biāo)確定優(yōu)化目標(biāo) 用決策變量表示的利潤、成本等。用決策變量表示的利潤、成本等。Step 4. Step 4. 尋找約束條件尋找約束條件

5、 決策變量之間、決策變量與常量之間的聯(lián)系。決策變量之間、決策變量與常量之間的聯(lián)系。 第一來源：需求；第一來源：需求； 第二來源：供給；第二來源：供給； 其它來源：輔助以及常識。其它來源：輔助以及常識。Step 5. Step 5. 構(gòu)成數(shù)學(xué)模型構(gòu)成數(shù)學(xué)模型 將目標(biāo)以及約束放在一起，寫成數(shù)學(xué)表達(dá)式。將目標(biāo)以及約束放在一起，寫成數(shù)學(xué)表達(dá)式。 6/22目目 錄錄 線性規(guī)劃線性規(guī)劃非線性規(guī)劃非線性規(guī)劃二次規(guī)劃二次規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃7/22例例1：加工奶制品的生產(chǎn)計劃：加工奶制品的生產(chǎn)計劃 一奶制品加工廠用牛奶生產(chǎn)一奶制品加工廠用牛奶生產(chǎn)A1，A2兩種奶制兩種奶制品，一桶牛奶可以在設(shè)備甲上用品，一桶牛

6、奶可以在設(shè)備甲上用12小時加工成小時加工成3公公斤斤A1，或者在設(shè)備乙上用，或者在設(shè)備乙上用8小時加工成小時加工成4公斤公斤A2。根。根據(jù)市場需求，生產(chǎn)的據(jù)市場需求，生產(chǎn)的A1、A2全部能夠售出，且每公全部能夠售出，且每公斤斤A1獲利獲利24元，每公斤元，每公斤A2獲利獲利16元?，F(xiàn)在加工廠每元。現(xiàn)在加工廠每天能夠得到天能夠得到50桶牛奶的供應(yīng)，每天正式工人總的勞桶牛奶的供應(yīng)，每天正式工人總的勞動時間為動時間為480小時，并且設(shè)備甲每天至多能加工小時，并且設(shè)備甲每天至多能加工100公斤公斤A1，設(shè)備乙的加工能力沒有限制。試為該廠制，設(shè)備乙的加工能力沒有限制。試為該廠制定一個生產(chǎn)計劃，使每天獲利

7、最大定一個生產(chǎn)計劃，使每天獲利最大?8/22每每天天5050桶牛奶桶牛奶 時間時間480480小時小時 至多加工至多加工100100公斤公斤A A1 1 制訂生產(chǎn)計劃，使每天獲利最大制訂生產(chǎn)計劃，使每天獲利最大 1 1桶桶牛奶牛奶 3 3公斤公斤A A1 1 1212小時小時 8 8小時小時 4 4公斤公斤A A2 2 或或獲利獲利2424元元/ /公斤公斤 獲利獲利1616元元/ /公斤公斤 問問 題題 分分 析析9/22引入決策變量引入決策變量 x1 桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 ，x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2（每天）（每天）目標(biāo)函數(shù)（每天獲利）目標(biāo)函數(shù)（每天獲利） 生產(chǎn)生產(chǎn)A1獲利：獲利：

8、243x1 生產(chǎn)生產(chǎn)A2獲利：獲利： 164x2 每天獲利總額：每天獲利總額：z=72x1+64x2 約束條件約束條件 原料供應(yīng)：原料供應(yīng)： x1+x250 勞動時間：勞動時間： 12x1+8x2480 加工能力：加工能力： 3x1100 非負(fù)約束：非負(fù)約束： x1 , x2 0模型構(gòu)成：模型構(gòu)成：10/22線性規(guī)劃數(shù)學(xué)模型：線性規(guī)劃數(shù)學(xué)模型：121212112max726450128480. .31000,0fxxxxxxs txxx 11/22線性規(guī)劃求解線性規(guī)劃求解標(biāo)準(zhǔn)形式：標(biāo)準(zhǔn)形式： min . . , , .Tfcxs tA xbAeq xbeqlbxub其中：其中： , , ,c

9、x b beq lb ub均為列向量，均為列向量， ,A Aeq為矩陣。為矩陣。 調(diào)用格式：調(diào)用格式：x,fval=linprog(c,A,b,Aeq,beq,lb,ub,options) 其中：其中：x給出極小點(diǎn)，給出極小點(diǎn)，fval給出目標(biāo)函數(shù)極小值，給出目標(biāo)函數(shù)極小值， options是控制參數(shù)，可用是控制參數(shù)，可用help查詢。查詢。12/22Matlab程序如下：程序如下： c=-72,64;A=1,1;12,8;3,0;b=50;480;100;Ib=0;0;ub=1e+10*1;1;x,fval=linprog(c,A,b, , ,lb,ub) 結(jié)果如下：結(jié)果如下： x=20;3

10、0 fval=-336013/22例例2 2：求解線性規(guī)劃問題：求解線性規(guī)劃問題123123123123max2357. . 2510,0zxxxxxxs txxxxxx Matlab程序如下：程序如下： c=2;3;-5; A =-2,5,-1; b=-10; Aeq=1,1,1; beq=7; lb=0;0;0; x,fval=linprog(c,A,b,Aeq,beq,lb) 14/22例例3 3：求解非線性規(guī)劃問題：求解非線性規(guī)劃問題2212121221212min25(1)0. .236fxxx xxxxxs txx 15/22非線性規(guī)劃求解非線性規(guī)劃求解標(biāo)準(zhǔn)形式：標(biāo)準(zhǔn)形式： min

11、 ( ),. .( )0, ( )0, . f xA xbAeq xbeqs tC xCeq xlbxub 其中：其中： 調(diào)用格式：調(diào)用格式：x,fval,h=fmincon(f,x0,A,b,Aeq,beq,lb,ub,nonlcon) 其中：其中： nonlcon是非線性約束函數(shù)，是非線性約束函數(shù)，x0是迭代初始點(diǎn)。是迭代初始點(diǎn)。( )0C x 和和 ( )0Ceq x 是非線性約束。是非線性約束。 16/22Matlab程序如下：程序如下： 建立非線性約束函數(shù)的建立非線性約束函數(shù)的m文件文件lpnon.mfunction c,ceq=lpcon(x)c=(x(1)-1)2-x(2);Ce

12、q= ;建立目標(biāo)函數(shù)的建立目標(biāo)函數(shù)的m文件文件fun.mfunction f=fun(x)f=x(1)2+x(2)2-x(1)*x(2)-2*x(1)-5*x(2);在命令窗口中輸入在命令窗口中輸入x0=0;1; A=-2 3; b=6;Aeq= ; beq= ; lb= ; ub= ;x,fval,h=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,lpcon)結(jié)果：結(jié)果： x=3;4, fval=-13, h=1 17/22例例4 4：求解二次規(guī)劃問題：求解二次規(guī)劃問題221212121212121min2622. .2223fxxx xxxxxs txxxx 18/22

13、二次規(guī)劃求解二次規(guī)劃求解標(biāo)準(zhǔn)形式：標(biāo)準(zhǔn)形式： 1min 2, . .,. TTx Hxc xA xbs tAeq xbeqlbxub 其中：其中：H是實(shí)對稱矩陣。是實(shí)對稱矩陣。調(diào)用格式：調(diào)用格式：x,fval=quadprog(H,c,A,b,Aeq,beq,lb,ub,x0) 19/22Matlab程序如下：程序如下： H=1,-1;-1,2;c=-2;-6;A=1,1;-1,2;2,1; b=2;2;3;Aeq= ; beq= ;lb=zeros(2,1); ub= ;x,fval=quadprog(H,c,A,b,Aeq,beq,lb,ub)結(jié)果：結(jié)果： x=0.6667; 1.3333

14、, fval=-8.222220/22例例5 5：求解整數(shù)規(guī)劃問題：求解整數(shù)規(guī)劃問題2222212345123451234512345123345max3428232400226800. . 262005200099,1,2,3,4,5iifxxxxxxxxxxxxxxxxxxxxs txxxxxxxxZ i ，21/22整數(shù)規(guī)劃求解整數(shù)規(guī)劃求解-隨機(jī)投點(diǎn)法隨機(jī)投點(diǎn)法編寫目標(biāo)函數(shù)和約束條件的編寫目標(biāo)函數(shù)和約束條件的m文件：文件： function f,g=mengte(x) f=x(1)2+x(2)2+3*x(3)2+ 4*x(4)2+2*x(5)2- 8*x(1)-2*x(2)-3*x(3)-x(4)-2*x(5); g(1)=sum(x)-400; g(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800; g(3)=2*x(1)+x(2)+6*x(3)-200; g(4)=x(3)+x(4)+5*x(5)-200;22/2