简单的线性规划问题(一).

运筹帷幄之中决胜千里之外运筹学(OperationsResearch)运筹学简述•运筹学（OperationsResearch,简写OR）•系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(ManagementScience)。运筹学所研究的问题，可简单地归结为一句话：•“依照给定条件和目标，从众多方案中选择最佳方案”•故有人称之为最优化技术。运筹学的历史与发展“运筹学思想的出现可以追溯到很早—“田忌赛马”。齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下方案安排：齐王上中下田忌下上中丁谓的皇宫修复工程北宋年间，丁谓负责修复火毁的开封皇宫。他的施工方案是：先将皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、运输及清废用“一沟三用”巧妙地解决了，体现了系统规划的思想。运筹学的历史与发展国际上运筹学的思想可追溯到1914年，当时的兰彻斯特提出了军事运筹学的作战模型。1917年，丹麦工程师埃尔朗在研究自动电话系统中通话线路与用户呼叫的数量关系问题时，提出了埃尔朗公式，研究了随机服务系统中的系统排队与系统拥挤问题。存储论的最优批量公式是在20世纪20年代初提出的。运筹学的历史与发展运筹学简述“运作研究(OperationalResearch)小组”:解决复杂的战略和战术问题。例如：1.如何合理运用雷达有效地对付德军德空袭2.对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；3.在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。在生产管理方面的应用，最早是1939年前苏联的康特洛为奇提出了生产组织与计划中的线性规划问题，并给出解乘数法的求解方法，出版了第一部关于线性规划的著作《生产组织与计划中的数学方法》。但当时并没有引起重视，直到1960年康特洛为奇再次出版了《最佳资源利用的经济计算》，才受到国内外的一致重视，为此康特洛为奇获得了诺贝尔经济学奖。线性规划提出后很快受到经济学家的重视，如：二次世界大战中从事运输模型研究的美国经济学家库普曼斯（T.C.Koopmans），他很快看到了线性规划在经济中应用的意义，并呼吁年轻的经济学家要关注线性规划。其中阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威茨等都获得了诺贝尔奖。运筹学的历史与发展20世纪50年代中期，钱学森、许国志等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。1978年11月，在成都召开了全国数学年会，对运筹学的理论与应用研究进行了一次检阅，1980年4月在山东济南正式成立了“中国数学会运筹学会”，1984年在上海召开了“中国数学会运筹学会第二届代表大会暨学术交流会”，并将学会改名为“中国运筹学会”。运筹学的历史与发展运筹学的主要内容数学规划（线性规划、整数规划、目标规划、动态规划等）图论存储论排队论对策论排序与统筹方法决策分析运筹学的主要内容•1.线性规划（LinearProgram）是一个成熟的分支，它有效的算法——单纯形法，主要解决生产计划问题，合理下料问题，最优投资问题。•2.整数规划(IntegrateProgram)：在线性规划的基础上，变量加上整数约束。•3.非线性规划(NonlinearProgram)：目标函数和约束条件是非线性函数，如证券投资组合优化:如何合理投资使风险最小。•4.动态规划(DynamicProgram)：多阶段决策问题。是美国贝尔曼于1951年提出的。运筹学的主要内容•5、图与网络(GraphTheoryandNetwork)：中国邮递员问题、哥尼斯堡城问题、最短路、最大流问题。•6、存储论（InventoryTheory)：主要解决生产中的库存问题，订货周期和订货量等问题。•7、排队论(QueueTheory)：主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量。•8、对策论(GameTheory)：主要研究具有斗争性质的优化问题。•9、决策分析(DecisionAnalysis)：主要研究定量化决策。运筹学在经济管理中的应用•运筹学在经济管理中的应用涉及的方面：1.生产计划2.运输问题3.人事管理4.库存管理5.市场营销6.财务和会计7.物流配送•另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。在现实生产、生活中经常会遇到资源利用、人力调配、生产安排等问题.这类问题在数学中将其归为线性规划问题.线性规划是利用数学为工具，来研究一定的人、财、物、时、空等资源在一定条件下，如何精打细算巧安排，用最少的资源，取得最大的经济效益.它是数学规划中理论较完整、方法较成熟、应用较广泛的一个分支,并能解决科学研究、工程设计、经常管理等许多方面的实际问题.某工厂用A,B两种配件生产甲,乙两种产品,每生产一件甲种产品使用4个A配件耗时1h,每生产一件乙种产品使用4个B配件耗时2h,该厂每天最多可从配件厂获得16个A配件和12个B配件,按每天工作8小时计算,该厂所有可能的日生产安排是什么?若生产1件甲种产品获利2万元,生产1件乙种产品获利3万元,采用哪种生产安排利润最大?问题提出32利润(万元)821所需时间1240B种配件1604A种配件资源限额乙产品(1件)甲产品(1件)资源把引例的有关数据列表表示如下:设甲,乙两种产品分别生产x,y件,数学建模2841641200xyxyxy0xy4348将上面不等式组表示成平面上的区域,区域内所有坐标为整数的点P(x,y)就代表所有可能的日生产安排,当点P(x,y)在上述平面区域中时所安排的生产任务x,y都是有意义的.设甲,乙两种产品分别生产x,y件,由己知条件可得:问题：求利润2x+3y的最大值.28xy4x3y若设利润为z,则z=2x+3y,这样上述问题转化为:当x,y在满足上述约束条件时,z的最大值为多少?2223-,-,333,3zzxyyxzy把变形为这是斜率为在轴上的截距为的直线当点P在可允许的取值范围变化时,,.3zz求截距的最值即可得的最值2841641200xyxyxy0xy4348233zyxM（4，2）142yx问题：求利润z=2x+3y的最大值.143224maxZ问题解决2841641200xyxyxy象这样关于x,y一次不等式组的约束条件称为线性约束条件z=2x+3y称为目标函数,(因这里目标函数为关于x,y的一次式,又称为线性目标函数)在线性约束下求线性目标函数的最值问题,统称为线性规划满足线性约束条件的解(x,y)叫做可行解所有可行解组成的集合叫做可行域使目标函数取得最值的可行解叫做这个问题的最优解概念形成2841641200xyxyxy133zyxN（2，3）142yx即求利润z=x+3y的最大值.max23311zy0x43481.上例中若生产一件甲产品获利1万元,生产一件乙产品获利3万元,采用哪种生产安排利润最大?变式训练2.求z=2x+y的最大、小值,使x、y满足约束条件：11yyxxy3.求z=3x+5y的最大、小值,使x、y满足约束条件：5315153xyyxxyxOyABCy=xx+y=1y=-12x+y=011yyxxyB(-1,-1)C(2,-1)zmin=-3zmax=3目标函数：z=2x+y例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多少kg?规范解答0105010500757750070140067146014007006147600002821:kg,kg,..........,:.xAyBzxyxyxyxyxyxyxxyyzxy解设每天食用食物食物总成本为依题意有即目标函数为,.作出以上不等式组所表示的平面区域如图中所示的阴影部分17374757671271727374757671Oxy7x+14y=614x+7y=67x+7y=57751476147714282128211677min,(,).xyxyMzxyz解方程组得代入得:AB答每天食用食物约143g,食物约571g,能够满足日常饮食要求,又使花费最低,最低成本为16元.282102821:,,.lxylMzxy作直线当移动直线过图中的点时取得最小值17374757671271727374757671Oxy7x+14y=614x+7y=67x+7y=5M28x+21y=0例2.要将两种大小不同的钢板截成A、B、C三种规格,每张钢板可同时截得三种规格的小钢板的块数如下表示：钢型A规格B规格C规格第一种钢板211第二种钢板123今需要A、B、C三种规格的成品分别为15、18、27块，则截这两种钢板多少张可得所需A、B、C三种规格成品，且使所用钢板张数最少？规格[解]：设需截第一种钢板x张,第二种钢板y张,共需这两种钢板共z张，根据题意可得：21521832700,,,,.xyxyxyzxyxy目标函数是作出以上不等式组所表示的平面区域，如图中所示的阴影部分.0:,lxylM作直线当平移直线过图中的点时,z取最小值.x+2y=18277.515180xy2x+y=15x+3y=27M327183921555183955,(,),(,),(,).xyMxyxyxyM解方程组得但此问题中的最优解中的都是整数,所以不是最优解x+2y=18277.515180xy2x+y=15x+3y=27C(4,8)B(3,9)M12394812min,(,)(,),zyxBCz经过可行域内整点且使最小的直线是它经过和它们是最优解.12:,.答要截得所需三种规格的钢板且使所截两种钢板张数最小的方法有两种,第一种截法是第一种钢板3张,第二种钢板张;第二种截法是截第一种钢板4张,第二种钢板8张.两种截法都最少要两种钢板张例3.一个化肥厂生产甲、乙两种混合肥料,生产1车皮甲种肥料的主要原料是磷酸盐4t、硝酸盐18t；生产1车皮乙种肥料需要的主要原料是磷酸盐1t、硝酸盐15t.现库存磷酸盐10t、硝酸盐66t，在此基础上生产这两种混合肥料.列出满足生产条件的数学关系式,并画出相应的平面区域.若生产1车皮甲种肥料，产生的利润为10000元,生产1车皮的乙种肥料，产生的利润为5000元,计算生产甲、乙两种肥料各多少车皮，能够产生最大的利润？解：设生产甲种肥料x车皮、乙种肥料y车皮，能够产生利润z万元.依题意有4101815660500,.xyxyzxyxy＋＋目标函数为作出以上不等式组所表示的平面区域，如图中所示的阴影部分.xyoM050:.,lxylMz作直线当平移直线过图中的点时,取最大值.容易求得M点的坐标为（2，2），则Zmax＝3答：生产甲种、乙种肥料各2车皮，能够产生最大利润，最大利润为3万元。解线性规划问题的步骤：(3)移:在线性目