1运筹学第五版第一章.pptVIP

Discrete Math. , DeRen Chen 运筹学 Operation Research 中国古代运筹学思想 在中文里翻译为“运筹”。 来源——公元前三世纪楚汉相争中，汉高祖刘邦的谋士张良常出谋献策，为刘邦打败项羽，推翻秦朝，统一中国立下大功。刘邦称誉他“运筹帷幄之中，决胜千里之外”。 运筹学的思想在古代就已经产生了。我国古代有很多有关运筹学的思想方法的典故。例如，齐王赛马、丁渭修皇宫等故事充分说明了我国不仅很早就有了朴素的运筹思想，而且已在生产实践中实际运用了运筹方法。 现代运筹学 50年代中期，钱学森、许国志等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。 1978年11月，在成都召开了全国数学年会，对运筹学的理论与应用研究进行了一次检阅，1980年4月在山东济南正式成立了“中国数学会运筹学会”，1984年在上海召开了“中国数学会运筹学会第二届代表大会暨学术交流会”，并将学会改名为“中国运筹学会”。 第一节 线性规划问题及其数学模型 问题的提出 例: 生产计划问题 决策变量（Decision variables） 目标函数（Objective function） 约束条件（Constraint conditions） 可行域（Feasible region) 最优解（Optimal solution) 该计划的数学模型 目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 ? 8 4x1 ? 16 4x2 ? 12 x1、 x2 ? 0 线性规划模型的一般形式 简写为 用向量表示 用矩阵表示 线性规划问题的标准形式 标准形式为: 化标准型的步骤： 1.目标函数是 2.约束条件为不等式,加入非负松驰变量化成等号； 3.取值无约束的变量； 4.小于0的变量。 预备知识 线性规划问题基本定理 图解法 线性规划问题求解的几种可能结果 由图解法得到的启示 第二节 线性规划的图解法 为了便于建立 维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。 求解下述线性规划问题： 1.画出线性规划问题的可行域： 2.目标函数的几何意义： 3.最优解的确定： 图解法的步骤： 建立坐标系，将约束条件在图上表示； 确立满足约束条件的解的范围； 绘制出目标函数的图形； 确定最优解。 无穷多最优解的情况： 目标函数与某个约束条件恰好平行 无界解（或无最优解）的情况： 可行域上方无界 无可行解的情况： 约束条件不存在公共范围 图解法的启示： 求解线性规划问题时，解的情况有：唯一最优解，无穷多最优解，无界解，无可行解； 若线性规划问题可行域存在，可行域是一个凸集； 若线性规划问题最优解存在，最优解或最优解之一一定能够在可行域的某个顶点取得； 解题思路是，先找凸集的任一顶点，计算其目标函数值。比较其相邻顶点函数值，若更优，则逐点转移，直到找到最优解。 Discrete Math. , DeRen Chen 第三节 单纯形法原理 预备知识 线性规划问题基本定理 Discrete Math. , DeRen Chen 凸集：如果集合 C 中任意两个点 ，其连线上的所有点也都是集合C 中的点。 上图中（1）（2）是凸集，（3）（4）不是凸集 顶点：如果对于凸集 C 中的点 X ，不存在C 中的任意其它两个不同的点 ，使得 X 在它们的连线上，这时称 X 为凸集的顶点。 Discrete Math. , DeRen Chen Discrete Math. , DeRen Chen Discrete Math. , DeRen Chen 运筹学公认起源于二次世界大战期间英美等国的军事运筹小组，这些小组的主要任务是进行Operational research( 运作研究)或Operational analysis(运作分析)。 二战后,运筹学的研究主要转向经济方面，重点集中在如何用一定的投入生产更多的产出，或一定的产出如何用更少的投入来生产，从而使运筹学在管理科学中获得了长足的发展。经过几十年的发