筹学胡运权第五版课件.pptxVIP

运筹学(OperationsResearch)

一、古代朴素的运筹学思想例如：田忌赛马二、运筹学的起源国外英文原名OperationsResearch简称“O.R.”直译为：运用研究或作业研究正式出现于1938年7月英国一份关于防空作战系统运行的研究报告中二战后运筹学的发展经历了三个阶段绪论

国内1956年成立第一个运筹学小组1957年从“夫运筹策帷幄之中，决胜于千里之外”中摘取“运筹”二字，将O.R.正式翻译为“运筹学”三、运筹学的定义研究工具：数学，计算机科学及其他相关科学研究目的：对有限资源进行合理规划、使用，并提供优化决策方案。研究对象：复杂系统的组织和管理参考《大英百科全书》、《辞海》、《中国企业管理百科全书》等。

四、运筹学研究的基本特点系统的整体优化多学科的配合模型方法的应用五、运筹学研究的基本步骤分析与表述问题建立数学模型对问题求解对模型和模型导出的解进行检验建立对解的有效控制方案的实施

第一章线性规划及单纯形法第二章线性规划的对偶理论第六章图与网络分析第三章运输问题第四章整数规划与分配问题六、本课程的主要学习内容

第一章线性规划及单纯形法LinearProgrammingandSimplexMethod

xa此为无约束的极值问题1.1一般线性规划问题的数学模型1-1问题的提出例1用一块边长为a的正方形铁皮做一个无盖长方体容器，应如何裁剪可使做成的容器的容积最大？解：如图设四个角上减去的小正方形边长为x，则容器体积为：时，容积最大

例2常山机器厂生产I、II两型产品。这两型产品都分别要在A、B、C三种不同设备上加工。按工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如下表：如何安排生产才能使总的利润最大？单位产品消耗设备工时III设备工时限量（小时）设备A设备B设备C240205121615单位利润（元）23

解：设计划期内两种产品的数量分别为x1，x2，则总利润为：max z=2x1+3x22x1+2x2?12 4x1?165x2?15x1?0，x2?0简记为：s.t.（约束于：）z=2x1+3x2在满足限制条件下求z的最大值。此为有约束极值问题

1-2线性规划问题的数学模型原型模型数学模型提炼数学工具1、原型：现实世界中人们关心、研究的实际对象。模型：将某一部分信息简缩、提炼而构造的原型替代物。数学模型：对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设,并运用适当数学工具得到的一个数学结构。

3、规划问题数学模型的三要素2、规划问题目标函数：问题要达到的目标要求，表示为决策变量的函数。用z=f(x1，x2，…，xn)表示。决策变量：决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。用x1，x2，…，xn表示。约束条件：决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。即求目标函数在若干约束条件下的最值。

4、线性规划问题（LinearProgramming）的数学模型（2）一般形式：（1）条件：决策变量为可控的连续变量，目标函数和约束条件都是线性的。简记为“L.P.”max(或min)z=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤（=，≥）b1a21x1+a22x2+…+a2nxn≤（=，≥）b2 …am1x1+am2x2+…+amnxn≤（=，≥）bmx1,x2,…,xn≥0

连加形式02其他形式：01

其中01称为价值行向量；02决策列向量03系数列向量04右端列向量05向量形式

1其中2称为价值行向量；3决策列向量4右端列向量5约束矩阵或系数矩阵矩阵形式

或02标准形式011-3线性规划问题的标准形式

2目标函数求极大值3约束条件全是等式（线性方程组）1条件5右端常数全非负4决策变量全非负

ABC则令转化为若目标函数求极小值，即标准化方法

若约束条件为不等式，则依次引入松弛变量或剩余变量（统称为松弛变量），转化为等式约束条件。注意：松弛变量在目标函数中系数全为0。约束为≥不等式，减去松弛变量，化为等式约束条件；约束为≤不等式，加上松弛变量，化