數(shù)學建模講座之七-最優(yōu)化模型課件

最優(yōu)化方法概述1、最優(yōu)化理論和方法是近二十多年來發(fā)展十分迅速的一個數(shù)學分支。2、在數(shù)學上，最優(yōu)化是一種求極值的方法。3、最優(yōu)化已經(jīng)廣泛的滲透到工程、經(jīng)濟、電子技術(shù)等領(lǐng)域。9/27/2023數(shù)學建模最優(yōu)化方法概述1、最優(yōu)化理論和方法是近二十多年來發(fā)展十分迅1在實際生活當中，人們做任何事情，不管是分析問題，還是進行決策，都要用一種標準衡量一下是否達到了最優(yōu)。（比如基金人投資）在各種科學問題、工程問題、生產(chǎn)管理、社會經(jīng)濟問題中，人們總是希望在有限的資源條件下，用盡可能小的代價，獲得最大的收獲。（比如保險）

9/27/2023數(shù)學建模在實際生活當中，人們做任何事情，不管是分析問題，還是進行決策2數(shù)學家對最優(yōu)化問題的研究已經(jīng)有很多年的歷史。以前解決最優(yōu)化問題的數(shù)學方法只限于古典求導方法和變分法（求無約束極值問題），拉格朗日（Lagrange）乘數(shù)法解決等式約束下的條件極值問題。計算機技術(shù)的出現(xiàn)，使得數(shù)學家研究出了許多最優(yōu)化方法和算法用以解決以前難以解決的問題。9/27/2023數(shù)學建模數(shù)學家對最優(yōu)化問題的研究已經(jīng)有很多年的歷史。8/63幾個概念最優(yōu)化是從所有可能方案中選擇最合理的一種以達到最優(yōu)目標的學科。最優(yōu)方案是達到最優(yōu)目標的方案。最優(yōu)化方法是搜尋最優(yōu)方案的方法。最優(yōu)化理論就是最優(yōu)化方法的理論。9/27/2023數(shù)學建模幾個概念最優(yōu)化是從所有可能方案中選擇最合理的一種以達到最優(yōu)目4經(jīng)典極值問題包括：①無約束極值問題②約束條件下的極值問題9/27/2023數(shù)學建模經(jīng)典極值問題包括：8/6/2023數(shù)學建模51、無約束極值問題的數(shù)學模型2、約束條件下極值問題的數(shù)學模型其中，極大值問題可以轉(zhuǎn)化為極小值問題來進行求解。如求：可以轉(zhuǎn)化為：9/27/2023數(shù)學建模1、無約束極值問題的數(shù)學模型2、約束條件下極值問題的數(shù)學模61、無約束極值問題的求解例1：求函數(shù)y=2x3+3x2-12x+14在區(qū)間[-3,4]上的最大值與最小值。解：令f(x)=y=2x3+3x2-12x+14 f’(x)=6x2+6x-12=6(x+2)(x-1) 解方程f’(x)=0，得到x1=-2，x2=1，又 由于f(-3)=23，f(-2)=34，f(1)=7，f(4)=142，綜上得，函數(shù)f(x)在x=4取得在[-3,4]上得最大值f(4)=142，在x=1處取得在[-3,4]上取得最小值f(1)=79/27/2023數(shù)學建模1、無約束極值問題的求解例1：求函數(shù)y=2x3+3x2-179/27/2023數(shù)學建模8/6/2023數(shù)學建模8用MATLAB解無約束優(yōu)化問題其中等式（3）、（4）、（5）的右邊可選用（1）或（2）的等式右邊.函數(shù)fminbnd的算法基于黃金分割法和二次插值法，它要求目標函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解.常用格式如下：（1）x=fminbnd(fun,x1,x2)（2）x=fminbnd(fun,x1,x2，options)（3）[x，fval]=fminbnd（…）（4）[x，fval，exitflag]=fminbnd（…）（5）[x，fval，exitflag，output]=fminbnd（…）9/27/2023數(shù)學建模用MATLAB解無約束優(yōu)化問題其中等式（3）、（49MATLAB(wliti1)主程序為wliti1.m:f='2*exp(-x).*sin(x)';fplot(f,[0,8]);%作圖語句[xmin,ymin]=fminbnd(f,0,8)f1='-2*exp(-x).*sin

(x)';[xmax,ymax]=fminbnd(f1,0,8)9/27/2023數(shù)學建模MATLAB(wliti1)主程序為wliti1.10例2有邊長為3m的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？解先編寫M文件fun0.m如下:function

f=fun0(x)f=-(3-2*x).^2*x;主程序為wliti2.m:[x,fval]=fminbnd('fun0',0,1.5);xmax=xfmax=-fval運算結(jié)果為:xmax=0.5000,fmax=2.0000.即剪掉的正方形的邊長為0.5m時水槽的容積最大,最大容積為2m3.MATLAB(wliti2)9/27/2023數(shù)學建模例2有邊長為3m的正方形鐵板，在四個角剪去相等的正方形以11命令格式為:（1）x=fminunc（fun,X0）；或x=fminsearch（fun,X0）（2）x=fminunc（fun,X0，options）；或x=fminsearch（fun,X0，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（...）2.多元函數(shù)無約束優(yōu)化問題標準型為：min9/27/2023數(shù)學建模命令格式為:2.多元函數(shù)無約束優(yōu)化問題標準型12例用fminsearch函數(shù)求解輸入命令:

f='100*(x(2)-x(1)^2)^2+(1-x(1))^2';[x,fval,exitflag,output]=fminsearch(f,[-1.22])運行結(jié)果:

x=1.00001.0000fval=1.9151e-010exitflag=1output=iterations:108funcCount:202algorthm:'Nelder-Meadsimplexdirectsearch

'9/27/2023數(shù)學建模例用fminsearch函數(shù)求解輸入命令:運行結(jié)果:8/613有約束最優(yōu)化最優(yōu)化方法分類（一）線性最優(yōu)化：目標函數(shù)和約束條件都是線性的則稱為線性最優(yōu)化。

非線性最優(yōu)化：目標函數(shù)和約束條件如果含有非線性的，則稱為非線性最優(yōu)化。

（二）靜態(tài)最優(yōu)化：如果可能的方案與時間無關(guān)，則是靜態(tài)最優(yōu)化問題。

動態(tài)最優(yōu)化：如果可能的方案與時間有關(guān)，則是動態(tài)最優(yōu)化問題9/27/2023數(shù)學建模有約束最優(yōu)化8/6/2023數(shù)學建模14有約束最優(yōu)化問題的數(shù)學建模有約束最優(yōu)化模型一般具有以下形式：或其中f(x)為目標函數(shù)，省略號表示約束式子，可以是等式約束，也可以是不等式約束。9/27/2023數(shù)學建模有約束最優(yōu)化問題的數(shù)學建模有約束最優(yōu)化模型一般具有以下形式15根據(jù)目標函數(shù)，約束條件的特點將最優(yōu)化方法包含的主要內(nèi)容大致如下劃分：線性規(guī)劃整數(shù)規(guī)劃非線性規(guī)劃動態(tài)規(guī)劃多目標規(guī)劃對策論最優(yōu)化方法主要內(nèi)容9/27/2023數(shù)學建模根據(jù)目標函數(shù)，約束條件的特點將最優(yōu)化方法包含16兩個引例問題一：某工廠在計劃期內(nèi)要安排生產(chǎn)I、II兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及A、B兩種原材料的消耗，如下表所示12kg40原材料B16kg04原材料A8臺時21設備III該工廠每生產(chǎn)一件產(chǎn)品I可獲利2元，每生產(chǎn)一件產(chǎn)品II可獲利3元。問應如何安排計劃使該工廠獲利最多？9/27/2023數(shù)學建模兩個引例問題一：某工廠在計劃期內(nèi)要安排生產(chǎn)I、II兩種產(chǎn)品，17解：該工廠生產(chǎn)產(chǎn)品Ix1件，生產(chǎn)產(chǎn)品IIx2件，我們可建立如下數(shù)學模型：s.t.9/27/2023數(shù)學建模解：該工廠生產(chǎn)產(chǎn)品Ix1件，生產(chǎn)產(chǎn)品IIx2件，我們18問題二：某廠每日8小時的產(chǎn)量不低于1800件.為了進行質(zhì)量控制，計劃聘請兩種不同水平的檢驗員.一級檢驗員的標準為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標準為：速度15件/小時，正確率95%，計時工資3元/小時.檢驗員每錯檢一次，工廠要損失2元.為使總檢驗費用最省，該工廠應聘一級、二級檢驗員各幾名？解設需要一級和二級檢驗員的人數(shù)分別為x1、x2人,則應付檢驗員的工資為：因檢驗員錯檢而造成的損失為：9/27/2023數(shù)學建模問題二：某廠每日8小時的產(chǎn)量不低于1800件.為了進行19故目標函數(shù)為：約束條件為：9/27/2023數(shù)學建模故目標函數(shù)為：約束條件為：8/6/2023數(shù)學建模20

運用最優(yōu)化方法解決最優(yōu)化問題的一般方法步驟如下：①前期分析：分析問題，找出要解決的目標，約束條件，并確立最優(yōu)化的目標。②定義變量，建立最優(yōu)化問題的數(shù)學模型，列出目標函數(shù)和約束條件。③針對建立的模型，選擇合適的求解方法或數(shù)學軟件。④編寫程序，利用計算機求解。⑤對結(jié)果進行分析，討論諸如：結(jié)果的合理性、正確性，算法的收斂性，模型的適用性和通用性，算法效率與誤差等。9/27/2023數(shù)學建模運用最優(yōu)化方法解決最優(yōu)化問題的一般方法步驟如21線性規(guī)劃某豆腐店用黃豆制作兩種不同口感的豆腐出售。制作口感較鮮嫩的豆腐每千克需要0.3千克一級黃豆及0.5千克二級黃豆，售價10元；制作口感較厚實的豆腐每千克需要0.4千克一級黃豆及0.2千克二級黃豆，售價5元。現(xiàn)小店購入9千克一級黃豆和8千克二級黃豆。問：應如何安排制作計劃才能獲得最大收益。9/27/2023數(shù)學建模線性規(guī)劃某豆腐店用黃豆制作兩種不同口22一、問題前期分析該問題是在不超出制作兩種不同口感豆腐所需黃豆總量條件下合理安排制作計劃，使得售出各種豆腐能獲得最大收益。二、模型假設1．假設制作的豆腐能全部售出。2．假設豆腐售價無波動。9/27/2023數(shù)學建模一、問題前期分析8/6/2023數(shù)學建模23變量假設：設計劃制作口感鮮嫩和厚實的豆腐各x1千克和x2千克，可獲得收益R元。目標函數(shù)：獲得的總收益最大?？偸找婵杀硎緸椋菏芤患夵S豆數(shù)量限制：受二級黃豆數(shù)量限制：9/27/2023數(shù)學建模變量假設：目標函數(shù)：獲得的總收益最大?？偸找婵杀硎緸椋菏?4綜上分析，得到該問題的線性規(guī)劃模型s.t.9/27/2023數(shù)學建模綜上分析，得到該問題的線性規(guī)劃模型s.t.8/6/202325用Matlab編程求解程序如下：[X,FVAL,EXITFLAG,OUTPUT]=LINPROG(f,A,b)

f=-[105];A=[0.30.4;0.50.2];B=[9;8];[X,FVAL,EXITFLAG,OUTPUT]=LINPROG(f,A,b)X=10.000015.0000FVAL=-175.00009/27/2023數(shù)學建模用Matlab編程求解程序如下：X=8/6/2023數(shù)學建26用YALMIP編程求解程序如下：x=sdpvar(1,2);C=[105];a=[0.30.4;0.50.2];b=[98];f=C*x';F=set(0<=x<=inf);F=F+set(a*x'<=b');solvesdp(F,-f)double(f)double(x)

ans=175ans=10159/27/2023數(shù)學建模用YALMIP編程求解程序如下：ans=8/6/2023數(shù)27線性規(guī)劃

設某工廠有甲、乙、丙、丁四個車間，生產(chǎn)A、B、C、D、E、F六種產(chǎn)品。根據(jù)機床性能和以前的生產(chǎn)情況，得知每單位產(chǎn)品所需車間的工作小時數(shù)、每個車間在一個季度工作小時的上限以及單位產(chǎn)品的利潤，如下表所示(例如，生產(chǎn)一個單位的A產(chǎn)品，需要甲、乙、丙三個車間分別工作1小時、2小時和4小時)問：每種產(chǎn)品各應該每季度生產(chǎn)多少，才能使這個工廠每季度生產(chǎn)利潤達到最大。

9/27/2023數(shù)學建模線性規(guī)劃設某工廠有甲28生產(chǎn)單位產(chǎn)品所需車間的工作小時數(shù)ABCDEF每個車間一個季度工作小時的上限甲111323500乙255500丙425500丁138500利潤(百元)4.02.45.55.04.58.59/27/2023數(shù)學建模生產(chǎn)單位產(chǎn)品所需車間的工作小時數(shù)ABCDEF每個車間一個季29這是一個典型的最優(yōu)化問題，屬線性規(guī)劃。假設：產(chǎn)品合格且能及時銷售出去；工作無等待情況等變量說明：xj：第j種產(chǎn)品的生產(chǎn)量（j=1,2,……,6）aij：第i車間生產(chǎn)單位第j種產(chǎn)品所需工作小時數(shù)（i=1,2,3,4;j=1,2,……,6）bi：第i車間的最大工作上限cj：第j種產(chǎn)品的單位利潤則：cjxj為第j種產(chǎn)品的利潤總額；aijxj表示第i車間生產(chǎn)第j種產(chǎn)品所花時間總數(shù)；9/27/2023數(shù)學建模這是一個典型的最優(yōu)化問題，屬線性規(guī)劃。8/6/2023數(shù)學建30于是，我們可建立如下數(shù)學模型：s.t.計算結(jié)果：Z(百元)x1x2x3x4x5x61320006040100409/27/2023數(shù)學建模于是，我們可建立如下數(shù)學模型：s.t.計算結(jié)果：Z(百元)x31運輸問題要從甲城調(diào)出蔬菜2000噸，從乙城調(diào)出蔬菜2500噸，從丙地調(diào)出3000噸，分別供應A地2000噸，B地2300噸、C地1800噸、D地1400噸，已知每噸運費如下表：供應單位調(diào)出單位ABCD甲21271340乙45513720丙32352030問：如何調(diào)撥才能使運費最?。?/27/2023數(shù)學建模運輸問題要從甲城調(diào)32假設：①假設題目中所給運費已考慮各地間公里數(shù)；②只考慮運量和運費，不考慮車輛調(diào)撥等其它相關(guān)因素③不考慮車輛返空的費用（或：所給運費已包含車輛返空的費用）變量說明：xij:從第i城運往第j地的蔬菜數(shù)量（i=1,2,3;j=1,2,3,4）aij:從第i城運往第j地的單位運費（i=1,2,3;j=1,2,3,4）bi:從第i城調(diào)出的蔬菜總量cj:第j地所需蔬菜總量9/27/2023數(shù)學建模假設：8/6/2023數(shù)學建模33可以建立如下模型：s.t.9/27/2023數(shù)學建模可以建立如下模型：s.t.8/6/2023數(shù)學建模34整數(shù)規(guī)劃最優(yōu)化問題中的所有變量均為整數(shù)時，這類問題稱為整數(shù)規(guī)劃問題。如果線性規(guī)劃中的所有變量均為整數(shù)時，稱這類問題為線性整數(shù)規(guī)劃問題。整數(shù)規(guī)劃可分為線性整數(shù)規(guī)劃和非線性整數(shù)規(guī)劃，以及混合整數(shù)規(guī)劃等。如果決策變量的取值要么為0，要么為1，則這樣的規(guī)劃問題稱為0－1規(guī)劃。9/27/2023數(shù)學建模整數(shù)規(guī)劃最優(yōu)化問題中的所有變量均為整數(shù)時，這35例1某鋼廠兩個煉鋼爐同時各用一種方法煉鋼。第一種煉法每爐用a小時，第二種用b小時（包括清爐時間）。假定這兩種煉法，每爐出鋼都是k公斤，而煉1公斤鋼的平均燃料費第一法為m元，第二法為n元。若要求在c小時內(nèi)煉鋼公斤數(shù)不少于d，試列出燃料費最省的兩種方法的分配方案的數(shù)學模型。9/27/2023數(shù)學建模例1某鋼廠兩個煉鋼爐同時各用一種方法煉鋼。第一種煉法36設用第一種煉法煉鋼x1爐，第二種煉鋼x2爐s.t.9/27/2023數(shù)學建模設用第一種煉法煉鋼x1爐，第二種煉鋼x2爐s.t.8/6/37引例2.資源分配問題：某個中型的百貨商場要求售貨人員每周工作5天，連續(xù)休息2天，工資200元/周，已知對售貨人員的需求經(jīng)過統(tǒng)計分析如下表，問如何安排可使配備銷售人員的總費用最少？星期一二三四五六日所需售貨員人數(shù)18151216191412開始休息的人數(shù)x1x2x3x4x5x6x7設決策變量如上，可建立如下模型：9/27/2023數(shù)學建模引例2.資源分配問題：星期一二三四五六日所需售貨員人數(shù)181389/27/2023數(shù)學建模8/6/2023數(shù)學建模39非線性規(guī)劃非線性規(guī)劃問題的一般數(shù)學模型：其中，，為目標函數(shù)，為約束函數(shù)，這些函數(shù)中至少有一個是非線性函數(shù)。9/27/2023數(shù)學建模非線性規(guī)劃非線性規(guī)劃問題的一般數(shù)學模型：8/6/2023數(shù)學40應用實例：供應與選址

某公司有6個建筑工地要開工，每個工地的位置（用平面坐標系a，b表示，距離單位：km）及水泥日用量d(t)由下表給出．目前有兩個臨時料場位于A(5,1)，B(2,7)，日儲量各有20t．假設從料場到工地之間均有直線道路相連．（1）試制定每天的供應計劃，即從A，B兩料場分別向各工地運送多少水泥，可使總的噸千米數(shù)最小．（2）為了進一步減少噸千米數(shù)，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為20t，問應建在何處，節(jié)省的噸千米數(shù)有多大？9/27/2023數(shù)學建模應用實例：供應與