第五章线性规划 线性规划的基本概念 二.求解线性规划的单纯形法 三.初始基本可行解
1 第五章 线性规划 一.线性规划的基本概念 二.求解线性规划的单纯形法 三.初始基本可行解
线性规划的基本概念 )应用实例 某厂生产甲、乙两种产品,已知:①两种产 品分别由两条生产线生产。第一条生产甲,每天 最多生产9件,第二条生产乙,每天最多生产7件; ②该厂仅有工人24名,生产甲每件用2工日,生 产乙每件用3工日;③产品甲、乙的单件利润分 别为40元和80元。问工厂如何组织生产才能获得 最大利润?
2 某厂生产甲、乙两种产品，已知：①两种产 品分别由两条生产线生产。第一条生产甲，每天 最多生产9件，第二条生产乙，每天最多生产7件； ②该厂仅有工人24名，生产甲每件用2工日，生 产乙每件用3工日；③产品甲、乙的单件利润分 别为40元和80元。问工厂如何组织生产才能获得 最大利润？ 一）应用实例 一 . 线性规划的基本概念
解:设甲、乙两种产品的日产件数分别为x1,x2 maxF(X)=40x+80x2日利润最大 Ⅹ∈DcR S.t.x,<9 生产能力限制 x,≤7 2x1+3x2≤24 劳动力限制 0 变量非负
3 日利润最大 生产能力限制 劳动力限制 变量非负 , . 1 2 解: 设甲、乙两种产品的日产件数分别为 x x , 0 2 3 24 7 9 max ( ) 40 80 1 2 1 2 2 1 2 1 2 + = + x x x x x x X D R F X x x s.t
二)线性规划的一般形式 min F(X=Cx,+C2x2+.+Cnx t a 12 X +...+a.x n·n ax tax+. x=b nn ax,+ax++a x=b 2 ≥0 式中,C;一价值系数;a1-结构系数 b.—限定系数 特点:1)为极小化问题;2)约束取等号; 3)限定系数非负;4变量非负
4 二)线性规划的一般形式 , ,... 0 ... ...... ... ... min ( ) ... 1 2 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 2 2 + + + = + + + = + + + = = + + + n m m m n n m n n n n n n x x x a x a x a x b a x a x a x b a x a x a x b F X c x c x c x s.t. 特点: 1)为极小化问题; 2)约束取等号; 3)限定系数非负; 4)变量非负. 式中， —价值系数； —结构系数 —限定系数 j c ij a i b
将数学模型化为标准型的方法 1)将极大化问题化为极小化问题一目标函数变号; 2)将不等式约束变为等式约束: (1)若g(X)≤b→g(X)+xk=b (2)若g(X)≥b→g(X)-xk=b xk—松弛变量 3)将任意变量化为非负变量 ∥/ x=x=x(开关变量) 4)将负的限定系数化为正值(两边乘-1)
5 • 将数学模型化为标准型的方法 1）将极大化问题化为极小化问题 gi X bi (1)若 ( ) gi X bi (2)若 ( ) k x —松弛变量 / // j j j x = x − x （开关变量） 4）将负的限定系数化为正值 （两边乘-1） 3）将任意变量化为非负变量 2）将不等式约束变为等式约束： —目标函数变号； i k bi g (X) + x = i k bi g (X) − x =