运筹学OperationalResearch教师简介运筹学简介古籍中的运筹问题古籍中的运筹问题“运筹”的出典我国当代数学家在《运筹学》中的贡献运筹学（OperationalResearch)运筹学的应用运筹学的发展：三个来源军事：运筹学的主要发源地运筹学的正式产生：第二次世界大战鲍德西（Bawdsey）雷达站的研究1939年，以Blackett为首的一个研究小组（代号“Blackett马戏团”），研究如何改进英国的空防系统，提高英国本土防空能力。Blackett备忘录1941年12月，Blackett应盟国政府的要求，写了五份题为“ScientistsattheOperationalLevel”的简短备忘录，建议在各大指挥部建立运筹学小组，此建议被迅速采纳。据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。大西洋反潜战：研究如何打破德国对英吉利海峡的海上封锁英国战斗机中队援法的决策管理经济（数理经济学）运筹学的性质和特点管理运筹学的工作程序运筹学的分支课程教材：主要授课内容：课程基本要求第一章线性规划（LinearProgramming，简称LP）Max（Min）Z=c1x1+c2x2+…+cnxn线性规划问题隐含的假定：比例性假定可加性假定连续性假定确定性假定线性规划问题隐含的假定：比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。连续性假定：线性规划问题中的决策变量应取连续值。确定性假定：线性规划问题中的所有参数都是确定的参数。线性规划问题不包含随机因素。例2某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：要求在充分利用各种资源条件下使建造住宅的总面积为最大(即求安排各住宅多少m2)，求建造方案。解:设今年计划修建砖混、壁板、大模住宅各为x1,x2,x3m2,z为总面积,则本问题的数学模型为:课堂练习课堂练习思考题二、线性规划的图解法（2）作目标函数的等值线最优解：x1=0，x2=1最优目标值z=32.LP解的几种情况补充知识：凸集从图解法中我们了解到以下事实：①若LP问题的可行域存在，则可行域一定是凸集。②若LP问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解的话）一定是可行域凸集的某个极点（顶点）。三、线性规划应用举例与软件求解例1（下料问题）某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？第二节单纯形法1.线性规划的标准型用单纯形法求解线性规划的前提是先将模型化为标准型：非标准形式如何化为标准2)不等式约束化为等式约束练习：请将例1的约束化为标准型一般地，记松弛变量的向量为Xs，则复习：非齐次线性方程组解若线性方程组没有现成的基，可利用增广矩阵的行初等变换法找到一组基。其中其解为从而解的每个分量都是非负数，就叫做可行解。基与解的对应关系：所对应的解2.基本概念（2）基矩阵与基变量——6个。（3）基本解与基本可行解例4：在上例中上二组概念间的联系：3.基本定理二、单纯形法的步骤1.确定初始基可行解2.最优性检验判断现行的基本可行解是否最优要判定是否已经达到最大值，只需将代入目标函数，使目标函数用非基变量表示，即：定理1：最优解判别定理对于线性规划问题若某个基本可行解所对应的检验向量，则这个基本可行解就是最优解。基本可行解的改进换入变量和换出变量的确定：换出变量的确定—最小比值原则如果确定为换入变量，方程其中为Ａ中与对应的系数列向量。现在需在中确定一个基变量为换出变量。当由零慢慢增加到某个值时，的非负性可能被打破。为保持解的可行性，可以按最小比值原则确定换出变量：若定理3：无最优解判别定理若是一个基本可行解，有一个检验数，但是，则该线性规划问题无最优解。寻找更好的基可行解以例1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。（3）换基、计算下一个基可行解、再检验，直至最优三、单纯形表单纯形表的主要结构：例5：用单纯形法求解例1σ的计算:x3例：借助人工变量求初始的基本可行解考虑线性规划问题：为了在约束方程组的系数矩阵中得到一个m阶单位矩阵作为初始可行基，在每个约束方程组的左端加上一个人工变量可得到：————————————————————————添加了m个人工变量以后，在系数矩阵中得到一个m阶单