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

幾個(gè)概念最優(yōu)化是從所有可能方案中選擇最合理的一種以達(dá)到最優(yōu)目標(biāo)的學(xué)科。最優(yōu)方案是達(dá)到最優(yōu)目標(biāo)的方案。最優(yōu)化方法是搜尋最優(yōu)方案的方法。最優(yōu)化理論就是最優(yōu)化方法的理論。有約束最優(yōu)化問題的數(shù)學(xué)建模有約束最優(yōu)化模型一般具有以下形式：或其中f(x)為目標(biāo)函數(shù)，省略號(hào)表示約束式子，可以是等式約束，也可以是不等式約束。根據(jù)目標(biāo)函數(shù)，約束條件的特點(diǎn)將最優(yōu)化方法包含的主要內(nèi)容大致如下劃分：線性規(guī)劃整數(shù)規(guī)劃非線性規(guī)劃動(dòng)態(tài)規(guī)劃多目標(biāo)規(guī)劃對(duì)策論最優(yōu)化方法主要內(nèi)容由某實(shí)際問題設(shè)立變量，建立一個(gè)目標(biāo)函數(shù)和若干個(gè)約束條件，目標(biāo)函數(shù)和約束條件都是變量的線性函數(shù)，而且變量是非負(fù)的，這樣的求函數(shù)最大值最小值問題，我們稱為線性最優(yōu)化問題，簡(jiǎn)稱為線性規(guī)劃問題。線性規(guī)劃的數(shù)學(xué)模型有三要素：（1）自變量（2）關(guān)于自變量的線性目標(biāo)函數(shù).（3）與自變量有關(guān)的若干個(gè)線性約束條件；2023/2/3數(shù)學(xué)建模實(shí)用教程－高教出版社6一、線性規(guī)劃模型

2.線性規(guī)劃模型的一般形式例線性規(guī)劃的標(biāo)準(zhǔn)形式為若是求目標(biāo)函數(shù)的最大值，則要求轉(zhuǎn)為最小值（加負(fù)號(hào)即可），約束條件也一樣要轉(zhuǎn)化成標(biāo)準(zhǔn)形式。2023/2/3數(shù)學(xué)建模實(shí)用教程－高教出版社9一、線性規(guī)劃模型3.線性規(guī)劃解的概念（1）解：用MATLAB優(yōu)化工具箱解線性規(guī)劃minz=cX1、模型：命令：x=linprog（c，A，b）

2、模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式：存在，則令A(yù)=[]，b=[].3、模型：minz=cX

VLB≤X≤VUB命令：[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）

[2]x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）

注意：[1]若沒有等式約束:,則令A(yù)eq=[],beq=[].[2]其中X0表示初始點(diǎn)4、命令：[x,fval]=linprog(…)返回最優(yōu)解ｘ及ｘ處的目標(biāo)函數(shù)值fval.解編寫M文件xxgh1.m如下：c=[-0.4-0.28-0.32-0.72-0.64-0.6];A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08];b=[850;700;100;900];

Aeq=[];beq=[];

vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)線性優(yōu)化其他matlab命令形式[x,fval,exitflag]=linprog(...)返回exitflag值，描述函數(shù)計(jì)算的退出條件。exitflag參數(shù)描述退出條件：·>0表示目標(biāo)函數(shù)收斂于解x處；·=0表示已經(jīng)達(dá)到函數(shù)評(píng)價(jià)或迭代的最大次數(shù)；·<0表示目標(biāo)函數(shù)不收斂。例求解下列優(yōu)化問題：min

s.t.

解：在Matlab命令窗口鍵入：>>f=[-5

-4

-6];>>A=[1-11;324;320];>>b=[20;42;30];>>lb=zeros(3,1);>>[x,fval,exitflag]=linprog(f,A,b,[],[],lb)x=0.000015.00003.0000fval=-78.0000exitflag=1注：對(duì)于同時(shí)存在等式與不等式約束的線性規(guī)劃問題，一定要注意約束條件間的相容性，否則求出的結(jié)果就是錯(cuò)誤的.

運(yùn)用最優(yōu)化方法解決最優(yōu)化問題的一般方法步驟如下：①前期分析：分析問題，找出要解決的目標(biāo)，約束條件，并確立最優(yōu)化的目標(biāo)。②建立模型：定義變量，建立最優(yōu)化問題的數(shù)學(xué)模型，列出目標(biāo)函數(shù)和約束條件。③確定求解方法：針對(duì)建立的模型，選擇合適的求解方法或數(shù)學(xué)軟件。④計(jì)算機(jī)求解：編寫程序，利用計(jì)算機(jī)求解。⑤結(jié)果分析：討論諸如：結(jié)果的合理性、正確性，算法的收斂性，模型的適用性和通用性，算法效率與誤差等。（二）、整數(shù)規(guī)劃的數(shù)學(xué)模型一般形式依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、0－1整數(shù)規(guī)劃。

純整數(shù)規(guī)劃：所有決策變量要求取非負(fù)整數(shù)（這時(shí)引進(jìn)的松弛變量和剩余變量可以不要求取整數(shù)）。全整數(shù)規(guī)劃：除了所有決策變量要求取非負(fù)整數(shù)外，系數(shù)aij和常數(shù)bi也要求取整數(shù)（這時(shí)引進(jìn)的松弛變量和剩余變量也必須是整數(shù)）?；旌险麛?shù)規(guī)劃：只有一部分的決策變量要求取非負(fù)整數(shù)，另一部分可以取非負(fù)實(shí)數(shù)。

0－1整數(shù)規(guī)劃：所有決策變量只能取0或1兩個(gè)整數(shù)。（三）、整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系

從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)上，通過舍入取整，尋求滿足整數(shù)要求的解即可。但實(shí)際上兩者卻有很大的不同，通過舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時(shí)甚至不能保證所得倒的解是整數(shù)可行解。這樣的整數(shù)規(guī)劃應(yīng)用專門的方法求解。2023/2/323二、整數(shù)規(guī)劃模型

0-1整數(shù)規(guī)劃模型數(shù)學(xué)建模實(shí)用教程－高教出版社2023/2/324二、整數(shù)規(guī)劃模型

4.0-1整數(shù)規(guī)劃模型數(shù)學(xué)建模實(shí)用教程－高教出版社文體部

宣傳部勞動(dòng)部學(xué)習(xí)部甲6231乙7432丙81075丁7854

試綜合考慮四名候選人的情況，確定四個(gè)部長(zhǎng)的最優(yōu)選擇方案．

指派問題：某學(xué)校學(xué)生會(huì)準(zhǔn)備在學(xué)生中選拔文體部、宣傳部、勞動(dòng)部、學(xué)習(xí)部四個(gè)部門的部長(zhǎng)，經(jīng)過層層篩選，最后剩下甲、乙、丙、丁四名候選人，根據(jù)各項(xiàng)考核與民主測(cè)評(píng)，四人主持各部的工作能力(量化為分值)如表所示.解決問題的目標(biāo)就是尋求四個(gè)部長(zhǎng)的最優(yōu)選擇方案，使得四個(gè)部長(zhǎng)的總體工作能力最大，也就是要求四個(gè)人主持四部門的工作能力最大化．約束條件為每一個(gè)部門只能有一個(gè)人任部長(zhǎng)和每一個(gè)人只能任一個(gè)部門的部長(zhǎng)．2023/2/326二、整數(shù)規(guī)劃模型

4.0-1整數(shù)規(guī)劃模型數(shù)學(xué)建模實(shí)用教程－高教出版社2023/2/327二、整數(shù)規(guī)劃模型

4.0-1整數(shù)規(guī)劃模型數(shù)學(xué)建模實(shí)用教程－高教出版社2023/2/328二、整數(shù)規(guī)劃模型

4.0-1整數(shù)規(guī)劃模型數(shù)學(xué)建模實(shí)用教程－高教出版社2023/2/329二、整數(shù)規(guī)劃模型

4.0-1整數(shù)規(guī)劃模型數(shù)學(xué)建模實(shí)用教程－高教出版社最優(yōu)分配方案是:甲去勞動(dòng)部當(dāng)部長(zhǎng)，乙去文體部當(dāng)部長(zhǎng)，丙去宣傳部當(dāng)部長(zhǎng)，丁去學(xué)習(xí)部當(dāng)部長(zhǎng)．一般的指派(分配)問題的提法：現(xiàn)有項(xiàng)工作共需要個(gè)人來完成．已知第人完成第項(xiàng)工作的效益(或費(fèi)用)為()，且要求一人只能完成一項(xiàng)工作，每一項(xiàng)工作必須要有一個(gè)人來完成．試給出一種最優(yōu)的指派方案，使完成這項(xiàng)工作的總效益最大(或費(fèi)用最小)．設(shè)，則問題的數(shù)學(xué)模型可寫成

一般的指派問題還有:人數(shù)和任務(wù)數(shù)不等的指派問題、一個(gè)人可做幾件事的指派問題、某事一定不能由某人做的指派問題等．在線性規(guī)劃問題中，如果研究對(duì)象可以歸結(jié)為互相對(duì)立的兩種可能情況，那么通過引入0-1變量，都可歸結(jié)為0-1規(guī)劃問題．MATLAB工具箱應(yīng)用在MATLAB優(yōu)化工具箱中，提供了函數(shù)bintprog來求解0-1整數(shù)規(guī)劃，其優(yōu)化模型為：其中為向量，為矩陣，而最優(yōu)解為0、1組合而成的向量.函數(shù)的調(diào)用格式如下：（1）x=bintprog(f)：此格式求解無約束條件的0-1整數(shù)規(guī)劃；（2）x=bintprog(f,A,b)：此格式求解帶不等式約束條件的0-1整數(shù)規(guī)劃；（3）x=bintprog(f,A,b,Aeq,beq)：此格式求解帶不等式約束條件和等式約束條件的0-1整數(shù)規(guī)劃；（4）x=bintprog(f,A,b,Aeq,beq,x0)：此格式求解帶不等式約束條件和等式約束條件的0-1整數(shù)規(guī)劃，并且提供初始值x0；（5）x=bintprog(f,A,b,Aeq,beq,x0,options)：此格式中的options提供了優(yōu)化的參數(shù)選項(xiàng)；（6）x=bintprog(problem)：此格式中的優(yōu)化問題描述由problem結(jié)構(gòu)指定；（7）[x,fval]=bintprog(…)：此格式中的fval輸出最優(yōu)值；（8）[x,fval,exitflag]=bintprog(…)：此格式中的exitflag返回函數(shù)的結(jié)束狀態(tài)；2023/2/335三、二次規(guī)劃模型

1.二次規(guī)劃模型的一般形式數(shù)學(xué)建模實(shí)用教程－高教出版社其中函數(shù)：quadprog功能：求解二次規(guī)劃問題。格式：x=quadprog(H,f,A,b)x=quadprog(H,f,A,b,Aeq,beq)x=quadprog(H,f,A,b,Aeq,beq,lb,ub)x=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)

x=quadprog(H,f,A,b)返回向量x，最小化函數(shù)1/2*x’*H*x+f’*x，其約束條件為A*x<=b。x=quadprog(H,f,A,b,Aeq,beq)仍求上面的解，但添加了等式約束條件Aeq*x=beq。x=quadprog(H,f,A,b,Aeq,beq,lb,ub)定義設(shè)計(jì)變量的下界lb和上界ub，使得lb<=x<=ub。x=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)同上，并設(shè)置初值x0。[x,fval]=quadprog(...)[x,fval,exitflag]=quadprog(...)[x,fval,exitflag,output]=quadprog(...)[x,fval,exitflag,output,lambda]=quadprog(...)[x,fval]=quadprog(...)返回解x處的目標(biāo)函數(shù)fval=1/2*x’*H*x+f’*x。[x,fval,exitflag]=quadprog(...)返回exitflag參數(shù)，描述計(jì)算的退出條件。[x,fval,exitflag,output]=quadprog(...)返回包含優(yōu)化信息的結(jié)構(gòu)輸出output。[x,fval,exitflag,output,lambda]=quadprog(...)返回解x處包含Lagrange乘子的lambda參數(shù)。求解下面的最優(yōu)化問題：目標(biāo)函數(shù)約束條件

解：首先，目標(biāo)函數(shù)寫成下面的矩陣形式：

在Matlab中實(shí)現(xiàn)>>H=[1-1;-12];>>f=[-2

-6];>>A=[11;-12;21];>>b=[2;2;3];>>lb=zeros(2,1);>>[x,fval,exitflag,output,lambda]=quadprog(H,f,A,b,[],[],lb)x=0.66671.3333fval=-8.2222exitflag=1output=iterations:3algorithm:'medium-scale:active-set'

firstorderopt:[]

cgiterations:[]lambda=lower:[2x1double]upper:[2x1double]

eqlin:[0x1double]

ineqlin:[3x1double]2023/2/344四、非線性規(guī)劃模型

1.非線性規(guī)劃模型的一般形式數(shù)學(xué)建模實(shí)用教程－高教出版社在許多實(shí)際的最優(yōu)化問題中，常常遇到目標(biāo)函數(shù)是幾個(gè)的情況，這一類問題我們稱之為多目標(biāo)優(yōu)化問題。例如，投資方向選擇問題，我們不僅要求投資的收益最大，而且要求投資的風(fēng)險(xiǎn)最小。再例如，購(gòu)買商品問題，我們既要考慮商品的價(jià)格，又要考慮商品的質(zhì)量，甚至還要考慮商品的性能等等。所謂多目標(biāo)優(yōu)化問題是指：目標(biāo)函數(shù)是兩個(gè)或兩個(gè)以上的最優(yōu)化問題。其數(shù)學(xué)模型為：

——目標(biāo)函數(shù)

——約束條件多目標(biāo)優(yōu)化問題解的存在性極其復(fù)雜，這是由多目標(biāo)優(yōu)化問題的目標(biāo)函數(shù)多個(gè)性和目標(biāo)函數(shù)相互之間的復(fù)雜性質(zhì)決定的。由于目標(biāo)函數(shù)在很多情況下不可能同時(shí)達(dá)到最大值或最小值，因而，多目標(biāo)最優(yōu)化問題很少有最優(yōu)解，而實(shí)際問題又要求我們做出決擇，求得一個(gè)比較好的解。什么樣的解才是我們需要的解呢？

對(duì)于同一個(gè)問題不同的要求導(dǎo)致不同的求解標(biāo)準(zhǔn)，從而就會(huì)得到不同的求解結(jié)果。為此，我們給出多目標(biāo)最優(yōu)化問題的條件最優(yōu)解概念。

最優(yōu)解：滿足約束條件且使所有目標(biāo)函數(shù)達(dá)到要求的最大值或最小值的點(diǎn)稱為多目標(biāo)優(yōu)化問題的最優(yōu)解。

可行解：滿足多目標(biāo)優(yōu)化問題的約束條件的點(diǎn)稱為可行解。

條件最優(yōu)解：滿足多目標(biāo)優(yōu)化問題的約束條件且滿足根據(jù)需要設(shè)定條件的可行解稱為條件最優(yōu)解。 對(duì)于一個(gè)多目標(biāo)優(yōu)化問題，即使最優(yōu)解存在，要求解它也是十分困難的，特殊情況下，我們也只好用搜索法求解。更何況它常常還不存在最優(yōu)解，因而我們必須尋求其求解條件最優(yōu)解的方法。為了求得滿足我們要求的解，常常不得不設(shè)定一些新的條件，從而求得條件最優(yōu)解。設(shè)定新條件的方法是我們求解多目標(biāo)優(yōu)化問題的基本方法。下面的“單目標(biāo)化方法、多重目標(biāo)函數(shù)方法和目標(biāo)關(guān)聯(lián)函數(shù)方法”都是針對(duì)目標(biāo)函數(shù)設(shè)定新條件的方法。單目標(biāo)化解法將原多目標(biāo)優(yōu)化問題多個(gè)目標(biāo)函數(shù)轉(zhuǎn)化成為只有一個(gè)目標(biāo)函數(shù)的單目標(biāo)優(yōu)化問題求解的方法稱為單目標(biāo)化方法。（1）單目標(biāo)化解法的基本思想步驟1：構(gòu)造一個(gè)新的目標(biāo)函數(shù)滿足性質(zhì)：在約束條件的區(qū)域內(nèi)的單調(diào)增函數(shù)。特別注意：構(gòu)造新目標(biāo)函數(shù)也可以根據(jù)實(shí)際問題，將

定義為

的不減函數(shù)。步驟2：建立單目標(biāo)優(yōu)化數(shù)學(xué)模型步驟3：求解上述單目標(biāo)優(yōu)化數(shù)學(xué)模型得到：?jiǎn)文繕?biāo)優(yōu)化問題的最優(yōu)解，從而可得到原多目標(biāo)優(yōu)化問題的最優(yōu)解或條件最優(yōu)解。

——目標(biāo)函數(shù)——約束條件定理告訴我們：如果多目標(biāo)最優(yōu)化問題的最優(yōu)解存在，則只需求解一個(gè)單目標(biāo)最優(yōu)化問題就可以得到。但是，如果多目標(biāo)最優(yōu)化問題的最優(yōu)解不存在呢？則單目標(biāo)最優(yōu)化問題的最優(yōu)解可能存在，也可能不存在。當(dāng)原多目標(biāo)最優(yōu)化問題的最優(yōu)解不存在，而單目標(biāo)最優(yōu)化問題的最優(yōu)解存在時(shí)，我們稱解為單目標(biāo)條件最優(yōu)解。這種解在一定程度上反應(yīng)了原多目標(biāo)最優(yōu)化問題的性質(zhì)，因此，在實(shí)踐中常常被選用。注：?jiǎn)文繕?biāo)化的常用目標(biāo)函數(shù)①均衡優(yōu)化函數(shù)②權(quán)重優(yōu)化函數(shù)其中為大于零的權(quán)重系數(shù)③平方和優(yōu)化函數(shù)

④平方和均衡優(yōu)化函數(shù)其中為大于零的權(quán)重系數(shù)例2：求解多目標(biāo)優(yōu)化問題解：?jiǎn)栴}涉及兩個(gè)目標(biāo)函數(shù)，可應(yīng)用單目標(biāo)化方法求解。（1）構(gòu)造單目標(biāo)函數(shù)

（2）求解模型得最優(yōu)解為此時(shí)最優(yōu)解為此時(shí)多重優(yōu)化解法

根據(jù)實(shí)際問題的性質(zhì)，將原多目標(biāo)優(yōu)化問題轉(zhuǎn)化成為多重單目標(biāo)優(yōu)化問題的方法稱為多重優(yōu)化法。

（1）多重優(yōu)化方法的基本思想

①根據(jù)多目標(biāo)優(yōu)化問題目標(biāo)函數(shù)的性質(zhì)，確定目標(biāo)函數(shù)優(yōu)化對(duì)象和優(yōu)化次序

②建立多重優(yōu)化數(shù)學(xué)模型第一重優(yōu)化：其中為中的某一函數(shù)求解得解集為第二重優(yōu)化：其中為

中的某一函數(shù)求解得解集為依次類推，進(jìn)行重優(yōu)化第重優(yōu)化：其中為中的某一函數(shù)求解得解集為即為多重優(yōu)化問題的最優(yōu)解集。③原多目標(biāo)優(yōu)化問題的最優(yōu)解集或條件最優(yōu)解集為值得特別注意的是，我們不一定對(duì)所有目標(biāo)函數(shù)進(jìn)行多重優(yōu)化，也可以根據(jù)需要只選取某幾個(gè)目標(biāo)函數(shù)進(jìn)行多重優(yōu)化，甚至只選取某一個(gè)目標(biāo)函數(shù)進(jìn)行優(yōu)化。目標(biāo)關(guān)聯(lián)函數(shù)方法在多目標(biāo)最優(yōu)化問題數(shù)學(xué)模型中，如果我們只是選定某一個(gè)目標(biāo)函數(shù)（稱為主目標(biāo)）做為目標(biāo)，而固定其余目標(biāo)函數(shù)（稱為次目標(biāo)）在允許取值范圍內(nèi)為常數(shù)，則得到下列單目標(biāo)優(yōu)化數(shù)學(xué)模型：目標(biāo)關(guān)聯(lián)函數(shù)還具有許多很好的性質(zhì)，當(dāng)原雙目標(biāo)優(yōu)化問題不存在最優(yōu)解時(shí)，應(yīng)用目標(biāo)關(guān)聯(lián)函數(shù)選取條件最優(yōu)解最有效。一般來說，如果多目標(biāo)優(yōu)化問題存在最優(yōu)解，我們就沒有必要應(yīng)用目標(biāo)關(guān)聯(lián)函數(shù)法求解，只需要應(yīng)用單目標(biāo)優(yōu)化法或多重目標(biāo)優(yōu)化法。如果多目標(biāo)優(yōu)化問題不存在最優(yōu)解，那末我們就可以應(yīng)用目標(biāo)關(guān)聯(lián)函數(shù)法求其條件最優(yōu)解。（2）思路2——建立單目標(biāo)優(yōu)化模型引入新的函數(shù)，從一定程度上反應(yīng)“收益最大和風(fēng)險(xiǎn)最小”的目標(biāo)，將此函數(shù)做為目標(biāo)