1线性规划与单纯形法

12020/2/25运筹学OperationalResearch主讲：张晓果22020/2/25绪论一、运筹学发展简介二、运筹学定义三、运筹学的性质与特点四、运筹学的应用五、运筹学的工作步骤六、运筹学的分支32020/2/25案例ⅠⅡ设备原料A原料B1402048台时16kg12kg例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时和原料A、B的消耗量如下表。该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排生产能使该厂获得最大的总利润？进一步考虑，如果产品的销售情况不容乐观，那么工厂的决策者会考虑不安排生产，而将设备和原材料出租，收取租费。那么出租报价应该怎么确定呢?42020/2/25一、运筹学（OR）发展简介运筹学是一门基础性的应用学科，主要是将社会经济建设实践中经济、军事、成产、管理、组织等事件中出现的一些带有普遍性的运筹问题加以提炼，然后利用科学方法进行分析、求解等。前者提供模型，后者提供理论和方法。运筹学主要研究系统最优化问题，通过对建立的模型求解，为决策者进行决策提供科学依据。52020/2/25一、运筹学（OR）发展简介•英国称为OperationalResearch•美国称为OperationsResearch•朴素运筹学思想的出现可以追溯到很早—战国时期田忌齐王赛马是对策论的典型范例。运筹学的三个起源：军事，经济，管理62020/2/25军事•第一次世界大战期间—1914-1915兰彻斯特的若干军事论文研究战争的胜负同兵力多寡、火力强弱之间的关系；—爱迪生解决反潜战的“战术对策演示盘”反潜战的研究项目：汇编各项典型统计数据用于选择回避或击毁潜艇的最佳方法，使用“战术对策演示盘”解决免受潜艇攻击的问题。72020/2/25军事•二战期间的案例—鲍德西（Bawdsey）雷达站的研究—“布莱克特马戏团/杂技班”的出色工作项目的巨大实际价值：明确的目标；整体化的思想；数量化的分析；多学科的协调；最优化解结果—大西洋反潜战—Morse小组的重要工作协助英国打破了德国对英吉利海峡的海上封锁；—英国战斗机中队援法决策82020/2/25军事运筹学的特点•定量化系统化方法迅速发展•采集真实的实际数据•多学科密切协作•解决方法渗透着物理学思想92020/2/25管理对运筹学的影响•动作研究与泰勒工作制•切削效率与车速、进刀量等因素的数学关系—优选问题，来提高切削的效率•提出管理的基本原则，研究了机构设置、权限、工厂布局、计划等问题，来提高管理的效率•用于生产活动分析和计划安排的甘特黑道图发展成为统筹方法•前苏联康特洛维奇的工作102020/2/25经济理论对运筹学的影响•QUSNAY（魁内）1758年在凡尔赛发表《经济表》对经济中各部门的平衡关系做了最早的研究•Walras（沃尔拉思）对经济平衡问题的研究•1932年VonNeumann提出第一个广义经济平衡模型•马克思是最总将数学用于经济研究的经济学家之一，在沃尔拉思钻研他的数理经济问题的同时，马克思也在研究他所碰到的数理经济问题112020/2/25运筹学的发展•萌芽时期朴素的OR思想自古有之•早期研究《经济表》、一战、生产组织与计划•形成与发展时期二战；战后•20世纪50-60年代走向成熟成立学会，创办刊物，高校开课，军事运筹学122020/2/25运筹学的发展趋势•成熟的学科分支纵深发展•新的研究领域产生•与新的技术结合•与其他学科的结合加强•传统优化观念不断变化132020/2/25二、运筹学定义•运筹学为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法——Morse和Kimball•运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测、比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策——英国运筹学会142020/2/25二、运筹学释义•运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理——中国企业管理百科全书（1984年版）•运筹学是一门应用于管理有组织系统的科学，为掌管这类系统的人提供决策目标和数量分析的工具——大英百科全书152020/2/25二、运筹学释义•运筹学用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，是实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案——中国大百科全书（自动控制与系统工程卷，1991年版）•现代运筹学涵盖了一切领域的管理与优化问题，称为ManagementScience162020/2/25三、运筹学的性质与特点•引入数学方法解决实际问题—定性与定量方法结合•系统与整体性—从全局考察问题•应用性—源于实践、为了实践、服务于实践•交叉学科—涉及经济、管理、数学、工程和系统等多学科•开放性—不断产生新的问题和学科分支•多分支—问题的复杂和多样性172020/2/25四、运筹学的应用•生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等。•库存管理：多种物资库存量的系统组织与安排管理，确定某些设备的能力或容量，如停车场的大小、合理的水库容量等•运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及厂址的选择等。•人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系、人才开发的规划、激励机制的研究等。182020/2/25•财务和会计：包括预测、贷款、成本分析、定价、证券管理、现金管理等。•市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。•城市管理：各种紧急服务系统的设计与应用，城市垃圾的清扫、搬运和处理，城市供水和污水处理系统的规划，区域规划，市区交通网络的规划与管理等。192020/2/25五、运筹学的工作步骤•提出问题——用自然语言描述问题。•建立数学模型——用变量、函数、方程描述问题。•求解——主要用数学方法将模型求解。解可以是最优解、次优解、满意解，复杂模型求解要用计算机。•解的检验——检查模型和求解步骤有无错误，检查解是否反映现实问题。•解的实施——决策者根据自己的经验和偏好，对方案进行选择和修改，作出实施的决定。202020/2/25六、运筹学的分支数学规划包括：线性规划，非线性规划，整数规划，目标规划，动态规划，随机规划，模糊规划；图论与网络；排队论；存储论；对策论；决策论；维修更新理论；可靠性和质量管理等。212020/2/25数学规划解决的主要问题形式是在给定条件下，按某一衡量指标来寻找安排的最优方案。它可以表示成求函数在满足约束条件下的极大极小值问题。一个数学规划问题，如果约束条件和目标函数都是线性函数，就叫线性规划。要解决线性规划问题，理论上讲要求解线性方程组。因此解线性方程组的方法，以及关于行列式、矩阵的知识，就是线性规划中非常必要的工具。222020/2/25七、如何学好运筹学学习运筹学要把重点放在分析、理解有关的概念、思路上。在学习过程中，应该多向自己提问，例如一个方法的实质是什么，为什么这样做，怎么做等。学习或复习时要掌握三个重要环节：1.认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书籍。一般每一本运筹学教材都有自己的特点，但是基本原理、概念都是一致的。注意主从，参考资料会帮助你开阔思路，使学习深入。232020/2/252.要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助理解概念、理论的。作业练习的主要作用也是这样，它同时还有让你自己检查自己学习的作用。因此，做题要有信心，要独立完成，不要怕出错。因为，整个课程是一个整体，各节内容有内在联系，只要学到一定程度，知识融会贯通起来，你自己就能够对所做题目的正确性作出判断。242020/2/253、要学会做学习小结。每一节或一章学完后，必须学会用精炼的语言来概述该书所讲内容。这样，你才能够从较高的角度来看问题，更深刻地理解有关知识和内容。这就称作“把书读薄”，若能够结合相关参考文献并深入理解，把相关知识从更深入、广泛的角度进行论述，则称为“把书读厚”。252020/2/25第一章线性规划与单纯形法本章内容重点•线性规划模型与解的主要概念•线性规划的单纯形法，线性规划多解分析•线性规划应用——建模262020/2/25第1节线性规划问题及其数学模型一、实例ⅠⅡ设备原料A原料B1402048台时16kg12kg例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时和原料A、B的消耗量如下表。该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排生产计划能使该厂获利最多？解：这个问题可以用下面的数学模型来描述，设计划期内产品Ⅰ、Ⅱ的产量分别为x1，x2，可获利润用z表示，则有：MaxZ=2x1+3x2x1+2x2≤84x1≤164x2≤12x1,x2≥0272020/2/25例2靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，两工厂之间有一条流量为每天200万m3的支流（见图）。第一化工厂每天排放污水2万m3，第二化工厂每天排放污水1.4万m3。污水从工厂1流到工厂2前会有20%自然净化。根据环保要求，河水中污水的含量应不大于0.2%。而工厂1和工厂2处理污水的成本分别为1000元/万m3和800元/万m3。问两工厂各应处理多少污水才能使处理污水的总费用最低？解：设工厂1和工厂2每天分别处理污水x1和x2万m3，则有：Minz=1000x1+800x2(2-x1)/500≤0.002[0.8(2-x1)+1.4-x2]/700≤0.002x1≤2,x2≤1.4x1,x2≥0282020/2/25二、总结•都有一个要达到的目标，可以用决策变量的线性函数(目标函数,ObjectiveFunction）来表示。按问题的不同，要求目标函数实现最大化或最小化。线性规划（LinearProgramming）问题的共同特征：•每一个问题都用一组决策变量(DecisionVariable)（x1,x2,…,xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的。•存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。结论：线性规划是研究在一组线性不等式或等式约束条件下，使某一线性目标函数取最大或最小的极值问题。292020/2/25满足以上条件的数学模型称为线性规划模型。线性规划模型的一般形式如下：0,,),(),(),(max(min)21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz302020/2/25三、线性规划问题的标准型1.标准型标准型的四个特点：目标最大化、约束条件为线性等式、决策变量均非负、约束条件右端项非负。312020/2/252.所有LP问题均可化为标准型(1)若目标函数为MinZ，令Z'=-Z，则MinZ等价于MaxZ’(2)将不等式约束条件化为等式约束条件322020/2/25令xj=xj-xj，对模型中的进行变量代换。不符合标准型的几个方面：⑴目标函数为minz=c1x1+c2x2++cnxn令z=-z,变为maxz=-c1x1-c2x2--cnxn⑵约束条件为a11x1+a12x2++a1nxn≤b1加入非负变量xn+1，称为松弛变量，有a11x1+a12x2++a1nxn+xn+1=b1⑶约束条件为a11x1+a12x2++a1nxn≥b1减去非负变量xn+1，称为剩余变量，有a11x1+a12x2++a1nxn-xn+1=b1⑷变量xj无约束。332020/2/25例3可化为max1235515002500000zxxxxx123124251234