《运筹学教学资料》运筹学第1章1-2节.ppt

Chapter1 线性规划(Linear Programming )
线性规划问题及其模型
线性规划问题几何意义
单纯形法
单纯形法计算步骤
单纯形法进一步讨论
应用举例
掌握Excel软件求解线性规划
本章主要内容:
线性规划是运筹学的一个重要分支,是研究较早、理论较完善、应用最广泛的一个学科。
由前苏联经济学家康托洛维奇于1939年提出,而此人也因此获得1960年的诺贝尔经济学奖。
1947年, (丹捷格)提出求线性规划的单纯形法,理论上趋向成熟,实际上的应用也越来越广泛。
因此,线性规划是求一组变量的值,使它满足一组线性式子,并使一个线性函数的值最大(或最小)的数学方法。
线性规划不仅仅是一种数学理论和方法,而且已成为现代管理工作中帮助管理者做出科学决策的重要手段。
线性规划所研究的问题主要包括两个方面:
一是在一项任务确定后,如何以最低成本(如人力、物力、
资金和时间等)去完成这一任务;
二是如何在现有资源条件下进行组织和安排,以产生最大收益。
第一章线性规划
§1 线性规划问题及其模型
§2 线性规划问题几何意义
§3 单纯形法
§4 单纯形法计算步骤
§5 单纯形法进一步讨论
§6 应用举例
问题的提出
在生产管理和经营活动中经常需要解决:如何合理地利用有限的资源,以得到最大的效益。
我们先通过几个实际问题来认识什么是线性规划。
问题的提出
【例1】某企业生产 A1, A2, A3三种产品,这些产品分别需要甲、乙两种原料。。(生产计划问题)
利润最大化问题
试问:该企业怎样安排生产才会使每天的利润最大?
企业生产数据表
问题的提出
解设该企业每天生产产品的数量分别为(单位:吨),则总利润的表达式为

(原料甲的限制)
(原料乙的限制)
此外,由于未知数(我们称之为决策变量) 是计划产量,
应有为非负的限制,即
问题的提出
由此得到问题的数学模型为
“subject to”的缩写,表示决策变量xj(j=1,2,3) 受它后面的条件约束.
问题的提出
决策变量:需决策的量,即待求的未知数;
目标函数:需优化的量,即欲达的目标,用决策变量的表达式表示;
约束条件:为实现优化目标需受到的限制,用决策变量的等式或不等式表示。
线性规划模型的三要素
问题的提出
练习1 某企业要在计划期内安排生产甲、乙两种产品,这个企业现有的生产资料是:设备18台时,原材料A 4吨,原材料B12吨;已知单位产品所需消耗生产资料及利润如下表。问应如何确定生产计划使企业获利最多。
产品
资源
甲
乙
资源量
设备/机时
3
2
18
原料A/吨
1
0
4
原料B/吨
0
2
12
单位赢利/万元
3
5
问题的提出