运筹学基础-线性规划(方法).ppt

第一章
线性规划及单纯形法
本章主要内容
线性规划概述
绪论
一般线性规划问题的数学模型
线性规划问题的图解法
线性规划的基本定理
单纯形法
用计算机软件求解线性规划问题
线性规划的应用举例
2
【开篇案例】
某旅行社为了迎接旅游黄金周的到来,对一日游导游人员的需求经过统计分析如表所示。为了保证导游充分休息,导游每周工作 5天,休息两天,并要求休息的两天是连续的。问应该如何安排导游人员的作息,既满足工作需要,又使配备的导游人数最少?
一、人力资源分配的问题
线性规划
时间
所需导游人数
星期日
40
星期一
34
星期二
32
星期三
35
星期四
28
星期五
46
星期六
42
3
【开篇案例】
明兴公司生产甲、乙、丙三种产品,都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作,亦可以自行生产,但产品丙必须本厂铸造才能保证质量。数据如右表。问:公司为了获得最大利润,甲、乙、丙三种产品各生产多少件?甲、乙两种产品的铸造中,由本公司铸造和由外包协作各应多少件?
二、生产计划的问题
线性规划
4
【开篇案例】
某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙,数据如右表。问:该厂应如何安排生产,使利润收入为最大?
三、配料问题
线性规划
5
【开篇案例】
某部门现有资金200万元,今后五年内考虑给以下的项目投资。已知:项目A:从第一年到第五年每年年初都可投资,当年末能收回本利110%;项目B:从第一年到第四年每年年初都可投资,次年末能收回本利125%,但规定每年最大投资额不超过30万元;项目C:需在第三年年初投资,第五年末能收回本利140%,但规定最大投资额不能超过80万元;项目D:需在第二年年初投资,第五年末能收回本利155%,但规定最大投资额不能超过100万元;
四、投资问题
问:,使得第五年年末拥有资金的本利金额为最大?
,使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小?
线性规划
6
归纳上述研究的主要内容:
(2)计划任务确定的情况旧:如何统筹安排,精心筹划,用最少的资源来实现。
这方面的问题涉及到系统的投入和求极小值问题
(1)资源确定的情况下:如何合理利用、合理规划,使得完成的任务最大。
这方面的问题涉及到系统的产出和求最大值问题
研究和应用的内容是实现系统的投入产出的问题,就是用最少的劳力和物力消耗,获利更多更好的社会需求产品。
此项研究即为规划问题
线性规划
7
线性规划是运筹学的一个重要分支。
自1947年美国数学家丹捷格()提出了求解线性规划问题的方法——单纯形法之后,线性规划在理论上趋于成熟,在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后,它的适用领域更广泛了。
线性规划概述
线性规划是一种合理利用资源、合理调配资源的应用数学方法。
其中:规划就是利用某种数学方法使得有效资源的运用最优化;线性就是用来描述就是之间关系的函数是线性函数。
线性规划
8
在生产管理和经济活动中经常提出这样一类问题, 即如何合理地利用有限的人力、物力、财力等资源,以便得到最好的经济效果。
在管理中一些典型的线性规划应用
主要包括:
合理利用线材问题:如何下料使用材最少
配料问题:在原料供应量的限制下如何获取最大利润
投资问题:从投资项目中选取方案,使投资回报最大
产品生产计划:合理利用人力、物力、财力等,使获利最大
劳动力安排:用最少的劳动力来满足工作的需要
运输问题:如何制定调运方案,使总运费最小
问题:如何建立线性规划模型?
线性规划
盈亏平衡问题:掌握企业盈亏界限,合理安排生产能力
9
【引例】生产计划的问题
某企业生产Ⅰ、Ⅱ两种产品。这两种产品都要分别在A、B、C、D四各不同设备上加工。生产每件产品Ⅰ需占用各设备为2、1、4、0小时,生产每件产品Ⅱ需占用各设备为2、2、0、4小时,各设备用于生产这两种产品的能力分别为12、8、16、12小时,又知生产一件产品Ⅰ获得2元,生产Ⅱ获得3元,问如何安排生产,使总的利润最大。
§ 一般线性规划问题的数学模型
则该问题的数学模型表示为
maxZ= 2x1 +3x2
2x1+2x2 ≤12
x1 +2x2 ≤8
4x1 ≤16
4x2 ≤12
x1 ≥0, x2 ≥0
设生产Ⅰ、Ⅱ产品为x1、x2件
问题:建立线性规划模型要考虑的关键要素?
线性规划
10