实例1:奶制品生产销售计划 实例1:奶制品生产销售计划 Max==12x1+8x2+22x3+16x4-1.5x5-1.5 Max二=12x+8x2+22x2+16x-1.5x-1.5x ≤50 曰4x1+3x2 +4xs+3x6≤ 五+五+≤50 4x1+x3)+2(x2+x6)+2x+2x6≤480 4(x1+x)+2(x2+x)+2x,+2x,≤480口2x+x2 +3xs+2x6≤24 x1+x5≤100 zl=1731.98 1-z=1731.98-17304=1.58 x,x2,其3,x4,x5,x620 x1,x2,x3,x4,x5,x620 所以1小时劳动时间的影 子价格应为3.26/2=1.6 0,168,19.2,0,24,0);==-20=1730.4 “影子价格” =(0,168,192,0,24,0);二=-20=1 单位劳动时间增加的利 inulin=(1.58:3.26;0.00) lag. ineqlin =(1.58; 3. 26, 0.00 润是1.63(元 l*12=1.58·12=18.96>15 →15元可增加桶牛奶,应否投资? 应该投资1 聘用临时工人增加劳动时间,工资最多每小时几元? 大学学实编) 实例:奶制品生产销售计划 NLP基本原理(不等式约束) Max==12x1+8x2+22x+16x4-1.5x-1.5x6 min ==f(x) 设x为可行解 若每公斤B的获利下降10% 位于约束边界/g0 4x+x)+2x2+x)+2+2x5480应将目标函敷中x的系数改 st.g(x)≤0,j= 为198,重新计算发现最优 x+x≤100 解和最优值均发生了变化 (x)=0.j∈J起作用约束(j=1) 若B2的获利向上波动10%, g(x)<0.j∈J不起作用约束j=23 4=075 原计划也不再是最优的 可行方向dx+M∈G(0<A<) MATLAB没有给出这种敏 81(x+d)=g,(x)+Vg(x)d+O(2) x=0.1681920240:=0=1704感性分析的结果(LNDC g1(x)2d<0(∈h1)( lag. ineqlin=(1. 58: 3. 26: 0.00) 和 LINGO软件可以给出) 下降方向df(x+)<f(x)0<<4)vf(xyd<0(2) ·B1,B2的获利经常有10%的波动,对计划有无影响? 着沿方向既可行又下降,则不是最优解③aa (学学奖 大学费学买验 Te Vgj(x)d<0 (eJn()v/(r)'d<0(2 KKT条件的几何解释 x为最优解口不存在满足(1)、2)的d vf(x)+∑AVg,(x)=0 minf(x)=(x-7)+(x2-3) 最优解的必要条件若x为最优解 且Vg,(x)O∈J)线性无关,则存在A1,…元1≥0 2,g,(x)=0,j=12 stg(x)=x2+x2-10≤0 8(x)=x+x2-4≤0 vf(x)+∑2Vg,(x)=0 KT条件 1g,(x)=0,j=12… 互补性条件 (7,3)。最优解在P(3,1)取得 v,Vg/(∈小)线性无关, s.b1(x)=0 Vf(P)+Vg, (P)+2Vg,(P)=0 8(x)≤0,/=1-1则存在和方20 P1)是KKT点 V(x)+Vb(x)+gvg;(x)=04(x)=0j=1…1 x其它点如Q均不是5 • 15元可增加1桶牛奶，应否投资？ 实例1: 奶制品生产销售计划 1 2 3 4 5 6 Max z = 12x + 8x + 22x +16x −1.5x −1.5x 50 3 4 1 5 2 6 ≤ + + x + x x x 4( ) 2( ) 2 2 480 x1 + x5 + x2 + x6 + x5 + x6 ≤ x1 + x5 ≤ 100 3 5 x = 0.8x 4 6 x = 0.75x 0 x1 ,x2 ,x3 ,x4 ,x5 ,x6 ≥ x=(0,168,19.2,0,24,0) ; z = -z0 =1730.4 lag.ineqlin =(1.58;3.26; 0.00) ; … 4x1 + 3x2 + 4x5 + 3x6 ≤ 600 601 z1=1731.98 z1-z = 1731.98-1730.4=1.58 z1=lag.ineqlin(1) z1*12=1.58*12= 18.96>15 应该投资！ “影子价格” 实例1: 奶制品生产销售计划 • 聘用临时工人增加劳动时间，工资最多每小时几元？ 1 2 3 4 5 6 Max z = 12x + 8x + 22x +16x −1.5x −1.5x 50 3 4 1 5 2 6 ≤ + + x + x x x 4( ) 2( ) 2 2 480 x1 + x5 + x2 + x6 + x5 + x6 ≤ x1 + x5 ≤ 100 3 5 x = 0.8x 4 6 x = 0.75x 0 x1 ,x2 ,x3 ,x4 ,x5 ,x6 ≥ x=(0,168,19.2,0,24,0) ; z = -z0 =1730.4 lag.ineqlin =(1.58;3.26; 0.00) ; … 4x1 + 3x2 + 4x5 + 3x6 ≤ 600 2 3 2 240 x1 + x2 + x5 + x6 ≤ lag.ineqlin(2)=3.26， 所以1小时劳动时间的影 子价格应为3.26/2=1.63， 即单位劳动时间增加的利 润是1.63(元) • B1，B2的获利经常有10%的波动，对计划有无影响？ 实例1: 奶制品生产销售计划 1 2 3 4 5 6 Max z = 12x + 8x + 22x +16x −1.5x −1.5x 50 3 4 1 5 2 6 ≤ + + x + x x x 4(x1 + x5 ) + 2(x2 + x6 ) + 2x5 + 2x6 ≤ 480 x1 + x5 ≤ 100 3 5 x = 0.8x 4 0 75 6 x = . x 0 x1 ,x2 ,x3 ,x4 ,x5 ,x6 ≥ x=(0,168,19.2,0,24,0) ; z = -z0 =1730.4 lag.ineqlin =(1.58;3.26; 0.00) ; 若每公斤B1的获利下降10%, 应将目标函数中x3的系数改 为19.8，重新计算发现最优 解和最优值均发生了变化 若B2的获利向上波动10%，y 原计划也不再是最优的 MATLAB没有给出这种敏 感性分析的结果（LINDO 和LINGO软件可以给出） NLP基本原理(不等式约束) st g x j l z f x j x n . . ( ) 0, 1,..., min ( ) ≤ = = ∈ℜ ∇g1 d g2=0 g1=0 g3=0 gj <0 o x 设x为可行解， 位于约束边界 1 g (x) 0, j J j = ∈ J1~起作用约束(j=1) 2 g (x) 0, j J j < ∈ J2~不起作用约束(j=2,3) (0 ) +λ ∈G <λ <λ0 可行方向d x d 下降方向d ( ) ( ) (0 ) +λ < < λ < λ0 f x d f x (G) ( ) 0 ( ) (1) 1 g x d j J T ∇ j < ∈ ∇f (x) d < 0 (2) T ( ) ( ) ( ) ( ) 2 g x λd g x λ g x d O λ T j + = j + ∇ j + 若x沿d方向既可行又下降，则x不是最优解 最优解的必要条件 ( ) ( ) 0 1 ∇ + ∑ ∇ = = f x g x j l j λi g x j l λ j j( ) = 0, =1,2,L ~KKT条件 互补性条件 g x j l s t h x i m f x j i x n ( ) 0 , 1,..., . . ( ) 0 , 1,..., min ( ) ≤ = = = ∈ℜ 则存在 和 ， 线性无关， 0 , ( ) 1 ≥ ∇ ∇ ∈ i j i j h g j J µ λ ( ) ( ) ( ) 0 1 1 ∇ + ∑ ∇ + ∑ ∇ = = = f x h x g x j l j i m i µ i i λ g x j l λ j j( ) = 0, =1,L x为最优解 不存在满足(1),(2)的d ( ) 0 ( ) (1) 1 g x d j J T ∇ j < ∈ ∇f (x) d < 0 (2) T 且 线性无关，则存在 ∇g j (x) ( j ∈ J 1 ) λ1 ,Lλ l ≥ 0 若x为最优解， KKT条件的几何解释 Q P ∇f -∇g1 -∇g2 ∇f -∇g1 -∇g2 ( ) 0 ( ) 4 0 . . ( ) 10 0 min ( ) ( 7) ( 3) 3 2 2 1 2 2 2 2 1 1 2 2 2 1 = ≥ = + − ≤ = + − ≤ = − + − g x x g x x x st g x x x f x x x ( ) ( ) 0 1 ∇ + ∑ ∇ = = f x g x j l j λi g x j l λ j j( ) = 0, =1,2,L x2 x 0 1 最优解在P(3,1)取得 ( ) ( ) 2 ( ) 0 1, 2, 0, 1 2 1 2 3 ∇ +∇ + ∇ = = = = f P g P g P λ λ λ P(3,1)是KKT点 其它点(如Q)均不是 • (7,3)