《运筹学基础及应用》PPT完整版

运运筹筹学学(OperationsResearch)经济学核心课程经济学核心课程经济学核心课程经济学核心课程绪绪论论（1）运筹学简述）运筹学简述（2）运筹学的主要内容）运筹学的主要内容（3）本课程的教材及参考书）本课程的教材及参考书（4）本课程的特点和要求）本课程的特点和要求（5）本课程授课方式与考核）本课程授课方式与考核（6）运筹学在工商管理中的应用）运筹学在工商管理中的应用本章主要内容：本章主要内容：Page3运筹学简述运筹学简述运筹学（运筹学（OperationsResearch）系统工程的最重要的理论基础之一，在美国有人把运系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学筹学称之为管理科学(ManagementScience)。运筹学所研。运筹学所研究的问题，可简单地归结为一句话：究的问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案依照给定条件和目标，从众多方案中选择最佳方案”故有人称之为最优化技术。故有人称之为最优化技术。Page4运筹学简述运筹学简述运筹学的历史运筹学的历史“运作研究运作研究(OperationalResearch)小组小组”:解决解决复杂的战略和战术问题。例如：复杂的战略和战术问题。例如：1.如何合理运用雷达有效地对付德军德空袭如何合理运用雷达有效地对付德军德空袭2.对商船如何进行编队护航，使船队遭受德国潜对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；艇攻击时损失最少；3.在各种情况下如何调整反潜深水炸弹的爆炸深在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。度，才能增加对德国潜艇的杀伤力等。Page5运筹学的主要内容运筹学的主要内容数学规划（数学规划（线性规划、整数规划、目标规划线性规划、整数规划、目标规划、动态、动态规划等）规划等）图论图论存储论存储论排队论排队论对策论对策论排序与统筹方法排序与统筹方法决策分析决策分析Page6本课程的教材及参考书本课程的教材及参考书选用教材选用教材 运筹学基础及应用运筹学基础及应用胡运权主编胡运权主编 哈工大出版社哈工大出版社参考教材参考教材运筹学教程运筹学教程胡运权主编胡运权主编 （第（第2 2版）清华出版社版）清华出版社管理运筹学管理运筹学韩伯棠主编韩伯棠主编 （第（第2 2版）高等教育出版社版）高等教育出版社运筹学运筹学(修订版修订版)钱颂迪主编钱颂迪主编 清华出版社清华出版社Page7本课程的特点和要求本课程的特点和要求先修课：先修课：高等数学，基础概率、线性代数高等数学，基础概率、线性代数特点：特点：系统整体优化；多学科的配合；模型方法的应用系统整体优化；多学科的配合；模型方法的应用运筹学的研究的主要步骤：运筹学的研究的主要步骤：真实系统真实系统系统分析系统分析问题描述问题描述模型建立模型建立与修改与修改模型求解模型求解与检验与检验结果分析与结果分析与实施实施数据准备数据准备Page8本课程授课方式与考核本课程授课方式与考核学科总成绩学科总成绩平时成绩平时成绩（4040）课堂考勤课堂考勤（5050）平时作业平时作业（5050）期末成绩期末成绩（6060）讲授为主，结合习题作业讲授为主，结合习题作业Page9运筹学在工商管理中的应用运筹学在工商管理中的应用运筹学在工商管理中的应用涉及几个方面：运筹学在工商管理中的应用涉及几个方面：1.1.生产计划生产计划2.2.运输问题运输问题3.3.人事管理人事管理4.4.库存管理库存管理5.5.市场营销市场营销6.6.财务和会计财务和会计另外，还应用于设备维修、更新和可靠性分析，项目的选择另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。与评价，工程优化设计等。Page10运筹学在工商管理中的应用运筹学在工商管理中的应用Interface上发表的部分获奖项目上发表的部分获奖项目组织组织应用应用效果效果联合航空公司联合航空公司在满足乘客需求的前提下，以最低成本进在满足乘客需求的前提下，以最低成本进行订票及机场工作班次安排行订票及机场工作班次安排每年节约成本每年节约成本600600万美元万美元CitgoCitgo石油公司石油公司优化炼油程序及产品供应、配送和营销优化炼油程序及产品供应、配送和营销每年节约成本每年节约成本70007000万万AT&TAT&T优化商业用户的电话销售中心选址优化商业用户的电话销售中心选址每年节约成本每年节约成本4.064.06亿美元，销亿美元，销售额大幅增加售额大幅增加标准品牌公司标准品牌公司控制成本库存（制定最优再定购点和定购控制成本库存（制定最优再定购点和定购量确保安全库存）量确保安全库存）每年节约成本每年节约成本380380万美元万美元法国国家铁路公司法国国家铁路公司制定最优铁路时刻表并调整铁路日运营量制定最优铁路时刻表并调整铁路日运营量每年节约成本每年节约成本15001500万美元，万美元，年收入大幅增加。年收入大幅增加。Taco BellTaco Bell优化员工安排，以最低成本服务客户优化员工安排，以最低成本服务客户每年节约成本每年节约成本13001300万美元万美元DeltaDelta航空公司航空公司优化配置上千个国内航线航班来实现利润优化配置上千个国内航线航班来实现利润最大化最大化每年节约成本每年节约成本1 1亿美元亿美元Page11“管理运筹学管理运筹学”软件介绍软件介绍“管理运筹学管理运筹学”2.02.0版包括：线性规划、运输问题、整数规划（版包括：线性规划、运输问题、整数规划（0-10-1整数整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共决策分析、预测问题和层次分析法，共1515个子模块。个子模块。Chapter1线性规划线性规划(LinearProgramming)LP的数学模型的数学模型图解法图解法单纯形法单纯形法单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法LP模型的应用模型的应用本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page13线性规划问题的数学模型线性规划问题的数学模型1.规划问题规划问题生产和经营管理中经常提出如何合理安排，使人力、生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。这就是规划问题。线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，用）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源最少的资源 （如资金、设备、原标材料、人工、时间等）（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标去完成确定的任务或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得最）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多好的经济效益（如产品量最多 、利润最大、利润最大.）Page14线性规划问题的数学模型线性规划问题的数学模型例例1.1如图所示，如何截取如图所示，如何截取x使铁皮所围成的容积最使铁皮所围成的容积最大？大？x xa aPage15线性规划问题的数学模型线性规划问题的数学模型例例1.2某企业计划生产甲、乙两种产品。这些产品分某企业计划生产甲、乙两种产品。这些产品分别要在别要在A、B、C、D、四种不同的设备上加工。按工四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？企业总的利润最大？设设备备产产品品ABCD利润（元）利润（元）甲甲21402乙乙22043有有效效台台时时1281612Page16线性规划问题的数学模型线性规划问题的数学模型解：设解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：分别为甲、乙两种产品的产量，则数学模型为：maxZ=2xmaxZ=2x1 1+3x+3x2 2 xx1 10,x0,x2 200s.t.s.t.2x2x1 1+2x+2x2 21212xx1 1+2x+2x2 2884x4x1 116164x4x2 21212Page17线性规划问题的数学模型线性规划问题的数学模型2.2.2.2.线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量决策变量决策变量DecisionvariablesDecisionvariables目标函数目标函数目标函数目标函数ObjectivefunctionObjectivefunction约束条件约束条件约束条件约束条件ConstraintsConstraints其特征是：其特征是：其特征是：其特征是：（1 1 1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的线性线性线性线性函数，函数，函数，函数，通常是求最大值或最小值；通常是求最大值或最小值；通常是求最大值或最小值；通常是求最大值或最小值；（2 2 2 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性线性线性不不不不等式或等式。等式或等式。等式或等式。等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？Page18线性规划问题的数学模型线性规划问题的数学模型目标函数：目标函数：目标函数：目标函数：约束条件：约束条件：约束条件：约束条件：3.3.线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：简写为：Page19线性规划问题的数学模型线性规划问题的数学模型向量形式：向量形式：向量形式：向量形式：其中：其中：Page20线性规划问题的数学模型线性规划问题的数学模型矩阵形式：矩阵形式：矩阵形式：矩阵形式：其中：其中：Page21线性规划问题的数学模型线性规划问题的数学模型3.线性规划问题的标准形式线性规划问题的标准形式特点：特点：(1)目标函数求最大值（有时求最小值）目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项约束条件都为等式方程，且右端常数项bi都大于或等于零都大于或等于零(3)决策变量决策变量xj为非负。为非负。Page22线性规划问题的数学模型线性规划问题的数学模型（2 2 2 2）如何化标准形式）如何化标准形式）如何化标准形式）如何化标准形式 目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ，则可将目标函数乘以，则可将目标函数乘以(-1)(-1)，可化为求极大值问题。，可化为求极大值问题。也就是：令也就是：令 ，可得到上式。，可得到上式。即即 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中：变量的变换变量的变换Page23线性规划问题的数学模型线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。称为松弛变量称为松弛变量称为剩余变量称为剩余变量 变量变量 的变换的变换 可令可令 ，显然，显然Page24线性规划问题的数学模型线性规划问题的数学模型例例1.3将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式用用 替换替换 ，且，且 解解:（）因为（