线性规划ppt课件.ppt

文档介绍：1
第五章线性规划



2
某厂生产甲、乙两种产品,已知:①两种产品分别由两条生产线生产。第一条生产甲,每天最多生产9件,第二条生产乙,每天最多生产7件;②该厂仅有工人24名,生产甲每件用2工日,生产乙每件用3工日;③产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润?
一)应用实例
一. 线性规划的基本概念
3
日利润最大
生产能力限制
劳动力限制
变量非负
解: 设甲、乙两种产品的日产件数分别为
.
4
二)线性规划的一般形式
.
特点: 1)为极小化问题; 2)约束取等号;
3)限定系数非负; 4)变量非负.
式中, —价值系数; —结构系数
—限定系数
5
将数学模型化为标准型的方法
1)将极大化问题化为极小化问题
—松弛变量
(开关变量)
(两边乘-1)
4)将负的限定系数化为正值
3)将任意变量化为非负变量
2)将不等式约束变为等式约束:
—目标函数变号;
6
.
化为标准型:
7
三)线性规划的基本概念
.

x2
x1
0
F=0
F*=620
(,7)
8
2. 线性规划的基本概念
1)可行解
—满足约束条件及非负条件的解。
(D内及其边界上的解)
2)基本解
—使n-m个变量等于0,解约束方程组(共有m个约束方程)所得的解。
基本解对应于约束边界的交点.
3)基本可行解
—可行域中的基本解(即D的顶点)。
4)基本变量与非基本变量
预先取为零值的n-m个变量为非基本变量,其余m个为基本变量。
x2
x1
0
F=0
F*=-620
(,7)
.
9
四)线性规划的基本性质
1)可行域D为凸集,每个基本可行解对应于D上的一个顶点;
2)只要可行域存在且封闭,则起码有一个基本可行解为最优点;
*ⅰ)若最优点所在的边界线与等值线平行,则该边界线上的点均为最优点;
ⅱ)若可行域不封闭,则可能有无界解。
3)最优点可在D的顶点中寻找。
10
二. 求解线性规划的单纯形法
一)基本思路
先取D的一个顶点作为初始点,由此出发朝可使目标函数降低最快的方向依次经过一系列的基本可行解,直至达到最优解.
*1)需获得一个初始基本可行解;
2)每次只更换一个非基本变量;
3)保证下降性和可行性.