數(shù)學(xué)建模最優(yōu)化模型課件ppt

1、最優(yōu)化模型血翹最優(yōu)化方法概述1、最優(yōu)化理論和方法是近二十多年來發(fā)展十分迅 速的一個數(shù)學(xué)分支。2、在數(shù)學(xué)上，最優(yōu)化是一種求極值的方法。3、最優(yōu)化已經(jīng)廣泛的滲透到工程、經(jīng)濟(jì)、電子技 術(shù)等領(lǐng)域。在實際生活當(dāng)中，人們做任何事情，不管是分析問題，還是進(jìn)行決策，都要用一種標(biāo)準(zhǔn)衡量一下是否達(dá)到了最優(yōu)。（比如基金人投資）在各種科學(xué)問題、工程問題、生產(chǎn)管理、社會經(jīng)濟(jì)問題中，人們總是希望在有限的資源條件 下，用盡可能小的代價，獲得最大的收獲。（比如保險）數(shù)學(xué)家對最優(yōu)化問題的研究已經(jīng)有很多年的 歷史。以前解決最優(yōu)化問題的數(shù)學(xué)方法只限于古典 求導(dǎo)方法和變分法（求無約束極值問題），拉格 朗日（lagrange）乘數(shù)法解

2、決等式約束下的條件 極值問題。計算機(jī)技術(shù)的出現(xiàn)，使得數(shù)學(xué)家研究出了許 多最優(yōu)化方法和算法用以解決以前難以解決的問 題。幾個概念最優(yōu)化是從所有可能方案中選擇最合理的一種 以達(dá)到最優(yōu)目標(biāo)的學(xué)科。最優(yōu)方案是達(dá)到最優(yōu)目標(biāo)的方案。最優(yōu)化方法是搜尋最優(yōu)方案的方法。最優(yōu)化理論就是最優(yōu)化方法的理論。經(jīng)典極值問題包括： 無約束極值問題約束條件下的極值問題1、無約束極值問題的數(shù)學(xué)模型min/(x)x *2、約束條件下極值問題的數(shù)學(xué)模型min/(x)s.t. gj(x) < 0, i = 1,h£x) = 0, i = 1.2.n其中，極大值問題可以轉(zhuǎn)化為極小值問題來進(jìn)行求解。如求:max/(x)可

3、以轉(zhuǎn)化為：min-/(x)x1、無約束極值問題的求解例1 ：求函數(shù)y=2x3+3x2-12x+14在區(qū)間-3,4上的最 大值與最小值。解:令f(x)=y=2x3+3x2-12x+14f，(x)=6x2+6x-12=6(x+2)(x-l)解方程f，(x)=o,得到xx= -2, x2=l,又由于f(-3)=23, f(-2)=34, f(l)=7, f(4)=142, 綜上得，函數(shù)f(x)sx=4取得在-3,4±得最大值f(4)=142,在*1處取得在3,4上取得最小值f(l)=7/（為鬲）二一#七f（叫禹）=卅+兀;用matlab解無約束優(yōu)化問題1.元函數(shù)無約束優(yōu)化問題：min /(

4、x) xj <x<x2常用格式如下：(1) x= fminbnd (fun，xl，x2)(2) x= fminbnd (funxlx2 , options)(3) x, fval= fminbnd ()(4) x, fval, exitflag = fminbnd ()(5) x, fval, exitflag, output = fminbnd ()其中等式(3).(4)、(5)的右邊可選用(1)或(2)的等式右邊.函數(shù)fminbnd的算法基于黃金分割法和二次插值法，它要求目標(biāo)函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解.matlab(wlitil)例1求x= 2ea sinx在0

5、vxv8中的最小值與最大值主程序為wlitil.m:f=f2*exp(-x).*sin(x)f;fplot(f,0,8); %作圖語句xminymin=fminbnd (f，0,8) fl=l2*exp(-x).*sin (x)f;xmaxymax=fminbnd (fl, 0,8)運(yùn)行結(jié)果：xmin = 3.9270ymin = -0.0279xmax = 0.7854ymax = 0.6448例2有邊長為3m的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大?解 設(shè)剪去的正方形的邊長為兀，則水槽的容積為：(3-2x)2兀建立無約束優(yōu)化模型為：min y =

6、 (3 - 2x)2兀，0<x <1.5先編寫m文件funo.m如下:function f=funo(x)f=-(3-2*x).a2*x;主程序為wliti2.m:x,fval=fminbnd (1 funo 0,l *5);xmax=x fmax=-fval運(yùn)算結(jié)果為：xmax = 0.50005fmax =2.0000.即剪掉的正方形的邊 長為0.5m時水槽的容積最大，最大容積為2m,2 多元函數(shù)無約束優(yōu)化問題標(biāo)準(zhǔn)型為：min f(x)命令格式為：(1) x= fminunc (funxo )；或x=fminsearch (funxo )(2) x= fminunc (funx

7、o , options)；stx=fminsearch (funxo , options)(3) x, fval= fminunc (.)；或x, fval= fminsearch (.)(4) x, fval, exitflag = fminunc (.)；或x, fval, exitflag = fminsearch(5) x, fval, exitflag, output = fminunc (.)；或x, fval, exitflag, output = fminsearch (.)例用fminsearch函數(shù)求解輸入命令：f=,100*(x(2)-x(l)a2)a2+(l-x(l)a

8、2,;x9fval9exitflag9output=fminsearch(f,-1.2 2)運(yùn)行結(jié)果:x =1.00001.0000fval =1.9151e-010 exitflag = 1output=iterations: 10 funccount: 202algorthm: fnelder-mead simplex direct search有約束最優(yōu)化最優(yōu)化方法分類（一）線性最優(yōu)化：目標(biāo)函數(shù)和約束條件都是線 性的則稱為線性最優(yōu)化。非線性最優(yōu)化：目標(biāo)函數(shù)和約束條件如果含有非線性的，則稱為非線性最優(yōu)化。（二）靜態(tài)最優(yōu)化：如果可能的方案與時間無關(guān), 則是靜態(tài)最優(yōu)化問題。動態(tài)最優(yōu)化：如果可能

9、的方案與時間有關(guān)， 則是動態(tài)最優(yōu)化問題有約束最優(yōu)化問題的數(shù)學(xué)建模有約束最優(yōu)化模型一般具有以下形式:min /(x)max /(%)“或“s.ts.t其中f(x)為目標(biāo)函數(shù)，省略號表示約束式子，可以是 等式約束，也可以是不等式約束。最優(yōu)化方法主要內(nèi)容根據(jù)目標(biāo)函數(shù)，約束條件的特點將最優(yōu)化方法包含的主要內(nèi)容大致如下劃分:線性規(guī)劃整數(shù)規(guī)劃非線性規(guī)劃動態(tài)規(guī)劃多目標(biāo)規(guī)劃對策論兩個引例問題一：某工廠在計劃期內(nèi)要安排生產(chǎn)i、ii兩種產(chǎn)品， 已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及a、b兩種原材料的 消耗，如下表所示i1原材料a4原材料b0viiu 口 k j016kg412kg該工廠每生產(chǎn)一件產(chǎn)品i可獲利2元，每生產(chǎn)

10、一件產(chǎn)品 ii可獲利3元。問應(yīng)如何安排計劃使該工廠獲利最多？解：該工廠生產(chǎn)產(chǎn)品i xl件，生產(chǎn)產(chǎn)品ii x2件, 我們可建立如下數(shù)學(xué)模型：max z = 2x + 3x9<16sete vx1 + 2x2 < 8 4xl4x2 < 12xi ,x2 > 0問題二：某廠每日8小時的產(chǎn)量不低于1800件為了進(jìn)行質(zhì)量 控制，計劃聘請兩種不同水平的檢驗員一級檢驗員的標(biāo)準(zhǔn)為: 速度25件/小時，正確率98%,計時工資4元/小時；二級檢驗員 的標(biāo)準(zhǔn)為：速度15件/小時，正確率95%,計時工資3元/小時.檢 驗員每錯檢一次，工廠要損失2元為使總檢驗費用最省，該工 廠應(yīng)聘一級、二級檢驗

11、員各幾名?解 設(shè)需要一級和二級檢驗員的人數(shù)分別為x】、x2人, 則應(yīng)付檢驗員的工資為：8 x 4 x xj + 8 x 3 x x2 = 32x, + 24x2因檢驗員錯檢而造成的損失為：(8x25x2%x 兀+ 8 x 15 x 5% x x2) x 2 = 8 +12x2故目標(biāo)函數(shù)為:min z 二(32x, + 24x2) + (8西 +12 兀)二 40西 + 36x2約束條件為:8x 25xx1 +8x15xx2 >1800xpx2 > 0運(yùn)用最優(yōu)化方法解決最優(yōu)化問題的一般 方法步驟如下：前期分析：分析問題，找出要解決的目標(biāo)，約束條件, 并確立最優(yōu)化的目標(biāo)。定義變量，建立

12、最優(yōu)化問題的數(shù)學(xué)模型，列出目標(biāo)函數(shù)和約束條件。 針對建立的模型，選擇合適的求解方法或數(shù)學(xué)軟件。 編寫程序，利用計算機(jī)求解。 對結(jié)果進(jìn)行分析，討論諸如：結(jié)果的合理性、正確性,算法的收斂性，模型的適用性和通用性，算法效率與 誤差等。線性規(guī)劃某豆腐店用黃豆制作兩種不同口感的豆腐出售。 制作口感較鮮嫩的豆腐每千克需要0. 3千克一級 黃豆及0. 5千克二級黃豆，售價10元；制作口感 較厚實的豆腐每千克需要0. 4千克一級黃豆及0. 2 千克二級黃豆，售價5元。現(xiàn)小店購入9千克一級 黃豆和8千克二級黃豆。問：應(yīng)如何安排制作計劃才能獲得最大收益。、問題前期分析 該問題是在不超出制作兩種不同口感豆腐所需黃豆

13、總量條件下合理安排制作計劃，使得售出 各種豆腐能獲得最大收益。二、模型假設(shè)1.假設(shè)制作的豆腐能全部售出。2假設(shè)豆腐售價無波動。變量假設(shè):設(shè)計劃制作口感鮮嫩和厚實的豆腐各燈千克和x2千克，可獲得收益r元。目標(biāo)函數(shù)：獲得的總收益最大?？偸找婵杀硎緸?r = 10xj +5x2受一級黃豆數(shù)量限制：0.3丙+0.4x2 <9受二級黃豆數(shù)量限制：0站+0.2x2<8綜上分析，得到該問題的線性規(guī)劃模型max r = 10 +5x203x + 0.4x2 <9set.下0.5x +0.2x? <81乙l兀,兀2 n °用matlab編程求解程序如下:x，fval,exitf

14、lagoutput二 linprog(f，a,b)f=-10 5;a = 0.3 0.4;0.5 0.2;b = 9;8;x.fval.exitflag,output二 linprog(f,a,b)10.000015.0000fval =-175.0000用yalmip編程求解程序如下: x=sdpvar(l,2);c=10 5;a=0.3 0.4;0.5 0.2;b=9 8; f=c*x；f=set(o<=x<=inf);ans =175ans =1015f=f+set(a*x'<=b,); solvesdp(f,-f) double(f) double(x)線性規(guī)

15、劃設(shè)某工廠有甲、乙、丙、丁四個車間，生產(chǎn)a、b、c、d、e、f六種產(chǎn)品。根據(jù)機(jī)床性能 和以前的生產(chǎn)情況，得知每單位產(chǎn)品所需車間的 工作小時數(shù)、每個車間在一個季度工作小時的上 限以及單位產(chǎn)品的利潤，如下表所示（例如，生產(chǎn) 一個單位的a產(chǎn)品，需要甲、乙、丙三個車間分別工作1 小時、2小時和4小時） 問：每種產(chǎn)品各應(yīng)該每季度生產(chǎn)多少，才能使這 個工廠每季度生產(chǎn)利潤達(dá)到最大。生產(chǎn)單位每個車間產(chǎn)品所需nt7個季度/kih 1車間的工t作小時丄 1 rjwj作小時數(shù)的上限甲111三3三三2三三3三500乙255500quu丙=4 =2 i二 5 二500丁13500利潤4.02.45.55.04.5.5（

16、百兀）這是一個典型的最優(yōu)化問題，屬線性規(guī)劃。假設(shè)：產(chǎn)品合格且能及時銷售出去；工作無等待情況等 變量說明：xj：第j種產(chǎn)品的生產(chǎn)量(j=l,2,6)aij；第i車間生產(chǎn)單位第j種產(chǎn)品所需工作小時數(shù)(i=l,2,3,4;j=l,2,6)山：第i車間的最大工作上限cj：第j種產(chǎn)品的單位利潤則：cjxj為第j種產(chǎn)品的利潤總額；坷內(nèi)表示第i車間生產(chǎn)第j種產(chǎn)品所花時間總數(shù)；于是，我們可建立如下數(shù)學(xué)模型:6max z = cjxjj=i工 口汨 <bti = 1,2,3,4set. j丿 th0<x：<一乞一，且為整數(shù) j = 1,2,34,5,6 即氣切l(wèi)<r<4計算結(jié)果:z

17、（百兀）e xie x2 ze x3 ze x4 z-z x5 zx61320e 0 e060e 40e 100 e40運(yùn)輸問題要從甲城調(diào)出蔬菜2000噸，從乙城調(diào)出蔬菜2500噸,從丙地調(diào)出3000噸，分別供應(yīng)a地2000噸，b地2300噸、c地1800噸、d地1400噸，已知每噸運(yùn)費如下表:問：如何調(diào)撥才能使運(yùn)費最省?假設(shè)： 假設(shè)題目中所給運(yùn)費已考慮各地間公里數(shù); 只考慮運(yùn)量和運(yùn)費，不考慮車輛調(diào)撥等其它相關(guān)因素 不考慮車輛返空的費用(或：所給運(yùn)費已包含車輛返 空的費用)變量說明:昨:從第i城運(yùn)往第j地的單位運(yùn)費(i=l,2,3;j=l,2,3,4 ) 叩從第i城調(diào)出的蔬菜總量勺:第j地所需

18、蔬菜總量可以建立如下模型:4工 xij = $(i = 1，2,3)3s.t. v 工 xq =cj(丿 = 123,4)i=(i = l,2,3;/ = l,2,3,4)v°x. < min(勺,c )jj整數(shù)規(guī)劃最優(yōu)化問題中的所有變量均為整數(shù)時，這類 問題稱為整數(shù)規(guī)劃問題。如果線性規(guī)劃中的所有變量均為整數(shù)時，稱 這類問題為線性整數(shù)規(guī)劃問題。整數(shù)規(guī)劃可分為線性整數(shù)規(guī)劃和非線性整數(shù) 規(guī)劃，以及混合整數(shù)規(guī)劃等。a如果決策變量的取值要么為0,要么為1,則 這樣的規(guī)劃問題稱為01規(guī)劃。例1某鋼廠兩個煉鋼爐同時各用一種方法煉鋼。 第一種煉法每爐用a小時，第二種用b小時（包 括清爐時間）

19、。假定這兩種煉法，每爐出鋼都是 k公斤，而煉1公斤鋼的平均燃料費第一法為m元, 第二法為ii元。若要求在c小時內(nèi)煉鋼公斤數(shù)不少 于d,試列出燃料費最省的兩種方法的分配方案 的數(shù)學(xué)模型。設(shè)用第_種煉法煉鋼心爐，第二種煉鋼無2爐max 乙= k(mx+ny)ax <cbx2 < c kg +x2) > d xpx2 >0且為整數(shù)引例2 資源分配問題:1!某個中型的百貨商場要求售貨人員每周工作5天，連續(xù)休息2天，工資200元/周，已知對售貨人 員的需求經(jīng)過統(tǒng)計分析如下表，問如何安排可使 配備銷售人員的總費用最少？設(shè)決策變量如上，可建立如下模型:min z = 200(% +

20、x? +x3+x4+ x5+x6+xy)x9 + x3 + x4 + x5 + x6 > 18x3 + x4+x5+ x6 + x7 > 15x4+x5+ x6 + xy +> 12s.t.<x5 + x6 + x7 + %, + x2 > 16x6 + x7 + xj + x9 + x3 > 19x7 + xj + x9 + x3 + x4 > 14+ x9 + x3 + x4 + x5 > 14xpx2,x3,x4,x5,x6,x7 >0且為整數(shù)非線性規(guī)劃非線性規(guī)劃問題的一般數(shù)學(xué)模型：min fx)s.t. g.t (x) < 0

21、,z = 1,2, ,m,hj(x) = 0,j = l, 2,/.其中，xue”，/(x)為目標(biāo)函數(shù)， g©),%(x)為約束函數(shù)，這些函數(shù)中至少有 一個是諾線性函數(shù)。應(yīng)用實例：供應(yīng)與選址某公司有6個建筑工地要開工，每個工地的位置(用平面坐標(biāo)系 a, b表示，距離單位：km)及水泥日用量d(t)由下表給出.目前有 兩個臨時料場位于a(5，l), b(2,7),日儲量各有20t.假設(shè)從料場到 工地之間均有直線道路相連(1)試制定每天的供應(yīng)計劃，即從a, b兩料場分別向各工地運(yùn)送多少水泥，可使總的噸千米數(shù)最小.(2)為了進(jìn)一步減少噸千米數(shù)，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為20t,問應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大?工地位置s b)及水泥日用量d1234561.258.750.55.757.25ab1n 7s4 7ss6 s7d354711（-）建立模型記工地的位置為（, bj）,水泥日用量為dj, i=l,.,6;料場