下载文档原格式
非线性规划作业非线性规划是运筹学中的一个重要分支，用于解决具有非线性目标函数和约束条件的优化问题。
本次作业将介绍非线性规划的基本概念、求解方法和应用，并提供一个实际问题供你进行求解和分析。
一、基本概念1. 非线性规划：非线性规划是指目标函数或者约束条件中至少有一个是非线性的优化问题。
它与线性规划相比，更具有灵便性和适合性。
2. 目标函数：非线性规划的目标函数是优化问题的目标，通常是最大化或者最小化的数学表达式。
它可能包含非线性项，如幂函数、指数函数等。
3. 约束条件：非线性规划的约束条件是对决策变量的限制条件，用于定义可行解的集合。
约束条件可以是等式或者不等式，也可以包含非线性项。
4. 局部最优解与全局最优解：非线性规划问题可能存在多个极值点，其中局部最优解是在某一特定区域内最优的解，而全局最优解是在整个可行域内最优的解。
二、求解方法1. 数学方法：非线性规划问题可以通过数学方法进行求解，如拉格朗日乘子法、KKT条件等。
这些方法基于数学推导和分析，可以得到问题的解析解。
2. 迭代方法：对于复杂的非线性规划问题，往往采用迭代方法进行求解。
典型的迭代方法包括牛顿法、拟牛顿法、单纯形法等。
这些方法通过不断迭代逼近最优解。
3. 优化软件：为了简化非线性规划问题的求解过程，可以使用专门的优化软件，如MATLAB、Gurobi、CPLEX等。
这些软件提供了丰富的求解算法和工具，可快速求解复杂问题。
三、应用案例假设你是一家创造公司的生产经理，你需要确定每一个产品的生产数量，以最大化公司的利润。
公司生产两种产品：A和B。
每一个产品的生产成本和利润如下：产品A：生产成本为1000元/件，利润为300元/件。
产品B：生产成本为1500元/件，利润为500元/件。
公司的生产能力有限，每天最多只能生产1000件产品。
此外，由于市场需求的限制，产品A和B的销售量之和不能超过800件。
你的任务是确定每一个产品的生产数量，以最大化公司的利润。
非线性规划作业1. 引言非线性规划是数学规划中的一个重要分支，广泛应用于工程、经济、管理等领域。
本文将针对非线性规划问题进行详细讨论和分析，并给出相应的标准格式文本。
2. 问题描述假设我们有一个非线性规划问题，目标是最小化一个目标函数，同时满足一组约束条件。
具体问题描述如下：最小化目标函数：f(x) = 3x^2 + 2x + 5约束条件：g(x) = x^2 - 4x + 3 ≤ 0h(x) = x - 2 ≥ 0其中，x为决策变量。
3. 模型建立为了解决上述非线性规划问题，我们需要建立相应的数学模型。
首先，我们定义目标函数和约束条件：目标函数：minimize f(x) = 3x^2 + 2x + 5约束条件：g(x) = x^2 - 4x + 3 ≤ 0h(x) = x - 2 ≥ 0接下来，我们将上述问题转化为标准格式的非线性规划模型。
标准格式如下：最小化目标函数：minimize f(x)约束条件：g(x) ≤ 0h(x) ≥ 04. 求解方法为了求解上述非线性规划问题，我们可以采用多种求解方法，如梯度下降法、牛顿法、拟牛顿法等。
在本文中，我们选择使用拟牛顿法进行求解。
拟牛顿法是一种迭代算法，通过逐步优化目标函数来逼近最优解。
具体步骤如下：步骤1：选择初始点x0和初始矩阵B0。
步骤2：计算梯度gk和搜索方向pk。
步骤3：计算步长αk。
步骤4：更新xk+1 = xk + αkpk。
步骤5：更新矩阵Bk+1。
步骤6：判断停止准则，如果满足停止准则，则停止迭代；否则返回步骤2。
5. 求解结果通过拟牛顿法求解上述非线性规划问题，我们得到最优解如下：最优解：x* = 1.5最优目标函数值：f(x*) = 10.256. 结论通过本文对非线性规划问题的详细讨论和分析，我们成功建立了相应的数学模型，并采用拟牛顿法进行了求解。
最终得到了最优解x* = 1.5和最优目标函数值f(x*) = 10.25。
MATLAB求解非线性规划非线性规划是一类涉及非线性目标函数或非线性约束条件的数学规划问题。
MATLAB是一种强大的数学计算软件，可以用来求解非线性规划问题。
本文将介绍MATLAB中求解非线性规划问题的方法。
1. 目标函数和约束条件在MATLAB中，非线性规划问题可以表示为以下形式：minimize f(x)subject to c(x)≤0ceq(x)=0lb≤x≤ub其中f(x)是目标函数，c(x)和ceq(x)是不等式和等式约束条件，lb和ub是变量的下限和上限。
2. 求解器MATLAB提供了多种求解器可以用来求解非线性规划问题。
其中常用的有fmincon和lsqnonlin。
lsqnonlin可以用来求解非线性最小二乘问题。
它使用的是Levenberg-Marquardt算法，能够有效地求解非线性最小二乘问题，并且具有较好的收敛性。
3. 示例下面我们来看一个求解非线性规划问题的示例。
假设我们要求解以下非线性规划问题：首先，我们需要定义目标函数和约束条件。
在MATLAB中，我们可以使用anonymous function来定义目标函数和约束条件。
代码如下：f = @(x)x(1)^2+2*x(2)^2+3*x(3)^2;c = @(x)[x(1)+x(2)+x(3)-4, x(1)*x(2)+x(1)*x(3)+x(2)*x(3)-3];ceq = [];lb = [0,0,0];接下来，我们使用fmincon求解非线性规划问题。
代码如下：[x,fval,exitflag,output] = fmincon(f,[1,1,1],[],[],[],[],lb,[],@(x)c(x));其中，第一个参数是目标函数，第二个参数是变量的初值，第三个参数是不等式约束条件，第四个参数是等式约束条件，第五个参数是变量的下限，第六个参数是变量的上限，第七个参数是非线性约束条件，最后一个参数是opts，可以设置其他求解参数。
科技信息基金项目：本文系国家自然基金项目（10971122）。
作者简介：高艳山（1986-），男，河北唐山人，硕士研究生，主要从事最优化算法、计算理论与数据处理等研究工作。
科学领域的很多问题都可以归结为线性规划。
然而，也有一些问题的目标函数和约束条件很难用线性函数来表达。
我们称这种数学规划为非线性规划。
非线性规划的一个重要理论是1951年Kuhn-Tucker 最优条件(简称KT 条件)的建立。
一般来说，解非线性规划问题要比求解线性规划问题困难得多。
到目前为止，还没有适用于各种非线性规划问题的一般算法，各个算法都有一定的局限性。
这正是需要人们进一步研究的课题。
1.无约束最优化优化包括数学规划的全部内容，最简单的优化问题是无约束最优化，对这类问题，已经研究出比较有效的求解方法，因而构成更一般非线性规划解法的出发点。
设目标函数是一个无约束的变量函数min f (x )，其中x ∈R n 。
我们知道，如果目标函数在其定义域内连续且存在一阶偏导数，则目标函数在点x *处达到极值的必要条件是函数对各个变量的一阶偏导数在该点等于零。
因此，只要找到使∇f (x )=0的点x *，问题就解决了。
但在实际的工程规划中，由于目标函数是高次多元函数，而且求导也存在困难，因而，在一般情况下，关于无约束非线性规划问题的解法常分成两类：I.解析法——间接最优化方法。
就是首先求出目标函数的一阶、二阶导数，需要求解由目标函数的偏导数所组成的方程组，以便求出稳定点，然后用梯度矩阵及Hesse 矩阵对所找到的稳定点进行判断，看它是否为最优点，当目标函数比较简单时，求解上述方程组和利用Hesse 矩阵进行判断并不困难，但当目标函数比较复杂或为非凸性函数时，应用此法会带来麻烦，有时甚至很难求解。
II.数值计算法——是直接优化方法。
直接法，这是一种建立在电算技术基础上的方法，无论在处理方法还是在概念上与经典方法、理论都不相同。
它的特点是：⑴是一种直接的数值解法，而不是分析方法；⑵按一定的逻辑结构，反复地重复进行同一类型的运算；⑶它是根据目标函数的变化规律，以适当的步长沿着使目标函数值下降的方向逐步向目标函数值的最优点进行探索并逼近的，故得出的是近似解，而非精确解，称为逐次逼近法或迭代法。
非线性规划作业一、引言非线性规划是运筹学中的重要分支，它研究的是在约束条件下求解非线性目标函数的最优解。
在实际问题中，不少情况下目标函数和约束条件都是非线性的，因此非线性规划在实际应用中具有广泛的意义。
本文将针对给定的非线性规划问题进行详细的讨论和求解。
二、问题描述假设我们有一家创造公司，生产两种产品A和B。
产品A的单价为100元/件，产品B的单价为200元/件。
公司的目标是最大化利润，同时满足以下约束条件：1. 产品A和B的生产总量之和不能超过1000件；2. 产品A的生产量不能超过500件；3. 产品B的生产量不能超过800件；4. 产品A和B的生产量都必须为正数。
三、数学建模为了进行数学建模，我们需要引入一些变量和符号来表示问题中的各个要素。
假设x表示产品A的生产量，y表示产品B的生产量，则目标函数可以表示为：Z = 100x + 200y同时，约束条件可以表示为：x + y ≤ 1000x ≤ 500y ≤ 800x, y ≥ 0四、问题求解为了求解上述非线性规划问题，我们可以采用常用的优化算法，如梯度下降法、牛顿法等。
这里我们选择使用梯度下降法来求解。
1. 初始化变量我们首先需要初始化变量x和y的初始值。
可以选择任意合理的初始值，这里我们选择x=300，y=500作为初始值。
2. 计算目标函数的梯度根据梯度下降法的原理，我们需要计算目标函数关于变量x和y的梯度。
在本问题中，目标函数的梯度可以表示为：∇Z = (100, 200)3. 更新变量根据梯度下降法的更新规则，我们可以通过以下公式来更新变量x和y的值：x = x - α * ∇Zy = y - α * ∇Z其中，α表示学习率，是一个控制更新步长的参数。
在实际应用中，可以根据经验选择一个合适的学习率。
4. 迭代求解通过重复进行步骤2和步骤3，直到目标函数收敛或者达到预设的迭代次数，我们可以得到最优解x*和y*。
五、数值实验为了验证上述求解方法的有效性，我们进行了一系列的数值实验。
学习非线性规划的基本方法非线性规划（Nonlinear Programming，简称NLP）是数学规划中的一种重要方法，被广泛应用于工程、经济、管理、物理等领域。
与线性规划相比，非线性规划在模型的描述和求解方法上更为复杂，但也更为灵活和准确。
本文将介绍非线性规划的基本方法，包括问题的建模、常用的求解算法和实际应用。
一、非线性规划问题的建模在开始学习非线性规划之前，我们首先需要对非线性规划问题进行合理的建模。
通常，一个典型的非线性规划问题可以表示为以下形式：最小化 f(x)约束g_i(x) ≤ 0, i = 1, 2, ..., mh_j(x) = 0, j = 1, 2, ..., n其中，f(x)是目标函数，g_i(x)是不等式约束条件，h_j(x)是等式约束条件，x为决策变量，m和n分别表示不等式约束条件和等式约束条件的个数。
在建模时，需要特别注意以下几点：1. 选择合适的决策变量，使得问题的描述和求解更加精确和高效。
2. 明确目标函数和约束条件，确保数学模型的准确性。
3. 充分考虑实际问题的特性，对问题进行合理的简化和假设。
二、非线性规划问题的求解算法非线性规划问题的求解算法可以分为两类：直接法和间接法。
直接法直接对非线性规划问题进行求解，而间接法先将非线性规划问题转化为等价的特殊结构问题，再对等价问题进行求解。
下面介绍两种常用的求解算法：单纯形法和内点法。
1. 单纯形法单纯形法是线性规划中常用的一种求解算法，但也可以用于求解非线性规划问题。
该算法通过寻找可行解的连续改进路径，不断接近最优解。
单纯形法的核心思想是在可行域内搜索目标函数极小值点。
2. 内点法内点法是一类有效的非线性规划求解方法，其基本思想是将原问题转化为一个等价的凸优化问题，通过寻找问题凸对偶的极值点来求解原问题。
该方法的优点是能够处理大规模的非线性规划问题，并具有较好的收敛性和全局最优性。
三、非线性规划的实际应用非线性规划方法在实际应用中具有广泛的应用前景。
2005年1月系统工程理论与实践第1期 文章编号:100026788(2005)0120110207区间非线性规划问题的确定化描述及其递阶求解蒋 峥,戴连奎,吴铁军(工业控制技术国家重点实验室,浙江大学智能系统与决策研究所,浙江杭州310027)摘要: 讨论以区间参数形式给出的不确定性非线性规划问题,提出了一种含有决策风险因子的新的区间参数不确定非线性规划的一般命题形式,并分别就不确定性参数出现在目标函数或约束条件中的不同情况,给出不同的表达形式Λ文章给出用遗传算法,采用递阶优化方式求解区间参数不确定非线性规划的具体算法Λ仿真结果表明该形式的可行性Λ关键词: 区间规划;非线性规划;遗传算法;决策风险中图分类号: O221 文献标识码: A D eterm in istic In terp retati on of In terval N on linearP rogramm ing and Its H ierarch ical Op ti m izati on So lu ti on sJ I AN G Zheng,DA I L ian2ku i,W U T ie2jun(N ati onalL abo rato ry of Indu strial Con tro l T echno logy,In stitu te of In telligen t System and D ecisi onM ak ing,Zhejiang U n i2 versity,H angzhou310027,Ch ina)Abstract: W e con sider a determ in istic fram ew o rk fo r non linear p rogramm ing invo lving in terval coeffi2cien ts.A new in terp retati on of non linear p rogramm ing under uncertain ty is p ropo sed by the in troducti onof the decisi on m ak ing risk coefficien t.W e p resen t differen t fo rm u lati on s fo r con tro lling the effects ofparam eter uncertain ty p resen t in the ob jective functi on o r con strain ts.A n algo rithm com b in ing GeneticA lgo rithm(GA)is p resen ted app lying the h ierarch ical op ti m izati on structu re.T he si m u lati on examp leshow s the feasib ility of the fo rm u lati on s.Key words: in terval p rogramm ing;non linear p rogramm ing;genetic algo rithm;decisi on m ak ing riskcoefficien t1 引言与传统的确定性数学规划不同,不确定系统优化问题中的部分参数是未知不确定的Λ按照这些不确定性参数表达方式的不同,可以将这类优化问题划分为随机规划(Stochastic P rogramm ing)、模糊规划(Fuzzy P rogramm ing)和区间参数规划(In terval P rogramm ing)[1]等三种主要形式Λ在随机规划中,决策者将不确定量看作是具有一定概率分布特性的随机变量Λ文献[2]与[3]提出了鲁棒优化(Robu st O p ti m iza2 ti on,RO)的概念,将非线性目标函数的期望值与方差进行加权平均,作为新的待优化的目标函数;在模糊规划中,决策者将不确定量看作是具有确定隶属度的模糊集Λ文献[4]对有约束条件的多个投资项目的选择问题,建立了一个模糊规划模型,并将其转化为一个线性规划模型Λ对于随机规划和模糊规划,决策者必须掌握决策变量的概率分布函数或隶属度函数Λ但实际上,要精确获得参数的这些性质往往很难,而获得这些参数的置信区间要容易得多Λ区间规划就是将目标函数或约收稿日期:2004203229资助项目:973计划资助(2002CB312200) 作者简介:蒋峥(1970-),男,湖北武汉人,博士研究生Λ研究领域为复杂工业过程智能优化ΛE2m ail:zjiang@ii pc.zju. ;戴连奎(1963-),男,浙江余杭人,工学博士,副教授Λ研究领域为复杂工业过程的建模、控制与智能优化ΛE2m ail: lkdai@ii ;吴铁军(1950-),男,浙江杭州人,工学博士,教授,博士生导师Λ研究领域为分布式智能系统控制与优化、微型及柔性机器人控制ΛE2m ail:tj w u@ii Λ束条件中的不确定性参数,以区间的形式给出并加以求解Λ文献[5]定义了区间线性规划的标准型,给出一种反映决策者满意度的区间数序关系,从而将区间不等式约束转化为确定型约束Λ文献[6]分别讨论了区间数线性规划问题保守可能解、保守必然解、冒进可能解和冒进必然解的最优性条件Λ文献[7]提出了一种基于模糊约束满意度的求解方法,把区间线性规划问题转化为确定型的一般参数规划问题来解决Λ文献[1]将系统可靠性优化设计问题描述为一个区间线性规划模型,提出了将区间规划模型转化为双目标规划模型,然后采用遗传算法求出双目标规划的Pareto 解Λ文献[8]提出了一种目标函数系数为区间数的区间线性规划的最大最小后悔解(m in i m ax ab so lu te regret )的启发式算法Λ目前对于区间不确定性规划问题的研究仅限于线性规划,但在实际的决策问题中,目标函数和约束条件函数往往是非线性的,如何在此情形下表达和处理决策者追求最优值和准备承担风险的能力是一个具有重要实际意义的研究领域Λ本文讨论区间不确定性非线性规划问题,引入决策风险因子,以反映决策者在追求最大目标函数值时所愿意承担的风险程度;同时,在目标函数中引入偏差惩罚项,以体现决策者对实际决策偏差大小的不同要求Λ由此将区间不确定性非线性规划问题转化为一个确定性的极大极小问题Λ2 区间非线性规划问题的确定化描述许多实际不确定性非线性系统的单目标优化问题可描述为[2]P1: m ax u J (y ,u ,w )(1a )sub .to:y =y (u ,w )(1b )y ∈[y m in ,y m ax ],u ∈[u m in ,u m ax ],w ∈[w m in ,w m ax ].(1c )其中,u ∈R m 为决策向量,y ∈R r 为系统约束输出,w ∈R q 为系统不确定参数,w m in 、w m ax 分别为w 置信区间的下界与上界ΖJ 通常是一个非线性目标函数,经常表示为收益Ζy =y (u ,w )表示包含有不确定参数的非线性等式约束Ζ针对上述优化问题,本文将不确定性的目标函数转化为一个确定性的极大极小问题;而对于不确定性的约束条件,本文仅考虑硬约束,即要求每个决策对所有不确定参数都是满足约束条件的Ζ下面首先讨论不确定性目标函数的转化问题Ζ211 不确定性目标函数的确定性转化对于优化问题P 1,给定一个决策u ∈[u m in ,u m ax ],则目标函数值J (u ,w )的变化区间可表示为7=[J m in (u ),J m ax (u )],其中J m in (u )=m in w ∈W J (u ,w ),J m ax (u )=m ax w ∈WJ (u ,w ),而区间W Χ{w w m in ≤w ≤w m ax }表示不确定参数w 的变化范围Ζ对于区间7中任意值Κ∈7,定义风险系数Α1,Α1=Κ-J m in (u )J m ax (u )-J m in (u ).(2)这里Α1表示因参数w 的不确定性而使决策u 实际获得的目标函数值大于等于Κ的风险因子,显然Α1∈[0,1]Ζ特别地,当Κ=J m in (u )时,Α1=0,表示决策者肯定能获得大于等于J m in (u )的目标函数值;当Κ=J m ax (u )时,Α1=1,表示决策者要想获得大于等于J m ax (u )的目标函数值所面临的风险最大Ζ将(2)式变换,得到Κ=Α1J m ax (u )+(1-Α1)J m in (u ),(3)(3)式表示在具有风险系数Α1的前提下,决策u 可以获得的最大目标函数值为ΚΖ于是,可将原不确定目标函数(1a )式转化为以下确定性的优化目标:m ax u Α1J m ax (u )+(1-Α1)J m in (u ),(4)其中,风险系数Α1∈[0,1]表示决策者在追求最大目标函数值时所愿意承担的风险程度Ζ此外,考虑到不确定参数w 会给决策u 实际获得的目标函数值J (u ,w )造成偏差,其最大偏差为d (u )=J m ax (u )-J m in (u ).(5)111第1期区间非线性规划问题的确定化描述及其递阶求解为了体现决策者在决策时对这种偏差大小的不同要求,本文在优化问题P 1的基础上分三种情况加以讨论:情况1:决策者要求偏差尽可能的小这时的优化目标可以用以下式子来表示m ax uΑ1J m ax (u )+(1-Α1)J m in (u )-M d (u ),(6)其中,M ≥0为一个反映目标函数大小与不确定性的平衡常数Ζ若决策者认为不确定性的影响小于追求最优值的要求,则M 取值应偏小Ζ反之,若决策者非常关注不确定性给决策结果造成偏差的后果,则M 取值应偏大Ζ情况2:决策者要求偏差严格限制在一定范围内这时的优化目标可以用以下式子来表示m ax u Α1J m ax (u )+(1-Α1)J m in (u )(7)sub.to:d (u )≤d m ax ,其中,d m ax >0为最大允许的偏差Ζ情况3:决策者要求偏差最好限制在一定范围内,即使超出该范围,也应尽可能的小这时的优化目标可以用以下式子来表示m ax u Α1J m ax (u )+(1-Α1)J m in (u )-M m ax (0,d (u )-d m ax ),(8)其中,M 为一个取值很大的正常数Ζ其实,情况3为情况1与情况2的综合反映Ζ若d m ax =0,则(8)式等价于(6)式;若M =+∞,则(8)式与(7)式等价Ζ(8)式的Α1J m ax (u )+(1-Α1)J m in (u )项反映了在风险因子Α1下所能取得的最优值,而M m ax (0,d (u )-d m ax )项反映了决策者对不确定参数给目标值造成偏差的容忍程度Ζ这样,(8)式就在风险因子意义下把问题P 1的不确定目标函数确定化了Ζ上述对目标函数的确定化方法可用下列数值例子来说明Ζ假设原目标函数为J (u ,w )=-0101u 2+u (w -8)-40,(9a )其中,决策量u ∈[100,1000],不确定参数w ∈[10,20]Ζ针对不确定参数w 取值的不同,目标函数与决策量u 的对应关系如图1所示,其中上边界即为J m ax (u ),下边界为J m in (u )Ζ假设按情况3的确定化方法,取M =100、d m ax =40,则确定化后的新目标函数为J θ(u )=Α1J m ax (u )+(1-Α1)J m in (u )-100m ax (0,d (u )-40)(9b )其中,Α1为风险系数Ζ212 约束条件中的不确定性考虑优化问题P 1,对于给定的决策u ∈[u m in ,u m ax ],定义y -j (u )Χm in w ∈W y j (u ,w ),y +j (u )Χm ax w ∈W y j (u ,w ),j =1,…,r .(10)本文仅考虑硬约束问题,即要求存在一个可行决策区域D ,使D 中任意一个决策u ∈D ,对任何w ∈W ,均满足y j m in ≤y -j (u )≤y +j (u )≤y j m ax , j =1,…,r .(11) 上述对约束条件的确定化方法可用下列数值例子来说明Ζ假设原约束条件为y (u ,w )=2w e -(u -2)22sin (013u )+4(1-w )e -(u -7)218sin (015u )+2,(12)其中,决策量u ∈[1,6],不确定参数w ∈[0,1],约束输出y ∈[112,412]Ζ211系统工程理论与实践2005年1月图1 目标函数值的不确定性图2 约束条件中的不确定性 如图2所示,因不确定参数w的取值不同,y(u,w)呈现为一个具有不同宽度的带状曲线簇,其上边界为y+(u),下边界为y-(u)Ζ假设要求112≤y(u,w)≤412,则对应的可行决策区域D为D={[1,1185], [3105,3172],[5151,6]}Ζ采用上述对约束条件的确定化方法,则确定化后的新的约束条件为y-(u)=m inw∈W y(u,w),y+(u)=m axw∈Wy(u,w)112≤y-(u)≤y+(u)≤412,1≤u≤6,其中,W=[0,1]表示不确定参数w的变化范围Ζ3 递阶优化算法通过上述讨论,原不确定性优化问题P1可转化为以下确定性优化命题:P2: m axuΑ1J m ax(u)+(1-Α1)J m in(u)-M m ax(0,d(u)-d m ax)(13) sub.to:y j m in≤y-j(u)≤y+j(u)≤y j m ax,j=1,…,r,u∈[u m in,u m ax]其中,y-j(u)=m inw∈W y j(u,w),y+j(u)=m axw∈Wy j(u,w)Ζ对于问题P2,由于目标函数和约束条件为非解析的非线性函数,采用基于导数的常规优化方法很难进行有效的求解,并且易陷入局部极值点Ζ而作为智能优化算法的代表之一的遗传算法,是一种随机优化和搜索方法,与目标函数是否可导无关,具有良好的全局优化性能和稳健性,适合于此类优化问题的求解Ζ另一方面,优化命题P2中存在着有待计算的J m ax(u)、J m in(u)、y-j(u)和y+j(u)的非线性子优化问题Ζ采用随机搜索策略求解P2时,参与搜索的种群规模越大,总的计算量就越大Ζ为了更好地适应大规模问题求解的实时性要求,本文采用递阶优化的方法来提高优化的性能Ζ递阶优化问题用来描述具有层次结构的决策问题,通常可归结为如下形式:上层决策者首先给定一个决策参数(或向量),下层决策者则在该参数下,根据自己的偏好在可能范围内优化自己的目标,上层再在下层的最佳反应的基础上,在可能范围内作出整体的最优决策Ζ由于下层决策可以采用并行计算的求解策略,这使得整体的寻优速度大幅度提高Ζ本文采用递阶遗传算法求解问题P2(如图3所示),其基本思想是:首先选取一定规模的上层决策{u i}构成初始种群,上层将相应的决策传递给下层单元,各下层单元再并行地计算J m ax(u i)、J m in(u i)、y+j(u i)和y-j(u i),并将结果反馈给上层,上层根据下层的反映对相应的决策作出评价,并进行遗传操作,寻求上层的最优决策u3Ζ算法实现步骤如下:1)给定风险因子Α1、平衡常数M≥0、惩罚因子M1>0、M2>0和最大允许偏差d m ax>0,随机产生规模为n的种群u i∈[u m in,u m ax],1≤i≤n,其中u i为种群中的第i个候选解Ζ同时设定群体进化代数;2)将种群中所有决策u i,1≤i≤n,分配到各下层计算单元(共r+1个);3)在其中r个下层计算单元,分别计算以下子优化问题:311第1期区间非线性规划问题的确定化描述及其递阶求解y +j (u i )=m ax w ∈W y j (u i ,w ),y -j (u i )=m in w ∈W y j (u i ,w ),1≤i ≤n ,1≤j ≤r ;(14) 在第r +1个下层计算单元,计算以下子优化问题:J m ax (u i )=m ax w ∈W J (u i ,w ),J m in (u i )=m in w ∈WJ (u i ,w ),1≤i ≤n .(15) 4)将y +j (u i ),y -j (u i ),J m ax (u i ),J m in (u i ),1≤j ≤r ,1≤i ≤n ,送回上层主计算单元;5)在主计算单元,对于种群中每一个候选解u i ,1≤i ≤n ,计算相应的综合目标函数:J θ(u i )=Α1J m ax (u i )+(1-Α1)J m in (u i )-M m ax (0,d (u i )-d m ax )-M 1∑r j =1m ax (0,yj m in -y -j (u i ))-M 2∑rj =1m ax (0,y +j (u i )-y j m ax ).(16) 6)保存至当前代为止的最优解u 3;7)如果已完成群体进化代数,转9),否则继续下一步;8)在式(16)的候选解目标评价基础上,进行复制、交叉、变异等遗传操作,产生新的种群,转2);9)最优解u 3输出Ζ图3 递阶优化算法框图对于问题P 2,采用递阶遗传算法和常规遗传算法的计算时间比较分析如下:假设遗传算法的种群规模为n ,迭代次数为m ,交叉概率为P c ,变异概率为P m Ζ由于每一个候选解的综合目标函数值的计算式(16)涉及到2(r +1)个子优化问题,设每一个子优化问题求解需要的计算时间为t f Ζ每次迭代中,除适应值计算外的其它运行时间设为t 0Ζ则在单台计算机上,采用常规遗传算法求解问题P 2所需机器运行时间t 1大致为:t 1=m [t 0+2(r +1)t f (p c +p m )n ]Ζ(17) 若在r +2台计算机上(其中1台作为上层主计算单元,其余r +1台用来并行地求解子优化问题(14)和(15)),采用递阶遗传算法求解问题P 2,所需机器运行时间t 2大致为:t 2=m [t 0+2t f (p c +p m )n +t c ],(18)其中t c 表示计算机间的通讯时间Ζ考虑到在通常情况下,有t f µt 0µt c ,p c µp m ,由式(17)和(18)我们可以估计出采用递阶遗传算法后,所需的计算时间占使用普通遗传算法求解所需时间的比值约为:t 2t 1=1r +1,(19)由此可见,对于问题P 2的求解,递阶遗传算法的寻优速度比常规遗传算法有很大提高Ζ4 计算举例考虑以下反应器温度过程控制的区间非线性规划问题[2]:411系统工程理论与实践2005年1月P3: m ax u x 2(150)(20)sub .to:d x 1(t )d t+2(010444+w 1)e -2500 Η(t )x 21(t )=0(21)d x 2(t )d t-(010444+w 1)e -2500 Η(t )x 21(t )+(688910+w 2)e -5000 Η(t )x 2(t )=0(22)d x 3(t )d t -(688910+w 2)e -5000 Η(t )x 2(t )=0(23)Η(t )=u 1(t -75)(t -150)11250-u 2t (t -150)5625+u 3t (t -75)11250(24)x 1(0)=2000,x 2(0)=0,x 3(0)=0x 1(150)-100≥0,x 3(150)-55≥0,Πw ∈W .其中,u =(u 1,u 2,u 3)为决策量,取值范围为:U ={u 298≤u i ≤398,i =1,2,3},w =(w 1,w 2)为不确定量,取值范围为:W ={w -010222≤w 1≤010222,-961446≤w 2≤961446}Ζ 如果给定决策量u 、不确定性参数w ,可以通过求解式(21)-(24)得到x 2(150),于是可以将u 、w 和x 2(150)之间的函数关系记作x 2(150)=J (u ,w )Ζ为叙述方便,引入下列符号:y 1(u ,w )=x 1(150)-100,y 2(u ,w )=x 3(150)-55,y -1(u )=m in w ∈W y 1(u ,w ),y -2(u )=m in w ∈W y 2(u ,w ),J m in (u )=m in w ∈WJ (u ,w ),J m ax (u )=m ax w ∈WJ (u ,w ),d (u )=J m ax (u )-J m in (u ).则按照本文提出的方法,确定化后的优化问题成为:m ax u(1-Α1)J m in (u )+Α1J m ax (u )-M m ax [0,d (u )-d m ax ]-M 1{m ax [0,-y -1(u )]+m ax [0,-y -2(u )]}(25)sub.to:u ∈U 假设在风险系数Α1下(25)式的最优解为u 3,最优值为Jθ3(Α1)=(1-Α1)J m in (u 3)+Α1J m ax (u 3)-M m ax [0,d (u 3)-d m ax ]-M 1{m ax [0,-y -1(u 3)]+m ax [0,-y -2(u 3)]}.最优解u 3下的偏差为d 3(Α1)=d (u 3)Ζ图4a Α1与J θ3(Α1)的关系 图4b Α1与d 3(Α1)的关系 采用第3节提出的递阶遗传算法求解问题(25),随机产生的初始种群规模取为n =30,群体进化代数取为m =100,惩罚因子取M 1=50,仿真结果如图4a 、图4b 所示Ζ当取风险因子Α1=016、平衡常数M =511第1期区间非线性规划问题的确定化描述及其递阶求解系统工程理论与实践2005年1月100和最大允许偏差d m ax=80时,对问题(25)寻优后的最优解为u3=(33212,31412,31610),转换后的问题P2的目标函数值为79312503Ζ将该最优决策u3代入原问题P1的目标函数,可计算出由于不确定参数w的存在,目标值x2(150)可能的变化范围为区间[74513,82512]Ζ 从仿真结果可以看出,目标函数值的大小与风险系数、最大允许偏差和平衡常数有着密切关系Ζ当风险系数越大,目标函数值就越大,这表明决策者要想获得更大的收益,决策所承担的风险也随着增大;当最大允许偏差取值越大,目标函数值也越大,这表明决策者若放宽不确定量给目标值造成影响的要求,决策者就可以有更大范围的决策选择机会,所获得的最优值也相应的增大Ζ而平衡常数的选择,反映了决策者决策时,权衡在追求最大收益和不确定量给决策结果造成负面影响之间的重要性孰轻孰重时的心态Ζ这三个参数的选择,在实际决策中(如风险投资业,军事领域等各行业),需按照上述原则,针对具体情况具体确定Ζ5 结论本文提出了一种新的区间参数不确定非线性规划的一般命题形式,并分别就不确定性参数出现在目标函数或约束条件中的不同情况,给出不同的表达形式Λ该形式能够恰当地反映出决策者在追求最优值时所准备承担的风险程度,同时也能反映出决策者对不确定参数给目标函数造成偏差程度的不同要求Λ针对该形式,本文提出的递阶遗传算法可以适应大规模问题求解的实时性要求,具有全局搜索特性,它的并行处理特性可较好地提高优化的性能Λ仿真结果表明该形式的可行性Λ参考文献:[1] Gen M,Cheng R.Op ti m al design of system reliab ility u sing in terval p rogramm ing and genetic algo rithm[J].Com2pu ters and Indu strial Engineering,1996,31(1):237-240.[2] D arlington J,Pan telides C C,R u stem B,T anyiB A.D ecreasing the sen sitivity of open2loop op ti m al so lu ti on s in de2cisi on m ak ing under uncertain ty[J].Eu ropean Jou rnal of Operati onal R esearch,2000,121(2):343-362.[3] D arlington J,Pan telides C C,R u stem B,T anyiB A.A n algo rithm fo r con strained non linear op ti m izati on under un2certain ty[J].A u tom atica,1999,35(2):217-228.[4] 宋业新,陈绵云,吴晓平.模糊多目标有约束投资项目选择建模[J].系统工程理论与实践,2002,22(5):115-119.SON G Ye2x in,CH EN M ian2yun,W U X iao2p ing.Fuzzy m u lti ob jects con strained investm en t p ro jects selecti on model2 ing[J].System s Engineering-T heo ry&P ractice,2002,22(5):115-119.[5] 郭均鹏,吴育华.区间线性规划的标准型及其求解[J].系统工程,2003,21(3):79-82.GUO Jun2peng,W U Yu2hua.Standard fo rm of in terval linear p rogramm ing and its so lu ti on[J].System s Engineer2 ing,2003,21(3):79-82.[6] 张吉军,樊玉英.区间数线性规划问题的最优性条件[J].运筹与管理,2003,12(2):44-47.ZHAN G J i2jun,FAN Yu2ying.T he op ti m ality conditi on s of in terval num ber linear p rogramm ing p rob lem[J].Opera2 ti on s R esearch and M anagem en t Science,2003,12(2):44-47.[7] 达庆利,刘新旺.区间数线性规划及其满意解[J].系统工程理论与实践,1999,19(4):3-7.DA Q ingli,L I U X inw ang.In terval num ber linear p rogramm ing and its satisfacto ry so lu ti on[J].System s Engineering -T heo ry&P ractice,1999,19(4):3-7.[8] M au sser H E,L aguna M.A heu ristic to m in i m ax ab so lu te regret fo r linear p rogram s w ith in terval ob jective functi oncoefficien ts[J].Eu ropean Jou rnal of Operati onal R esearch,1999,117(1):157-174.611。
