《第二章线性规划.ppt》由会员分享，可在线阅读，更多相关《第二章线性规划.ppt（41页珍藏版）》请在三一文库上搜索。
1、第二章 线性规划,第一节 线性规划问题及其数学模型 第二节 线性规划问题的图解法 第三节 单纯形法 第四节 线性规划的对偶问题 第五节 线性规划在卫生管理中的应用,第一节 线性规划问题及其数学模型,一、线性规划问题的特征和建模的步骤,二、线性规划问题的数学模型及一般形式,三、线性规划问题的标准形式,（一）线性规划问题的标准形式,（二）书写形式,（三）标准形式的转化,2、任务给定，如何合理地计划、统筹安排 以最少的资源完成它,1、资源给定，如何合理地计划、统筹安排 才能发挥最大的效益；,一、线性规划问题的特征和建模的步骤,(一) 线性规划研究的内容,（三）都有一个目标要求，并且这个目标可以表示为
2、决策变量的线性函数（称为目标函数）。,（一）可用一组变量（x1，x2 , xn）（称之为决策变量）来表示问题的方案，正常要求这组变量的取值是非负的，称为非负约束；,（二）存在某种限制条件，这些限制条件都可以用线性等式或不等式来表示。（这些等式或不等式称之为规划问题的约束条件方程式）,(二) 线性规划问题的共同特征,(三) 建立模型的三个步骤, 确定一组变量（决策变量）； 表示出一定的限制条件； 写出目标函数。,Max ( Min ) Z = c1 x1 + c2 x2 + + cn xn,约束条件：,目标函数：,二、线性规划问题的数学模型及一般形式,第二节 线性规划问题的图解法,一 、图解法解
3、极大化问题 二、 图解法求解极小化问题 三、 线性规划模型的解的各种情况 四、 解法的优点及局限性,一 、用图解法解极大化问题,例1MaxZ 60x 50y 2x 4y 80 3x 2y 60 x, y 0,(1) 以 x、y 作为坐标轴，建立平面直角坐标系，根据 x、y 非负的约束，可行解区域位于坐标图的第一象限（见图（a）,1图示全部约束条件， 确定可行解区域,（2）用等式约束代替非等 式约束，画出直线 2x4y80 3x2y60 （见图（b）,（3）根据不等式约束 2x4y 80 3x2y 60 确定可行解区域 （见图（c）,（ 1）等直线法：把目标函数 Z60x50y 看成是随着Z的取
4、值不同而产生的一族直线。令目标函数值分别为0、600、1200作平行线族（图（2）,从图中可见，Z值越高，目标函数直线离原点越远。所以，寻找最优解问题可归结为：找出离原点最远的一条直线与可行解集的交点。,2从可行解中找出最优解,（1）等直线法 （2）试算法,（2）试算法：,（a）线性规划的可行域是凸多边形或凸集； （b）线性规划的最优解如果存在，必然在 可行解集的某个顶点上达到。,* 试算法是根据下面线性规划解的性质而得出的一种算法：,* 根据线性规划解的性质，先求出可行解集各顶点的坐标，然后试算目标函数之值，使目标函数达到极值的解，即为最优解,（见下面表13）,表13 例1试算结果,最优解为
5、（x，y）（10，15） 最优值为 ZMax 1350,二、 图解法求解极小化问题,例 MinZ 50x 80y 4x + 10y 40 10x 5y 50 35x + 35y 245 x， y 0,解： 1、图示全部约束条件， 确定可行解区域,2可行解中找出最优解 （1）用等直线法求最优解。本例是极小值问题，因此目标函数值取离原点尽可能近的等直线的值（见图（4）。通过 p2 点的等直线离原点最近， p2 点的坐标既满足全部约束条件又能使目标函数取得最小值， 故为最优解。,（2）用试算法求最优解（见表14）,表1-4 例2试算结果,最优解为（x，y）（5，2） 最优值为 ZMin 410,三、
6、线性规划模型的解的各种情况,例3,解：在本例中，由于目标函数（Z2x4y）的等直线与约束条件（x2y 8）的直线相平行，故最优解同时在两个顶点上达到。则在此两顶点连线上的任何一点都是最优解，即有无限多个最优解。,从图（6）可见，本 例的可行域无上界，目 标函数的值可趋于无穷 大。在这种情况下无法 确定最优解。,解：,例4,从图（7）可以看出， 本题的可行域是一个空集，因此无可行解。这是由于本题中包括了相互矛盾的约束条件的缘故。,解：,例5,线性规划问题解的几种情况,（1）有唯一的最优解。这时最优解一定在可行域的 某个顶点达到； （2）有最优解，但不唯一。这时最优解一定充满一个线段，此线段是可行
7、域的一条边； （3）有可行解，但没有最优解。这时可行域上的点能使目标函数趋向无穷大； （4）没有可行解（空集）。即线性规划问题是不可行的。,图解法的优点及局限性,图解法的局限性： 一般仅适用于只有两个变量的。对于三维以上的模型，约束条件表现为平面，这就难用图解法去求解了。,图解法的优点： 直观、形象，它容易使人具体地认识线性规划模型的求解过程。,线性规划的标准形有如下四个特点： 目标最大化、 约束为等式、 变量均非负、 右端项非负。,三、线性规划问题的标准形式,（一）线性规划问题的标准形式,（二）书写形式,1.简缩形式,2.矩阵形式 见教材 P12,二、线性规划模型的解,我们把满足约束条件（1
8、-3）、（1-4）的解称为线性规划模型的可行解。当mn时，约束方程组（1-3）可以有无穷多个解。全部可行解的集合，称为可行域。 线性规划模型的最优解，就是指能满足（1-2），即能使目标函数达到最大值的可行解。,1线性规划的解,对应于最优解的目标函数之值，称为最优值。,三、单纯形法的基本原理 （一）典型方程组 见规划教材第二章把后面的片子都改成新的内容,第三节 单纯形法,一、线性规划问题的标准型 二、线性规划模型的解 （性质略，见P15）,2线性规划标准形式的基、 基本解、基本可行解,我们称这个解为基本解，若这个解能同时满足线性规划模型的非负约束条件，则把这个基本解称为基本可行解。,基,基变量,
9、非基变量,称变量 在约束方程组对应的系数列向量为线性规划模型的一个基。基对应的变量称为基变量，其它变量称为非基变量。即：,任取A中的3个线性无关列向量构成矩阵B，那么B为线性规划的一个基。如果B为单位矩阵，则称B为一个单位基。线性规划 的任一个基，总可以 通过线性方程组的变 换化成单位基。,一般形式：,对于线性规划的约束条件系数矩阵A,设B是A矩阵中的一 个非奇异（可逆）的子矩阵，则称B为线性规划的一个基。 任取A中的m个线性无关列向量构成矩阵B，那么B为线性规 划的一个基。如果B为单位矩阵，则称B为一个单位基。 称对应于基B的变量为基变量，而其它变量称为非基变量。,（1） 线性规划的基、基变
10、量,（2） 基本解、基本可行解和可行基,对于线性规划问题，设矩阵B为一个基，令所有非基变量为零，可以得到m个关于基变量的线性方程，解这个线性方程组得到基变量的值。我们称这个解为一个基本解。若得到的基变量的值均非负，则称为基本可行解，同时称这个基B为可行基。,返回,第一步 建立平面直角坐标系 第二步 求满足约束条件的可行解区域 第三步 作目标函数的等值线簇，确定 目标函数值增加方向（或用等 值线法）。 第四步 从可行解区内找满足目标函数 的最优解。,1.两个变量的线性规划问题的图解法步骤,本次课小结,第二节 线性规划问题的图解法,2. 图解法的优点及局限性,线性规划问题解的几种情况,图解法的局限
11、性：一般仅适用于只有两个变量的。对于三维以上的模型，约束条件表现为平面，这就难用图解法去求解了。,本次课小结,（1）有唯一的最优解； （2）有最优解，但不唯一； （3）有可行解，但没有最优解； （4）没有可行解（空集）。,图解法的优点：直观、形象，它容易使人具体地认识线性规划模型的求解过程。,一、线性规划问题的标准型（四个特点） 二、线性规划模型的解及有关概念,第三节 线性规划模型的解及有关概念,线性规划模型的解的概念： 可行解、可行域、最优解、 基本解、基本可行解。,2线性规划标准形式的基的概念： 基、单位基、可行基、 基变量、非基变量。,本次课小结,练 习,1思考题 (1)建立线性规划模型
12、的三个步骤是什么? (2)两个变量的线性规划问题的图解法的一般步骤是什么? (3)求解线性规划问题时可能出现几种结果? (4)什么是线性规划的标准型?如何把一个非标准形式的线性规划问题转化成标准形式? (5)理解线性规划问题的可行解、基本解、基本可行解、最优解的概念。,练 习,2判断下列说法是否正确 (1)线性规划问题的最优解一定在可行域的顶点达到。 (2)线性规划的可行解集是凸集。 (3)如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 (4)如果一个线性规划问题有可行解，那么它必有最优解。,作 业,求解线性规划问题 （1）Max Z = 10 x1 +5 x2 3x1 +4x29 5x1+2x28 x1, x2 0 （2）Max Z = 2x1 +x2 3x1 +5x215 6x1+2x224 x1, x2 0,