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

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

第三頁，共四十一頁，編輯于2023年，星期三

數(shù)學家對最優(yōu)化問題的研究已經(jīng)有很多年的歷史。以前解決最優(yōu)化問題的數(shù)學方法只限于古典求導方法和變分法（求無約束極值問題），拉格朗日（Lagrange）乘數(shù)法解決等式約束下的條件極值問題。計算機技術的出現(xiàn)，使得數(shù)學家研究出了許多最優(yōu)化方法和算法用以解決以前難以解決的問題。第四頁，共四十一頁，編輯于2023年，星期三幾個概念最優(yōu)化是從所有可能方案中選擇最合理的一種以達到最優(yōu)目標的學科。最優(yōu)方案是達到最優(yōu)目標的方案。最優(yōu)化方法是搜尋最優(yōu)方案的方法。最優(yōu)化理論就是最優(yōu)化方法的理論。第五頁，共四十一頁，編輯于2023年，星期三經(jīng)典極值問題包括：①無約束極值問題②約束條件下的極值問題第六頁，共四十一頁，編輯于2023年，星期三1、無約束極值問題的數(shù)學模型2、約束條件下極值問題的數(shù)學模型

其中，極大值問題可以轉化為極小值問題來進行求解。如求：

可以轉化為：第七頁，共四十一頁，編輯于2023年，星期三1、無約束極值問題的求解例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)=7第八頁，共四十一頁，編輯于2023年，星期三第九頁，共四十一頁，編輯于2023年，星期三用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（…）第十頁，共四十一頁，編輯于2023年，星期三MATLAB(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)第十一頁，共四十一頁，編輯于2023年，星期三例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運算結果為:xmax=0.5000,fmax=2.0000.即剪掉的正方形的邊長為0.5m時水槽的容積最大,最大容積為2m3.MATLAB(wliti2)第十二頁，共四十一頁，編輯于2023年，星期三

命令格式為:（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)化問題標準型為：min第十三頁，共四十一頁，編輯于2023年，星期三例用fminsearch函數(shù)求解輸入命令:

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

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

'第十四頁，共四十一頁，編輯于2023年，星期三有約束最優(yōu)化最優(yōu)化方法分類（一）線性最優(yōu)化：目標函數(shù)和約束條件都是線性的則稱為線性最優(yōu)化。

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

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

動態(tài)最優(yōu)化：如果可能的方案與時間有關，則是動態(tài)最優(yōu)化問題第十五頁，共四十一頁，編輯于2023年，星期三有約束最優(yōu)化問題的數(shù)學建模有約束最優(yōu)化模型一般具有以下形式：或

其中f(x)為目標函數(shù)，省略號表示約束式子，可以是等式約束，也可以是不等式約束。第十六頁，共四十一頁，編輯于2023年，星期三

根據(jù)目標函數(shù)，約束條件的特點將最優(yōu)化方法包含的主要內容大致如下劃分：線性規(guī)劃整數(shù)規(guī)劃非線性規(guī)劃動態(tài)規(guī)劃多目標規(guī)劃對策論最優(yōu)化方法主要內容第十七頁，共四十一頁，編輯于2023年，星期三兩個引例問題一：某工廠在計劃期內要安排生產(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元。問應如何安排計劃使該工廠獲利最多？第十八頁，共四十一頁，編輯于2023年，星期三解：該工廠生產(chǎn)產(chǎn)品Ix1件，生產(chǎn)產(chǎn)品IIx2件，我們可建立如下數(shù)學模型：s.t.第十九頁，共四十一頁，編輯于2023年，星期三問題二：某廠每日8小時的產(chǎn)量不低于1800件.為了進行質量控制，計劃聘請兩種不同水平的檢驗員.一級檢驗員的標準為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標準為：速度15件/小時，正確率95%，計時工資3元/小時.檢驗員每錯檢一次，工廠要損失2元.為使總檢驗費用最省，該工廠應聘一級、二級檢驗員各幾名？解設需要一級和二級檢驗員的人數(shù)分別為x1、x2人,則應付檢驗員的工資為：因檢驗員錯檢而造成的損失為：第二十頁，共四十一頁，編輯于2023年，星期三故目標函數(shù)為：約束條件為：第二十一頁，共四十一頁，編輯于2023年，星期三

運用最優(yōu)化方法解決最優(yōu)化問題的一般方法步驟如下：①前期分析：分析問題，找出要解決的目標，約束條件，并確立最優(yōu)化的目標。②定義變量，建立最優(yōu)化問題的數(shù)學模型，列出目標函數(shù)和約束條件。③針對建立的模型，選擇合適的求解方法或數(shù)學軟件。④編寫程序，利用計算機求解。⑤對結果進行分析，討論諸如：結果的合理性、正確性，算法的收斂性，模型的適用性和通用性，算法效率與誤差等。第二十二頁，共四十一頁，編輯于2023年，星期三線性規(guī)劃某豆腐店用黃豆制作兩種不同口感的豆腐出售。制作口感較鮮嫩的豆腐每千克需要0.3千克一級黃豆及0.5千克二級黃豆，售價10元；制作口感較厚實的豆腐每千克需要0.4千克一級黃豆及0.2千克二級黃豆，售價5元。現(xiàn)小店購入9千克一級黃豆和8千克二級黃豆。問：應如何安排制作計劃才能獲得最大收益。第二十三頁，共四十一頁，編輯于2023年，星期三一、問題前期分析該問題是在不超出制作兩種不同口感豆腐所需黃豆總量條件下合理安排制作計劃，使得售出各種豆腐能獲得最大收益。二、模型假設1．假設制作的豆腐能全部售出。2．假設豆腐售價無波動。第二十四頁，共四十一頁，編輯于2023年，星期三變量假設：設計劃制作口感鮮嫩和厚實的豆腐各x1千克和x2千克，可獲得收益R元。目標函數(shù)：獲得的總收益最大。總收益可表示為：受一級黃豆數(shù)量限制：受二級黃豆數(shù)量限制：第二十五頁，共四十一頁，編輯于2023年，星期三綜上分析，得到該問題的線性規(guī)劃模型s.t.第二十六頁，共四十一頁，編輯于2023年，星期三用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.0000第二十七頁，共四十一頁，編輯于2023年，星期三用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=1015第二十八頁，共四十一頁，編輯于2023年，星期三線性規(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)利潤達到最大。

第二十九頁，共四十一頁，編輯于2023年，星期三生產(chǎn)單位產(chǎn)品所需車間的工作小時數(shù)ABCDEF每個車間一個季度工作小時的上限甲111323500乙255500丙425500丁138500利潤(百元)4.02.45.55.04.58.5第三十頁，共四十一頁，編輯于2023年，星期三這是一個典型的最優(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ù)；第三十一頁，共四十一頁，編輯于2023年，星期三于是，我們可建立如下數(shù)學模型：s.t.計算結果：Z(百元)x1x2x3x4x5x6132000604010040第三十二頁，共四十一頁，編輯于2023年，星期三整數(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ī)劃。第三十三頁，共四十一頁，編輯于2023年，星期三例1某鋼廠兩個煉鋼爐同時各用一種方法煉鋼。第一種煉法每爐用a小時，第二種用b小時（包括清爐時間）。假定這兩種煉法，每爐出鋼都是k公斤，而煉1公斤鋼的平均燃料費第一法為m元，第二法為n元。若要求在c小時內煉鋼公斤數(shù)不少于d，試列出燃料費最省的兩種方法的分配方案的數(shù)學模型。第三十四頁，共四十一頁，編輯于2023年，星期三設用第一種煉法煉鋼x1爐，第二種煉鋼x2爐s.t.第三十五頁，共四十一頁，編輯于2023年，星期三非線性規(guī)劃非線性規(guī)劃問題的一般數(shù)學模型：其中，，為目標函數(shù)，為約束函數(shù)，這些函數(shù)中至少有一個是非線性函數(shù)。第三十六頁，共四十一頁，編輯于2023年，星期三應用實例：供應與選址

某公司有6個建筑工地要開工，每個工地的位置（用平面坐標系a，b表示，距離單位：km）及水泥日用量d(t)由下表給出．目前有兩個臨時料場位于A(5,1)，B(2,7)，日儲量各有20t．假設從料場到工地之間均有直線道路相連．