线性规划 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