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

《运筹学基础-线性规划(方法).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章线性规划及单纯形法本章主要内容线性规划概述绪论一般线性规划问题的数学模型线性规划问题的图解法线性规划的基本定理单纯形法用计算机软件求解线性规划问题线性规划的应用举例2【开篇案例】某旅行社为了迎接旅游黄金周的到来，对一日游导游人员的需求经过统计分析如表所示。为了保证导游充分休息，导游每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排导游人员的作息，既满足工作需要，又使配备的导游人数最少？一、人力资源分配的问题线性规划时间所需导游人数星期日40星期一34星期二32星期三35星期四28星

2、期五46星期六423【开篇案例】明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如右表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？二、生产计划的问题线性规划4【开篇案例】某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，使利润收入为最大？三、配料问题线性规划5【开篇

3、案例】某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元；四、投资问题问：a.应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金

4、额为最大？b.应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？线性规划6归纳上述研究的主要内容：（2）计划任务确定的情况旧：如何统筹安排，精心筹划，用最少的资源来实现。这方面的问题涉及到系统的投入和求极小值问题（1）资源确定的情况下：如何合理利用、合理规划，使得完成的任务最大。这方面的问题涉及到系统的产出和求最大值问题研究和应用的内容是实现系统的投入产出的问题，就是用最少的劳力和物力消耗，获利更多更好的社会需求产品。此项研究即为规划问题线性

5、规划7线性规划是运筹学的一个重要分支。自1947年美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法——单纯形法之后，线性规划在理论上趋于成熟，在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后，它的适用领域更广泛了。线性规划概述线性规划是一种合理利用资源、合理调配资源的应用数学方法。其中：规划就是利用某种数学方法使得有效资源的运用最优化；线性就是用来描述就是之间关系的函数是线性函数。线性规划8在生产管理和经济活动中经常提出这样一

6、类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。在管理中一些典型的线性规划应用主要包括：合理利用线材问题：如何下料使用材最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大产品生产计划：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小问题：如何建立线性规划模型？线性规划盈亏平衡问题：掌握企业盈亏界限，合理安排生产能力9【引例】生产计划的问题某企业生产Ⅰ、Ⅱ两

7、种产品。这两种产品都要分别在A、B、C、D四各不同设备上加工。生产每件产品Ⅰ需占用各设备为2、1、4、0小时，生产每件产品Ⅱ需占用各设备为2、2、0、4小时，各设备用于生产这两种产品的能力分别为12、8、16、12小时，又知生产一件产品Ⅰ获得2元，生产Ⅱ获得3元，问如何安排生产，使总的利润最大。§1.1一般线性规划问题的数学模型则该问题的数学模型表示为maxZ=2x1+3x22x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1≥0,x2≥0设生产Ⅰ、Ⅱ产品为x1、x2件问题：建立线性

8、规划模型要考虑的关键要素？线性规划10一、线性规划问题的三大要素决策变量是指实际系统或决策问题中有待确定的因素，是系统中的可控因素。如生产Ⅰ、Ⅱ产品为x1、x2件，x1、x2即为决策变量决策变量的取值范围。如此题的x1≥0、x2≥0约束条件任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。如设备能力、原材料数量等是决策者对决策问题目标的数学描述。如时间最省、利润最大、成本最低。此题是利润最大maxZ=2x1+3x2