A→[B,NB可逆 A=1-2010 LP基本性质 x7→[xB,x 3200 可行域存在时,必是凸多面体 3n+22+5=14=[BB2B2P2B Ax= BxB+ NxN=b 可行解对应于可行域的顶点 最优解存在时,必在可行域的顶点取得 B=IP3P4ps]→x=(00,2,214)7O点 最优解只需在有限个可行解中寻找 B=[乃351→x=(20,4,08)Q点 LP的遢常解油是单施形油 B=[P2P3P5]→x=(0-13016)R点 单形法的本尾隐是 B=[BP2P]→x=(41.50)P点 从一个顶点转换到另一个顶点(即构成xg和x的 基本可行解x:Ac=b,x20(x20,x=00⊙ 向量p间的转换),使目标函数下降最多 LP其他算法 MATLAB求解LP min2三cx 内点法( (Interior point method) S!.Ax≤b1,A2x=b2,V1≤x≤v 0世纪80年代人们提出的一类新的算法—内点算 [x, fval, exitflag, output, lambda] 法也是迭代法,但不再从可行域的一个顶点转换到另 linprog(c, Al, bl, A2, b2, vl, v2, x0, options) 个顶点,而是直接从可行域的内部逼近最优解 1 ambda~ lagrange乘子 有效集( Active Set)方法 x0~初始解(缺省时为0) 维数等于约束个数,非零分 options~ MATLAB控制参数 量对应于起作用的束 线性规划是二次规划的一个特例(只需令所有二次 项为零即可),因此也可以用二次规划的算法(如有效 中间所缺参数项补[ 集方法,详见下节关于二次规划的介绍)解线性规划 lambda upper lambda. lower (学学奖 大学酸学实验) MATLAB求解LP 实例1:奶制品生产销售计划 options~ MATLAB控制参数:三种算法选择 Max==12x1+8x2+22x3+16x4-1.5x5-1.5x 缺省时采用大规模算法〔是一种内点算法 曰4x1+3r2 +4x;+3x6 e”参数设为“om时,采用中规模算法 4x+x,)+2x2+x)+2x+2x.5480中2x+x +3xs+2x≤ 该模式下缺省的算法是二次规划的算法(一种有效集方法); 叫1282216-1.5-1.5 当opr中“ Largescale"参数设置为“om”,并且“ Simplex”参数设 l=430043;210032;100010; 量为“on"时,采用单纯形算法 x3-0.8xs=0 bl=60024010 A2=|001040.80:0001040.75l 只有有效集方法可以由用户提供初始解x0,其他两个算法则不 x,x2,x,x,x,x20b2=100 需要(即使提供了也会被忽略 vl=000000 X, zO, ef, out, lag linprog(-c, Al, bl, A2, b2, vl) ag.ineqlin, lag eqi Exam080l m =(0,168,192,0,24,0);二=-z0=1730 ag. ineqlin=(1.58:3.26;0.004 3 2 14 2 2 2 1 2 5 1 2 4 1 2 3 + + = − + = − + + = x x x x x x x x x ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − − = 3 2 0 0 1 1 2 0 1 0 1 1 1 0 0 A A⇒[B,N]，B可逆 [ , ] T N T B T x ⇒ x x Ax = BxB + NxN = b [ ] = p1 p2 p3 p4 p5 xN xB B b 1 0 − = ⇒ = x2 x O 1 T B [ p p p ] x (0,0,2,2,14) = 3 4 5 ⇒ = T B [ p p p ] x (2,0,4,0,8) = 1 3 5 ⇒ = T B [ p p p ] x (0, 1,3,0,16) = 2 3 5 ⇒ = − O点 Q点 R点 Q R 基本可行解x ：Ax=b, x ≥0 (xB≥0，xN=0) T B [ p p p ] x (4,1,5,0,0) = 1 2 3 ⇒ = P点 P 可行域存在时，必是凸多面体； 可行解对应于可行域的顶点； 最优解存在时，必在可行域的顶点取得。 LP基本性质 最优解只需在有限个可行解中寻找 单纯形法的基本思路是 从一个顶点转换到另一个顶点（即构成xB和xN的 向量pi 间的转换），使目标函数下降最多。 LP的通常解法是单纯形法 内点法(Interior point method) 20世纪80年代人们提出的一类新的算法——内点算 法也是迭代法，但不再从可行域的一个顶点转换到另一 个顶点，而是直接从可行域的内部逼近最优解。 LP其他算法 有效集(Active Set)方法 线性规划是二次规划的一个特例（只需令所有二次 项为零即可），因此也可以用二次规划的算法（如有效 集方法，详见下节关于二次规划的介绍）解线性规划 [x,fval,exitflag,output,lambda] = linprog(c,A1,b1,A2,b2,v1,v2,x0,options) MATLAB 求解 LP 1 1 2 2 1 2 . . , , min s t A x b A x b v x v z c xT ≤ = ≤ ≤ = 输入： x0~初始解(缺省时为0) options ~ MATLAB控制参数 中间所缺参数项补[] 输出： lambda ~ Lagrange乘子， 维数等于约束个数，非零分 量对应于起作用约束 • lambda.ineqlin • lambda. eqlin • lambda. upper • lambda. lower Exam0802.m MATLAB 求解 LP options ~ MATLAB控制参数:三种算法选择 • 缺省时采用大规模算法（是一种内点算法）； • 当opt中“LargeScale”参数设置为“off”时，采用中规模算法， 该模式下缺省的算法是二次规划的算法（一种有效集方法）； • 当opt中“LargeScale”参数设置为“off”，并且“Simplex”参数设 置为“on”时，采用单纯形算法。 只有有效集方法可以由用户提供初始解x0，其他两个算法则不 需要（即使提供了也会被忽略）。 Exam0801.m c=[12 8 22 16 -1.5 -1.5]; A1=[4 3 0 0 4 3;2 1 0 0 3 2;1 0 0 0 1 0]; b1=[600 240 100]; A2=[0 0 1 0 -0.8 0;0 0 0 1 0 -0.75]; b2=[0 0]; v1=[0 0 0 0 0 0]; [x,z0,ef,out,lag]=linprog(-c,A1,b1,A2,b2,v1) lag.ineqlin, lag.eqlin 实例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 0.8 0 x3 − x5 = x4 − 0.75x6 = 0 0 x1 ,x2 ,x3 ,x4 ,x5 ,x6 ≥ 4x1 + 3x2 + 4x5 + 3x6 ≤ 600 2 3 2 240 x1 + x2 + x5 + x6 ≤ x=(0,168,19.2,0,24,0) ; z = -z0 =1730.4; lag.ineqlin =(1.58;3.26; 0.00) ; … shili0801.m