运筹学第1章线性规划及单纯形 法复习题.ppt

文档介绍：第1章线性规划及单纯形法
(Linear Programming and Simplex Method)
§1一般线性规划问题及其数学模型
§2图解法
§3单纯形法原理
§5单纯形法的进一步讨论
§7线性规划应用
§4单纯形法的计算步骤
§6数据包络分析
为了完成一项任务或达到一定的目的,怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的,这个过程就是规划。
例一、有一正方形铁皮,如何截取 x 使容积为最大?
x
a
此为无约束极值问题
(一)、问题的提出
§1一般线性规划问题及其数学模型
设备
产品
A
B
C
D
利润(元)
Ⅰ
2
1
4
0
2
Ⅱ
2
2
0
4
3
有效台时
12
8
16
12
例二、已知资料如表所示,问如何安排生产才能使利润最大?或如何考虑利润大,产品好销。
模型
max Z = 2x1 + 3x2
x1 ≥ 0 , x2 ≥ 0
.
2x1 + 2x2 ≤ 12
x1 + 2x2 ≤ 8
4x1 ≤ 16
4x2 ≤ 12
此为带约束的极值问题
问题中总有未知的变量,需要我们去解决。
要求:有目标函数及约束条件,一般有非负条件存在,由此组成规划数学模型。
如果在规划问题的数学模型中,变量是连续的(数值取实数)其目标函数是线性函数(一次方),约束条件是有关变量的线性等式或不等式,这样,规划问题的数学模型是线性的。反之,就是非线性的规划问题。
(二)、数学模型  1、
目标函数:
约束条件:
①
②
③
2、线性规划数学模型的一般形式
也可以记为如下形式:
目标函数:
约束条件:
如将上例用表格表示如下:
设变量
产品 j
设备 i
有效台时
利润
向量形式:
矩阵形式:
3、线性规划的标准形式
①
②
③