线性规划 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 不存在最大值