第2讲规划技术--线性规划0

第二讲规划技术 线性规划四川大学工商管理学院管理科学系 钟 胜 副教授Tel： 84533811 Email： L I N E A R P R O G R A M M I N G04年 7月 1管理运筹学讲义Linear programming(LP) is a tool for solving optimization problems.In 1947, George Dantzig developed an efficient method, the simplex algorithm, for solving linear programming problems. Since the development of the simplex algorithm, LP has been used to solve optimization problems in industries as diverse as banking, education, forestry, petroleum, and trucking. In a survey of Fortune 500 firms, 85% of those responding said that they had used LP.04年 7月 2管理运筹学讲义线性规划 (Linear Programming)是运筹学的重要组成部分，也是最基础的部分。自 1947年丹齐格 (G.B.Dantzig)提出了求解线性规划的一般方法单纯形法以来，线性规划在理论上趋向成熟，日臻完善，尤其是计算机处理问题的规模及运算速度提高后，线性规划的应用领域更加广泛。无论工业、农业、商业、交通运输、军事、经济计划和管理决策等领域都有应用。大到一个国家、一个地区，小到一个企业、一个车间、一个班组都有运用线性规划后提高经济效益的例子。04年 7月 3管理运筹学讲义第一节 线性规划的模型与图解法第二节 单纯形法第三节 对偶问题与灵敏度分析第四节 线性规划软件简介第五节 运输问题第六节 线性整数规划第七节 线性规划应用实例04年 7月 4管理运筹学讲义See You!04年 7月 5管理运筹学讲义第一节 线性规划的模型与图解法1.1 线性规划问题及其数学模型1.2 两变量问题的图解法1.3 线性规划模型的标准形式及解的概念04年 7月 6管理运筹学讲义1.1 线性规划问题及其数学模型1.1.1 线性规划问题的提出及主要概念1.1.2 线性规划问题的数学模型In this section,we introduce linear programming and define some important terms that are used to describe linear programming problems.04年 7月 7管理运筹学讲义1.1.1 线性规划问题的提出及主要概念在生产管理和经营活动中，组织常常必须对如何向不同的活动分配资源的问题做出决策，以便最好地达成组织的目标。这样的问题通常有两类， 一类 是如何合理地使用有限的劳动力、设备、资金等资源，以最大化效益； 另一类 是为了达到一定的目标，应如何组织生产，或合理安排工艺流程，或调整产品的成分 以使资源消耗最少。04年 7月 8管理运筹学讲义向不同的活动分配的资源可以是资金、不同的人员以及机器、设备。而需要这些资源的活动也可以是各类生产活动，例如产品生产、营销、在不同媒体做广告、金融活动、进行资金投资或其他一些活动。由于所有活动都要求一定资源作支撑，而资源却是有限的，这必然导致活动间的冲突与矛盾。这就需要管理者利用一些科学的方法进行协调，以使资源达到最大的效用。04年 7月 9管理运筹学讲义显然，上述活动所引起的问题是一类 有约束的最优化问题 （ Constrained Optimization）。线性规划 正是解决有约束的最优化问题的一种常用的方法，其涉及的 主要概念 包括：决策变量（ Decision Variables） :最优化问题的决策对象；约束条件（ Constraints） :对决策所能产生的结果的限制。目标（ Objective） :决策所希望达到的最优结果（最大或最小）；04年 7月 10管理运筹学讲义解决线性规划问题的过程通常分为四个步骤：定义问题和收集数据。 必需向管理者咨询所要 考虑问题涉及到的数据及确定研究的合理目标。建立模型，用恰当的数学式表示问题。求出问题的最优解。进行敏感性分析，检查条件发生变化时可能发 生的情况。04年 7月 11管理运筹学讲义案例 1： 潘得罗索工业公司的产品组合潘得罗索工业公司是一家墨西哥公司，截止1998年，公司产销量占该国的四分之一。与其他胶合板生产厂商一样，潘得罗索工业公司的许多产品因厚度和所用木材的质量而有所不同。由于产品在一个竞争的环境中进行销售，产品的价格由市场决定，所以产品的价格每月都有很大的变化。结果导致每项产品对公司整体利润的贡献也有很大的变化。这样，在某个月一个产品可能比另一个产品赚取更大的利润，而在下一个月的情况则可能正好相反。04年 7月 12管理运筹学讲义所以，每个月管理层面临的 关键问题 是选择产品组合（ Product Mix）， 以尽可能多地获取利润。这一选择是很复杂的，因为它需要考虑当前生产产品必须的 各种资源的可得数量 。六项最重要的资源为： 四种类型的原木（根据原木的质量区分）； 生产胶合板的两项关键作业的生产能力（磨压作业和抛光作业）。04年 7月 13管理运筹学讲义从 1980年开始，潘得罗索工业公司管理部门每个月使用 线性规划 决定下个月的产品组合。线性规划的数学模型考虑了这一决策的所有相关限制条件，包括生产产品所需的有限的可得资源，然后求解模型，找出 可行并且最大的可能利润产品组合 。线性规划还给潘得罗索工业公司的管理层提供了其它一些有价值的信息，包括 当前生产中某一特定资源的采购决策及其对利润的影响 。例如，假设公司为生产某一特别赚钱的产品所需的某类原木只有少量供应，线性规划将表明如果赶紧购买该类原木会对产品组合以及利润产生多大的影响。04年 7月 14管理运筹学讲义采用线性规划后，潘得罗索工业公司的成绩是显著的。产品组合调整使公司总利润增加了 20% ，线性规划的其他贡献包括更好的原材料利用、更好的资本投资和更好的人员利用。04年 7月 15管理运筹学讲义案例 2： 航空业的成本控制航空业在 1983年和 1984年发生了史无前例的行业竞争，尽管如此，联合航空公司还是开通了 48个新机场的服务，并且取得了很大的增长。 1984年，它是唯一的一家在美国全部 50个州开通服务的公司， 1984年的收入比 1983年增长了 6个百分点，达到 62亿美元，而同时成本的增长少于 2% ，因此营运利润提高，达到了 5.64亿美元。04年 7月 16管理运筹学讲义在航空业， 成本控制是关键 。作为公司管理扩展的一部分， 1982年联合航空公司的高层管理部门实施了一个成本控制项目， 目标 是根据消费者的需求进行 工作排程 ，以 改进航空订票处和机场工作人员的利用率 。那时，联航在其 11个航班订票处有超过 4000名机场销售代表和支持人员。在 10个最大的机场，大约有 1000名顾客服务代表，有些是兼职的，每班 28小时不等；大部分是全职的，每班 810小时，有许多不同的上班时间。每个订票处都是全天 24小时营业（通过电话订票），各个重要的机场也是如此。04年 7月 17管理运筹学讲义为了更有效地满足服务要求，在每个地点为所有员工进行工作排程，这是一个组合的梦魇。一旦一名雇员上了班，就会工作一个班次（ 210小时不等），只有就餐和每隔两个小时短暂的休息时间。那么，一周 7天及一天 24小时，每个班次需要多少雇员上班呢？如何排程？幸运的是，线性规划能解决这些组合的梦魇问题。据估计，建立在线性规划基础上的计算机规划系统每年为联合航空公司在直接薪酬和津贴成本上节省了 600万美元，得到的其它好处包括改善客户服务以及降低雇员的工作负担。04年 7月 18管理运筹学讲义1.1.2 线性规划问题的数学模型例 1： 一家玻璃制品公司生产带有花样图案的彩色玻璃花瓶。每一个花瓶经过艺术玻璃吹风机从液态加工而成，然后进入储藏室冷却至室温。花瓶有大、小两种尺寸，但生产过程几乎相当，而且使用同一种材料。不论尺寸，每一个花瓶都需要 20分钟的艺术加工，每周艺术加工工作时间为 40小时；大、小花瓶每个需彩色玻璃 2 OZ和 1 OZ， 每周可用的玻璃为 160 OZ； 另外，一个小花瓶占用 2单位储存空间，大花瓶占用 3个单位储存空间，一共有 260个储存空间。大、小花瓶的利润贡献率分别为 12元 /个和 10元 /个。问应该怎样安排生产，利润值最大。04年 7月 19管理运筹学讲义花瓶种 类 占用材料（ OZ）艺术 加工（小 时 ）储 存空间 （ 1单位）利 润值（元）大 花瓶 2 1/3 3 12小 花瓶 1 1/3 2 10每周可用能力 160 40 260 04年 7月 20管理运筹学讲义分析建模 ： 用 B表示每周生产大花瓶的数量，S表示每周生产小花瓶的数量，则决策变量 (Decision Variables)为 B、 S。目标函数 (Objective Function)：材料约束 (Constraint of material)：时间约束 (Constraint of time)：储存约束 (Constraint of inventory)：非负约束 (Sign restriction) ：04年 7月 21管理运筹学讲义模型 ：04年 7月 22管理运筹学讲义由上可知，数学建模过程主要有四个步骤： 确定决策变量； 确定目标函数； 确定约束条件； 确定非负约束。04年 7月 23管理运筹学讲义例 2： 某寻呼台每天需要话务员人数、值班时间以及工资情况如下表所示。每班话务员在轮班开始时报到，并连续工作 9小时。问如何安排，使得既满足需求又使总支付工资最低，试建立数学模型。04年 7月 24管理运筹学讲义时 间 最少人数 每人工 资0 3 6 603 6 4 606 9 8 559 12 10 5012 15 13 4815 18 15 4518 21 13 5021 24 8 5604年 7月 25管理运筹学讲义分析建模 ： 决策变量为从第 i 班 开始工作的人数 ， 设为 xi（ i =1,2,3,4,5,6,7,8）。目标函数 ：04年 7月 26管理运筹学讲义第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：第班人数约束：非负约束：04年 7月 27管理运筹学讲义模型 ：04年 7月 28管理运筹学讲义例 3： 某集团有 1000000元资金供投资，该集团有 5个可供选择的投资项目，其中各种资料如下表：投 资项 目 风险 (%) 红 利 (%) 增