《第1讲序言线性规划模型》由会员分享，可在线阅读，更多相关《第1讲序言线性规划模型（57页珍藏版）》请在文档大全上搜索。
1、管理运筹学1管理运筹学管理运筹学四川大学商学院冯 结 制教师联系方式教师联系方式 冯结冯结 电话电话 : : 1898076527018980765270，8543600785436007（H H） 电子邮箱：电子邮箱：本课程学习要求本课程学习要求 1.1.必备三物：必备三物： 2. 2.成绩评定：成绩评定： 平时平时成绩占成绩占2020% % 期中期中测验占测验占20%20% 期末期末考试占考试占6060% %绪论 运筹学概述 运筹学的历史 运筹学与管理科学 运筹学的工作步骤 运筹学的主要分支 运筹学与计算机学习要求 1.了解运筹学的含义和历史。 2.掌握运筹学的工作步骤。 3.了解运筹学的
2、主要分支。 4.明了运筹学与计算机的关系。关于“运筹”一词 出自史记高祖本纪： 夫运筹帷幄之中，决胜于千里之外夫运筹帷幄之中，决胜于千里之外 英文名：Operations ResearchOperations Research， 或或Operational Research , Operational Research , 缩写为O.RO.R. 什么是运筹学？ 运筹学是一门应用于管理有组织系统的科学，为系统提供决策目标和数量分析的工具。 大英百科全书 运筹学“应用分析，实验，量化的方法，对经济管理系统中人，财，物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。” 中国
3、企业管理百科全书我们的看法 运筹学是研究一个系统的组织管理中可以定量的优化问题，它采用的主要方法是建立数学模型并求解。 运筹学可以称为“管理数学”。运筹学的历史 起源：主要因二次世界大战 创建：二战后至50年代初 成长：50 年代初至50年代末 普及：60年代至今核武器发展方向决策 数学模型： 其中，k ：毁伤力值 y ：爆炸力 c ：命中精度cyk232有关管理科学： 英文名：英文名：Management Sciences,Management Sciences,缩写为缩写为MSMS 开始于开始于1919世纪末世纪末2020世纪初。世纪初。 广义：是一门应用多学科多领域理论，方法和广义：是一
4、门应用多学科多领域理论，方法和技术的综合性交叉学科，研究人类管理活动的技术的综合性交叉学科，研究人类管理活动的社会行为和规律。社会行为和规律。 狭义：管理科学即决策的科学，定量部分主要狭义：管理科学即决策的科学，定量部分主要涉及运筹学，是一门采用科学方法分析和解决涉及运筹学，是一门采用科学方法分析和解决管理决策问题的技术科学。管理决策问题的技术科学。运筹学与管理科学 管理科学的发展有赖于其他学科的发展。 运筹学的目的在于为管理服务，是管理科学研究深化的标志。常见运筹学问题： 分配问题 库存问题 排队问题 决策问题 更新问题 路线问题 对抗问题 搜索问题 火炮设计问题 设计一火炮系统，使每门火炮
5、依次发射，设计一火炮系统，使每门火炮依次发射，只要有一门火炮击中目标，其余的火炮只要有一门火炮击中目标，其余的火炮就停止射击。为了有效地击中目标，采就停止射击。为了有效地击中目标，采用几门火炮最好？用几门火炮最好？问题分析问题分析 何谓何谓“有效有效”击中？影响因素有哪些？击中？影响因素有哪些？ 采用哪种数学模型？采用哪种数学模型？ 如何求解？如何求解？ 解是什么？解是什么？ 具体实施效果如何具体实施效果如何？运筹学的工作步骤 （1）分析与表述问题）分析与表述问题 （2）建立数学模型）建立数学模型 （3）模型求解）模型求解 （4）结果分析与模型检验）结果分析与模型检验 （5）方案实施）方案实施
6、运筹学的主要分支 1.线性规划线性规划 2.非线性规划非线性规划 3.图与网络分析图与网络分析 4.存贮论存贮论 5.决策论决策论 6.对策论对策论 7.动态规划动态规划 8.排队论排队论 . . . . . .常用运筹学软件常用运筹学软件 LINDO LINGO AB：QM WinQSB STORM第第1 1章章 线性规划线性规划 本章要求：本章要求： 1. 1.掌握并熟练应用线性规划的模型处理实际问题掌握并熟练应用线性规划的模型处理实际问题 2. 2.掌握线性规划的图解法掌握线性规划的图解法 3. 3.掌握单纯形法求解线性规划掌握单纯形法求解线性规划 4. 4.理解线性规划对偶问题的基本性
7、质理解线性规划对偶问题的基本性质 5. 5.理解有关灵敏度分析内容理解有关灵敏度分析内容 6. 6.了解运输问题的表上作业法求解了解运输问题的表上作业法求解 关于“线性规划” 英文名：Linear Programming,缩写为LP 自1947年丹齐格提出求解一般线性规划的有效方法单纯形法后，得到迅速发展，成为运筹学应用最广泛的分支。 特点： 1.应用广泛 2.模型简单易建 3.求解方法成熟线性规划是运筹学的重要组成部分，也是最线性规划是运筹学的重要组成部分，也是最基础的部分。自基础的部分。自1947年丹齐格（年丹齐格（G.B.Dantzig）提提出了求解线性规划的一般方法单纯形法以来，出了求
8、解线性规划的一般方法单纯形法以来，线性规划在理论上趋向成熟，日臻完善，尤其是线性规划在理论上趋向成熟，日臻完善，尤其是计算机处理问题的规模及运算速度提高后，线性计算机处理问题的规模及运算速度提高后，线性规划的应用领域更加广泛。无论工业、农业、商规划的应用领域更加广泛。无论工业、农业、商业、交通运输、军事、经济计划和管理决策等领业、交通运输、军事、经济计划和管理决策等领域都有应用。大到一个国家、一个地区，小到一域都有应用。大到一个国家、一个地区，小到一个企业、一个车间、一个班组都有运用线性规划个企业、一个车间、一个班组都有运用线性规划后提高经济效益的例子。后提高经济效益的例子。简介简介问题的提出
9、问题的提出在生产管理和经营活动中，组织常常必须对如在生产管理和经营活动中，组织常常必须对如何向不同的活动何向不同的活动分配资源分配资源的问题做出决策，以便最的问题做出决策，以便最好地达成组织的目标。好地达成组织的目标。这样的问题通常有两类，一类是如何合理地使这样的问题通常有两类，一类是如何合理地使用有限的劳动力、设备、资金等资源，以用有限的劳动力、设备、资金等资源，以最大化效益最大化效益；另一类是为了达到一定的目标，应如何组织生产，或另一类是为了达到一定的目标，应如何组织生产，或合理安排工艺流程，或调整产品的成分合理安排工艺流程，或调整产品的成分以以使资源使资源消耗最少消耗最少。向不同的活动分
10、配的资源可以是资金、不同的向不同的活动分配的资源可以是资金、不同的人员以及机器、设备。而需要这些资源的活动也可人员以及机器、设备。而需要这些资源的活动也可以是各类生产活动，例如产品生产、营销、在不同以是各类生产活动，例如产品生产、营销、在不同媒体做广告、金融活动、进行资金投资或其他一些媒体做广告、金融活动、进行资金投资或其他一些活动。活动。由于所有活动都要求一定资源作支撑，而资源由于所有活动都要求一定资源作支撑，而资源却是有限的，这必然导致活动间的冲突与矛盾。这却是有限的，这必然导致活动间的冲突与矛盾。这就需要管理者利用一些科学的方法进行协调，以使就需要管理者利用一些科学的方法进行协调，以使资
11、源达到最大的效用。资源达到最大的效用。显然，上述活动所引起的问题是一类显然，上述活动所引起的问题是一类有约束的有约束的最优化问题（最优化问题（Constrained Optimization）。线性规划线性规划正是解决有约束的最优化问题的一种正是解决有约束的最优化问题的一种常用的方法，其涉及的主要概念包括：常用的方法，其涉及的主要概念包括：目标（目标（Objective）:所要达到的最优结果（最所要达到的最优结果（最大或最小）；大或最小）；约束条件（约束条件（Constraints）:对所能产生结果的对所能产生结果的限制。限制。解决线性规划问题的一般步骤解决线性规划问题的一般步骤定义问题和定义
12、问题和收集数据收集数据。必须向管理者咨询所要。必须向管理者咨询所要考虑问题涉及到的数据及确定研究的合理目标。考虑问题涉及到的数据及确定研究的合理目标。建立模型建立模型，用恰当的数学式表示问题。，用恰当的数学式表示问题。求求出问题的出问题的最优解最优解。进行进行敏感性分析敏感性分析，检查条件发生变，检查条件发生变化时可能发生的情况。化时可能发生的情况。引例：引例：LPLP的应用的应用 例例1 1：大通曼哈顿银行员工工作安排：大通曼哈顿银行员工工作安排 例例2 2：航空公司机组人员排程：航空公司机组人员排程时间段时间段需求数需求数专职可用数专职可用数兼职可用数兼职可用数9.00-10.009.00
13、-10.001414292910.00-11.0010.00-11.002525292911.00-12.0011.00-12.0026261515111112.00-13.0012.00-13.0038381414262613.00-14.0013.00-14.0055552929262614.00-15.0014.00-15.0060602929313115.00-16.0015.00-16.0051512929222216.00-17.0016.00-17.00292929295 517.00-18.0017.00-18.0014149 95 518.00-19.0018.00-19.0
14、09 99 90 0利用利用LPLP安排的结果安排的结果专职员工数专职员工数开始开始员工数员工数午饭时间午饭时间员工数员工数离开离开2929人人9.009.00141411.00-12.0011.00-12.00202017.0017.00151512.00-13.0012.00-13.009 918.0018.00兼职员工数兼职员工数开始开始员工数员工数离开离开111111.0011.00 9 915.0015.002 216.0016.00151512.0012.00 151516.0016.005 514.0014.00 5 518.0018.00例例2 2：航空业的成本控制：航空业的成
15、本控制 航空业在航空业在19831983年和年和19841984年发生了史无前例的年发生了史无前例的行业竞争，尽管如此，联合航空公司还是开通了行业竞争，尽管如此，联合航空公司还是开通了4848个新机场的服务，并且取得了很大的增长。个新机场的服务，并且取得了很大的增长。19841984年，年，它是唯一的一家在美国全部它是唯一的一家在美国全部5050个州开通服务的公司，个州开通服务的公司，19841984年的收入比年的收入比19831983年增长了年增长了6 6个百分点，达到个百分点，达到6262亿美元，而同时成本的增长少于亿美元，而同时成本的增长少于2%2%，因此营运利润，因此营运利润提高，达到
16、了提高，达到了5.645.64亿美元。亿美元。 在航空业，在航空业，成本控制成本控制是关键。作为公是关键。作为公司管理扩展的一部分，美国航空公司的高司管理扩展的一部分，美国航空公司的高层管理部门实施了一个成本控制项目，目层管理部门实施了一个成本控制项目，目标是根据消费者的需求进行标是根据消费者的需求进行工作排程工作排程，以，以减少成本并且改进航空订票处和机场工作减少成本并且改进航空订票处和机场工作人员的利用率。人员的利用率。 美国航空公司机组人员美国航空公司机组人员线性规划排程介绍线性规划排程介绍建立线性规划模型建立线性规划模型 （1）确定确定决策变量决策变量：通常为非负，决策变量的：通常为非
17、负，决策变量的一组一组 取值称为线性规划的一组取值称为线性规划的一组解解，表示一个方，表示一个方案。案。（2）确定确定目标函数目标函数z z：它是决策变量的它是决策变量的线性函数线性函数，我们要使它取最大值或最小值。我们要使它取最大值或最小值。 （3）确定确定约束条件约束条件：可用决策变量的一组：可用决策变量的一组线性线性等式或不等式等式或不等式表示。表示。例：生产计划问题例：生产计划问题 某厂计划安排生产某厂计划安排生产A A，B B两种产品，已知生产单两种产品，已知生产单位产品的利润与所需的劳动力，设备台时及原位产品的利润与所需的劳动力，设备台时及原材料的消耗如图所示。问应该如何安排生产获
18、材料的消耗如图所示。问应该如何安排生产获利最大？利最大？产品产品A A产品产品B B资源限制资源限制劳动力（工时）劳动力（工时） 设备（台时）设备（台时） 原材料（公斤）原材料（公斤）9 9 4 4 3 34 4 5 5 1010360 360 200 200 300300单位产品利润（元）单位产品利润（元）7070120120实例：实例：潘得罗索潘得罗索公司的产品组合公司的产品组合 潘得罗索工业公司是一家墨西哥公司，截止潘得罗索工业公司是一家墨西哥公司，截止1998年，公司产销量占该国的四分之一。年，公司产销量占该国的四分之一。 与其他胶合板生产厂商一样，潘得罗索工业与其他胶合板生产厂商一样
19、，潘得罗索工业公司的许多产品因厚度和所用木材的质量而有所不公司的许多产品因厚度和所用木材的质量而有所不同。由于产品在一个竞争的环境中进行销售，产品同。由于产品在一个竞争的环境中进行销售，产品的价格由市场决定，所以产品的价格每月都有很大的价格由市场决定，所以产品的价格每月都有很大的变化。结果导致每项产品对公司整体利润的贡献的变化。结果导致每项产品对公司整体利润的贡献也有很大的变化。这样，在某个月一个产品可能比也有很大的变化。这样，在某个月一个产品可能比另一个产品赚取更大的利润，而在下一个月的情况另一个产品赚取更大的利润，而在下一个月的情况则可能正好相反。则可能正好相反。 所以，每个月管理层面临的
20、关键问题所以，每个月管理层面临的关键问题是是选择产品组合选择产品组合（Product Mix），），以尽可以尽可能多地获取利润。能多地获取利润。 这一选择是很复杂的，因为它需要考这一选择是很复杂的，因为它需要考虑当前生产产品必须的虑当前生产产品必须的各种资源各种资源的可得数的可得数量。六项最重要的资源为：量。六项最重要的资源为：四种类型四种类型的的原木原木（根据原木的质量区分）；生产胶（根据原木的质量区分）；生产胶合板的两项关键作业的合板的两项关键作业的生产能力生产能力（磨压作磨压作业业和和抛光作业抛光作业）。）。从从1980年开始，潘得罗索工业公司管理部门每年开始，潘得罗索工业公司管理部门每
21、个月使用个月使用线性规划线性规划决定下个月的产品组合决策。线决定下个月的产品组合决策。线性规划的数学模型考虑了这一决策的所有相关限制性规划的数学模型考虑了这一决策的所有相关限制条件，包括生产产品所需的有限的可得资源，然后条件，包括生产产品所需的有限的可得资源，然后求解模型，找出可行并且最大的可能利润产品组合。求解模型，找出可行并且最大的可能利润产品组合。 线性规划还给潘得罗索工业公司的管理层提供线性规划还给潘得罗索工业公司的管理层提供了其它一些了其它一些有价值的生产信息有价值的生产信息，包括当前生产中某，包括当前生产中某一特定资源的采购决策及其对利润的影响。例如，一特定资源的采购决策及其对利润
22、的影响。例如，假设公司为生产某一特别赚钱的产品所需的某类原假设公司为生产某一特别赚钱的产品所需的某类原木只有少量供应，线性规划将表明如果赶紧购买该木只有少量供应，线性规划将表明如果赶紧购买该类原木会对产品组合以及利润产生多大的影响。类原木会对产品组合以及利润产生多大的影响。采用线性规划后，潘得罗索工业采用线性规划后，潘得罗索工业公司的成绩是显著的。产品组合调整公司的成绩是显著的。产品组合调整使公司总利润增加了使公司总利润增加了20%，线性规划，线性规划的其他贡献包括更好的原材料利用、的其他贡献包括更好的原材料利用、更好的资本投资和更好的人员利用。更好的资本投资和更好的人员利用。LP应用效果应用
23、效果建立线性规划问题的数学模型建立线性规划问题的数学模型例例1：一家玻璃制品公司生产带有花样图案的彩：一家玻璃制品公司生产带有花样图案的彩色玻璃花瓶。每一个花瓶经过艺术玻璃吹风机从液态色玻璃花瓶。每一个花瓶经过艺术玻璃吹风机从液态加工加工而成，然后而成，然后进入储藏室冷却进入储藏室冷却至室温。花瓶有大、至室温。花瓶有大、小两种尺寸，但生产过程几乎相当，而且使用同一种小两种尺寸，但生产过程几乎相当，而且使用同一种材料材料。不论尺寸，每一个花瓶都需要。不论尺寸，每一个花瓶都需要20分钟的艺术加分钟的艺术加工，每周艺术加工工作时间为工，每周艺术加工工作时间为40小时；大、小花瓶每小时；大、小花瓶每个
24、需彩色玻璃个需彩色玻璃2 OZ和和1 OZ，每周可用的玻璃为每周可用的玻璃为160 OZ；另外，一个小花瓶占用另外，一个小花瓶占用2单位储存空间，大花瓶占用单位储存空间，大花瓶占用3个单位储存空间，一共有个单位储存空间，一共有260个储存空间。大、小花瓶个储存空间。大、小花瓶的利润贡献率分别为的利润贡献率分别为12元元/个和个和10元元/个。问应该怎样安个。问应该怎样安排生产，利润值最大。排生产，利润值最大。花瓶种类花瓶种类占用材料占用材料（OZ）艺术加工艺术加工（小时）（小时）储存空间储存空间（1单位）单位）利润值利润值（元）（元）大花瓶大花瓶21/3312小花瓶小花瓶11/3210每周可用
25、每周可用能力能力16040260分析建模分析建模：用：用B表示每周生产大花瓶的数量，表示每周生产大花瓶的数量，S表示每周生产小花瓶的数量，则表示每周生产小花瓶的数量，则决策变量决策变量为为B、S。目标函数：目标函数：SBZ1012max材料约束：材料约束：1602 SB时间约束：时间约束：403131SB储存约束储存约束：26023 SB非负约束：非负约束：0, 0SBLP模型模型：0, 0260234031311602. .1012maxSBSBSBSBtsSBZ由上可知，由上可知，LP数学建模过程主要有三个步骤：数学建模过程主要有三个步骤：确定确定决策变量决策变量；确定确定目标函数目标函数
26、；确定确定约束条件约束条件（包括非负约束）（包括非负约束）。 例例2：某寻呼台每天需要话务员人数、：某寻呼台每天需要话务员人数、值班时间以及工资情况如下表所示。每班话值班时间以及工资情况如下表所示。每班话务员在轮班开始时报到，并连续工作务员在轮班开始时报到，并连续工作9小时。小时。问如何安排，使得既满足需求又使总支付工问如何安排，使得既满足需求又使总支付工资最低，试建立数学模型。资最低，试建立数学模型。时时 间间最少人数最少人数每人工资每人工资0 03 36 660603 36 64 460606 69 98 855559 91212101050501212151513134848151518
27、18151545451818212113135050212124248 85656分析建模分析建模：决策变量为：决策变量为从第从第 i 班开始工作班开始工作的人的人数，设为数，设为 xi（i =1,2,3,4,5,6,7,8）。）。目标函数目标函数：)(56)(50)(45)(48)(50)(55)(60)(60min876765654543432321218187xxxxxxxxxxxxxxxxxxxxxxxxZ第班人数约束：第班人数约束：6187xxx第班人数约束：第班人数约束：4218xxx第班人数约束：第班人数约束：8321xxx第班人数约束：第班人数约束：10432xxx第班人数约束
28、：第班人数约束：13543xxx第班人数约束：第班人数约束：15654xxx第班人数约束：第班人数约束：13765xxx第班人数约束：第班人数约束：8876xxx非负约束：非负约束：)8 , 7 , 6 , 5 , 4 , 3 , 2 , 1(0ixiLP模型模型：)8 , 7 , 6 , 5 , 4 , 3 , 2 , 1(0813151310846. .176166151143143153165175min87676565454343232121818787654321ixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxZi例例3：某集团有：某集团有1000000元资金
29、供投资，该集团有元资金供投资，该集团有5个可个可供选择的投资项目，其中各种资料如下表：供选择的投资项目，其中各种资料如下表：投资项目投资项目风险，风险，%红利，红利，%增长，增长，%信用度信用度110510112681783187141041262245410710该集团的目标为：投资风险最小，每年红利至少该集团的目标为：投资风险最小，每年红利至少80000元，最低平均增长率元，最低平均增长率14%，最低平均信用度，最低平均信用度6，请用线性规划，请用线性规划方法描述该问题方法描述该问题。分析建模分析建模：决策变量为各项目的投资数额，设为：决策变量为各项目的投资数额，设为 xi（i =1,2,
30、3,4,5）。）。目标函数目标函数：5432104. 012. 018. 006. 01 . 0minxxxxxZ投资额约束：投资额约束：红利约束：红利约束：增长额约束增长额约束：平均信用度约束：平均信用度约束：100000054321xxxxx800001 . 006. 007. 008. 005. 054321xxxxx14000007. 022. 014. 017. 01 . 054321xxxxx65/ )10410811(54321xxxxx非负约束：非负约束：)5 , 4 , 3 , 2 , 1(0ixiLP模型模型：) 5 , 4 , 3 , 2 , 1( 065/ )10410
31、811(14000007. 022. 014. 017. 01 . 0800001 . 006. 007. 008. 005. 01000000. .04. 012. 018. 006. 01 . 0min5432154321543215432154321ixxxxxxxxxxxxxxxxxxxxxt sxxxxxZi例例4：某石油公司利用三种油料生产两种混合：某石油公司利用三种油料生产两种混合原料。每种油的成本和每天的可用量如表所示：原料。每种油的成本和每天的可用量如表所示：油油成本，元成本，元/L可用量，可用量，LA810000B1015000C1220000两种混合原料中各种油料所占比例
32、如下表所示：两种混合原料中各种油料所占比例如下表所示：混合原料混合原料油料油料A油料油料B油料油料C1最多占最多占25%最少占最少占30%最多占最多占40%2最少占最少占20%最多占最多占50%最少占最少占30%原料售价为原料售价为30元元/L，原料售价为原料售价为35元元/L，该公该公司有一项长期合同，每天供应两种原料各司有一项长期合同，每天供应两种原料各10000L。试建立该问题的数学规划模型。试建立该问题的数学规划模型。分析建模分析建模：决策变量为：决策变量为加入到原料中的各种油加入到原料中的各种油料料的量：的量：A 1为加入原料中的油料为加入原料中的油料 A 的升数；的升数；A 2为加
33、入原料中的油料为加入原料中的油料 A 的升数；的升数；B 1为加入原料中的油料为加入原料中的油料 B 的升数；的升数；B 2为加入原料中的油料为加入原料中的油料 B 的升数；的升数；C 1为加入原料中的油料为加入原料中的油料 C 的升数；的升数；C 2为加入原料中的油料为加入原料中的油料 C 的升数。的升数。两种原料的销售收入：两种原料的销售收入：30（ABC）35（ABC）三种油料的成本：三种油料的成本：8（AA 2 2）10（BB 2 2）12（CC 2 2）目标函数目标函数为：为：212121231825202722maxCCBBAAZ三种可用油料的约束：三种可用油料的约束：各种油料所占
34、比例的约束：各种油料所占比例的约束：200001500010000212121CCBBAA)( 3 . 0)(5 . 0)(2 . 0)(4 . 0)( 3 . 0)(25. 0222222222222111111111111CBACCBABCBAACBACCBABCBAA长期供货合同约束：长期供货合同约束：1000010000222111CBACBA非负约束：非负约束：)2 , 1(0,iCBAiiiLPLP模型模型？线性规划的一般模型线性规划的一般模型 目标函数：目标函数：Max(minMax(min) z=c) z=c1 1x x1 1+c+c2 2x x2 2+ +c+cn nx xn
35、 n 约束条件：约束条件： a a1111x x1 1+a+a1212x x2 2+ +a+a1n1nx xn n ( (，= =) ) b b1 1 a a2121x x1 1+a+a2222x x2 2+ +a+a2n2nx xn n ( (，= =) ) b b2 2 . . a am1m1x x1 1+a+am2m2x x2 2+ + +a amnmnx xn n ( (，= =) ) b bm m注：决策变量，指注：决策变量，指x x1 1,x,x2 2, , ,x xn n 可行解：指满足所有约束条件的一组决策变量可行解：指满足所有约束条件的一组决策变量. . 最优解：使目标函数最大（或最小）的可行解最优解：使目标函数最大（或最小）的可行解. . 谢谢 谢！谢！ 再再 见！见！
