《简单的线性规划问题(一).PPT课件》由会员分享，可在线阅读，更多相关《简单的线性规划问题(一).PPT课件（37页珍藏版）》请在金锄头文库上搜索。
1、简单线性规划问题,运 筹 学( Operations Research ),什么是运筹学? Operational Research 运用研究、 运作研究,什么是运筹学 是一门应用学科，它 广泛应用现有的科学 技术知识和数学方法 解决实际中提出的专 门问题，为决策者选 择最优决策提供量化 依据。,运筹学简述,运筹学（Operations Research,简写OR ） 系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(Management Science)。运筹学所研究的问题，可简单地归结为一句话： “依照给定条件和目标，从众多方案中选择最佳方案” 故有人称之为最优化技术。,运
2、筹学的历史与发展,“运筹学思想的出现可以追溯到很早“田忌赛马” 。,齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下方案安排： 齐王 上中 下 田忌 下上 中,丁谓的皇宫修复工程 北宋年间，丁谓负责修复火毁的开封皇宫。他的施工方案是：先将皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、运输及清废用“一沟三用”巧妙地解决了，体现了系统规划的思想。,运筹学的历史与发展,国际上运筹
3、学的思想可追溯到1914年，当时的兰彻斯特提出了军事运筹学的作战模型。1917年，丹麦工程师埃尔朗在研究自动电话系统中通话线路与用户呼叫的数量关系问题时，提出了埃尔朗公式，研究了随机服务系统中的系统排队与系统拥挤问题。存储论的最优批量公式是在20世纪20年代初提出的。,运筹学的历史与发展,运筹学简述,“运作研究(Operational Research)小组”:解决复杂的战略和战术问题。例如： 如何合理运用雷达有效地对付德军德空袭 对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少； 在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。,在生产管理方面的应用，最早是
4、1939年前苏联的康特洛为奇提出了生产组织与计划中的线性规划问题，并给出解乘数法的求解方法，出版了第一部关于线性规划的著作生产组织与计划中的数学方法。 但当时并没有引起重视，直到1960年康特洛为奇再次出版了最佳资源利用的经济计算，才受到国内外的一致重视，为此康特洛为奇获得了诺贝尔经济学奖。 线性规划提出后很快受到经济学家的重视，如：二次世界大战中从事运输模型研究的美国经济学家库普曼斯（T.C.Koopmans），他很快看到了线性规划在经济中应用的意义，并呼吁年轻的经济学家要关注线性规划。其中阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威茨等都获得了诺贝尔奖。,运筹学的历史与发展,20世纪50年代中期，
5、钱学森、许国志等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。 1978年11月，在成都召开了全国数学年会，对运筹学的理论与应用研究进行了一次检阅，1980年4月在山东济南正式成立了“中国数学会运筹学会”，1984年在上海召开了“中国数学会运筹学会第二届代表大会暨学术交流会”，并将学会改名为“中国运筹学会”。,运筹学的历史与发展,运筹学的主要内容,数学规划（线性规划、整数规划、
6、目标规划、动态规划等） 图论 存储论 排队论 对策论 排序与统筹方法 决策分析,运筹学的主要内容,1. 线性规划（Linear Program）是一个成熟的分支，它有效的算法单纯形法，主要解决生产计划问题，合理下料问题，最优投资问题。 2. 整数规划(Integrate Program)：在线性规划的基础上，变量加上整数约束。 3. 非线性规划(Nonlinear Program)：目标函数和约束条件是非线性函数，如证券投资组合优化:如何合理投资使风险最小。 4. 动态规划(Dynamic Program)：多阶段决策问题。是美国贝尔曼于1951年提出的。,运筹学的主要内容,5、图与网络(Gr
7、aph Theory and Network)：中国邮递员问题、哥尼斯堡城问题、最短路、最大流问题。 6、存储论（Inventory Theory)：主要解决生产中的库存问题，订货周期和订货量等问题。 7、排队论(Queue Theory)：主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量。 8、对策论(Game Theory)：主要研究具有斗争性质的优化问题。 9、决策分析(Decision Analysis) ：主要研究定量化决策。,运筹学在经济管理中的应用,运筹学在经济管理中的应用涉及的方面： 生产计划 运输问题 人事管理 库存管理 市场营销 财务和会计 物流配送 另外
8、，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。,在现实生产、生活中经常会遇到资源利用、 人力调配、生产安排等问题. 这类问题在数学中 将其归为线性规划问题. 线性规划是利用数学为工具，来研究一定的 人、财、物、时、空等资源在一定条件下，如何 精打细算巧安排，用最少的资源，取得最大的经 济效益. 它是数学规划中理论较完整、方法较成 熟、应用较广泛的一个分支,并能解决科学研究、 工程设计、经常管理等许多方面的实际问题.,某工厂用A,B两种配件生产甲,乙两种产品, 每生产一件甲种产品使用4个A配件耗时1h,每 生产一件乙种产品使用4个B配件耗时2h,该厂 每天最多可从配件厂
9、获得16个A配件和12个B 配件,按每天工作8小时计算,该厂所有可能的 日生产安排是什么?,若生产1件甲种产品获利2万元,生产1 件乙 种产品获利3万元, 采用哪种生产安排利润最 大?,问题提出,把引例的有关数据列表表示如下:,设甲,乙两种产品分别生产x, y件,数学建模,将上面不等式组表示成平面 上的区域, 区域内所有坐标 为整数的点P (x,y) 就代表所 有可能的日生产安排, 当点P (x, y)在上述平面区域中时所安排的生产任务x, y都是有意义的.,设甲,乙两种产品分别生产x, y件,由己知条件可得:,问题：求利润2x+3y的最大值.,若设利润为z,则z=2x+3y,这样上述问题转化
10、为:,当x,y在满足上述约束条件时,z的最大值为多少?,当点P在可允许的取值范围变化时,M（4，2）,问题：求利润z=2x+3y的最大值.,问题解决,象这样关于x,y一次不等式组的 约束条件称为线性约束条件,z=2x+3y称为目标函数, (因这里目标函 数为关于x, y的一次式, 又称为线性目 标函数),在线性约束下求线性目标函数的最值问题,统称 为线性规划,满足线性约束条件的解(x,y)叫做可行解,所有可行解组成的集合叫做可行域,使目标函数取得最值的可行解叫做这个问题的 最优解,概念形成,N（2，3）,即求利润z=x+3y的最大值.,1.上例中若生产一件甲产品获利1万元,生产一件 乙产品获利
11、3万元,采用哪种生产安排利润最大?,变式训练,2. 求z=2x+y的最大、小值,使x、y满足约束条件：,3.求z=3x+5y的最大、小值,使x、y满足约束条件：,zmin=-3,zmax=3,例1.营养学家指出，成人良好的日常饮食应该至少提供 0.075kg的碳水化合物，0.06kg的蛋白质, 0.06kg的脂 肪.1kg食物A含有0.105kg碳水化合物, 0.07kg蛋白质, 0.14kg脂肪，花费28元；而1kg食物B含有0.105kg碳 水化合物, 0.14kg蛋白质, 0.07kg脂肪, 花费21元.为了 满足营养专家指出的日常饮食要求, 同时使花费最低, 需要同时食用食物A和食物B
12、多少kg?,规范解答,例2 . 要将两种大小不同的钢板截成A、B、C三种规格, 每张钢板可同时截得三种规格的小钢板的块数如下表 示：,今需要A、B、C三种规格的成品分别为15、18、 27块，则截这两种钢板多少张可得所需A、B、C三种 规格成品，且使所用钢板张数最少？,规格,解：设需截第一种钢板x张,第二种钢板y张,共需这两种钢 板共z张，根据题意可得：,作出以上不等式组所 表示的平面区域，如 图中所示的阴影部分.,例3.一个化肥厂生产甲、乙两种混合肥料,生产1车皮甲 种肥料的主要原料是磷酸盐4t、硝酸盐18t；生产1车皮 乙种肥料需要的主要原料是磷酸盐1t、硝酸盐15t.现库 存磷酸盐10t
13、、硝酸盐66t，在此基础上生产这两种混合 肥料.列出满足生产条件的数学关系式,并画出相应的平 面区域.若生产1车皮甲种肥料，产生的利润为10000元, 生产1车皮的乙种肥料，产生的利润为5000元,计算生产 甲、乙两种肥料各多少车皮，能够产生最大的利润？,解：设生产甲种肥料x车皮、乙种肥料y车皮，能够产生利润z万 元.依题意有,作出以上不等式组所表示的平面区域，如图 中所示的阴影部分.,M,容易求得M点的坐标为 （2，2），则Zmax3,答：生产甲种、乙种肥料各2车 皮，能够产生最大利润，最 大利润为3万元。,解线性规划问题的步骤：,(3)移:在线性目标函数所表示的一组平行线中，利用 平移的方
14、法找出与可行域有公共点且纵截距最 大或最小的直线;,(4)求:通过解方程组求出最优解；,(5)答:作出答案.,(2)画:画出线性约束条件所表示的可行域；,(1)列:设变量，列出约束条件和目标函数；,先定可行域和平移方向，再找最优解.,最优解一般在可行域的顶点处取得,在哪个顶点取得不仅与B的符号有关,而且 还与直线 z=Ax+By的斜率有关,方法总结,某厂拟生产甲、乙两种适销产品，每件销售收入 分别为3000元、2000元, 甲、乙产品都需要在A、B两 种设备上加工,在每台A、B上加工1件甲所需工时分别 为1h、2h，加工1件乙所需工时分别为2h, 1h.A、B两 种设备每月有效使用台时数分别为
15、400h和500h。如何 安排生产可使收入最大？,解设每月生产甲产品x件，生产乙产品y件，每月收入 为Z千元，目标函数为Z3x2y，满足的条件是,作出可行域如图阴影部分所示,强化练习,Z 3x2y 变形为它表示斜率为 的直线系，Z与这条直线的截距有关.,当直线经过点M时，截距最大，Z最大。,M,解方程组,可得M（200，100）,Z 的最大值Zmax 3x2y800（千元）,故生产甲产品200件， 乙产品100件，收入最 大，为80万元。,课堂小结,本节主要学习了线性约束下如何求目 标函数的最值问题 正确列出变量的不等关系式,准确作出 可行域是解决目标函数最值的关健 线性目标函数的最值一般都是在可行域 的顶点或边界取得. 把目标函数转化为某一直线, 其斜率与 可行域边界所在直线斜率的大小关系一定要 弄清楚.,
