第02章 节 线性规划建模及单纯形法 运筹学第3版课件.ppt

1
第二章线性规划概念、建模与求解
本章内容重点
线性规划模型结构
线性规划的图解法与线性规划的解
线性规划解的基本概念与性质
线性规划单纯形法
线性规划建模
某工厂拥有A、B、C 三种类型的设备,生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三设备可利用的时数如下表所示:
问题:工厂应如何安排生产可获得最大的总利润?
案例
产品甲
产品乙
设备能力/h
设备
A
3
2
65
设备
B
2
1
4
0
设备
C
0
3
75
利润/(元
/
件)
1500
2500
4
第一节线性规划模型结构
一、线性规划问题的提出
在实践中,根据实际问题的要求,常常可以建立线性规划问题数学模型。
例2-1 我们首先分析开篇案例提到的问题。
解:设变量 xi 为第 i 种(甲、乙)产品的生产件数(i=1,2)。根据题意,我们知道两种产品的生产受到设备能力(机时数)的限制。对设备A:两种产品生产所占用的机时数不能超过65,于是我们可以得到不等式:
3 x1 + 2 x2 ≤65;
5
对设备B:两种产品生产所占用的机时数不能超过40,于是我们可以得到不等式:2 x1 + x2 ≤ 40;
对设备C :两种产品生产所占用的机时数不能超过75,于是我们可以得到不等式:3x2 ≤75 ;另外,产品数不可能为负,即 x1, x2 ≥ 0。
8
这是一个典型的利润最大化的生产计划问题。其中,“Max”是英文单词“Maximize”的缩写,含义为“最大化”;“.”是“subject to”的缩写,表示“满足于……”。因此,上述模型的含义是:在给定条件限制下,求使目标函数 z 达到最大的x1, x2 的取值。
9
约束条件:
a11x1+a12x2+…+a1nxn≤( =, ≥)b1
a21x1+a22x2+…+a2nxn≤( =, ≥)b2
.
.
.
am1x1+am2x2 +…+amnxn≤( =, ≥)bm

x1 ,x2 ,…,xn ≥ 0
:
一般形式
目标函数:
Max(Min) z = c1x1 + c2x2 + …+ cnxn
向量形式与矩阵形式
设决策变量 x = (x1, x2, …, xn)T,