第1章-线性规划及单纯形法.ppt

「线性规划」带来巨额财富
与其他传统数学学科相比较, 线性规划算是非常「年轻」却非常「实用」的一门应用数学。根据二十世纪八十年代的一项调查, 在美国「财富」杂志(Fortune) 名列前五百名的大公司中, 百分八十五均曾应用线性规划的方法来协助公司的营运。由此可见线性规划应用面的宽广与普及。
第1章 线性规划及单纯形法
§1 一般线性规划问题的数学模型
§2 图解法
§3 单纯形法原理
§4 单纯形法的计算步骤
§5单纯形法的进一步讨论
§6 数据包络分析
主
要
内
容
§1 一般线性规划问题的数学模型
问题的提出
线性规划问题的数学模型
线性规划问题的标准形式
线性规划问题的解
常山机器厂生产I、II两种产品，这两种产品都要分别在A、B、C三种不同设备上加工。生产两种产品，已知的条件如下表所示，问该企业应安排生产两种产品各多少件，使总的利润收入为最大。
生产每件产品占用设备时间(h)
产品I
产品
II
计划期内用于生产的能力
设备A
2
2
12
设备B
4
0
16
设备C
0
5
15
单位产品的利润（元）
2
3
生产计划问题
1-1 问题的提出
问 题 分 析
占用设备时间(h)
产品I
产品
II
可用的能力
设备A
2
2
12
设备B
4
0
16
设备C
0
5
15
利润（元）
2
3
可控因素(决策变量):
设在计划期内生产I、II两种产品的数量分别为
目标：
达到最大.
使得总利润最大，即利润函数：
受制条件：
计划期内设备的使用量不超过可用量：
设备B：
设备C：
设备A：
模 型
.
1-2 线性规划问题的数学模型
(1) 规划问题的数学模型的3个组成要素：
决策变量、目标函数、约束条件
(2) 线性规划问题的数学模型：
决策变量为可控的连续变量、
目标函数和约束条件关于决策变量都是线性
目标函数
约束条件
(3) 一般线性规划问题的数学模型的表示形式：
以上模型的简写形式
为待定的决策变量
价值系数
矩阵
 
 
 
 为系数矩阵(或约束矩阵)。
向量表示形式
其中
矩阵表示形式
价值向量
右端向量
(2)化为标准形式的方法
1-3 线性规划问题的标准形式
取极大
bi≥0,等式约束
非负约束
(1)标准形式
①
②
松弛变量
③
剩余变量
说明：松弛变量和剩余变量在实际问题中分别表示未被利用的资源和超用的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。