《最优化方法》课程教学资源（题解）第十次 线性规划

线性规划 1.线性规划模型 2.标准型 3.图解法 4解的概念和性质 5单纯形算法

线性规划 1. 线性规划模型 2. 标准型 4.解的概念和性质 5.单纯形算法 3.图解法

线性规划模型 例1生产计划问题 某工厂利用某种原材料生产A、B、C三种产品,它们的单位 产品所需材料的数量和耗费的加工时间各不相同,如下表。 A、B、C单位产品的利润为457千元。问:该厂应如何安排 生产计划,才能使所获利润最大? 产品 资源 资源总量 原材料2 15 C32 100 工时 150

一 .线性规划模型 例1 生产计划问题 生产计划，才能使所获利润最大？ 、 、 单位产品的利润为 、、千元。问：该厂应如何安 排 产品所需材料的数量和耗费的加工时间各不相同，如下表。 某工厂利用某种原材料生 产 、 、 三种产品，它们的单位 A B C 4 5 7 A B C 产品 资源原材料 工时 A B C 资源总量 2 1 1.5 2 3 2 100 150

解:1.确定决策变量 设A、B、C的产量分别为x1、x2、x3 2.确定目标函数 设总利润为S,则 S=4x1+5x,+7x 3 3.确定约束条件 2x1+15x2+3x3≤100 x1+2x,+2x3≤150 ≥0,i=1,2,3 4.数学模型minS=4x1+5x2+7x3 2x1+1.5x2+3x3≤100 +2x2+2x3≤150 ≥0,i=1,2,3

解：2.确定目标函数 1. 确定决策变量 设 A、B、C的产量分别为x1、x2、x3。 设总利润为S，则S = 4x1 + 5x2 + 7x3 3.确定约束条件2x1 + 1.5x2 + 3x3  100 0, 1,2,3 1 2 2 2 3 150  = + +  x i x x x i 4. 数学模型 min S = 4x1 + 5x2 + 7x3       = + +  + +  0, 1,2,3 2 2 150 2 1.5 3 100 . . 1 2 3 1 2 3 x i x x x x x x s t i

线性规划模型: (1)一组决策变量; (2)一个线性目标函数; (3)-组线性的约束条件。 线性规划模型(LP)的一般形式: min (max ∑ a1x1+a12x2+…+a1nxn≥(=,≤)b1 21x1+a2x2+…+a2mxn≥(=,≤)b2 m1X1+am2x2+…+amxn≥(=,≤) (=,≤)0,i=1

线性规划模型： (1)一组决策变量； (2)一个线性目标函数； (3)一组线性的约束条件。 线性规划模型(LP)的一般形式： = n i i xi c 1 min (max)           =  = + + +  =  + + +  =  + + +  =  x i n a x a x a x b a x a x a x b a x a x a x b s t i m m mn n m n n n n ( , )0, 1,2, , ( , ) ( , ) ( , ) . . 1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1     

标准型 1.标准型 max ∑ lI X1+ x+… 1242 Inn 21X1+a22x2+…+a2nxn st mIx +am2x 2+.+amman=bm x;≥0,i=1,2,…,n 记c=(c1, x=(x 1929 nxn 则线性规划标准型可记为 max C x Ax=b st ≥0

二. 标准型 1.标准型 = n i i xi c 1 max           = + + + = + + + = + + + = x i n a x a x a x b a x a x a x b a x a x a x b s t i m m mn n m n n n n 0, 1,2, , . . 1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1      。则线性规划标准型可记 为 记 i j m n T n T m T n A a c c c c b b b b x x x x =  = = = ( ) ( , , , ) , ( , , , ) , ( , , , ) , 1 2  1 2  1 2  c x T max     = 0 . . x Ax b s t

2.化标准型 (1)目标函数: 原问题目标函数: min c x→max-crx (2)约束条件 (i)原问题条件:a1x1+a12x2+…+amxn≤b an11+n2x2+…+ a.r+x n+I xn;≥0 xn+:称为松弛变量 n (i)原问题条件:an1x1+a12x2+…+ aux≥b aix+aix2+ .+ainrn-xu+i=b xn+称为剩余变量 ≥0 i)原问题:x:无非负约束,则令 ≥0

2. 化标准型 (1)目标函数： c x T 原问题目标函数: min c x T  max − (2)约束条件：ai x ai x ain xn bi (i) 原问题条件： 1 1 + 2 2 ++      + + + + =  + + 0 1 1 2 2 n i i i in n n i i x a x a x  a x x b xn+i 称为松弛变量。 ai x ai x ai n xn bi (ii) 原问题条件： 1 1 + 2 2 ++      + + + − =  + + 0 1 1 2 2 n i i i in n n i i x a x a x  a x x b xn+i 称为剩余变量。 原问题： 无非负约束，则令 。     = − , 0 ( ) i i i i i i u v x u v iii x

例1将下述线性规划模型化为标准型。 min 2x-3x+x+3x 4 2x1-x,+3x3+xA≥3 3x1+2x2+2x4=7 st x1+4x2-3x3-x4≤6 x1,x3,x4≥0,x2无约束 解:令x2=u2-V2,则 max-2x1+3u2-3v,-x3 3 3x 2x1-l2+v2+3x3+x4-x5=3 3x1+2l2-2v2+2x4=7 st x1+4 1 2 4v,-3x3-x4+ 6 1’34,15x7,2,V2≥0

例1 将下述线性规划模型化为标准型。 1 2 3 4 min 2x − 3x + x + 3x         − + − −  + + = − + +  1 3 4 2无约束 1 2 3 4 1 2 4 1 2 3 4 , , 0, 4 3 6 3 2 2 7 2 3 3 . . x x x x x x x x x x x x x x x s t 解：令x2 = u2 − v2 ,则 1 2 2 3 4 max − 2x + 3u − 3v − x − 3x         − + − − − + = + − + = − + + + − = , , , , , , 0 4 4 3 6 3 2 2 2 7 2 3 3 . . 1 3 4 5 7 2 2 1 2 2 3 4 7 1 2 2 4 1 2 2 3 4 5 x x x x x u v x u v x x x x u v x x u v x x x s t

图解法 例2求解线性规划maxx=4x1+3x2 x1+2x,≤4 st 2x1+x2≤5 解:(1)画出可行解的范围 (2)利用等值线平移的方法求极值点。2 以z为参数,则方程4x1+3x2=z 表示一族等值平行线。 A B 极大值点为顶点B 1 +2x 2 4 2

三.图解法 例2 求解线性规划       +  +  = + , 0 2 5 2 4 . . max 4 3 1 2 1 2 1 2 1 2 x x x x x x s t z x x 解：(1)画出可行解的范围。 1 x 2 x o A B C (2) 利用等值线平移的方法求极值点。 表示一族等值平行线。 以z为参数，则方程 x + x = z 4 1 3 2 x1 + 2x2 = 4 2x1 + x2 = 5 极大值点为顶点B

例3将例2中的目标函数改为z=x1+2x2 解:分析同例2。 等值线:x1+2x2=zo B ∴极大值点为线段AB上的 C 任一点。 2r +xy=5

例3 将 例2中的目标函数改为z = x1 + 2x2。 1 x 2 x o A B C x1 + 2x2 = 4 2x1 + x2 = 5 解：分析同例2。 等值线：x1 + 2x2 = z。 任一点。 极大值点为线段AB上的

例4求解线性规划maxz=4x1+3x2 x1+x,≥2 st x≤2 x2≥0 152 解:分析同例2 2 2 2 等值线:4x1+3x2=z ∴不存在最大值。 B x1+x2=2

1 x 2 x o A B C 2 x1 − x2 = 2 x1 + x2 = 解：分析同例2。 等值线：4x1 + 3x2 = z。 例4 求解线性规划       −  +  = + , 0 2 2 . . max 4 3 1 2 1 2 1 2 1 2 x x x x x x s t z x x 不存在最大值