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

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

第三頁，共四十七頁，2022年，8月28日數(shù)學(xué)家對最優(yōu)化問題的研究已經(jīng)有很多年的歷史。以前解決最優(yōu)化問題的數(shù)學(xué)方法只限于古典求導(dǎo)方法和變分法（求無約束極值問題），拉格朗日（Lagrange）乘數(shù)法解決等式約束下的條件極值問題。計算機(jī)技術(shù)的出現(xiàn)，使得數(shù)學(xué)家研究出了許多最優(yōu)化方法和算法用以解決以前難以解決的問題。第四頁，共四十七頁，2022年，8月28日幾個概念最優(yōu)化是從所有可能方案中選擇最合理的一種以達(dá)到最優(yōu)目標(biāo)的學(xué)科。最優(yōu)方案是達(dá)到最優(yōu)目標(biāo)的方案。最優(yōu)化方法是搜尋最優(yōu)方案的方法。最優(yōu)化理論就是最優(yōu)化方法的理論。第五頁，共四十七頁，2022年，8月28日經(jīng)典極值問題包括：①無約束極值問題②約束條件下的極值問題第六頁，共四十七頁，2022年，8月28日1、無約束極值問題的數(shù)學(xué)模型2、約束條件下極值問題的數(shù)學(xué)模型其中，極大值問題可以轉(zhuǎn)化為極小值問題來進(jìn)行求解。如求：可以轉(zhuǎn)化為：第七頁，共四十七頁，2022年，8月28日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第八頁，共四十七頁，2022年，8月28日第九頁，共四十七頁，2022年，8月28日用MATLAB解無約束優(yōu)化問題其中等式（3）、（4）、（5）的右邊可選用（1）或（2）的等式右邊.

函數(shù)fminbnd的算法基于黃金分割法和二次插值法，它要求目標(biāo)函數(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（…）第十頁，共四十七頁，2022年，8月28日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)第十一頁，共四十七頁，2022年，8月28日例2有邊長為3m的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？解先編寫M文件fun0.m如下:functionf=fun0(x)f=-(3-2*x).^2*x;主程序為wliti2.m:[x,fval]=fminbnd('fun0',0,1.5);xmax=xfmax=-fval運(yùn)算結(jié)果為:xmax=0.5000,fmax=2.0000.即剪掉的正方形的邊長為0.5m時水槽的容積最大,最大容積為2m3.MATLAB(wliti2)第十二頁，共四十七頁，2022年，8月28日命令格式為:（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)化問題標(biāo)準(zhǔn)型為：min第十三頁，共四十七頁，2022年，8月28日例用fminsearch函數(shù)求解輸入命令:

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

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

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

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

某公司有6個建筑工地要開工，每個工地的位置（用平面坐標(biāo)系a，b表示，距離單位：km）及水泥日用量d(t)由下表給出．目前有兩個臨時料場位于A(5,1)，B(2,7)，日儲量各有20t．假設(shè)從料場到工地之間均有直線道路相連．（1）試制定每天的供應(yīng)計劃，即從A，B兩料場分別向各工地運(yùn)送多少水泥，可使總的噸千米數(shù)最?。?）為了進(jìn)一步減少噸千米數(shù)，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為20t