数学建模优化

几个概念最优化是从所有可能方案中选择最合理的一种以达到最优目标的学科。最优方案是达到最优目标的方案。最优化方法是搜寻最优方案的方法。最优化理论就是最优化方法的理论。有约束最优化问题的数学建模有约束最优化模型一般具有以下形式：或其中f(x)为目标函数，省略号表示约束式子，可以是等式约束，也可以是不等式约束。根据目标函数，约束条件的特点将最优化方法包含的主要内容大致如下划分：线性规划整数规划非线性规划动态规划多目标规划对策论最优化方法主要内容由某实际问题设立变量，建立一个目标函数和若干个约束条件，目标函数和约束条件都是变量的线性函数，而且变量是非负的，这样的求函数最大值最小值问题，我们称为线性最优化问题，简称为线性规划问题。线性规划的数学模型有三要素：（1）自变量（2）关于自变量的线性目标函数.（3）与自变量有关的若干个线性约束条件；2023/2/3数学建模实用教程－高教出版社6一、线性规划模型

2.线性规划模型的一般形式例线性规划的标准形式为若是求目标函数的最大值，则要求转为最小值（加负号即可），约束条件也一样要转化成标准形式。2023/2/3数学建模实用教程－高教出版社9一、线性规划模型3.线性规划解的概念（1）解：用MATLAB优化工具箱解线性规划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(…)返回最优解ｘ及ｘ处的目标函数值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)线性优化其他matlab命令形式[x,fval,exitflag]=linprog(...)返回exitflag值，描述函数计算的退出条件。exitflag参数描述退出条件：·>0表示目标函数收敛于解x处；·=0表示已经达到函数评价或迭代的最大次数；·<0表示目标函数不收敛。例求解下列优化问题：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注：对于同时存在等式与不等式约束的线性规划问题，一定要注意约束条件间的相容性，否则求出的结果就是错误的.

运用最优化方法解决最优化问题的一般方法步骤如下：①前期分析：分析问题，找出要解决的目标，约束条件，并确立最优化的目标。②建立模型：定义变量，建立最优化问题的数学模型，列出目标函数和约束条件。③确定求解方法：针对建立的模型，选择合适的求解方法或数学软件。④计算机求解：编写程序，利用计算机求解。⑤结果分析：讨论诸如：结果的合理性、正确性，算法的收敛性，模型的适用性和通用性，算法效率与误差等。（二）、整数规划的数学模型一般形式依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、0－1整数规划。

纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。全整数规划：除了所有决策变量要求取非负整数外，系数aij和常数bi也要求取整数（这时引进的松弛变量和剩余变量也必须是整数）。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。

0－1整数规划：所有决策变量只能取0或1两个整数。（三）、整数规划与线性规划的关系

从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。这样的整数规划应用专门的方法求解。2023/2/323二、整数规划模型

0-1整数规划模型数学建模实用教程－高教出版社2023/2/324二、整数规划模型

4.0-1整数规划模型数学建模实用教程－高教出版社文体部

宣传部劳动部学习部甲6231乙7432丙81075丁7854

试综合考虑四名候选人的情况，确定四个部长的最优选择方案．

指派问题：某学校学生会准备在学生中选拔文体部、宣传部、劳动部、学习部四个部门的部长，经过层层筛选，最后剩下甲、乙、丙、丁四名候选人，根据各项考核与民主测评，四人主持各部的工作能力(量化为分值)如表所示.解决问题的目标就是寻求四个部长的最优选择方案，使得四个部长的总体工作能力最大，也就是要求四个人主持四部门的工作能力最大化．约束条件为每一个部门只能有一个人任部长和每一个人只能任一个部门的部长．2023/2/326二、整数规划模型

4.0-1整数规划模型数学建模实用教程－高教出版社2023/2/327二、整数规划模型

4.0-1整数规划模型数学建模实用教程－高教出版社2023/2/328二、整数规划模型

4.0-1整数规划模型数学建模实用教程－高教出版社2023/2/329二、整数规划模型

4.0-1整数规划模型数学建模实用教程－高教出版社最优分配方案是:甲去劳动部当部长，乙去文体部当部长，丙去宣传部当部长，丁去学习部当部长．一般的指派(分配)问题的提法：现有项工作共需要个人来完成．已知第人完成第项工作的效益(或费用)为()，且要求一人只能完成一项工作，每一项工作必须要有一个人来完成．试给出一种最优的指派方案，使完成这项工作的总效益最大(或费用最小)．设，则问题的数学模型可写成

一般的指派问题还有:人数和任务数不等的指派问题、一个人可做几件事的指派问题、某事一定不能由某人做的指派问题等．在线性规划问题中，如果研究对象可以归结为互相对立的两种可能情况，那么通过引入0-1变量，都可归结为0-1规划问题．MATLAB工具箱应用在MATLAB优化工具箱中，提供了函数bintprog来求解0-1整数规划，其优化模型为：其中为向量，为矩阵，而最优解为0、1组合而成的向量.函数的调用格式如下：（1）x=bintprog(f)：此格式求解无约束条件的0-1整数规划；（2）x=bintprog(f,A,b)：此格式求解带不等式约束条件的0-1整数规划；（3）x=bintprog(f,A,b,Aeq,beq)：此格式求解带不等式约束条件和等式约束条件的0-1整数规划；（4）x=bintprog(f,A,b,Aeq,beq,x0)：此格式求解带不等式约束条件和等式约束条件的0-1整数规划，并且提供初始值x0；（5）x=bintprog(f,A,b,Aeq,beq,x0,options)：此格式中的options提供了优化的参数选项；（6）x=bintprog(problem)：此格式中的优化问题描述由problem结构指定；（7）[x,fval]=bintprog(…)：此格式中的fval输出最优值；（8）[x,fval,exitflag]=bintprog(…)：此格式中的exitflag返回函数的结束状态；2023/2/335三、二次规划模型

1.二次规划模型的一般形式数学建模实用教程－高教出版社其中函数：quadprog功能：求解二次规划问题。格式：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(...)返回包含优化信息的结构输出output。[x,fval,exitflag,output,lambda]=quadprog(...)返回解x处包含Lagrange乘子的lambda参数。求解下面的最优化问题：目标函数约束条件

解：首先，目标函数写成下面的矩阵形式：

在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四、非线性规划模型

1.非线性规划模型的一般形式数学建模实用教程－高教出版社在许多实际的最优化问题中，常常遇到目标函数是几个的情况，这一类问题我们称之为多目标优化问题。例如，投资方向选择问题，我们不仅要求投资的收益最大，而且要求投资的风险最小。再例如，购买商品问题，我们既要考虑商品的价格，又要考虑商品的质量，甚至还要考虑商品的性能等等。所谓多目标优化问题是指：目标函数是两个或两个以上的最优化问题。其数学模型为：

——目标函数

——约束条件多目标优化问题解的存在性极其复杂，这是由多目标优化问题的目标函数多个性和目标函数相互之间的复杂性质决定的。由于目标函数在很多情况下不可能同时达到最大值或最小值，因而，多目标最优化问题很少有最优解，而实际问题又要求我们做出决择，求得一个比较好的解。什么样的解才是我们需要的解呢？

对于同一个问题不同的要求导致不同的求解标准，从而就会得到不同的求解结果。为此，我们给出多目标最优化问题的条件最优解概念。

最优解：满足约束条件且使所有目标函数达到要求的最大值或最小值的点称为多目标优化问题的最优解。

可行解：满足多目标优化问题的约束条件的点称为可行解。

条件最优解：满足多目标优化问题的约束条件且满足根据需要设定条件的可行解称为条件最优解。 对于一个多目标优化问题，即使最优解存在，要求解它也是十分困难的，特殊情况下，我们也只好用搜索法求解。更何况它常常还不存在最优解，因而我们必须寻求其求解条件最优解的方法。为了求得满足我们要求的解，常常不得不设定一些新的条件，从而求得条件最优解。设定新条件的方法是我们求解多目标优化问题的基本方法。下面的“单目标化方法、多重目标函数方法和目标关联函数方法”都是针对目标函数设定新条件的方法。单目标化解法将原多目标优化问题多个目标函数转化成为只有一个目标函数的单目标优化问题求解的方法称为单目标化方法。（1）单目标化解法的基本思想步骤1：构造一个新的目标函数满足性质：在约束条件的区域内的单调增函数。特别注意：构造新目标函数也可以根据实际问题，将

定义为

的不减函数。步骤2：建立单目标优化数学模型步骤3：求解上述单目标优化数学模型得到：单目标优化问题的最优解，从而可得到原多目标优化问题的最优解或条件最优解。

——目标函数——约束条件定理告诉我们：如果多目标最优化问题的最优解存在，则只需求解一个单目标最优化问题就可以得到。但是，如果多目标最优化问题的最优解不存在呢？则单目标最优化问题的最优解可能存在，也可能不存在。当原多目标最优化问题的最优解不存在，而单目标最优化问题的最优解存在时，我们称解为单目标条件最优解。这种解在一定程度上反应了原多目标最优化问题的性质，因此，在实践中常常被选用。注：单目标化的常用目标函数①均衡优化函数②权重优化函数其中为大于零的权重系数③平方和优化函数

④平方和均衡优化函数其中为大于零的权重系数例2：求解多目标优化问题解：问题涉及两个目标函数，可应用单目标化方法求解。（1）构造单目标函数

（2）求解模型得最优解为此时最优解为此时多重优化解法

根据实际问题的性质，将原多目标优化问题转化成为多重单目标优化问题的方法称为多重优化法。

（1）多重优化方法的基本思想

①根据多目标优化问题目标函数的性质，确定目标函数优化对象和优化次序

②建立多重优化数学模型第一重优化：其中为中的某一函数求解得解集为第二重优化：其中为

中的某一函数求解得解集为依次类推，进行重优化第重优化：其中为中的某一函数求解得解集为即为多重优化问题的最优解集。③原多目标优化问题的最优解集或条件最优解集为值得特别注意的是，我们不一定对所有目标函数进行多重优化，也可以根据需要只选取某几个目标函数进行多重优化，甚至只选取某一个目标函数进行优化。目标关联函数方法在多目标最优化问题数学模型中，如果我们只是选定某一个目标函数（称为主目标）做为目标，而固定其余目标函数（称为次目标）在允许取值范围内为常数，则得到下列单目标优化数学模型：目标关联函数还具有许多很好的性质，当原双目标优化问题不存在最优解时，应用目标关联函数选取条件最优解最有效。一般来说，如果多目标优化问题存在最优解，我们就没有必要应用目标关联函数法求解，只需要应用单目标优化法或多重目标优化法。如果多目标优化问题不存在最优解，那末我们就可以应用目标关联函数法求其条件最优解。（2）思路2——建立单目标优化模型引入新的函数，从一定程度上反应“收益最大和风险最小”的目标，将此函数做为目标