之图解法及解的概念.ppt

此组片的内容讲三节课,*第一节 基本概念 *第二节 线性规划问题的图解法 *第三节 线性规划模型的解及性质 *第四节 单纯形法 第五节 对偶规划 第六节 运输问题及表上作业法,第一章 线性规划,第二节 线性规划问题的图解法,一 、图解法解极大化问题 二、 图解法求解极小化问题 三、 线性规划模型的解的各种情况 四、 解法的优点及局限性,一 、用图解法解极大化问题,例1MaxZ 60x 50y 2x 4y 80 3x 2y 60 x, y 0,(1)以x、y作为坐标轴，建立平面直角坐标系，根据x、y非负的约束，可行解区域位于坐标图的第一象限（见图（a）,1图示全部约束条件， 确定可行解区域,（2）用等式约束代替非 等式约束，画出直线 2x4y80 和 3x2y60 （见图（b）,2从可行解中找出 最优解,（1）等直线法 （2）试算法,（ 1）等直线法：把目标函数 Z60x50y 看成是随着Z的取值不同而产生的一族直线。令目标函数值分别为0、600、1200作平行线族（见图（2）.,从图中可见，Z值越高，目标函数直线离原点越远。所以，寻找最优解问题可归结为：找出离原点最远的一条直线与可行解集的交点。,（2）试算法：,（a）线性规划的可行域是凸多边形或凸集； （b）线性规划的最优解如果存在，必然在 可行解集的某个顶点上达到。,* 试算法是根据下面线性规划解的性质而得出的一种算法：,* 根据线性规划解的性质，先求出可行解集各顶点的坐标，然后试算目标函数之值，使目标函数达到极值的解，即为最优解,（见下面表13）,表13 例1试算结果,最优解为（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,返回,三、线性规划模型的解的各种情况,例3,解：在本例中，由于目标函数（Z2x4y）的等直线与约束条件（x2y 8）的直线相平行，故最优解同时在两个顶点上达到。则在此两顶点连线上的任何一点都是最优解，即有无限多个最优解。,从图（6）可见，本例的可行域无上界，目标函数的值可趋于无穷大。在这种情况下无法确定最优解。,解：,例4,从图（7）可以看出，本题的可行域是一个空集，因此，无可行解。这是由于本题中包括了相互矛盾的约束条件的缘故。,解：,例5,线性规划问题解的几种情况,（1）有唯一的最优解。这时最优解一定在可行域的某个顶点达到； （2）有最优解，但不唯一。这时最优解一定充满一个线段，此线段是可行域的一条边； （3）有可行解，但没有最优解。这时可行域上的点能使目标函数趋向无穷大； （4）没有可行解（空集）。即线性规划问题是不可行的。,返回,图解法的优点及局限性,图解法的优点：直观、形象，它容易使人具体地认识线性规划模型的求解过程。,图解法的局限性：一般仅适用于只有两个变量的。对于三维以上的模型，约束条件表现为平面，这就难用图解法去求解了。,返回,第三节 线性规划模型的解及有关概念,一、线性规划问题的标准型 二、线性规划模型的解 （性质略，见P16）,线性规划的标准形有如下四个特点： 目标最大化、 约束为等式、 变量均非负、 右端项非负。,一、线性规划问题的标准型,返回,二、线性规划模型的解,我们把满足约束条件（1-3）、（1-4）的解称为线性规划模型的可行解。当mn时，约束方程组（1-3）可以有无穷多个解。全部可行解的集合，称为可行域。 线性规划模型的最优解，就是指能满足（1-2），即能使目标函数达到最大值的可行解。,1线性规划的解,2线性规划标准形式的基、 基本解、基本可行解,我们称这个解为基本解，若这个解能同时满足线性规划模型的非负约束条件，则把这个基本解称为基本可行解。,任取A中的3个线性无关列向量构成矩阵B，那么B为线性规划的一个基。如果B为单位矩阵，则称B为一个单位基。 线性规划的任一个基， 总可以通过线性方程 组的变换化成单位基。,一般形式：,对于线性规划的约束条件系数矩阵A,设B是A矩阵中的一 个非奇异（可逆）的子矩阵，则称B为线性规划的一个基。 任取A中的m个线性无关列向量构成矩阵B，那么B为线性规 划的一个基。如果B为单位矩阵，则称B为一个单位基。 称对应于基B的变量为基变量，而其它变量称为非基变量。,（1） 线性规划的基、基变量,（2） 基本解、基本可行解和可行基,对于线性规划问题，设矩阵B为一个基，令所有非基变量为零，可以得到m个关于基变量的线性方程，解这个线性方程组得到基变量的值。我们称这个解为一个基本解。若得到的基变量的值均非负，则称为基本可行解，同时称这个基B为可行基。,返回,第一步 建立平面直角坐标系 第二步 求满足约束条件的可行解区域 第三步 作目标函数的等值线簇，确定 目标函数值增加方向（或用等 值线法）。 第四步 从可行解区内找满足目标函数 的最优解。,1.两个变量的线性规划问题的图解法步骤,本次课小结,第二节 线性规划问题的图解法,2. 图解法的优点及局限性,图解法的优点：直观、形象，它容易使人具体地认识线性规划模型的求解过程。,线性规划问题解的几种情况,图解法的局限性：一般仅适用于只有两个变量的。对于三维以上的模型，约束条件表现为平面，这就难用图解法去求解了。,本次课小结,（1）有唯一的最优解； （2）有最优解，但不唯一； （3）有可行解，但没有最优解； （4）没有可行解（空集）。,一、线性规划问题的标准型（四个特点） 二、线性规划模型的解及有关概念,第三节 线性规划模型的解及有关概念,线性规划模型的解的概念： 可行解、可行域、最优解、 基本解、基本可行解。,2线性规划标准形式的基的概念： 基、单位基、可行基、 基变量、非基变量。,本次课小结,练 习,1思考题 (1)建立线性规划模型的三个步骤是什么? (2)两个变量的线性规划问题的图解法的一般步骤是什么? (3)求解线性规划问题时可能出现几种结果? (4)什么是线性规划的标准型?如何把一个非标准形式的线性规划问题转化成标准形式? (5)理解线性规划问题的可行解、基本解、基本可行解、最优解的概念。,练 习,2判断下列说法是否正确 (1)线性规划问题的最优解一定在可行域的顶点达到。 (2)线性规划的可行解集是凸集。 (3)如果一个线性规划问题有两个不同的最优解，