工商管理专业基础课运筹学.ppt

工商管理专业基础课运筹学
主讲人:刘舒燕
武汉理工大学管理学院工商管理系
第一部分线性规划(Linear Programming,简称LP)
线性规划的发展
1939年,前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题
1947年,Dantzig提出求解线性规划的单纯形法
1950-1956年,主要研究线性规划的对偶理论
1958年,发表整数规划的割平面法
1960年,Dantzig和Wolfe研究成功分解算法,奠定了大规模线性规划问题理论和算法的基础。
1979年,Khachiyan,1984年,Karmarkaa研究成功线性规划的多项式算法。
线性规划研究的主要问题
一类是已有一定数量的资源(人力、物质、时间等),研究如
何充分合理地使用它们,才能使完成的任务量为最大。
——实际上,上述两类问题是一个问题的两个不同的方面,都是求问
题的最优解( max 或 min )。
另一类是当一项任务确定以后,研究如何统筹安排,才能使完成
任务所耗费的资源量为最少。
第一章线性规划基础
某厂生产两种产品,下表给
出了单位产品所需资源及单位产品
利润
问:应如何安排生产计划,才能使
总利润最大?
§ 线性规划的基本概念
一、问题的提出
解:
:设产品I、II的产量分
别为 x1、x2
:设总运费为z,则有:
max z = 2 x1 + 3 x2
:
x1 + 2x2 ≤ 8
4x1 ≤ 16
4x2 ≤ 12

x1, x2≥0
某厂生产三种药物,这些药
物可以从四种不同的原料中提取。
下表给出了单位原料可提取的药物
量
要求:生产A种药物至少160单位;
B种药物恰好200单位,C种药物不
超过180单位,且使原料总成本最
小。
解:
:设四种原料的使用
量分别为: x1、x2 、x3 、x4
:设总成本为z,则有:
min z = 5 x1 + 6 x2 + 7 x3 + 8 x4
:
x1 + 2x2 + x3 + x4 ≥160
2x1 +4 x3 +2 x4 =160
3x1 +x2 +x3 +2 x4 ≤180

x1、x2 、x3 、x4≥0
药物
原料
A
B
C
单位成本
(元/吨)
甲
1
2
3
5
乙
2
0
1
6
丙
1
4
1
7
丁
1
2
2
8
二、数学模型
: X = (x1,x2,…..,xn)T
:max(minz) = c1 x1 + c2 x2 + ……. + cnxn
: a11x1 + a12 x2 +……..+ a1n xn ≤(=≥) b1
a21x1 + a22 x2 +……..+ a2n xn ≤(=≥) b2
…………………………………………
am1x1 + am2 x2 +……..+ amn xn ≤(=≥) bm
x1,x2,……xn≥0
§ 线性规划数学模型的建立
一、建模条件
1 优化条件:问题所要达到的目标能用线型函数描述,且能够用极值
(max 或 min)来表示;
2 限定条件:达到目标受到一定的限制,且这些限制能够用决策变量的
线性等式或线性不等式表示;
3 选择条件:有多种可选择的方案供决策者选择,以便找出最优方案。
二、建模步骤
1 确定决策变量:即需要我们作出决策或选择的量。一般情况下,题目
问什么就设什么为决策变量。
2 找出所有限定条件:即决策变量受到的所有的约束;
3 写出目标函数:即问题所要达到的目标,并明确是max 还是 min。
三、建模案例
某工厂生产A、B两种产品,有关资料如下表所示:
设总成本为z,A、B产品销量为x1、x2,
产品C的销售量为x3,报废量为x4,则:
max z = 4 x1 + 10 x2 + 3 x3 - 2 x4
2 x1 + 3x2 ≤ 12
3x1 + 4x2 ≤ 24
-2x2 +x3 + x4 = 0
x3 ≤ 5
x1、x2 、x3 、x4≥0