非线性规划概念 

　　非线性规划是具备非线性约束要求或指标函数的数学规划，是运筹学的一种要紧分支。非线性规划探讨一种n元实函数在一组等式或不等式的约束要求下的极值难题，且指标函数和约束要求至少有个是未知量的非线性函数。指标函数和约束要求皆是线性函数的情形则隶属线性规划。 

非线性规划进行史 

　　公元前 500年古希腊在讨论建筑美学中就已发觉了长方形长与宽的最好比重为0.618,称为黄金切割比。其倒数于今在优选法中仍获得广大利用。在微积分显露从前，已有众多学者最初探讨用数学方法解决最改良难题。比如阿基米德声明：给定周长，圆所包围的面积为第一大。这便是欧洲古代城堡差不多都建成圆形的原因。可是 最改良方法真实造成为科学方法规在17世纪今后。17世纪，I.牛顿和G.W.莱布尼茨在它们所组建的微积分中，提议求解具备若干自变量的实值函数的第一大值和最小值的方法。今后又进一步讨论具备未知函数的函数极值，从而造成变分法。这一时代的最改良方法可行称为古典最改良方法。 

　　最改良方法不同类别的最改良难题可行有不同的最改良方法，即便统一类别的难题也可有多个最改良方法。反之,某些最改良方法可适用于不同类别的模子。最改良难题的求解方法通常可行分成剖析法、干脆法、数值计算法和其它方法。 

· ① 剖析法：这类方法只适用于指标函数和约束要求有显著的剖析表明式的概况。求解方法是：先求出最优的必需要求，获得一组方程或不等式，再求解这组方程或不等式，通常是用求导数的方法或变分法求出必需要求，经过必需要求将难题简单化，因而也称间接法。 

· ② 干脆法：当指标函数较为繁杂或许不行用变量显函数描画时，没有办法用剖析法求必需要求。此时可采纳干脆搜索的方法通过多个次迭代搜索到最优点。这类方法常在 依据经历或经过试验获得所需结果。关于一维搜索(单变量极值难题)，最重要的用消去法或多项式插值法；关于多维搜索难题(多变量极值难题)最重要的利用爬山法。 

· ③ 数值计算法：这类方法也是一个干脆法。它以梯度法为根基，是以是一个剖析与数值计算相联合的方法。 

· ④ 其它方法：如网站最改良方法等。 

　　依据函数的剖析性质，还可行对各式方法作进一步分类。比如，假如指标函数和约束要求皆是线性的，就造成线性规划。线性规划有专门的解法，诸如单纯形法、解乘数法、椭球法和卡马卡法等。当指标或约束中有一非线性函数时,就造成非线性规划。当指标是两次的,而约束是线性时，则称为两次规划。两次规划的理论和方法都较老练。假如指标函数具备少许函数的平方和的方式，则有专门求解平方和难题的改良方法。指标函数具备多项式方式时，可造成一类几何规划。 

　　非线性规划是20世纪50年代才最初造成的一门新兴学科。1951年H.W.库恩和A.W.塔克发表的对于最优性要求(后来称为库恩·塔克要求)的论文是非线性规划正规诞生的一种要紧标记。在50年代还得出了可分离规划和两次规划的n种解法,他们大皆是以G.B.丹齐克提议的解线性规划的单纯形法为根基的。50年代末到60年代末显露了众多解非线性规划难题的有用的算法，70年代又获得进一步的进行。非线性规划在工程、治理、经济、科研、军事等方面都有 广大的利用，为最优设置提供了有力的用具。 

　　第两次全球大战首尾，源于军事上的须要和科学技艺和制造的快速进行，众多实质的最改良难题曾经没有办法用古典方法来解决，这就推进了近代最改良方法的发生。近代最改良方法的造成和进行进程中最要紧的事故有： 

· 以苏联康托罗维奇和美国G.B.丹齐克为代表的线性规划； 

· 以美国库恩和塔克尔为代表的非线性规划； 

· 以美国R.贝尔曼为代表的动态规划； 

· 以苏联庞特里亚金为代表的极大值原理等。 

　　这点方法后来都造成体制，成为近代很活泼的学科，对推进运筹学、治理科学、操控论和体系工程等学科的进行起了要紧效用 

非线性规划数学模子 

　　对实质规划难题作定量剖析，必需构建数学模子。构建数学模子起首要选定适当的指标变量和决策变量，并构建起指标变量与决策变量之中的函数关连,称之为指标函数。接下来将各式节制要求加以抽象,得出决策变量应满足的少许等式或不等式，称之为约束要求。非线性规划难题的通常数学模子可表述为求未知量x1,x2,…,xn,使满足约束要求： 

· gi(x1，…，xn)≥0　i＝1,…,m 

· hj(x1，…，xn)＝0　j＝1,…,p 

　　并使指标函数f(x1，…,xn)达到最小值(或第一大值)。此中f，诸gi和诸hj皆是定义在n维向量体积Rn的某子集D(定义域)上的实值函数,且至少有个是非线性函数。 

　　上述模子可简记为： 

· min f(x) 

· s.t. gi(x)≥0　i＝1,…,m 

· hj(x)＝0 j＝1,…,p 

　　此中x＝(x1，…,xn)隶属定义域D，符号min显示“求最小值”，符号s.t.显示“受约束于”。 

　　定义域D中满足约束要求的点称为难题的可以解。整体可以解所成的集合称为难题的可以集。关于一种可以解x*,假如存留x*的一种邻域，使指标函数在x*处的值f(x*)优于(指适中于或不小于)该邻域中全部其它可以解处的函数值，则称x*为难题的局部最优解（简单称呼局部解）。假如f(x*)优于一切可以解处的指标函数值,则称x*为难题的全体最优解（简单称呼全体解）。实用非线性规划难题请求全体解，而现存解法许多不过求出局部解。 

非线性规划求解法 

一维最改良方法 　 

　　指寻求一元函数在某区间上的最优值点的方法。这种方法不但有实用价格，况且大批多维最改良方法都依赖于一系列的一维最改良。经常使用的一维最改良方法有黄金切割法、切线法和插值法。 

· ① 黄金切割法：又称0.618法。它适用于单峰函数。其根本思想是：在初始寻查区间中设置一列点，经过逐次相比其函数值，一步步缩短寻查区间，以得出近似最优值点。 

· ② 切线法：又称牛顿法。它也是针对单峰函数的。其根本思想是：在一种猜测点周边将指标函数的导函数线性化，用此线性函数的零点作为新的猜测点，一步步迭代去逼近最优点。 

· ③ 插值法：又称多项式逼近法。其根本思想是用多项式（平常用两次或三次多项式）去拟合指标函数。 

　　另外，另有斐波那契法、割线法、有理插值法、分批搜索法等。 

没有约束最改良方法 　 

　　指寻求 n元实函数f在全个n维向量体积Rn上的最优值点的方法。这种方法的意义在于：尽管实用规划难题许多是有约束的，但众多约束最改良方法可将有约束难题转化为多个没有约束难题来求解。 

　　没有约束最改良方法许多是逐次一维搜索的迭代算法。这种迭代算法可分为两类。一类须要用指标函数的导函数,称为剖析法。另一类不涉及导数，只用到函数值,称为干脆法。这点迭代算法的根本思想是：在一种近似点处选定一种有益搜索方向,沿这种方向发展一维寻查,得出新的近似点。接下来对新点施行同样手续，如许来回迭代，直到满足预定的精度请求为止。依据搜索方向的取法不同，可行有各式算法。隶属剖析型的算法有： 

· ① 梯度法：又称最速下调法。这是早期的剖析法，收敛速度较慢。 

· ② 牛顿法：收敛速度快，但不固定，计算也较难题。 

· ③ 共轭梯度法：收敛较快，成果较好。 

· ④ 变尺度法：这是一类效能较高的方法。此中达维登-弗莱彻-鲍威尔变尺度法，简单称呼 DFP法，是最经常使用的方法。 

　　隶属干脆型的算法有交替方向法（又称坐标轮换法）、形式搜索法、旋转方向法、鲍威尔共轭方向法和单纯形提速法等。 

约束最改良方法 

　　指前述通常非线性规划模子的求解方法。经常使用的约束最改良方法有四种。 

· ① 拉格朗日乘子法：它是将原难题转化为求拉格朗日函数的驻点。 

· ② 制约函数法：又称系列没有约束最小化方法，简单称呼SUMT法。它又分两类，一类叫处罚函数法，或称外点法；另一类叫阻碍函数法，或称内点法。他们皆是将原难题转化为一系列没有约束难题来求解。 

· ③ 可以方向法：这是一类经过逐次选取可以下调方向去逼近最优点的迭代算法。如佐坦迪克法、弗兰克－沃尔夫法、投影梯度法和简约梯度法都隶属此类算法。 

· ④ 近似型算法：这种算法包括序贯线性规划法和序贯两次规划法。前者将原难题化为一系列线性规划难题求解，后者将原难题化为一系列两次规划难题求解。 

非线性规划分类 

凸规划 

　　这是一类特殊的非线性规划。在前述非线性规划数学模子中，若f是凸函数，诸gi皆是凹函数,诸hj皆是一次函数，则称之为凸规划。所谓f是凸函数,是指f有如是性质：它的定义域是凸集,且关于定义域中任意两点x和y及任一小于1的正数α，下式都成立： 

　　　　　　　　　　　　　　　　　　　　　　　　　　　　f((1-α)x +αy)α≤(1-α)f(x)+αf(y) 

　　将上述不等式中的不等号反向即得凹函数的定义。所谓凸集，是指具备如是性质的集合：连结集合中任意两点的直线段上的点悉数隶属该集合。关于通常的非线性规划难题，局部解未必是全体解。但凸规划的局部解必为全体解，况且凸规划的可以集和最优解集皆是凸集。 

两次规划 

　　一类特殊的非线性规划。它的指标函数是两次函数，约束要求是线性的。求解两次规划的方法好多。较简便易好的是沃尔夫法。它是根据库恩·塔克要求，在线性规划单纯形法的根基上加以修正而成的。另外另有莱姆基法、毕尔法、凯勒法等。 

几何规划 

　　一类特殊的非线性规划。它的指标函数和约束函数皆是正定多项式（或称正项式）。几何规划自身通常非是凸规划，但经适当变量替换，即可变为凸规划。几何规划的局部最优解必为全体最优解。求解几何规划的方法有两类。一类是经过对偶规划去求解；另一类是干脆求解原规划，这种算法许多构建在依据几何不等式将多项式转化为单项式的思想上。 

非线性规划的利用 

　　非线性规划在经营治理、工程设置、科学探讨、军事指挥等方面普及地存留着最改良难题。比如：如何在现存人工、物力、财力要求下合乎道理布置产物制造，以取得最高的利润；如何设置某种产物，在满足规格、功能请求的前提下，达到最低的本钱；如何确定一种自动操控体系的某些参数，使体系的事业状况最好；如何分配一种能源体系中各电站的负荷，在确保必定目标请求的前提下，使总耗费最小；如何布置储存储量，既能确保供给，又使库存费率最低；如何组织货源，既能满足顾客须要，又使资金盘活最快等。关于静态的最改良难题，当指标函数或约束要求显露未知量的非线性函数，且不便于线性化，或勉强线性化后会招致较大误差时，就可利用非线性规划的方法去料理。 

   凡本网注明稿件来源“华夏商业网”的全部文字、相片稿件，均归本网全部。全部媒体、网络或私人如需转载，经本网合同受权，转载时请注明稿件来自：华夏商业网，违者责任自负。