LP的一般形式 目标函数( Objective function) mmnc1x1+C2x+…+Cnx n n st.a1x1+a12x2+…amxn=b1i=1,2,…,p a1x1+a2x2+…anxn≥b1i=p+1,…,m x.≥0 j=1,2,,q x,无限制 j=q+1,…,n 约束条件( Constraints) 2021/1/27 山东大学软件学院
2021/1/27 山东大学 软件学院 11 x j q n x j q a x a x a x b i p m a x a x a x b i p c x c x c x j j i i i n n i i i i n n i n n 1,..., 0 1,2,..., 1,..., s.t. 1,2,..., min 1 1 2 2 1 1 2 2 1 1 2 2 = + = + + = + + + = = + + + 无限制 目标函数（Objective function） 约束条件（Constraints） LP的一般形式
LP中各项的名称 x;j=1,2,n为待定的决策变量, C=(c1,C2;…,Cn)为价值向量(或费用向量), 1,2,,n为价值系数(或费用系数) b=(b1,b2,bn)为右端向量, 矩阵 11 12 n 2n 为系数矩阵。 2021/1/27 山东大学软件学院 12
2021/1/27 山东大学 软件学院 12 x j ; j = 1,2,...,n 为待定的决策变量， ( , , , ) 1 2 n c = c c c 为价值向量（或费用向量）， c j ; j = 1,2,...,n 为价值系数（或费用系数）， ( , ,..., ) b = b1 b2 bm 为右端向量， 矩阵 为系数矩阵。 = m m mn n n a a a a a a a a a A 1 2 21 22 2 11 12 1 LP中各项的名称
LP的规范型和标准型 min Cx min CX t.Ax≥b s.t. Ax= b x≥0 x≥0 规范形式 标准形式 Canonical form Standard form 2021/1/27 山东大学软件学院 13
2021/1/27 山东大学 软件学院 13 LP的规范型和标准型 0 s.t. min x Ax b c x 0 s.t. min = x Ax b c x 规范形式 Canonical form 标准形式 Standard form
基本概念 可行解:满足所有约束条件的向量x=(x,x2…x) 可行域:所有的可行解的全体D=4x=bx≥20}。 最优解:在可行域中目标函数值最大(或最小)的可 行解。 最优值:最优解的目标函数值z=cx,其中x为 个最优解。 2021/1/27 山东大学软件学院 14
2021/1/27 山东大学 软件学院 14 可行解：满足所有约束条件的向量 = ( , , ) 1 2 n x x x x 。 可行域：所有的可行解的全体 D = x Ax = b, x 0。 最优解：在可行域中目标函数值最大（或最小）的可 行解。 最优值：最优解的目标函数值 * * z c x = ，其中 x *为一 个最优解。 基本概念
模型转换 LP的三种形式实际上是相互等价的,因为它们之间可以 进行相互转换。下面介绍转换的方法。 今去掉无限制变量 令无限制变量x=x一x,其中x,x为非负变量。 今目标转换 求最大可以等价成求负的最小: max Cxo min -C'X 2021/1/27 山东大学软件学院 15
2021/1/27 山东大学 软件学院 15 令无限制变量 + − x j = x j − x j ，其中 + − x j x j , 为非负变量。 求最大可以等价成求负的最小： c x c x max min − ❖目标转换 ❖去掉无限制变量 模型转换 LP的三种形式实际上是相互等价的，因为它们之间可以 进行相互转换。下面介绍转换的方法