运筹学1章.ppt

导 语 导 语 运筹学发展渊源 运筹学的性质和特征 运筹学解决问题的步骤 运筹学的主要内容 运筹学内容 数学规划：线性规划 非线性规划 整数规划 动态规划 随机规划 模糊规划 灰色规划等等 图与网络理论 存储论 排队论 博弈论 决策论 系统模拟等等 目 录 第一章 线性规划基础 第二章 线性规划专题 第三章 整数规划 第四章 动态规划 第五章 图与网络分析第六章 存储论 第一章 线性规划基础 1.线性规划问题及其数学模型 建模过程的一般形式 综上所述， 不难看出。线性规划应用范围非常广泛。建模过程可归纳如下 （1）确定一组决策变量 （2）确定一个线性目标函数 （3）确定一组线性约束条件 在实际问题时，不同的问题其目标函数和约束条件的表达不尽相同，必须具体问题具体分析。 这里第一章第二节。 规划问题建模后就要求解，找出最优方案。 线性规划求解法目前目前常用的有两种方法：图解法和单纯形法。 图解法简单直观，但只适用于于两个变量； 单纯形法是线性规划的通用方法，适应于任意多个变量，但比较抽象。 本节讨论图解法。 图解法求解线性规划是利用模型中方程式的几何图形来直接找到最优解。从原理上，我们可以利用平面和立体空间图形来分别求解两个变量或者三个变量的线性规划问题。但立体图形麻烦，求解三个变量的线性规划问题不太适用。所以图解法只适用于两个变量，故实际意义不大。 研究图解法的一个重要目的是在于了解和剖析线性规划的原理及过程。 在以x1,x2为坐标轴的直角坐标系中， x1、x2≥0是指第一象限。 每个约束条件都代表一个平面。如x1+x2≤6是代表以直线x1+x2=6为边界的左下方的半平面,若同时满足x1，x2≥0,x1+x2≤6,x1+2x2≤8,x2≤3的约束条件的点，必然落在由这三个半平面交成的第三世界国家象限区域内。该区域内每一个点都是这个线性规划问题的解（可行解），因此该区域是线性规划的解集合（可行解域）。 我们再分析目标函数Z=3x1+4x2，在这个坐标平面上，它可表示以Z为参数、-3/4为斜率的一族平行线： x2=-3/4x1+Z/4 位于赋一直线上的点，具有相同的目标函数值，因而称它为“等值线”，当Z值由小变大时，直线x2=-3x1/4+Z/4沿其法线方向（3，4）的右上方移动，可以找到最优解的坐标为（4，2），于是最优值为Z=3*4+4*2=20，最优街道计划方案是甲产品4吨，乙2 吨，最大利润2000元。 用图解法计算过程： 1）绘出每个约束议程的约束平面 设约束方程为a1x1+a2x2≤(≥,=)b (1)画出直线a1x1+a2x2=b (2)若约束方程为a1x1+a2x2≤b 则半平面在直线-（a1,a2)方向 (3)若约束方程为a1x1+a2x2≥b 则半平面在直线（a1,a2)方向 (4)若约束方程为a1x1+a2x2=b 则半平面为该直线 2）绘出可行解域 各个约束半平面相交的区域 3）作法线相垂直的目标函数等值线 设目标函数为Z=c1x1+c2x3,作与方向（c1,c2)相垂直的目标函数等值线在可行解域中移动 (1)若目标函数为求最大值，则目标函数等值线沿方向（c1，c2）同方向移动 (2)若目标函数为求最小值，则目标函数等值线沿方向（c1，c2）相反方向移动 移动中确定使目标达到最优的可行解，该解即为最优解。 4）解出最优解 对于一般线性规划问题，求解结果还可能出现多种情况 1）无穷多最优解（多重解） 2）无界解（无最优解） 3）无可行解（解为空集合） 此问题的最优解在x1+2x2=8的中间线段上，该线段上任意一点都使Z取得相同的最大值，这个线性规划问题有无穷多最优解。 该问题可行解域为空集，即无可行解，当然也无最优解。 图解法简单直观，单纯形法比较抽象，但它们之间有许多共性的东西。我们可以把它们共性的东西提取出来，使单纯形法中抽象的东西用低维的图形表示出来，有助于理解单纯形法原理，这就是线性规划的几何意义 从图解法中直观地见到，当线性规划问题的可行解域非空时，它是有界或无界的凸多边形。若线性规划问题存在最优解，它一定在可行解域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多个解。线性规划的这些特性并不因变量的个数增加而改变。 设有两点W1(x1,Y1)，W2(x2,Y2)。我们要求出W1，W2连线