數學建模優(yōu)化

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

2.線性規(guī)劃模型的一般形式例線性規(guī)劃的標準形式為若是求目標函數的最大值，則要求轉為最小值（加負號即可），約束條件也一樣要轉化成標準形式。2023/2/3數學建模實用教程－高教出版社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=[]，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]若沒有等式約束:,則令Aeq=[],beq=[].[2]其中X0表示初始點4、命令：[x,fval]=linprog(…)返回最優(yōu)解ｘ及ｘ處的目標函數值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值，描述函數計算的退出條件。exitflag參數描述退出條件：·>0表示目標函數收斂于解x處；·=0表示已經達到函數評價或迭代的最大次數；·<0表示目標函數不收斂。例求解下列優(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注：對于同時存在等式與不等式約束的線性規(guī)劃問題，一定要注意約束條件間的相容性，否則求出的結果就是錯誤的.

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

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

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

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

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

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

宣傳部勞動部學習部甲6231乙7432丙81075丁7854

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

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

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

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

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

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

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

1.二次規(guī)劃模型的一般形式數學建模實用教程－高教出版社其中函數：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，最小化函數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)定義設計變量的下界lb和上界ub，使得lb<=x<=ub。x=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)同上，并設置初值x0。[x,fval]=quadprog(...)[x,fval,exitflag]=quadprog(...)[x,fval,exitflag,output]=quadprog(...)[x,fval,exitflag,output,lambda]=quadprog(...)[x,fval]=quadprog(...)返回解x處的目標函數fval=1/2*x’*H*x+f’*x。[x,fval,exitflag]=quadprog(...)返回exitflag參數，描述計算的退出條件。[x,fval,exitflag,output]=quadprog(...)返回包含優(yōu)化信息的結構輸出output。[x,fval,exitflag,output,lambda]=quadprog(...)返回解x處包含Lagrange乘子的lambda參數。求解下面的最優(yōu)化問題：目標函數約束條件

解：首先，目標函數寫成下面的矩陣形式：

在Matlab中實現>>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ī)劃模型的一般形式數學建模實用教程－高教出版社在許多實際的最優(yōu)化問題中，常常遇到目標函數是幾個的情況，這一類問題我們稱之為多目標優(yōu)化問題。例如，投資方向選擇問題，我們不僅要求投資的收益最大，而且要求投資的風險最小。再例如，購買商品問題，我們既要考慮商品的價格，又要考慮商品的質量，甚至還要考慮商品的性能等等。所謂多目標優(yōu)化問題是指：目標函數是兩個或兩個以上的最優(yōu)化問題。其數學模型為：

——目標函數

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

對于同一個問題不同的要求導致不同的求解標準，從而就會得到不同的求解結果。為此，我們給出多目標最優(yōu)化問題的條件最優(yōu)解概念。

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

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

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

定義為

的不減函數。步驟2：建立單目標優(yōu)化數學模型步驟3：求解上述單目標優(yōu)化數學模型得到：單目標優(yōu)化問題的最優(yōu)解，從而可得到原多目標優(yōu)化問題的最優(yōu)解或條件最優(yōu)解。

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

④平方和均衡優(yōu)化函數其中為大于零的權重系數例2：求解多目標優(yōu)化問題解：問題涉及兩個目標函數，可應用單目標化方法求解。（1）構造單目標函數

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

根據實際問題的性質，將原多目標優(yōu)化問題轉化成為多重單目標優(yōu)化問題的方法稱為多重優(yōu)化法。

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

①根據多目標優(yōu)化問題目標函數的性質，確定目標函數優(yōu)化對象和優(yōu)化次序

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

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