第五章线性规划
线性规划（Linear Programming，简记为LP）是数学规
划的一个重要的分支，其应用极其广泛．
1939年，前苏联数学家康托洛维奇（Л.B.Kah ）在《生产组织与计划中的数学方法》一书中，最早提出和研究
了线性规划问题．1947年美国数学家丹泽格（G. B. Dantzig）提出了一般线性规划的数学模型及求解线性规划的通用方法
─单纯形方法，为这门科学奠定了基础．此后30年，线性规
划的理论和算法逐步丰富和发展．1979年前苏联数学家哈奇
扬提出了利用求解线性不等式组的椭球法求解线性规划问题，这一工作有重要的理论意义，但实用价值不高．1984年在美
国工作的印度数学家卡玛卡(N. Karmarkar)提出了求解线性
规划的一个新的内点法，这是一个有实用价值的多项式时间
算法．这些为线性规划更好地应用于实际提供了完善的理论
基础和算法．
第一节
线性规划问题及其数学模型一、问题的提出
例1 某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知条件如表所示。问应如何安排计划使该工厂获
利最多？
ⅠⅡ现有资源
设备
原材料A 原材料B 1
4
2
4
8台时
16kg
12kg
每件利润23
ⅠⅡ现有资源
设备原材料A 原材料B 140
204
8台时16kg 12kg
每件利润
23
解: 设x 1、x 2 分别表示在计划期内产品Ⅰ、Ⅱ的产量。
12
max 23z x x =+..s t 1228
x x +≤1
416
x ≤2412x ≤12,0
x x ≥
二、线性规划问题的标准型
112211112211211222221122123max ..,,0n n n n n n m m m mn n m n z c x c x c x s t a x a x a x b a x a x a x b a x a x a x b x x x x =+++??+++=?
?+++=?
?
?+++=?
≥? ，
，其中1,,0
m b b ≥
1
1
max ..,1,2,,0,
1,2,,n
j j
j n
ij j i j j z c x s t a x b i m
x j n
=====≥=∑∑ 12(,,,)
T
n c c c =c 12(,,,)
T
n x x x =x 12(,,,)
T
m b b b =b 1112121
22212n n m m mn a a a a a a a a a ?????
?=??????
A
12[,,,]n = p p p
max ..()T
z s t ?=?
=≥??≥?
c x Ax b b x 001max ..()T
n j j j z s t x =?=??
=≥???≥?∑c x p b b x 00
对于不是标准形式的线性规划问题，可以通过下列方法将线性规划的数学模型化为标准形式：（1）目标函数的转换对min z 可以化max()z -（2）右端项的转换
对0i b <，给方程两边同时乘以1
-（3）约束条件的转换
约束条件为≤方程左边加上一个变量,称为松弛变量约束条件为≥方程左边减上一个变量,称为剩余变量（4）变量的非负约束
变量j x 无限制时，令,,0j j j j j x x x x x ''''''=-≥变量0j x ≤时，令j j
x x '=-
例将下列线性规划模型转化为标准形式
123123123123
12min 23..72325
00x x x s t x x x x x x x x x x x -+-??++≤??
-+≥??--=-?
≥≥??，
解（1）变量的非负约束令345
x x x =-1245
max 233x x x x -+-..s t
6
12457
x x x x x ++-+=712452
x x x x x -+--=12453225x x x x -++-=
§2 两变量线性规划问题的图解法
例1 求下列线性规划的解
12121212max ..284300z x x s t x x x x x x =+??+≤??≤??≤?
≥≥??，
解（1）画可行域
c A B D C 2
x 1x O （2）画出目标函数的梯度向量：
（3）作目标函数的一条等值线,120
x x z +=将等值线沿梯度方向移动当等值线即将离开可行
例2 求下列线性规划的解
12121212max 2..284300z x x s t x x x x x x =+??+≤??≤??≤?
≥≥??，
解（1）画可行域
c A B D C 2
x 1x O （2）画出目标函数的梯度向量：
（3）作目标函数的一条等值线,120
2x x z +=将等值线沿梯度方向移动当等值线即将离开可行域时与可行域“最后的交点点为问题的最优解
例3 求下列线性规划的解
12121212max ..
2200z x x s t x x x x x x =+??-≤??-≥-??≥≥?，
c
2
x 1
x O
无解
例4 求下列线性规划的解
12121212min 3..123600z x x s t x x x x x x =-??≤??≥??≥≥?++，
2
x 1
x O
线性规划问题的性质：
（1）线性规划的可行域为凸集，顶点个数有限．若可行域非空有界，则可行域为凸多边形．（2）线性规划可能有唯一最优解，可能有无数多个最优解，也可能无解最优解．无最优解可能是目标函数在可行域上无界，也可能可行域为空集．（３）若线性规划有最优解，则最优解必可在可行域的某个顶点达到．若两个顶点都为最优解，那么这两点连线上的所有点都是线性规划的最优解．
§3 线性规划解的概念及其性质
1 线性规划解的概念考虑线性规划问题
max ..()T
z s t ?=?
=≥??≥?
c x Ax b b x 00定义.1 矩阵A 中任何一组m 个线性无关的列向量构成的可逆矩阵B 称为线性规划的一个基矩阵
与这些列向量对应的变量称为基变量(basis variable ）
其余变量称为基对应的非基变量(nonbasis variable ）
B 若设一个基为12(,,)m B p p p = ，12,,,m x x x ——为基B 对应的基变量1,,m n x x + ——为基B 对应的非基变量
1B m x x x ????=??????
1m N n x x x +??
??=??????
12(,,,)
m m n ++= N p p p (,)
=A B N 从而
令
=Ax b 则(,)N x ??
=????B x B N b
1
1
B N
x B b B Nx --=-B N Bx Nx b
+=令0N x =则1
B x B b
-=1
0B b -??
??
??
——基本解（basis solution ）满足1
0B b -??≥????
,=≥0Ax b x 的基本解——基本可行解
（basis feasible solution ）对应的基称为可行基（feasible basis ）．
B 可以写成即:
定义4 若基本可行解中所有基变量都为正，这样的基本可行解称为非退化解（non-degenerate solution）．若基本可行解中某基变量为零，这样的基本可行解称为退化解（degenerate solution）．
例
12
12
1
12max ..28400z x x s t x x x x x =-??+≤??
≤??≥≥?，
标准化得：12123141234max ..28400,00z x x s t x x x x x x x x x =-??++=??+=??≥≥≥≥?，，12341210(,,,)1001??
==??
??
A p p p p 子阵
是否为基基变量
非基变量
基本解
目标函数值
134(,)
=B p p 34
,x x 12,x x (0,0,8,4)是231(,)
=B p p 31
,x x 24,x x (4,0,4,0)
312(,)
=B p p 12,x x 34
,x x (4,2,0,0)424(,)
=B p p 24
,x x 13,x x (0,4,0,4)-4
514(,)=B p p 14
,x x 23
,x x (8,0,0,4)
-是是
是
是042基
本可行
解1
x O
(4,0)
(4,2)
(0,4)
(8,0)
2
x 顶点
2 解的判别定理
定理1 最优解的判别准则设B 为线性规划LP 的一个基，
1(1)0
-≥B b 1(2)T T
--≥0
B
c B A c 则基对应的基本可行解1
-??
????0B b 是LP 的最优解．
1
(1,2,,)σ--== T
B
j j j c B p c j n 为变量对应的检验数
j x 112[0,,0,,,]
σσσ-++-= ，T T
B
m m n c B A c 显然基变量对应得检验数为零．
定理2 无穷多个最优解的判别定理
在线性规划的最优解中，某个非基变量对应的检验数为零，则线性规划有无数多最优解．定理3 无界解的判别定理
设B 为线性规划的一个可行基，若基本可行解中s x 对应的检验数0σ
-≤0s B p 则线性规划具有无界解（或称无解）．
某非基变量
五种最优化方法 1.最优化方法概述 1.1最优化问题的分类 1）无约束和有约束条件； 2）确定性和随机性最优问题（变量是否确定）； 3）线性优化与非线性优化（目标函数和约束条件是否线性）； 4）静态规划和动态规划（解是否随时间变化）。 1.2最优化问题的一般形式（有约束条件）： 式中f（X）称为目标函数（或求它的极小，或求它的极大），si（X）称为不等式约束，hj（X）称为等式约束。化过程就是优选X，使目标函数达到最优值。 2.牛顿法 2.1简介 1）解决的是无约束非线性规划问题； 2）是求解函数极值的一种方法； 3）是一种函数逼近法。 2.2原理和步骤
3.最速下降法（梯度法） 3.1最速下降法简介 1）解决的是无约束非线性规划问题； 2）是求解函数极值的一种方法； 3）沿函数在该点处目标函数下降最快的方向作为搜索方向； 3.2最速下降法算法原理和步骤
4.模式搜索法（步长加速法） 4.1简介 1）解决的是无约束非线性规划问题； 2）不需要求目标函数的导数，所以在解决不可导的函数或者求导异常麻烦的函数的优化问题时非常有效。 3）模式搜索法每一次迭代都是交替进行轴向移动和模式移动。轴向移动的目的是探测有利的下降方向，而模式移动的目的则是沿着有利方向加速移动。 4.2模式搜索法步骤
5.评价函数法 5.1简介 评价函数法是求解多目标优化问题中的一种主要方法。在许多实际问题中，衡量一个方案的好坏标准往往不止一个，多目标最优化的数学描述如下：min (f_1(x),f_2(x),...,f_k(x)) s.t. g(x)<=0 传统的多目标优化方法本质是将多目标优化中的各分目标函数，经处理或数学变换，转变成一个单目标函数，然后采用单目标优化技术求解。常用的方法有“线性加权和法”、“极大极小法”、“理想点法”。选取其中一种线性加权求合法介绍。 5.2线性加权求合法 6.遗传算法 智能优化方法是通过计算机学习和存贮大量的输入-输出模式映射关系，进
第五章线性规划在管理中的应用 某企业停止了生产一些已经不再获利的产品，这样就产生了一部分剩余生产力。管理层考虑将这些剩余生产力用于新产品Ⅰ、Ⅱ、Ⅲ的生产。可用的机器设备是限制新产品产量的主要因素，具体数据如下表： 司的利润最大化。 1、判别问题的线性规划数学模型类型。 2、描述该问题要作出决策的目标、决策的限制条件以及决策的总绩效测度。 3、建立该问题的线性规划数学模型。 4、用线性规划求解模型进行求解。 5、对求得的结果进行灵敏度分析（分别对最优解、最优值、相差值、松驰/剩余量、对偶价格、目标函数变量系数和常数项的变化范围进行详细分析）。 6、若销售部门表示，新产品Ⅰ、Ⅱ生产多少就能销售多少，而产品Ⅲ最少销售18件，请重新完成本题的1-5。 解： 1、本问题是资源分配型的线性规划数学模型。 2、该问题的决策目标是公司总的利润最大化，总利润为： + + 决策的限制条件： 8x1+ 4x2+ 6x3≤500 铣床限制条件 4x1+ 3x2≤350 车床限制条件 3x1+ x3≤150 磨床限制条件 即总绩效测试（目标函数）为： max z= + + 3、本问题的线性规划数学模型 max z= + + S．T．8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1+ x3≤150 x1≥0、x2≥0、x3≥0 4、用Excel线性规划求解模板求解结果：最优解（50，25，0），最优值：30元。 5、灵敏度分析
目标函数最优值为: 30 变量最优解相差值 x1 50 0 x2 25 0 x3 0 .083 约束松弛/剩余变量对偶价格 1 0 .05 2 75 0 3 0 .033 目标函数系数范围: 变量下限当前值上限 x1 .4 .5 无上限 x2 .1 .2 .25 x3 无下限.25 .333 常数项数范围: 约束下限当前值上限 1 400 500 600 2 275 350 无上限 3 150 （1）最优生产方案： 新产品Ⅰ生产50件、新产品Ⅱ生产25件、新产品Ⅲ不安排。最大利润值为30元。 （2）x3 的相差值是意味着，目前新产品Ⅲ不安排生产，是因为新产品Ⅲ的利润太低，若要使新产品Ⅲ值得生产，需要将当前新产品Ⅲ利润元/件，提高到元/件。 （3）三个约束的松弛/剩余变量0，75，0，表明铣床和磨床的可用工时已经用完，而车床的可用工时还剩余75个工时； 三个对偶价格，0，表明三种机床每增加一个工时可使公司增加的总利润额。 （4）目标函数系数范围 表明新产品Ⅰ的利润在元/件以上，新产品Ⅱ的利润在到之间，新产品Ⅲ的利润在以下，上述的最佳方案不变。 （5）常数项范围 表明铣床的可用条件在400到600工时之间、车铣床的可用条件在275工时以上、磨铣床的可用条件在到工时之间。各自每增加一个工时对总利润的贡献元，0元，元不变。 6、若产品Ⅲ最少销售18件，修改后的的数学模型是： max z= + + S．T．8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1+ x3≤150 x3≥18 x1≥0、x2≥0、x3≥0 这是一个混合型的线性规划问题。 代入求解模板得结果如下： 最优解（44，10，18），最优值：元。 灵敏度报告： 目标函数最优值为: 变量最优解相差值 x1 44 0 x2 10 0 x3 18 0 约束松弛/剩余变量对偶价格
线性规划法的数学模型如下： 设X1，X2，X3，…，X n为各变量，n为变量个数，m为约束条件数，a ij(i＝1，2…,m；j＝1，2…,n)为各种系数，b1,b2,b3,…，b m为常数，C1，C2,C3,…C n为目标函数系数，Z为目标值，则线性规划模型如下： a11X1＋a12X2＋…＋a1n X n≥(＝≤)b1 a21X1＋a22X2＋…＋a2n X n≥(＝≤)b2 ………………… a m1X1＋a m2X2＋…＋a mn X n≥(＝≤) b m X1，X2，…，X n≥0 目标函数Zmin（max）＝C1X1＋C2X2十…＋C n X n 线性规划计算方法: 鲜花店向李大民预定两种花卉——百合、玫瑰。其中每株收购价百合为4元,玫瑰为3元,鲜花店需要百合在1100～1400株之间,玫瑰在800～1200株之间,李大民只有资金5000元, 要去购买良种花苗, 在自家902m的温室中培育,每株苗价百合为2.5元,玫瑰为2元,由于百合与玫瑰生长所需采光条件的不同,百合每株大约占地0.052m，玫瑰每株大约占地0.032m，应如何配置才能使李大民获利最大? 数学建模：设种百合x1 株,玫瑰x2 株,则 2. 5 x1 + 2 x2 ≤5000 0. 05 x1 + 0. 03 x2 ≤90 x1 ≥1100 x1 ≤1400 x2 ≥800
x2 ≤1200 目标函数求最大值(即获利)Max z = (4 - 2. 5) x1 + (3 - 2) x2 = 1. 5 x + x1 可以看出,变量数为2,约束方程数为6,目标函数求最大值,打开线性规划计算软件,输入如下所示: 输入完成后点“计算”按纽，即可完成计算结果如下图：
最优化方法 一、引言 最优化理论与方法是一门应用性很强的年轻学科。它研究某些数学上定义的问题的最优解，即对于给出的实际问题，从众多的方案中选出最优方案。 虽然最优化可以追朔到十分古老的极值问题，然而，他成为一门独立的学科诗在上世纪40年代末，是在1947年Dantzing 提出求解一般线性规划问题的单纯型法之后。现在，解线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等各种最优化问题的理论的研究发展迅速，新方法不断出现，实际应用日益广泛。在电子计算机的推动下，最优化理论与方法在经济计划、工程设计、生产管理、交通运输等方面得到了广泛应用，成为一门十分活跃的学科。 现在大多数有代表性的最优化算法已有可以方便使用的软件包，如lindo\lingo 优化软件包。但有效利用这些成果是以有待解决的问题已被模型化成最优化问题的形式为前提的。要做到这点，要有深刻的洞察力和综合能力，这需要掌握最优化算法的结构和特点，并与专业知识的结合和兼蓄。 最优化有着丰富的内容和方法，本课我们主要介绍线性规和非线性规划的主要方法与理论他们是最优化理论的重要分支，也是最基本的部分。 第一部分：线性规划 第一章：单纯型法 第一节问题的引出: 例 1：某制造公司需要生产n 种产品，生产这n 种产品需要m 种不同的原材料，第i （i=1,2,.....m.。）种原材料的拥有量为b i 。实际情况很复杂，我们将其简化或理想化，只关注某个时间点的特定情况，第i 种原材料在某时间点的市场价格为ρi ，生产单位数量的第j 种产品需消耗第i 种原材料a ij 个单位。第j 种产品在同一时间点上的市场价格为σj 。 考虑问题一：如何安排1，2，…….n 种产品的生产，从而使收益最大 设第j 种的产量为j x 单位，第j 种产品的收益与市场销售价i σ有关，也与生产第j 种产 品所消耗的原材料费用1 m i j i i a ρ=∑有关，因此第j 种单位产品的纯收入为1 m j j ij i i c a σρ==-∑， 全部纯收入 j j c x ∑，此时0j x ≥。 而我们不可能超出原材料的拥有量生产产品。生产n 种产品时，所消耗的第i （i=1,2,.....m.。）种原材料的总量为 11221 n i i in n ij j j a x a x a x a x =++ +=∑
题目：用外点法求解非线性约束最优化问题 学院信息管理学院 学生姓名余楠学号 81320442 专业数量经济学届别 2013 指导教师易伟明职称教授 二O一三年十二月
用外点法求解非线性约束最优化问题 摘要 约束最优化问题是一类重要的数学规划问题。本文主要研究了用外点罚函数法对约束非线性规划问题进行求解。对于一个约束非线性规划用罚函数求解的基本思路是通过目标函数加上惩罚项，将原约束非线性规划问题转化为求解一系列无约束的极值问题。本文最后利用c语言编程得到满足允许误差内的最优解。 本文主要对一个约束非线性规划问题的实例，首先利用上述迭代的方法，计算出各迭代点的无约束极值问题的最优解。然后应用c语言编程，得到精确地最优解，需迭代四次次才使得ε≤0.001，得到的最优解为* X=(333 .0)T。 .0, 666 关键词：外点罚函数法非线性规划约束最优化迭代最优解
一、背景描述 线性规划的目标函数和约束条件都是决策变量的线性函数，但如果目标函数或约束条件中含有决策变量的非线性函数，就称为非线性规划。非线性规划与线性规划一样，也是运筹学的一个极为重要的分支，它在经济、管理、计划、统计以及军事、系统控制等方面得到越来越广泛的应用。 非线性规划模型的建立与线性规划模型的建立类似，但是非线性规划问题的求解却是至今为止的一个研究难题。虽然开发了很多求解非线性规划的算法，但是目前还没有适用于求解所有非线性规划问题的一般算法，每个方法都有自己特定的适用范围。 罚函数法是应用最广泛的一种求解非线性规划问题的数值解法，它的基本思路是通过目标函数加上惩罚项，将原约束非线性规划问题转化为求解一系列无约束的极值问题。这种惩罚体现在求解过程中，对于企图违反约束的那些迭代点，给予很大的目标函数值，迫使这一系列无约束问题的极小值点无限的向可行集（域）逼近，或者一直保持在可行集（域）内移动，直到收敛于原来约束问题的极小值点。 外点法的经济学解释如下：若把目标函数看成“价格”，约束条件看成某种“规定”，采购人员在规定的范围内采购时价格最便宜，但若违反了规定，就要按规定加收罚款。采购人员付出的总代价应是价格和罚款的综合。采购人员的目标是使总代价最小，当罚款规定的很苛刻时，违反规定支付的罚款很高。这就迫使采购人员在规定的范围内采购。数学上表现为罚因子足够大时，无约束极值问题的最优解应满足约束条件，而成为约束问题的最优解。 二、基础知识 2.1 约束非线性优化问题的最优条件 该问题是一个约束非线性优化问题，利用外点罚函数法求解该问题，约束非线性优化问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此有以下几个定理。
第五章线性规划在管理中的应用 5.1 某企业停止了生产一些已经不再获利的产品，这样就产生了一部分剩余生产力。管理层考虑将这些剩余生产力用于新产品Ⅰ、Ⅱ、Ⅲ的生产。可用的机器设备是限制新产品产量的主要因素，具体数据如下表： 量，使得公司的利润最大化。 1、判别问题的线性规划数学模型类型。 2、描述该问题要作出决策的目标、决策的限制条件以及决策的总绩效测度。 3、建立该问题的线性规划数学模型。 4、用线性规划求解模型进行求解。 5、对求得的结果进行灵敏度分析（分别对最优解、最优值、相差值、松驰/剩余量、对偶价格、目标函数变量系数和常数项的变化范围进行详细分析）。 6、若销售部门表示，新产品Ⅰ、Ⅱ生产多少就能销售多少，而产品Ⅲ最少销售18件，请重新完成本题的1-5。 解： 1、本问题是资源分配型的线性规划数学模型。 2、该问题的决策目标是公司总的利润最大化，总利润为： 0.5x1+ 0.2x2+ 0.25x3 决策的限制条件： 8x1+ 4x2+ 6x3≤500 铣床限制条件 4x1+ 3x2≤350 车床限制条件 3x1+ x3≤150 磨床限制条件 即总绩效测试（目标函数）为： max z= 0.5x1+ 0.2x2+ 0.25x3 3、本问题的线性规划数学模型 max z= 0.5x1+ 0.2x2+ 0.25x3 S．T．8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1+ x3≤150 x1≥0、x2≥0、x3≥0 4、用Excel线性规划求解模板求解结果：最优解（50，25，0），最优值：30元。 5、灵敏度分析
目标函数最优值为 : 30 变量最优解相差值 x1 50 0 x2 25 0 x3 0 .083 约束松弛/剩余变量对偶价格 1 0 .05 2 75 0 3 0 .033 目标函数系数范围 : 变量下限当前值上限 x1 .4 .5 无上限 x2 .1 .2 .25 x3 无下限 .25 .333 常数项数范围 : 约束下限当前值上限 1 400 500 600 2 275 350 无上限 3 37.5 150 187.5 （1）最优生产方案： 新产品Ⅰ生产50件、新产品Ⅱ生产25件、新产品Ⅲ不安排。最大利润值为30元。 （2）x3 的相差值是0.083意味着，目前新产品Ⅲ不安排生产，是因为新产品Ⅲ的利润太低，若要使新产品Ⅲ值得生产，需要将当前新产品Ⅲ利润0.25元/件，提高到0.333元/件。 （3）三个约束的松弛/剩余变量0，75，0，表明铣床和磨床的可用工时已经用完，而车床的可用工时还剩余75个工时； 三个对偶价格0.05，0，0.033表明三种机床每增加一个工时可使公司增加的总利润额。 （4）目标函数系数范围 表明新产品Ⅰ的利润在0.4元/件以上，新产品Ⅱ的利润在0.1到0.25之间，新产品Ⅲ的利润在0.333以下，上述的最佳方案不变。 （5）常数项范围 表明铣床的可用条件在400到600工时之间、车铣床的可用条件在275工时以上、磨铣床的可用条件在37.5到187.5工时之间。各自每增加一个工时对总利润的贡献0.05元，0元，0.033元不变。 6、若产品Ⅲ最少销售18件，修改后的的数学模型是： max z= 0.5x1+ 0.2x2+ 0.25x3 S．T．8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1+ x3≤150 x3≥18 x1≥0、x2≥0、x3≥0 这是一个混合型的线性规划问题。 代入求解模板得结果如下： 最优解（44，10，18），最优值：28.5元。 灵敏度报告： 目标函数最优值为 : 28.5 变量最优解相差值 x1 44 0 x2 10 0
最优化方法及其应用 作者：郭科 出版社：高等教育出版社 类别：不限 出版日期：20070701 最优化方法及其应用 的图书简介 系统地介绍了最优化的理论和计算方法,由浅入深,突出方法的原则,对最优化技术的理论作丁适当深度的讨论,着重强调方法与应用的有机结合,包括最优化问题总论,线性规划及其对偶问题,常用无约束最优化方法,动态规划,现代优化算法简介,其中前八章为传统优化算法,最后一章还给出了部分优化问题的设计实例,也可供一般工科研究生以及数学建模竞赛参赛人员和工程技术人员参考, 最优化方法及其应用 的pdf电子书下载 最优化方法及其应用 的电子版预览 第一章 最优化问题总论1.1 最优化问题数学模型1.2 最优化问题的算法1.3 最优化算法分类1.4
组合优化问題简卉习题一第二章 最优化问题的数学基础2.1 二次型与正定矩阵2.2 方向导数与梯度2.3 Hesse矩阵及泰勒展式2.4 极小点的判定条件2.5 锥、凸集、凸锥2.6 凸函数2.7 约束问题的最优性条件习题二第三章 线性规划及其对偶问题3.1线性规划数学模型基本原理3.2 线性规划迭代算法3.3 对偶问题的基本原理3.4 线性规划问题的灵敏度习题三第四章 一维搜索法4.1 搜索区间及其确定方法4.2 对分法4.3 Newton切线法4.4 黄金分割法4.5 抛物线插值法习题四第五章 常用无约束最优化方法5.1 最速下降法5.2 Newton法5.3 修正Newton法5.4 共轭方向法5.5 共轭梯度法5.6 变尺度法5.7 坐标轮换法5.8 单纯形法习題五第六章 常用约束最优化方法6.1外点罚函数法6.2 內点罚函数法6.3 混合罚函数法6.4 约束坐标轮换法6.5 复合形法习题六第七章 动态规划7.1 动态规划基本原理7.2 动态规划迭代算法7.3 动态规划有关说明习题七第八章 多目标优化8.1 多目标最优化问题的基本原理8.2 评价函数法8.3 分层求解法8.4目标规划法习题八第九章 现代优化算法简介9.1 模拟退火算法9.2遗传算法9.3 禁忌搜索算法9.4 人工神经网络第十章 最优化问题程序设计方法10.1 最优化问题建模的一般步骤10.2 常用最优化方法的特点及选用标准10.3 最优化问题编程的一般过程10.4 优化问题设计实例参考文献 更多 最优化方法及其应用 相关pdf电子书下载
习题二包括题目：P36页5（1）（4） 5（4）
习题三 包括题目：P61页1(1)(2); 3; 5; 6; 14；15(1) 1(1)(2)的解如下 3题的解如下
5,6题 14题解如下 14. 设22121212()(6)(233)f x x x x x x x =+++---, 求点在(4,6)T -处的牛顿方向。 解：已知 (1) (4,6)T x =-，由题意得 121212212121212(6)2(233)(3)()2(6)2(233)(3)x x x x x x x f x x x x x x x x +++-----?? ?= ?+++-----?? ∴ (1)1344()56g f x -?? =?= ??? 21212122211212122(3)22(3)(3)2(233)()22(3)(3)2(233)22(3)x x x x x x x f x x x x x x x x +--+--------? ??= ? +--------+--?? ∴ (1)2(1)1656()()564G x f x --?? =?= ?-?? (1)1 1/8007/400()7/4001/200G x --?? = ?--?? ∴ (1)(1)11141/100()574/100d G x g -?? =-= ?-?? 15（1）解如下 15. 用DFP 方法求下列问题的极小点 （1）22 121212min 353x x x x x x ++++ 解：取 (0) (1,1)T x =，0H I =时，DFP 法的第一步与最速下降法相同 2112352()156x x f x x x ++???= ?++??， (0)(1,1)T x =，(0) 10()12f x ???= ??? (1)0.07800.2936x -??= ?-??， (1) 1.3760() 1.1516f x ???= ?-?? 以下作第二次迭代 (1)(0) 1 1.07801.2936x x δ-??=-= ?-??， (1)(0) 18.6240()()13.1516f x f x γ-??=?-?= ?-?? 0110 111011101 T T T T H H H H H γγδδδγγγ=+-
陆吾生教授是加拿大维多利亚大学电气与计算机工程系 (Dept. of Elect. and Comp. Eng. University of Victoria) 的正教授, 且为我校兼职教授，曾多次来我校数学系电子系讲学。陆吾生教授的研究方向是：最优化理论和小波理论及其在1维和2维的数字信号处理、数字图像处理、控制系统优化方面的应用。 现陆吾生教授计划在 2007 年 10－11 月来校开设一门为期一个月的短期课程“最优化理论及其应用”（每周两次，每次两节课），对象是数学系、计算机系、电子系的教师、高年级本科生及研究生，以他在2006年出版的最优化理论的专著作为教材。欢迎数学系、计算机系、电子系的研究生及高年级本科生选修该短期课程，修毕的研究生及本科生可给学分。 上课地点及时间：每周二及周四下午2:00开始，在闵行新校区第三教学楼326教室。（自10月11日至11月8日） 下面是此课程的内容介绍。 ----------------------------------- 最优化方法及应用 I. 函数的最优化及应用 1.1 无约束和有约束的函数优化问题 1.2 有约束优化问题的Karush-Kuhn-Tucker条件 1.3 凸集、凸函数和凸规划 1.4 Wolfe对偶 1.5 线性规划与二次规划 1.6 半正定规划 1.7 二次凸锥规划 1.8 多项式规划 1.9解最优化问题的计算机软件 II 泛函的最优化及应用 2.1 有界变差函数 2.2 泛函的变分与泛函的极值问题 2.3 Euler-Lagrange方程 2.4 二维图像的Osher模型 2.5 泛函最优化方法在图像处理中的应用 2.5.1 噪声的消减 2.5.2 De-Blurring 2.5.3 Segmentation ----------------------------------------------- 注：这是一门约二十学时左右的短期课程，旨在介绍函数及泛函的最优化理论和方法，及其在信息处理中的应用。只要学过一元及多元微积分和线性代数的学生就能修读并听懂本课程。课程中涉及到的算法实现和应用举例都使用数学软件MATLAB 华东师大数学系
线性规划的方法及应用 1 引言 运筹学最初是由于第二次世界大战的军事需要而发展起来的，它是一种科学方法，是一种以定量的研究优化问题并寻求其确定解答的方法体系．线性规划（Linear Progromming ，简称LP ）是运筹学的一个重要分支，其研究始于20世纪30年代末，许多人把线性规划的发展列为20世纪中期最重要的科学进步之一．1947年美国的数学家丹泽格提出了一般的线性规划数学模型和求解线性规划问题的通用方法――单纯形法，从而使线性规划在理论上趋于成熟．此后随着电子计算机的出现，计算技术发展到一个高阶段，单纯形法步骤可以编成计算机程序，从而使线性规划在实际中的应用日益广泛和深入．目前，从解决工程问题的最优化问题到工业、农业、交通运输、军事国防等部门的计划管理与决策分析，乃至整个国民经济的综合平衡，线性规划都有用武之地，它已成为现代管理科学的重要基础之一． 2 线性规划的提出 经营管理中如何有效地利用现有人力物力完成更多的任务，或在预定的任务目标下，如何耗用最少的人力物力去实现．这类问题可以用数学语言表达，即先根据问题要达到的目标选取适当的变量，问题的目标通常用变量的函数形式（称为目标函数），对问题的限制条件用有关变量的等式或不等式表达（称为约束条件）．当变量连续取值，且目标函数和约束条件为线性时，称这类模型为线性规划的模型．有关对线性规划问题建模、求解和应用的研究构成了运筹学中的线性规划分支．线性规划实际上是:求一组变量的值，在满足一组约束条件下，求得目标函数的最优解.从而线性规划模型的基本结构为： ①变量：变量又叫未知数，它是实际系统的位置因素，也是决策系统中的可控因素，一般称为决策变量，常引用英文字母加下标来表示，如n x x x ,,,21 等． ②目标函数：将实际系统的目标用数学形式表示出来，就称为目标函数，线性规划的目标函数是求系统目标的数值，即极大值（如产值极大值，利润极大值）或极小值（如成本极小值，费用极小值等等）． ③约束条件：约束条件是指实现系统目标的限制因素．它涉及到企业内部条件和外部环境的各个方面，如原材料供应设备能力、计划指标．产品质量要求和市场销售状态等等，这些因素都对模型的变量起约束作用，故称其为约束条件．约束条件的数学表示有三种，即 ,,,线性规划的变量应为非负值，因为变量在实际问题中所代表的均为实物，所以不能为负． 线性规划问题有多种形式，函数有的要求实现最大化，有的要求最小化；约束条件可以是“ ”，
最优化方法及其Matlab程序设计 1.最优化方法概述 在生活和工作中，人们对于同一个问题往往会提出多个解决方案，并通过各方面的论证，从中提取最佳方案。最优化方法就是专门研究如何从多个方案中科学合理地提取出最佳方案的科学。最优化是每个人，每个单位所希望实现的事情。对于产品设计者来说，是考虑如何用最少的材料，最大的性能价格比，设计出满足市场需要的产品。对于企业的管理者来说，则是如何合理、充分使用现有的设备，减少库存，降低能耗，降低成本，以实现企业的最大利润。 由于优化问题无所不在，目前最优化方法的应用和研究已经深入到了生产和科研的各个领域，如土木工程、机械工程、化学工程、运输调度、生产控制、经济规划、经济管理等，并取得了显著的经济效益和社会效益。 用最优化方法解决最优化问题的技术称为最优化技术，它包含两个方面的内容： 1）建立数学模型。 即用数学语言来描述最优化问题。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。 2）数学求解。 数学模型建好以后，选择合理的最优化算法进行求解。 最优化方法的发展很快，现在已经包含有多个分支，如线性规划、整数规划、非线性规划、动态规划、多目标规划等。 2.最优化方法（算法）浅析 最优化方法求解很大程度上依赖于最优化算法的选择。这里，对最优化算法做一个简单的分类，并对一些比较常用的典型算法进行解析，旨在加深对一些最优化算法的理解。 最优化算法的分类方法很多，根据不同的分类依据可以得到不同的结果，这里根据优化算法对计算机技术的依赖程度，可以将最优化算法进行一个系统分类：线性规划与整数规划；非线性规划；智能优化方法；变分法与动态规划。 2.1 线性规划与整数规划 线性规划在工业、农业、商业、交通运输、军事和科研的各个研究领域有广泛应用。例如，在资源有限的情况下，如何合理使用人力、物力和资金等资源，以获取最大效益；如何组织生产、合理安排工艺流程或调制产品成分等，使所消耗的资源（人力、设备台时、资金、原始材料等）为最少等。 线性规划方法有单纯形方法、大M法、两阶段法等。 整数规划有割平面法、分枝定界法等。 2.2 非线性规划 20世纪中期，随着计算机技术的发展，出现了许多有效的算法——如一些非线性规划算法。非线性规划广泛用于机械设计、工程管理、经济生产、科学研究和军事等方面。
1 2 ( ( 最优化方法部分课后习题解答 1.一直优化问题的数学模型为： 习题一 min f (x ) = (x ? 3)2 + (x ? 4)2 ? g (x ) = x ? x ? 5 ≥ ? 1 1 2 2 ? 试用图解法求出： s .t . ?g 2 (x ) = ?x 1 ? x 2 + 5 ≥ 0 ?g (x ) = x ≥ 0 ? 3 1 ??g 4 (x ) = x 2 ≥ 0 （1） 无约束最优点，并求出最优值。 （2） 约束最优点，并求出其最优值。 （3） 如果加一个等式约束 h (x ) = x 1 ? x 2 = 0 ，其约束最优解是什么？ * 解 ：（1）在无约束条件下， f (x ) 的可行域在整个 x 1 0x 2 平面上，不难看出，当 x =（3，4） 时， f (x ) 取最小值，即，最优点为 x * =（3，4）：且最优值为： f (x * ) =0 （2）在约束条件下， f (x ) 的可行域为图中阴影部分所示，此时，求该问题的最优点就是 在约束集合即可行域中找一点 (x 1 , x 2 ) ，使其落在半径最小的同心圆上，显然，从图示中可 以看出，当 x * = 15 , 5 ) 时， f (x ) 所在的圆的半径最小。 4 4 ?g (x ) = x ? x ? 5 = 0 ? 15 ?x 1 = 其中：点为 g 1 (x ) 和 g 2 (x ) 的交点，令 ? 1 1 2 ? 2 求解得到： ? 4 5 即最优点为 x * = ? ?g 2 (x ) = ?x 1 ? x 2 + 5 = 0 15 , 5 ) ：最优值为： f (x * ) = 65 ?x = ?? 2 4 4 4 8 （3）.若增加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。 2.一个矩形无盖油箱的外部总面积限定为 S ，怎样设计可使油箱的容量最大？试列出这个优 化问题的数学模型，并回答这属于几维的优化问题. 解：列出这个优化问题的数学模型为： max f (x ) = x 1x 2 x 3 ?x 1x 2 + 2x 2 x 3 + 2x 1x 3 ≤ S
lingo 软件求解线性规划及灵敏度分析 注：以目标函数最大化为例进行讨论，对求最小的问题，有类似的分析方法！所有程序运行环境为lingo10。 一、用lingo 软件求解线性规划 例1： m a x 23..4310 3512,0 z x y s t x y x y x y =++≤+≤≥ 在模型窗口输入： model: max=2*x+3*y; 4*x+3*y<=10; 3*x+5*y<12; ! the optimal value is :7.454545 ; End 如图所示： 运行结果如下（点击 工具栏上的‘solve ’或点击菜单‘lingo ’下的‘solve ’即可）： Global optimal solution found. Objective value: 7.454545（最优解函数值） Infeasibilities: 0.000000 Total solver iterations: 2（迭代次数）
Variable （最优解） Value Reduced Cost X 1.272727 0.000000 Y 1.636364 0.000000 Row Slack or Surplus Dual Price 1 7.454545 1.000000 2 0.000000 0.9090909E-01 3 0.000000 0.5454545 例2： 12123124125m a x 54.. 390280450 z x x s t x x x x x x x x x x =+++=++=++=≥ 在模型窗口输入： model: max=5*x1+4*x2; x1+3*x2+x3=90; 2*x1+x2+x4=80; x1+x2+x5=45; end 运行（solve ）结果如下： Global optimal solution found. Objective value: 215.0000 Infeasibilities: 0.000000 Total solver iterations: 3 Variable Value Reduced Cost X1 35.00000 0.000000 X2 10.00000 0.000000 X3 25.00000 0.000000 X4 0.000000 1.000000 X5 0.000000 3.000000 Row Slack or Surplus Dual Price 1 215.0000 1.000000 2 0.000000 0.000000 3 0.000000 1.000000 4 0.000000 3.000000 例3
统计学梯度下降法（SGDs）易于实现，然而它有两个主要的缺陷。第一个缺陷是它需要手动调谐大量的参数，比如学习速率和收敛准则。第二个缺陷是它本质上是序列方法，不利于并行计算或分布式计算。（然而，在计算资源如RAM受限的情况下，序列方法倒是一个不错的选择。） 这里介绍一些非线性优化算法：牛顿算法，伪牛顿算法和共轭梯度法。其中，伪牛顿算法包括DFP、BFGS和L-BFGS算法。 考虑如下的无约束最小化问题： min x f(x)（1） 其中x=(x1,…,x N)T∈?N. 为简便起见，这里假设f是凸函数，且二阶连续可导。记（1）的解为x?. 牛顿算法（Newton‘s Method） 基本思想：在现有的极小点估计值的附近对f(x)做二阶泰勒展开，进而找到下 其中g(k)=?f(x)| x(k)是梯度矩阵，H(k)=?2f(x)| x(k) 是海森矩阵。 牛顿算法是一种具有二次收敛性的算法。对于非二次函数，若函数的二次性态较强，或迭代点已进入极小点的领域，则其收敛速度也是很快的，这是牛顿算法的主要优点。但牛顿算法由于迭代公式中没有步长因子，而是定步长迭代，所以对于非二次函数，有时会出现f(x(k+1))>f(x(k))的情况，这表明牛顿算法不能保证函数值稳定地下降。由此，人们提出了阻尼牛顿算法，在原始牛顿算法的第4步中，采用一维搜索（line search）算法给d(k)加一个步长因子λ(k)，其中： λ(k)=arg minλ∈?f(x(k)+λd(k))（2）一维搜索算法将另作介绍。 拟牛顿算法（Quasi-Newton Methods） 基本思想：不直接计算二阶偏导数，而是构造出近似海森矩阵（或海森矩阵的逆）的正定对称阵，在拟牛顿条件下优化目标函数。 下文中，用B表示对H的近似，用D表示对H?1的近似，并令s(k)=x(k+1)?x(k)，y(k)=g(k+1)?g(k).
第五章 线性规划（LP ） 第一节 向量和矩阵的基本知识 1．矩阵的概念 定义1：由t s ?个数ij c 排成的一个s 行t 列（数）表?? ?? ? ? ? ??st s s t t c c c c c c c c c 2122221 112 11叫做一个s 行t 列（或t s ?）矩阵。ij c 叫做这个矩阵的元素；常用大写字母A 、B 等表示矩阵，有时为明确t s ?矩阵记为t s A ?或() t s ij c A ?=。 注意： （1）解释几个术语：行、列、下标等。 （2）矩阵与行列式形式不同、意义不同，行列式表示一个数，矩阵只是一个数表；行列式要求行列数相同，而矩阵不然。 例如：（1）三阶矩阵 （2）45?的矩阵 210121312A ????=?????? B=1 1000011000 01100 001 1????? ??????? 向量是一种特殊的矩阵，分为行向量和列向量。 （1）行向量是1n ?的矩阵，它的具体形式为 12[,,,]n a a a a = ； （2）列向量是1n ?的矩阵，它的具体形式为： 12 n b b b b ??????=?????? ，或者12[,,,]T n b b b b = 。 例如： [1,2,,]a n = ；100b ???? ??=?????? 2．几种特殊矩阵 （1）零矩阵：元素全为零的矩阵；记为O 。
Note ：零矩阵只是给出了元素的特征（全为0），由于行、列数的不同有不同形式的零矩阵。例如 二阶零矩阵： 0000A ??=????，34?零矩阵：000000000000B ?? ??=?????? 。 （2）负矩阵：设()ij m n A a ?=，则称()ij m n a ?-为A 的负矩阵；记为A -。 Note ：负矩阵是相对于一个给定的矩阵而言的。 （3）方阵：行列数相同的矩阵。n 行n 列矩阵叫n 阶矩阵。 二阶方阵1112A -?? =???? ；四阶方阵12342 34134124 12 3A ??????=?????? . （4）单位矩阵：主对角线上元素全为1，其余元素全为0的方阵。 Note ： （1）单位阵是一类特殊方阵。 （2）定义给出了元素特征，由于阶数不同有不同形式的单位阵。n 阶单位矩阵记为n I 。 例如，三阶单位阵100010001A ????=?????? , （3）矩阵的相等：设A 、B 是数域F 上两个矩阵，若1）A 、B 具有相同的行数和列数；2） 对应位置上的元素相等。则称A 与B 相等。记为A=B 。 3、矩阵的运算及性质 (1）加法： 定义：设()ij m n A a ?=，()ij m n B b ?=；A 与B 的和为矩阵()ij ij m n a b ?+；记为A B +，即A B +=()ij ij m n a b ?+。 Note ：(1)注意可加的条件以及相加的结果，实质转化为数的加法运算。 (2）利用负矩阵可以定义矩阵的减法：设()ij m n A a ?=，()ij m n B b ?=，定义 A B -=()A B +-=()ij ij m n a b ?-。 例1：设121111121A ????=--????-??，111211321B -????=-?????? ，于是
简单线性规划问题的几种简单解法 依不拉音。司马义（吐鲁番市三堡中学，838009） “简单的线性规划问题”属于高中数学新课程必修5，进入了高考试题，并且保持了较大的考察比例，几乎是每年高考的必考内容，也是高中数学教学的一个难点。 简单的线性规划是指目标函数只含两个自变量的线性规划。简单线性规划问题的标准型为： 1112220(0)0(0),(),0(0) m m m A x B y C A x B y C m N z Ax By A x B y C +++≥≤??++≥≤?∈=+???++≥≤?L 约束条件 目标函数 ， 下面介绍简单线性规划问题的几种简单解法。 1. 图解法 第一步、画出约束条件表示的可行区域，这里有两种画可行区域的方法。 ⑴代点法：直线Ax+By+C=0（c 不为0）的某侧任取一点，把它的坐标代入不等式，若不等式成立，则不等式表示的区域在该点的那一侧；若不成立，则在另一侧。 ⑵B 判别法：若Ｂ＞0（＜０），则不等式Ax+By+C ＞0（＜０）表示的区域在直 线Ax+By+C ＝0的上方；若Ｂ＞０（＜０），则不等式Ax+By+C ＜０(＞0)表示的区域在直线Ax+By+C ＝0的下方。（即若B 与0的大小方向跟不等式的方向相同，则可行区域是边界线的上方；若B 与0的大小方向与不等式的方向相反，则可信分区域是边界线的下方） 用上面的两种方法画出可行区域是很简单，所以这里不必举例说明。 第二步、在画出的可行区域内求最优解（使目标函数取最大值或最小值的点），这 个可以用下面的两种办法解决。 ⑴y 轴上的截距法：若b >0，直线y a b x z b =- +所经过可行域上的点使其y 轴上的截距最大（最小）时，便是z 取得最大值（最小值）的点；若b <0，直线y a b x z b =-+所经过可行域上的点使其y 轴上的截距最大（最小）时，是z 取得最小值（最小值）的点（提醒：截距不是距离，截距可以取正负）。 例1．设x,y 满足约束条件x y y x y +≤≤≥???? ?10,,,求z x y =+2的最大值、最小值。 解：如图1作出可行域，因为y 的系数1大于0，目标函数z x y =+2表示直线 y x z =-+2在y 轴上的截距， 当直线过A （1，0）时，截距值最大z max =?+=2102，当直线过点O （0，0）时，截距值最小min 2000z =?+=。
精心整理 五种最优化方法 1.最优化方法概述 1.1最优化问题的分类 1）无约束和有约束条件； 2）确定性和随机性最优问题（变量是否确定）； 3 4 1.2 2. 2.1 1 2 3 2.2 3. 3.1 1 2 3 3.2 4.模式搜索法(步长加速法) 4.1简介 1）解决的是无约束非线性规划问题； 2）不需要求目标函数的导数，所以在解决不可导的函数或者求导异常麻烦的函数的优化问题时非常有效。 3）模式搜索法每一次迭代都是交替进行轴向移动和模式移动。轴向移动的目的是探测有利的下降
方向，而模式移动的目的则是沿着有利方向加速移动。 4.2模式搜索法步骤 5.评价函数法 5.1简介 评价函数法是求解多目标优化问题中的一种主要方法。在许多实际问题中，衡量一个方案的好坏标准往往不止一个，多目标最优化的数学描述如下： min(f_1(x),f_2(x),...,f_k(x)) s.t.g(x)<=0 传统的多目标优化方法本质是将多目标优化中的各分目标函数，经处理或数学变换，转变成一个单目标函数，然后采用单目标优化技术求解。常用的方法有“线性加权和法”、“极大极小法”、“理想点法”。选取其中一种线性加权求合法介绍。 5.2线性加权求合法 6.遗传算法 智能优化方法是通过计算机学习和存贮大量的输入-输出模式映射关系，进而达到优化的一种方法，主要有人工神经网络法，遗传算法和模拟退火法等。 6.1遗传算法基本概念 1.个体与种群 个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼。 种群就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。 2.适应度与适应度函数 适应度就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。 适应度函数就是问题中的全体个体与其适应度之间的一个对应关系。该函数就是遗传算法中指导搜索的评价函数。 6.2遗传算法基本流程 遗传算法的中心思想就是对一定数量个体组成的生物种群进行选择、交叉、变异等遗传操作,最终求得最优解或近似最优解。 遗传算法步骤 步1在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；
非线性约束最优化方法 ——乘子法 1.1 研究背景 最优化理论与方法是一门应用性相当广泛的学科，它的最优性主要表现在讨论决策问题的最佳选择性，讨论计算方法的理论性质，构造寻求最佳解的计算方法，以及实际计算能力。伴随着计算数学理论的发展、优化计算方法的进步以及计算机性能的迅速提高，规模越来越大的优化问题得到解决。因为最优化问题广泛见于经济计划、工程设计、生产管理、交通运输、国防等重要领域，它已受到政府部门、科研机构和产业部门的高度重视。然而，随着人们对模型精度和最优性的要求所得到的优化命题往往具有方程数多、变量维数高、非线性性强等特点，使得相关变量的存储、计算及命题的求解都相当困难，从而导致大规模非线性优化很难实现。因此，寻求高效、可靠的大规模非线性优化算法成为近年来研究的热点。 本文讨论的问题属于非线性约束规划的范畴，讨论了其中的非线性等式约束最优化问题方面的一些问题。 1.2非线性约束规划问题的研究方法 非线性约束规划问题的一般形式为 （NPL ） {}{} m in (),, s.t. ()0,1,2,...,, ()0,1,2,...,n i i f x x R c x i E l c x i I l l l m ∈=∈=≤∈=+++ 其中，(),()i f x c x 是连续可微的. 在求解线性约束优化问题时，可以利用约束问题本身的性质，
但是对于非线性约束规划问题，由于约束的非线性使得求解这类问题比较复杂、困难。因此，我们将约束问题转化为一系列无约束优化问题，通过求解一系列无约束优化问题，来得到约束优化问题的最优解。我们用到的几类主要的方法有:罚函数法、乘子法以及变尺度法。 传统上我们所提出的非线性约束最优化方法一般都遵循下列三个基本思路之一 1 借助反复的线性逼近把线性方法扩展到非线性优化问题中来 2 采用罚函数把约束非线性问题变换到一系列无约束问题 3 采用可变容差法以便同时容纳可行的和不可行的X 矢量 其中源于思路2 的乘子罚函数法具有适合于等式及不等式约束不要求初始点为严格内点，甚至不要求其为可行点对自由度的大小无任何要求等特点。 1.3乘子法 罚函数法的主要缺点在于需要惩罚因子趋于无穷大，才能得到约束问题的极小点，这会使罚函数的Hesse矩阵变得病态，给无约束问题的数值求解带来很大问题，为克服这一缺点，Hestenes和Powell 于1964年各自独立地提出乘子法。所谓乘子法是：由问题的Lagrange 函数出发，考虑它的精确惩罚，从而将约束优化问题化为单个函数的无约束优化问题，它同精确罚函数法一样，具有较好的收敛速度和数值稳定性，且避免了寻求精确罚函数法中关于罚参数阈值的困难，它们一直是求解约束优化问题的主要而有效的算法。 考虑如下非线性等式约束优化问题：