三部分运筹学方法课件

第第 三三 部部 分分 运筹学方法运筹学方法运筹学概述运筹学的性质和特点运筹学 的发展：三个来源运筹学实质与解决方法运筹学的主要分支 运筹学的发展：三个来源 军 事 管 理 经 济 运筹学的性质和特点v运筹学是用数学方法研究各种系统最优化问题的学科。其研究方法是应用数学语言来描述实际系统，建立相应的数学模型，并对模型进行研究和分析，据此求得模型的最优解；其目的是制定合理运用人力、物力和财力的最优方案；为决策者提供科学决策的依据；其研究对象是各种社会系统，可以是对新的系统进行优化设计，也可以是研究已有系统的最佳运营问题。因此，运筹学既是应用数学，也是管理科学，同时也是系统工程的基础之一。v运筹学的特点定量化分析多学科交叉，如综合利用了心理学、经济学、物理、化学等方法最优决策运筹学的研究对象 1）机器、工具、设备、人员等如何最佳利用问题 方法有：线性规划、整数规划、网络图、动态规划、目标规划等2）竞争现象如战争、投资、商品竞争 方法是对策论3）拥挤现象如公共汽车排队、打电话、买东西、飞机着陆、船舶进港等方法是排队论运筹学的实质在于模型的建立和使用。应用运筹学处理问题时，首先要求从系统观点来分析问题，即不仅要求提出需要解决的问题和希望达到的目标，而且还要弄清问题所处的环境和约束条件，包括：时间、地点、资金、原材料、设备、人力、能源、动力、信息、技术等的环境和约束条件，以及要处理问题中的主要因素、各种环境和约束条件之间的逻辑关系。运筹学实质与解决方法运筹学的主要分支 各个分支充实完善形成体系各个分支充实完善形成体系确定性模型确定性模型数学规划数学规划线性规划线性规划整数规划整数规划非线性规划非线性规划动态规划动态规划几何规划几何规划参数规划参数规划多目标规划多目标规划组合优化组合优化图论与网络分析图论与网络分析优选与统筹方法优选与统筹方法随机性模型随机性模型对策论对策论排队论（随机服务系统）排队论（随机服务系统）可靠性理论可靠性理论库存论库存论搜索论搜索论计算机随机模拟计算机随机模拟决策论决策论第四章第四章 线性规划模型线性规划模型线性规划模型的建立线性规划模型的建立线性规划模型的标准形线性规划模型的标准形 线性规划模型的图解法线性规划模型的图解法线性规划模型的单纯形法线性规划模型的单纯形法求解线性规划的计算软件求解线性规划的计算软件建立线性规划模型有三个基本步骤：第一步，找出问题中的所有相关的未知变量（决策变量），并用代数符号表示它们，根据变量的物理性质研究变量是否有非负性；第二步，找出问题中的目标，写成变量的线性函数，作为线性规划模型的目标函数；第三步，找出问题中所有的限制或约束，写成变量的线性方程或线性不等式，作为线性规划模型的约束条件。第一节第一节 线性规划模型的建立线性规划模型的建立例题例题5.1(生产计划问题生产计划问题)某厂计划内将安排生产I,II两种产品，已知生产单位重量的产品所需的设备为A及B、C两种原料的消耗如表1所示：生产单位重量的产品I可获利2万，生产单位重量的产品II可获利5万。问：如何安排生产可使工厂获得的利润最多？例题例题5.2（合理下料问题）（合理下料问题）某厂生产过程中需要用长度分别为31米、25米和17米的同种棒料毛坯分别为200、100和300根，而现在只有一种长度为9米的原料，问应如何下料才能使废料最少?解解 解决下料问题的关键在于找出所有可能的下料方法(如果不能穷尽所有的方法，也应尽量多收集各种可能的下料方法)，然后对这些方案进行最佳结合。对给定的9米长的棒料进行分割，可以有9种切割方法，见表5.2所示。表5.2 毛坯切割方案表例题例题5.3（合理配料问题）根据对（合理配料问题）根据对77种食物所含的九种种食物所含的九种营养物：热量营养物：热量(糖与脂肪糖与脂肪)、蛋白质、钙、铁、维生素、蛋白质、钙、铁、维生素A、维生素维生素BI、维生素维生素B2、草酸与维生素草酸与维生素C的成份及食物的成份及食物的市场价格调查，按照医生所提出的对每个人每天所的市场价格调查，按照医生所提出的对每个人每天所需的营养要求，可得表需的营养要求，可得表5.3问怎样采购食物才能在保证营养要求的前提下花费最问怎样采购食物才能在保证营养要求的前提下花费最省？这就是营养问题或饮食问题，配料问题就是由此省？这就是营养问题或饮食问题，配料问题就是由此而推广来的。而推广来的。n第二节第二节 线性规划模型的标准形线性规划模型的标准形一线性规划模型的可行解和最优解一线性规划模型的可行解和最优解满足目标函数，即使得目标函数达到最大值或最小值的可行解，称为该线性规划模型的最优解。把最优解代入目标函数所得到的目标函数的最大值或最小值称为最优值。定义定义5.2 某个线性规划模型的全体可行解组成的集合，称为该线性规划模型的可行解域。二线性规划模型的标准型二线性规划模型的标准型线性规划模型的标准型线性规划模型的标准型为：线性规划模型的标准型还可以记为：标准型具有以下特点：目标函数是求最大值；约束条件为线性方程组；未知变量都有非负限制。线性规划模型的非标准型，在以下三种情况下可化为标准型：目标函数是求最小值约束条件为不等式模型中的某些变量没有非负限制第三节第三节 线性规划模型的图解法线性规划模型的图解法例题例题5.4 求以下线性规划问题的最优解：（1）第一步，求可行解域：可行解域是所有满足约束条件的数组，四个不等式是四个半平面，而可行解域就是这四个半平面的公共部分。其形状为一个凸多边形区域，可行解是凸多边形内的一个点，如图5.1。图5.1 例题5.4（1）的可行解域第二步，求最优解：图5.2 例题5.4（1）的最优解（2）线性规划的可行解域一般为凸多边形，而有时则是无界的凸多边形，如本题图5.3所示。图5.3 例题5.4（2）的可行解域注：若线性规划存在唯一最优解，则一定是可行解域的某个顶点。若两个顶点都是最优解，则这两个顶点连线上的任一点都是最优解，若可行解区域无界，则可能不存在最优解。第四节第四节 线性规划模型的单纯形法线性规划模型的单纯形法一用换元迭代法解线性规划问题一用换元迭代法解线性规划问题这种方法的过程的几何意义为：从凸多边形（或多面体）线性规划问题解的一个顶点（可行基）经换基迭代转变到另一顶点（可行基），最终达到最优顶点，这就是线性规划问题解的换元迭代法，它奠定了矩阵形式的单纯形方法的基础。二二 单纯形方法的理论基础单纯形方法的理论基础三三.换基迭代求最优解的过程换基迭代求最优解的过程求解-单纯形法将所给问题化为标准形找出一个初始可行基,建立初始单纯形表检查所有检验数(若全为非负,则已得到最优解,计算停止.否则继续下一步)考察是否无解(若是,计算停止,否则继续下一步)确定入基变量,出基变量对初始单纯形表进行单纯形变换四四.用单纯形法解线性规划问题用单纯形法解线性规划问题第五节第五节 求解线性规划的计算软件求解线性规划的计算软件一一 用用LINDO软件解线性规划软件解线性规划LINDO是“Linear interactive and discrete optimizer”的缩写，它是解决线性规划，整数规划等规划问题的有力工具，在大型计算机上，它可用于解决50000个约束条件，200000个变量的线性规划问题。安装好LINDO软件后，在桌面上双击LINDO图标，得一个空白图框，然后在空白图框内输入求解问题，如二二 用用MATLAB优化工具箱解线性优化工具箱解线性规划规划MATLAB是Matrix Laboratory（矩阵实验室）的缩写。它早期是线性代数课的教学软件，后来逐步应用于实际工程问题的计算，目前已成为工程界和应用数学人员常用的数学软件之一。MATLAB是一种交互式的高级计算机软件，有如下特点：它以矩阵运算为基本运算，用命令式语句运行，附有数值计算，最优化，信号处理，系统识别，控制系统等几十个工具箱（Toolbox）；MATLAB使用十分方便，几乎是直接把算式键入计算机，立刻得出计算结果，因此有“电子草稿纸”的美誉；具有很强的图形表现能力。nMatlab软件求解线性规划的命令如下：结果：x=15.0000 5.0000 10.0000Z=25.0000第第 三三 部部 分分 运筹学方法运筹学方法第五章第五章 非线性规划的概念和原理非线性规划的概念和原理非线性规划的实例及数学模型非线性规划的实例及数学模型 无约束非线性规划问题无约束非线性规划问题约束非线性规划问题约束非线性规划问题第一节第一节 非线性规划的实例及数学模型非线性规划的实例及数学模型例题例题6.1 投资问题：假定国家的下一个五年计划内用于发展某种工业的总投资为b亿元，可供选择兴建的项目共有几个。已知第j个项目的投资为 亿元，可得收益为 亿元，问应如何进行投资，才能使盈利率（即单位投资可得到的收益）为最高？例题例题6.4 砂石运输问题砂石运输问题 设有设有 的砂、石要由甲地运输到已地，运的砂、石要由甲地运输到已地，运输前需要先装入一个有底无盖并在底部有滑行输前需要先装入一个有底无盖并在底部有滑行器的木箱中，砂、石运到已地后，从箱中倒出，器的木箱中，砂、石运到已地后，从箱中倒出，再继续用空箱装运，不论箱子大小，每装运一再继续用空箱装运，不论箱子大小，每装运一箱，需箱，需0.1元，箱底和两端的材料费为元，箱底和两端的材料费为20元元/，箱子两侧材料费为箱子两侧材料费为5元元/，箱底的两个滑行，箱底的两个滑行器与箱子同长，材料费为器与箱子同长，材料费为2.5元元/，问木箱，问木箱的长、宽、高应各为多少米，才能使运费与箱的长、宽、高应各为多少米，才能使运费与箱子的成本费的总和为最小。子的成本费的总和为最小。第二节第二节 无约束非线性规划问题无约束非线性规划问题各种不同的无约束优化算法的主要区别在于：确定搜索方向的方法各种不同的无约束优化算法的主要区别在于：确定搜索方向的方法不同，根据在确定搜索方向时是否使用导数可将这些方法分为两不同，根据在确定搜索方向时是否使用导数可将这些方法分为两类：类：（1）不使用导数的无约束优化方法，又称为直接搜索法，包）不使用导数的无约束优化方法，又称为直接搜索法，包括坐标轮换法，括坐标轮换法，Hooke-Jeeves方法，方法，Rosenbrock方法，方法，Zangwill 方法，方法，Powell方法和随机搜索法等，一般认为方法和随机搜索法等，一般认为Powell方法是比较有效的。方法是比较有效的。（2）。用导数的无约束优化方法，包括梯度法（最速下降法），）。用导数的无约束优化方法，包括梯度法（最速下降法），牛顿法，阻尼牛顿法（这两种方法都要使用二阶导数），共轭梯牛顿法，阻尼牛顿法（这两种方法都要使用二阶导数），共轭梯度法，度法，DFP算法，算法，BFGS算法等。一般认为：变尺度算法是求解算法等。一般认为：变尺度算法是求解无约束优化问题时使用导数的算法中较为有效而且收敛也较快的无约束优化问题时使用导数的算法中较为有效而且收敛也较快的一类算法，其中一类算法，其中BFGS算法是数值稳定性较好的一种方法，因而算法是数值稳定性较好的一种方法，因而是大家乐于采用的一种算法。是大家乐于采用的一种算法。下面我们主要介绍两种基本的迭代法：下面我们主要介绍两种基本的迭代法：梯度法和牛顿法梯度法和牛顿法梯度法梯度法 牛顿法与梯度法的搜索方向不同，优点是收敛速度快，但有时却不适用而需采取改进措施，并且当维数较高时，的计算量很大，这就产生拟牛顿法和无记忆拟牛顿法等。自然，这些数值方法比图解法和解析法要复杂一些，计算量也要大一些，一般都需要使用计算机。好在科技人员已研制出各种求解无约束优化算法的计算软件，使用它们，多数情况下可以顺利地求得优化问题的最优解。第三节第三节 约束非线性规划问题约束非线性规划问题一凸规划问题一凸规划问题凸规划具有两个重要性质：凸规划的可行集是凸集凸规划的可行集是凸集凸规划的局部最小解就是它的全局最小凸规划的局部最小解就是它的全局最小解解 （证明略）（证明略）二其它类型的约束非线性规划问二其它类型的约束非线性规划问题题近三十年来，约束优化方法有了很大的发展，求解方法大近三十年来，约束优化方法有了很大的发展，求解方法大体上可分为以下几类：体上可分为以下几类：利用问题的最优性条件来求解的方法（如例题利用问题的最优性条件来求解的方法（如例题6.9中用的方法）。中用的方法）。用线性规划或二次规划来逐次逼近非线性优化问题的方法，例如线用线性规划或二次规划来逐次逼近非线性优化问题的方法，例如线性逼近法（性逼近法（SLP法）、二次逼近法（序列二次规划法，简记为法）、二次逼近法（序列二次规划法，简记为SQP法）等。法）等。把约束非线性规划问题转化为一个或一系列无约束非线性规划问题把约束非线性规划问题转化为一个或一系列无约束非线性规划问题来求解的方法，例如惩罚函数法（也叫来求解的方法，例如惩罚函数法（也叫SUMT外点法）、碰壁函数外点法）、碰壁函数法（也叫法（也叫SUMT内点法）、混合罚函数法、精确罚函数法和乘子法内点法）、混合罚函数法、精确罚函数法和乘子法等。等。对约束非线性规划问题不预先进行转换，直接进行处理的分析方法，对约束非线性规划问题不预先进行转换，直接进行处理的分析方法，如可行方向法、梯度投影法、既约梯度法、广义既约梯度法（如可行方向法、梯度投影法、既约梯度法、广义既约梯度法（GRG法）、凸单纯形法等。法）、凸单纯形法等。对约束非线性规划问题不预先作转换的直接求解方法，如随机试验对约束非线性规划问题不预先作转换的直接求解方法，如随机试验法等。法等。数值试验和应用实践证实：数值试验和应用实践证实：20世纪世纪70年代以来出现的一些新年代以来出现的一些新方法，如乘子法、精确罚函数法、方法，如乘子法、精确罚函数法、GRG法和法和SQP法是比较有效的求法是比较有效的求解方法，它们已经研制成了计算软件，并在实际中得到了成功的应解方法，它们已经研制成了计算软件，并在实际中得到了成功的应用。用。