运筹学模型-线性规划.pptVIP

运筹学模型 九江职业技术学院 林娜 运筹学作为科学名字是出现在20世纪30年代末。当时英、美对付德国的空袭，雷达作为防空系统的一部分，从技术上是可行的，但实际运用时却并不好用。为此一些科学家研究如何合理运用雷达开始进行一类新问题的研究。因为它与研究技术问题不同，就称之为“运用研究”（Operational Research）（我国在1957年正式定名为运筹学）。为了进行运筹学研究，在英、美的军队中成立了一些专门小组，开展了护航舰队保护商船队的编队问题和当船队遭受德国潜艇攻击时，如何使船队损失最少的问题的研究。研究了反潜深水炸弹的合理爆炸深度后，使德国潜艇被摧毁数增加到400%，研究还使船只在受敌机攻击时，中弹数由47%降到29%。二战结束后，在英、美军队中相继成立了更为正式的运筹研究组织。并以兰德公司（RAND）为首的一些部门开始着重研究战略性问题、未来的武器系统的设计和未来战争的战略。到60年代，参与了战略力量的构成和数量问题研究，除军事方面的应用研究以外，相继在工业、农业、经济和社会问题等各领域都有应用。与此同时，运筹学有了飞快的发展，并形成了运筹学的许多分支。如数学规划（线性规划、非线性规划、整数规划、目标规划、动态规划、随机规划等）、图论与网络、排队论（随机服务系统理论）、存贮论、对策论、决策论等。 0 绪 论 0-1 运筹学简史 在中国，最早的运筹学思想有战国时期的田忌赛马，它是对策论的一个典型例子，北宋时期的丁渭造皇宫，它是统筹规划的一个例子。 50年代中期，钱学森、许国志等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。 1978年11月，在成都召开了全国数学年会，对运筹学的理论与应用研究进行了一次检阅，1980年4月在山东济南正式成立了“中国数学会运筹学会”，1984年在上海召开了“中国数学会运筹学会第二届代表大会暨学术交流会”，并将学会改名为“中国运筹学会”。 究竟什么是运筹学? ??? 运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。运筹学可以根据问题的要求，通过数学上的分析、运算，得出各种各样的结果，最后提出综合性的合理安排，以达到最好的效果。 0-2 运筹学的概念 0-3 运筹学的基本内容 1、线性规划（Linear Program）是一个成熟的分支，它有效的算法——单纯形法，主要解决生产计划问题，合理下料问题，最优投资问题。 2、整数规划(Integrate Program)：在线性规划的基础上，变量加上整数约束。 3、非线性规划(Nonlinear Program)：目标函数和约束条件是非线性函数，如证券投资组合优化:如何合理投资使风险最小。 4、动态规划(Dynamic Program):多阶段决策问题。是美国贝尔曼于1951年提出的。 5、图与网络(Graph Theory and Network)：中国邮递员问题、哥尼斯堡城问题、最短路、最大流问题。 6、存储模型（Inventory Theory)：主要解决生产中的库存问题，订货周期和订货量等问题。 7、排队论(Queue Theory)：主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量。 8、对策论(Game Theory)：主要研究具有斗争性质的优化问题。 9、决策分析(Decision Analysis) ：主要研究定量化决策。 今天我们给大家介绍的是应用最为广泛的线性规划 1 线性规划问题及其数学模型 1-1 问题的提出 例1某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获得的利润如下表所示。问应如何安排生产计划使该工厂获利最多？ Ⅰ Ⅱ 资源限量 设备 1 2 8(台时) 原材料A 4 0 16(kg) 原材料B 0 4 12(kg) 单位产品利润（元） 2 3 　 解：设x1, x2分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。 由于资源的限制，所以有： 机器设备的限制条件: x1+2x2≤8 原材料A的限制条件： 4x1≤16 （称为资源约束条件） 原材料B的限制条件： 4x2≤12 同时，产品Ⅰ、Ⅱ的产量不能是负数，所以有 x1≥0，x2≥0 （称为变量的非负约束）