操作研究模型 - 线性规划.ppt

运筹学模型;运筹学作为科学名字是出现在20世纪30年代末。当时英、美对付德国的空袭，雷达作为防空系统的一部分，从技术上是可行的，但实际运用时却并不好用。为此一些科学家研究如何合理运用雷达开始进行一类新问题的研究。因为它与研究技术问题不同，就称之为“运用研究”（Operational Research）（我国在1957年正式定名为运筹学）。为了进行运筹学研究，在英、美的军队中成立了一些专门小组，开展了护航舰队保护商船队的编队问题和当船队遭受德国潜艇攻击时，如何使船队损失最少的问题的研究。研究了反潜深水炸弹的合理爆炸深度后，使德国潜艇被摧毁数增加到400%，研究还使船只在受敌机攻击时，中弹数由47%降到29%。二战结束后，在英、美军队中相继成立了更为正式的运筹研究组织。并以兰德公司（RAND）为首的一些部门开始着重研究战略性问题、未来的武器系统的设计和未来战争的战略。到60年代，参与了战略力量的构成和数量问题研究，除军事方面的应用研究以外，相继在工业、农业、经济和社会问题等各领域都有应用。与此同时，运筹学有了飞快的发展，并形成了运筹学的许多分支。如数学规划（线性规划、非线性规划、整数规划、目标规划、动态规划、随机规划等）、图论与网络、排队论（随机服务系统理论）、存贮论、对策论、决策论等。 ; 在中国，最早的运筹学思想有战国时期的田忌赛马，它是对策论的一个典型例子，北宋时期的丁渭造皇宫，它是统筹规划的一个例子。 50年代中期，钱学森、许国志等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。 1978年11月，在成都召开了全国数学年会，对运筹学的理论与应用研究进行了一次检阅，1980年4月在山东济南正式成立了“中国数学会运筹学会”，1984年在上海召开了“中国数学会运筹学会第二届代表大会暨学术交流会”，并将学会改名为“中国运筹学会”。 ;究竟什么是运筹学?; 0-3 运筹学的基本内容;5、图与网络(Graph Theory and Network)：中国邮递员问题、哥尼斯堡城问题、最短路、最大流问题。 6、存储模型（Inventory Theory)：主要解决生产中的库存问题，订货周期和订货量等问题。 7、排队论(Queue Theory)：主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量。 8、对策论(Game Theory)：主要研究具有斗争性质的优化问题。 9、决策分析(Decision Analysis) ：主要研究定量化决策。 ;1 线性规划问题及其数学模型 1-1 问题的提出;解：设x1, x2分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。 由于资源的限制，所以有： 机器设备的限制条件: x1+2x2≤8 原材料A的限制条件： 4x1≤16 （称为资源约束条件） 原材料B的限制条件： 4x2≤12 同时，产品Ⅰ、Ⅱ的产量不能是负数，所以有 x1≥0，x2≥0 （称为变量的非负约束） 显然，在满足上述约束条件下的变量取值，均能构成可行方案，例如x1 =1，x2=0; x1 =3.5，x2=2等等，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1，x2以得到最大的利润，即使函数 Z=2x1+3x2的值达到最大。;例2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，两工厂之间有一条流量为每天200万m3的支流（见图）。 第一化工厂每天排放污水2万m3，第二化工厂每天排放污水 1.4万m3。污水从工厂1流到工厂2前会有20%自然净化。根据环保要求，河水中污水的含量应不大于0.2%。而工厂1和工厂2处理污水的成本分别为1000元/万m3和800元/万m3。问两工厂各应处理多少污水才能使处理污水的总费用最低？;1-2 线性规划的基本概念;1、线性规划的数学模型;1-3 线性规划的实例;例4 合理利用线材问题 现要做一百套钢管，每套要长为2.9m、2.1m和1.5m的钢管各一根。已知原料长7.4m，问应如何下料，使用的原料最省。;例5 连续投资问题 某公司经调研分析知，在今后三年内有四种投资机会。方案A是在三年内每年年初投资，年底可获利15%，并可将本金收回；方案B是在第一年的年初投资，第二年的年底可获利45%，并将本金收回，但该项投资不得超过2万元；方案C是在第二年的年初投资，第三年的年底可获利65%，并将本金收回，但该项投资不得超过1.5