高等运筹课件1.ppt

* 二、惩罚函数法 1、外点法 对问题 minf(X) X?D 构建minF(X,μ)=f(X)+ μP(X) μ0,对于所有X,P(X)≥0,当且仅当X?D时，P(X)=0 P(X)是罚函数， μ为罚因子， * 不断增加μ，使F极小点X不断靠近可行域 P(X)的取法： 当st hj(X)=0 j=1,2,…l时，取P(X)=∑[hj(X)]2 当st gi(X)≥0 i=1,2…m 时，取 P(X)=∑[min {0,gi(X)} ]2 * x MP(x) g(x)=x-a≥0 a M=1 M=10 M=100 * 例：求解非线性规划 minf(X)=x1+x2 g1(X)=-x12+x2≥0 g2(x)=x1≥0 * 2、内点法 基本思想：从原问题可行点出发，在可行域边界建立一个障碍函数q(X)，阻挡可行点离开可行域，从而使迭代在可行域内部逐渐逼近约束最优解。逐渐缩小r 当约束为gi(X)≥0 时，q(X)=r∑[1/ gi(X)] * 例：用内点法求解 minf(x)=x3/3 x-a≥0 * 第二章 多目标规划 * 第一节 基本概念 例：由n种成分组成的香蕉配方，可用x=(x1,x2,...xn)表示，对于每个配方要同时考察几个指标，如强度f1(x),硬度f2(x) ，伸长率，变形率等，如何得到好的配方。 再如薪酬设计，业绩考评等都需要考虑多方面的指标。 绝对最优解? 有效解 ?弱有效解（非劣解） * fi(x) x f1(x) f2(x) f2(x) fi(x) x f1(x) f2(x) f1(x) f1(x) f2(x) 例 minf(x)=(f1(x),f2(x)) * 练习 1、f1(x)=2x-x2 f2(x)= R=[0,2] max 2、f1(x)=2x-x2 f2(x)=x R=[0,2] max 3、 f1(x)=2x-x2 f2(x)=1/8(-12x2+36x-15) R=[0,2] max x 0≤x≤1 －2x+3 1≤x≤2 * 4、f1(x)=-3x1+2x2 f2=x1+2x2 求max 5、上例中f2= 4x1+3x2其他不变 求max -2x1-3x2+18≥0 -2x1- x2+10≥0 x1 ≥0 x2 ≥0 R: * 第二节 化多为少法 1、主要目标法 2、线性加权和法 找合理权系数的方法：α法 以两目标规划为例 * f1* f10 f2* f20 M2 M1 C f1 f2 f1越小越好,f2越大越好 M1与M2连线左上区域边界是非劣解，可知C点是非劣解。 f10=minf1=f1(x1) f20=maxf2 = f2(x2) f1*= f1(x2) f2*= f2(x1) M1与M2连线斜率为α1/ α2 试确定α1 ， α2 * * 例： minf1(x)= 4x1+ x2 maxf2=3x1+2x2 R: {x|2x1+ x2≤4 x1+ x2≤3 x1 ,x2≥0} * 3、理想点法 上例子图 例P250 F0(理想点） F(x*) F(x1) F(x2) 12 24 * * 4、平方和加权法 5、乘除法 6、功效系数法 例 越小越好 越大越好 1 0 * 直线型效用函数、保守型效用函数、冒险型效用函数、渴望型效用函数 1 货币 效用曲线的确定 例：某决策人面临一项可能最多获利20万元，或者最大损失10万元的项目，试确定决策者效用曲线 * * 多维效用并和规则 （1）距离规则：如果是二维，当二效用同时达到最大值时，并和效用才达到最大值，当二效用同时取最小值时，并和效用取零效用。二效用之一达到最大均不能使并和效用到达最大。 * （2）代换规则：对二维效用并和， 只要其中一个目标效用最大，并和效用取得最大值（完全并联) * （3）加法规则（互补）一 目标效用的减少可以由另一目标效用值的增加得到补偿，只有当二效用均达到最高时总效用最大。ρ为权系数 * （4）乘法规则 （串联）目标之间无相互完全不可能替代，只要任意目标效用为0,则总效用为0 * （5）混合规则 * 三、层次分析法（AHP) * * * * * * * 例 求