运筹学——约束极值问题

在数学优化问题中，当我们寻找某个函数在满足一定约束条件下的极值（最大值或最小值）时，我们通常面对的是带有约束条件的优化问题。

这个问题可以通过拉格朗日乘数法（Lagrange Multiplier Method）或者KKT条件（Karush-Kuhn-Tucker Conditions，对于非线性优化问题中的约束条件）等方法来解决。

例如，设有函数f(x, y)要在区域D内找极值，区域D由g(x, y)=c这样的一组或几组约束条件定义，这里的c是一个常数。

拉格朗日乘数法的基本思想是构造拉格朗日函数L(x, y, λ) = f(x, y) - λ(g(x, y) - c)，其中λ是拉格朗日乘子。

接下来需要求解L(x, y, λ)的偏导数，并令它们等于零，得到一组方程组，解这个方程组就可以找到可能的极值点。

对于KKT条件，它扩展了拉格朗日乘数法，适用于更广泛的优化问题，包括不等式约束。

在满足KKT条件的情况下，优化问题的解有可能是最优解。

具体步骤如下：
1.构造拉格朗日函数（若有不等式约束，需要构造广义拉格朗日函数）。

2.对目标函数和所有的约束函数分别求偏导数，并令它们等于零，得到必要条
件。

3.检验求得的点是否满足KKT条件，包括互补松弛条件、梯度条件以及可行
性条件（即该点必须位于可行域内）。

4.对于可能的极值点，还需进行二阶条件检验（如海森矩阵判别法）来判断是
局部极大值、局部极小值还是鞍点。

通过这些方法，我们可以在给定约束条件下寻找到函数的极值点。

第七章约束极值问题1．库恩—塔克条件设X*是非线性规划的极小点，而且与X*点的各起约束作用的梯度线性无关，则存在向量，使下述条件成立上述条件常称为K一Τ条件，满足这个条件的点(它当然也满足非线性规划的所有约束条件)称为库恩—塔克点(或K—Τ点)。

2．制约函数(1)常用的制约函数基本上有两类：一为惩罚函数(或称罚函数)，一为障碍函数，对于这两种函数，SUMT有外点法和内点法。

(2)外点法的迭代步骤如下：①取M1>0(例如说取M1=1)，允许误差ε>0，并令k：=1。

②求无约束问题的最优解：③若对某一个j(1≤j≤l)有-gi(X(k))≥ε则取Mk+1>Mk(例如，Mk+1=cMk，c=5或10)令 k：=k+1并转向第2步。

否则，停止迭代，得Xmin≈X(k)(3)内点法迭代步骤。

①取ri >0(例如，r1=1)，允许误差ε>0。

②找出一可行内点X(0)∈R0，并令k：=1。

③构造障碍函数，障碍项可采用倒数函数，也可采用对数函数。

④以X(k-1)∈R0为初始点，并对障碍函数进行无约束极小化(在R0内)3．可行方向法的迭代步骤(1)确定允许误差ε1>0和ε2>0，选初始近似点X(0)∈R，并令k：=0。

(2)确定起作用约束指标集。

J(X(k))={j｜gi(X(k))=0，1≤j≤l)①若J(X(k))= ∅ (∅为空集)，而且‖▽f(X(k))‖2≤ε1，停止迭代，得点X(k)；②若J(X(k))= ∅，但▽‖f(X k)‖2>ε1，则取搜索方向D(k)=-▽f(X(k))，然后转向第(5)步；③若J(X(k))=∅，转下一步。

(3)求解线性规划。

设它的最优解是(D(k)，ηk)(4)检验是否满足｜ηk｜≤ε2。

若满足则停止迭代，得到点X(k)；否则，以D(k)为搜索方向，并转向下一步。

(5)解下述一维极值问题。

(6)令 X(k-1)=X(k)+λkD(k)k：=k+1转回第(2)步。

第四章 非线性规划⎧⎪⎧⎨⎨⎪⎩⎩无约束最优化问题线性规划约束最优化问题非线性规划⎧⎨⎩凸规划约束最优化问题非凸规划⎧⎨⎩直接解法约束最优化问题求解方法间接解法间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。

由于这类方法可以选用有效的无约束优化方法，且易于处理同时具有不等式约束和等式约束的问题，因而在工程优化中得到了广泛的应用。

直接解法是在满足不等式约束的可行设汁区域内直接按索问题的约束最优解。

第一节 目标函数的约束极值问题所谓约束优化设计问题的最优性条件．就是指在满足等式和不等式约束条件下，其目标函数值最小的点必须满足的条件，须注意的是，这只是对约束的局部最优解而言。

对于带有约束条件的目标函数，其求最优解的过程可归结为：一、约束与方向的定义 一）起作用约束与松弛约束对于一个不等式约束()0g X ≤来说，如果所讨论的设计点()k X 使该约束()0g X =(或者说()k X当时正处在该约束的边界上)时，则称这个约束是()k X点的一个起作用约束或紧约束，而其他满足()0g X <的约束称为松弛约束。

冗余约束40g ≤当一个设计点同时有几个约束起作用时，即可定义起作用约束集合为{}()()()|()0,1,2,,k k u I X u g X u m ===其意义是对()k X点此时所有起作用约束下标的集合。

二）冗余约束如果一个不等式约束条件的约束面(即()0g X =)对可行域的大小不发生影响，或是约束面不与可行域D 相交，即此约束称为冗余约束。

三）可行方向可行方向：一个设计点()k X 在可行域内，沿某一个方向S 移动，仍可得到一个属于可行域的新点，则称该方向为可行方向。

1）设计点为自由点 设计点()k X 在可行域内是一个自由点，在各个方向上都可以作出移动得到新点仍属于可行域，如图所示。

2）设计点为约束边界点当设计点()k X 处于起作用约束i g 上时，它的移动就会受到可行性的限制。

§6 多目标决策分析简介 一、问题的提出如设计导弹, 射程远, 耗料少, 命中高等多目标. 如企业生产, 费用最少, 质量最好, 利润最大等. 一般只能是兼顾, 满意等 二、基本概念 一般形式12min (),(),...,():()0,1,2,...,p i V f x f x f x VP g x i m ⎧⎡⎤=⎪⎣⎦⎨≥=⎪⎩其中12(),(),...,()p f x f x f x 为目标函数,()0i g x ≥为约束条件, x 为决策变量. 记{|()0,1,...,}i R x g x i m =≥=,称为VP 的可行解集(决策空间), F(R)=为VP 像集. 定义1 设x R ∈, 若对x R ∀∈, 有()(),1,2,...,i i f x f x i m ≤=则称x 为VP 的绝对最优解, 解集记ab R *.一般很难, 或根本不存在, 故引入非劣解或有效解. 意大利经济学家Pareto:2f 1f 12((),())f x f x g当一个国家的资源和产品是以这样一种方式配置时，即没有一种重新配置，能够在不使一个其他人的生活恶化的情况下改善任何人的生活， 则可以说处于Pareto 最优.定义2设x R ∈, 若不存在x R ∈, 使()(),1,2,...,i i f x f x i p ≤=且至少有一个()()j j f x f x <, 则称x 为VP 的有效解 (或Pareto 最优解),()f x 称为有效点.2f 1f 12((),())f x f x •有效解集记为e R *和有效点集记为e F *常转化为加权形式的一个单目标函数1min ()():pj j j f x P x R λλ=⎧⎪⎨⎪∈⎩∑, 其中10,1p j j j λλ=≥=∑ (12(,,...,)T p λλλλ=,不加证明地引入: 定理1 设x 是单目标问题()P λ的最优解, 若下面两个条件之一成立, 则e x R *∈ 1) 0,1,2,...,j j p λ>=; 2) x 是()P λ的惟一解.定理2 设12(),(),...,()p f x f x f x 是凸函数. 若设x 是多目标问题VP 的有效解, 则存在λΛ+∈,使得x 是()P λ的最优解.三、权系数的确定这里假设: 决策者是根据综合效用(最大)来决策, 则基本思想为: 对重要的分量()j f x , 给大权. 即假设决策者的效用函数为:1()()pi i i u x f x λ==∑其中()i f x 为给出的每个属性的效用函数, 只要再确定权系数i λ, 就可求出使max ()u x 的决策(或解).确定i λ方法有: 1. 专家法 首先给专家填表, 然后汇总, 如右表 算出均值j λ,算出偏差||ij ij j ∆λλ=-, 让偏差大的发言,1212111212122212.........1...2..................n nn n K K Kny y y Kλλλλλλλλλλλλ专家修改权系数, 直到基本满意为止. 有一定的科学性.2. 特征向量法利用AHP 法确定权系数, 即确定111212122212//...///.../............//.../n n n n n n ww A λλλλλλλλλλλλλλλλ⎡⎤⎢⎥⎢⎥≈⎢⎥⎢⎥⎢⎥⎣⎦判断CI 满意后, 求出max λ, 求出特征向量λ即为权系数.四、有限方案的多目标决策方法(关于max 的) 1. 决策矩阵及其规范化设12{,,...,}m X X X X =为可行方案,12{,,...,}n Y y y y =为属性集(相当于各目标)每个方案i X 关于属 性j y 的结果记为:(),1,...,,1,...,ij j ij y f x i m j n === 作决策矩阵, 如右图.1211112122122212...........................nn n mm m mny y y X y y y Xy y y X y y y 属性方案统一量纲的方法有(各目标物理量不一致) (1) 列向量规范化:21/mij ij iji z y y==∑(2) 线性变换, 设maxmax jij iy y =若希望j y 愈大愈好, 则令max/ij ij jz y y =若希望j y 愈小愈好, 则令max1/ij ij jz y y =-(注:各目标都归结为最大, 如设01i y ≤≤, 则12[min ,max ]y y →12[max(1),max ]y y -(3) 其它变换若望i y 大, 则选min max min ij j ij j j y y z y y -=-,若望i y 小, 则选max max min j ij ij jjy y z yy-=-2. 简单线性加权法设()j u ⋅为第j 个目标的效用值, 通过求1max ()nj j x Rj u u x λ∈==∑选择使综合效用值u 最大的方案作为最优方案. 例 某人拟 购买一套住房, 有四处地点可 选, 有关信息 如右表.解 设决策人对各属性比较后得2123451234(m )(km)3.010010772.5808351.850205112.2701258y y y y y X X X X 价格面积距离设备环境方案万元1313-表11/31/21/41/531211/221/211/21/24121152211A ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦价格面积距离设备环境 用AHP 方法, 可求得特征向量(已作归一化)(0.0598,0.1942,0.1181,0.2363,0.3916)T λ=clear;clca=[1 1/3 1/2 1/4 1/5; 3 1 2 1 1/2; 2 1/2 1 1/2 1/2; 4 1 2 1 1 ;5 2 2 1 1];n=5;for i=1:5temp=1;for j=1:5 temp=temp*a(i,j);end; w(i)=temp^(1/n);end;wsum=sum(w);w=w/wsumlmbdmax=(1./w)*a*w'/n[v,d]=eig(a)(有误差)规范化表对第1, 3列用maxmax minj ijijj jy yzy y-=-规范化;对第2, 4, 5列用minmax minij jijj jy yzy y-=-规范化;2123451 2 3 4(m)(km)3.01001077 2.5808351.850205112.2701258 y y y y yX X X X 价格面积距离设备环境方案万元010.83310.3330.4170.61001000.510.6670.40.6670.50.667Z ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦然后计算出每个方案i X 的综合效用1()ni j ij j u X z λ==∑得到: 1()0.6593u X =, 2()0.2596u X =,3()0.5696u X =, 4()0.5757u X =,所以选第1方案.***补充: 1. 基本解法例1设21()2f x x x =-2,01()23,12x x f x x x ≤≤⎧=⎨-+≤≤⎩ [0,2],R =求max ()x RV F x ∈-.解单个最优解(0)111(1)max ()ff f x ==;(0)222(1)max ()f f f x ==是同一个点, 所以1x =是问题的最优解.11f 2f 1f x122f2. 变量空间与目标函数空间的图解法clear;clf;x=[0:1/50:1];f1=2*x-x.^2; f2=x; for i=1:size(x,2)subplot(121);axis([0,2,-1,1]);plot(x(i),f1(i),'.');hold on;plot(x(i),f2(i),'.'); subplot(122);axis([0 1 -1 1]);plot(f1(i),f2(i),'.');hold on; pause(0.1); end2()f βg 1f 12(1)1()(1)1f f x f *⎡⎤⎡⎤==⎢⎥⎢⎥⎣⎦⎣⎦()f α2f g 11f 2f 1f x 122f |α|βx−−→x=[1:1/50:2]; f1=2*x-x.^2; f2=-2*x+3; for i=1:size(x,2)subplot(121);plot(x(i),f1(i),'.');hold on;plot(x(i),f2(i),'.'); subplot(122);plot(f1(i),f2(i),'.');hold on; pause(0.1); end例2 设212()2,(),[0,2]f x x x f x x R =-==,求最大. 解 易得单独的(1)(2)1,2x x ==, 无公共解.1f 2f 11f 2f 2f ()f α'()f α()f βg gg 1[1,2]内都是非劣解.例3 设21()2,f x x x =- 22()(123615)8,f x x x =-+-[0,2]R =,求最大max ()x RV F x ∈-. 解 易求得(1)(2)1, 1.5x x ==, 无公共解. [1,1.5]内都是非劣解.2f 11f 2f 2f 11f 1.5clear;clf;x=[0:1/50:2]; f1=2*x-x.^2; f2=(-12*x.^2+36*x-15)/8; for i=1:size(x,2)subplot(121);axis([0,2,-2,2]);plot(x(i),f1(i),'.');hold on;plot(x(i),f2(i),'.'); subplot(122);axis([0 1 -2 2]);plot(f1(i),f2(i),'.');hold on; pause(0.1); endsubplot(121);grid on;subplot(122);grid on;例4 设112()32,f x x x =-+ 212()2f x x x =+1212122318:2100,0x x R x x x x --+⎧⎪--+⎨⎪≥≥⎩, 求max ()x RV F x ∈-.解得(0,6)是单独最优解, 但这一解可接受.例5 设112()32,f x x x =-+ 212()43f x x x =+,R 同例4, 求max ()x RV F x ∈-. 解 易得(1)(0,6)x =,(2)(3,4)x =非最优解, 但非劣解.62x 1x 112f =212f =(3,4)B AC 2f 1f 1A 'B 'C 'g g g这两点连线上的点都是非劣解.%p439%%%%例666666666666666%%第一段 clf;112f =224f =62x 1x (3,4)A B (5,0)C 2f 1f 1A 'B 'C 'g g gx1=[0:1/10:5];x2=zeros(1,size(x1,2));for i=1:size(x1,2)subplot(121);axis([0 6 0 6]);hold on;plot(x1(i),x2(i),'.');f1=-3*x1(i)+2*x2(i);f2=x1(i)+2*x2(i);subplot(122);axis([-16 12 0 12]); hold on; plot(f1,f2,'.');pause(0.1);endpause;%%第2段x1=[5:-1/10:3];x2=10-2*x1;for i=1:size(x1,2)subplot(121); %axis([0 6 0 6]);hold on;plot(x1(i),x2(i),'.');f1=-3*x1(i)+2*x2(i);f2=x1(i)+2*x2(i);subplot(122);%axis([-16 12 0 12]); hold on;plot(f1,f2,'.');pause(0.1);endpause;%%第3段x1=[3:-1/10:0];x2=(18-2*x1)/3;for i=1:size(x1,2)subplot(121);%axis([0 6 0 6]);hold on;plot(x1(i),x2(i),'.');f1=-3*x1(i)+2*x2(i);f2=x1(i)+2*x2(i);subplot(122);%axis([-16 12 0 12]); hold on;plot(f1,f2,'.');pause(0.1);endpause;%%第4段x2=[6:-1/10:0];x1=zeros(1,size(x2,2));for i=1:size(x1,2)subplot(121);%axis([0 6 0 6]);hold on;plot(x1(i),x2(i),'.');f1=-3*x1(i)+2*x2(i);f2=x1(i)+2*x2(i);subplot(122);%axis([-16 12 0 12]); hold on;plot(f1,f2,'.');pause(0.11);end。