●LP四要素 st: subject约束条件 称为目标函数 x称为决策变量 max或min成为优化准则 lp defl 若目标函数z为决策变量x的线性函数,约 束条件亦为决策变量x的线性不等式(或等 式),则该数学表达式(模型)称为线性规 划。若目标与约束中至少有一为非线性时, 则该模型称为非线性模型(NLP)
23 ⚫ LP四要素 • s.t ：subject约束条件 • z称为目标函数 • xj称为决策变量 • max或min成为优化准则 ⚫ LP def1： 若目标函数z为决策变量xj的线性函数，约 束条件亦为决策变量xj的线性不等式（或等 式），则该数学表达式（模型）称为线性规 划。若目标与约束中至少有一为非线性时， 则该模型称为非线性模型（NLP）
模型的标准化 ●标准化LP模型的特点 目标函数仅限与极大化(或极小化) 所有约束条件均由等式表示 所有决策变量限于取非负值 每一约束不等式(或等式)之右端均为非负值
24 模型的标准化 ⚫ 标准化LP模型的特点 • 目标函数仅限与极大化（或极小化） • 所有约束条件均由等式表示 • 所有决策变量限于取非负值 • 每一约束不等式（或等式）之右端均为非负值
maXz=C1X1十Cnx+…+Cnx nn maxz=∑cx st aux,+a,2x2+.+ainr,=b, a21+a2x2+…+a2nxn st x;≥0,j=1~n amex+am2*2+.+ammo,=b ≥0,t=l~n 其中C=(c1,c2…,Cn) X=(x max z= CX 152 b=(bh2…bn) ∫sAX=b X≥0 22 n:决策变量个数 m:约束方程个数25 m1 m2
25 = = + + + = + + + = + + + = = + + + x j m b i m a x a x a x b a x a x a x b st a x a x a x b z c x c x c x j i m m m n n m n n n n n n 0, 1 ~ , 0, 1 ~ . max 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 2 2 = = = = = = b i m x j n st a x b z c x i j n j i j j i n j j j 0, 1~ 0, 1~ . max 1 1 = = 0 . max X st AX b z CX = = = = m m m n n n T n T n n a a a a a a a a a A b b b b X x x x C c c c 1 2 2 1 2 2 2 1 1 1 2 1 1 2, 1 2 1 2 ( , , ) ( , , , ) 其中 ( , , , ) n：决策变量个数 m：约束方程个数
模型的标准化 约東方程的标准化(增加变量个数换取 求解难度)
26 模型的标准化 ⚫ 约束方程的标准化（增加变量个数换取 求解难度）
例非标准约束引入变量类型标准形约束 例1x1+x2≤300松|s>0 x1+x2+s1=300 弛 2x1+x2400变|s2>0 2x1+X+s=400 x2S250量 s30 X2+s2=250 例2x+x1≥60 tX 1-S1=60 X2>70 s2>0 1+x2-S2=70 x2+x3260 2+xy-S3=60 X3+x4≥50 剩余变量 0 x3+x-S=50 X+x=20 S2>0 20 5+x6≥30 S>0 X+x656=30
27 例 非标准约束 引入变量类型 标准形约束 例1 x1+x2≤300 松 弛 变 量 s1≥0 x1+x2+s1=300 2x1+x2≤400 s2≥0 2x1+x2+s2=400 x2≤250 s3≥0 x2+s3=250 例2 x6+x1≥60 剩 余 变 量 s1≥0 x6+x1 -s1=60 x1+x2≥70 s2≥0 x1+x2 -s2=70 x2+x3≥60 s3≥0 x2+x3 -s3=60 x3+x4≥50 s1≥0 x3+x4 -s4=50 x4+x5≥20 s2≥0 x4+x5 -s5=20 x5+x6≥30 s3≥0 x5+x6 -s6=30