第五章线性规划 线性规划的基本概念 二.求解线性规划的单纯形法 三.初始基本可行解
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 =
化为标准型: minF(X)=-40x1-80x2 X∈D C PS s t +x2=9 x2+x4=7 2x1+3x2+xx=24 12 ≥0 6
6 , ,..., 0 2 3 24 7 9 min ( ) 40 80 1 2 5 1 2 5 2 4 1 3 5 1 2 + + = + = + = = − − x x x x x x x x x x X D R F X x x s.t. 化为标准型:
)线性规划的基本概念 1.线性规划的图解 max F(X)=40x,+80x (1.5,7)F*=620 X∈DcR St.x1≤9 2x1+3x,<24 x1,x2≥0 0
7 三）线性规划的基本概念 , 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. 1.线性规划的图解 x2 x1 0 F=0 (1.5,7) F*=620
2.线性规划的基本概念 1)可行解 1.5,7)F*=620 满足约束条件及非负条件的解。P x,=0 (D内及其边界上的解) x2=0 2)基本解 使n-m个变量等于0,解约束方程 组(共有m个约束方程)所得的解。=9 基本解对应于约束边界的交点.0 x=0 F=0 3)基本可行解 mIn F(X)=-40x1-80x2 可行域中的基本解(即D的顶点)。x=D=R 4)基本变量与非基本变量 S.t. 1+x3=9 预先取为零值的nm个变量为非x2+x=7 基本变量,其余m个为基本变量。 2x1+3x,+x=24 8
8 2. 线性规划的基本概念 1）可行解 —满足约束条件及非负条件的解。 （D内及其边界上的解） 2）基本解 —使n-m个变量等于0，解约束方程 组(共有m个约束方程)所得的解。 基本解对应于约束边界的交点. 3）基本可行解 —可行域中的基本解（即D的顶点）。 4）基本变量与非基本变量 预先取为零值的n-m个变量为非 基本变量，其余m个为基本变量。 x3 = 0 x2 x1 0 F=0 (1.5,7) F*=-620 x4 = 0 x5 = 0 x1 = 0 x2 = 0 , ,..., 0 2 3 24 7 9 min ( ) 40 80 1 2 5 1 2 5 2 4 1 3 5 1 2 + + = + = + = = − − x x x x x x x x x x X D R F X x x s.t
四)线性规划的基本性质 1)可行域D为凸集,每个基本可行解对应于D上的 一个顶点; 2)只要可行域存在且封闭,则起码有一个基本可 行解为最优点; *i)若最优点所在的边界线与等值线平行,则该 边界线上的点均为最优点; i)若可行域不封闭,则可能有无界解。 3)最优点可在D的顶点中寻找
9 四）线性规划的基本性质 1）可行域D为凸集，每个基本可行解对应于D上的 一个顶点； 2）只要可行域存在且封闭，则起码有一个基本可 行解为最优点； *ⅰ）若最优点所在的边界线与等值线平行，则该 边界线上的点均为最优点； ⅱ）若可行域不封闭，则可能有无界解。 3)最优点可在D的顶点中寻找
二、求解线性规划的单纯形法 一)基本思路 先取D的一个顶点作为初始点,由此出发朝 可使目标函数降低最快的方向依次经过一系 列的基本可行解,直至达到最优解 *1)需获得一个初始基本可行解; 2)每次只更换一个非基本变量 3)保证下降性和可行性
10 二. 求解线性规划的单纯形法 一)基本思路 先取D的一个顶点作为初始点,由此出发朝 可使目标函数降低最快的方向依次经过一系 列的基本可行解,直至达到最优解. *1)需获得一个初始基本可行解; 2)每次只更换一个非基本变量; 3)保证下降性和可行性