求解线性规划(LP)的基本原理 二维线性规划的图解法 max(or minE= x,xER" max =3x +x s.1.x1-x2≥ Ax≤b.x≥0 rad z c∈R",A∈Rm,b∈R 3x,+2x:≤14~L 盘肌划的圆油 起作用约束:L2;L3 限划的单形 朝的内成油 最优解(4,1),最优值z=13 LP的约来和目标函敷均为线性函数 求解LP的特殊情形max=3x,+x x1-2x:≤2-L2 可行域线段组成的凸多边形超平面组成的凸多面体 3x,+2x.≤14-L3 目标函数等值线为直线 等值线是超平面 最优解凸多边形的某个顶点凸多面体的某个顶点 -3x1+2x214~L无L3 3x1+x2≤14~L3 求解LP的基本思想 从可行域的某一顶点开始,只需在有限多个顶点中 个一个找下去,一定能得到最优解 算法:怎样从一点转到下一点,尽快找到最优解。 无可行解无最优解(无界)最优解不唯 (学学奖 大学费学买验 线性规划的标准形和基本性质 对标准形求解mn=-3x-x2+0x2+0x+0x nz=-3x1-x2+0·x3+0x4+0 .x1-x2≥-2 mmn二=cx s..-x+x2+x3=2x≥0 x-2x2+x4=2, 3. ∈ 3x1+2x2+x5=14,x≥0 x1,x2≥0 先求可行解 x+x2+x3=2 加入松弛变量剩余变量将不等式变为等式 标 lIn 2 准s1.Ax=b,x≥0 形 A∈Rm×n 再在有限个可行解中寻找最优解3 求解线性规划(LP)的基本原理 基本模型 . . , 0 max( min) , ≤ ≥ = ∈ st Ax b x or z c x x R T n n m n m c ∈ R A ∈ R b ∈ R × , , •二维线性规划的图解法 •一般线性规划的单纯形算法 •一般线性规划的内点算法 二维线性规划的图解法 x2 0 x1 L1 L2 L3 z1=0 z2=2 z3=6 z4=10 z5=13 grad z x* * 起作用约束：L2;L3 最优解（4，1），最优值zmax=13 ~L1 ~L2 ~L3 , 0 3 2 14 2 2 . . 2 max 3 1 2 1 2 1 2 1 2 1 2 ≥ + ≤ − ≤ − + ≤ = + x x x x x x s t x x z x x x1 − x2 ≥ −2 求解LP的基本思想 从可行域的某一顶点开始，只需在有限多个顶点中 一个一个找下去，一定能得到最优解。 LP的约束和目标函数均为线性函数 2维 可行域 线段组成的凸多边形 目标函数 等值线为直线 最优解 凸多边形的某个顶点 n维 超平面组成的凸多面体 等值线是超平面 凸多面体的某个顶点 算法：怎样从一点转到下一点，尽快找到最优解。 x2 x1 0 L1 L2 L3 x2 x1 0 L1 L2 L3 x2 x1 0 L1 L2 求解LP的特殊情形 ~L1 ~L2 ~L3 无可行解 无最优解(无界) 最优解不唯一 1 2 ~ 3 − 3x + 2x ≥ 14 L 无 L3 x2 x1 0 L1 L2 L3 z=c , 0 3 2 14 2 2 . . 2 max 3 1 2 1 2 1 2 1 2 1 2 ≥ + ≤ − ≤ − + ≤ = + x x x x x x s t x x z x x 2 x1 − x2 ≥ − 3 1 2 14 ~ L3 x + x ≤ 线性规划的标准形和基本性质 A R m n s t Ax b x z c x m n T ∈ ≤ = ≥ = × , . . , 0 标 min 准 形 加入松弛变量/剩余变量将不等式变为等式 , 0 3 2 14, 0 2 2, 0 min 3 0 0 0 1 2 1 2 5 5 1 2 4 4 1 2 3 4 5 ≥ + + = ≥ − + = ≥ = − − + ⋅ + ⋅ + ⋅ x x x x x x x x x x z x x x x x s.t. −x1 +x2 +x3 =2, x3 ≥0 , 0 3 2 14 2 2 . . 2 max 3 1 2 1 2 1 2 1 2 1 2 ≥ + ≤ − ≤ − + ≤ = + x x x x x x s t x x z x x x1 − x2 ≥ −2 , , , , 0 3 2 14, 2 2, . . 2 min 3 0 0 0 1 2 3 4 5 1 2 5 1 2 4 1 2 3 1 2 3 4 5 ≥ + + = − + = − + + = = − − + ⋅ + ⋅ + ⋅ x x x x x x x x x x x st x x x z x x x x x , , , , 0 3 2 14, 2 2, 2 1 2 3 4 5 1 2 5 1 2 4 1 2 3 ≥ + + = − + = − + + = x x x x x x x x x x x x x x 对标准形求解 先求可行解 A R m n s t Ax b x z c x m n T ∈ ≤ = ≥ = × , . . , 0 min Ax = b, x ≥ 0 满足 再在有限个可行解中寻找最优解