之图解法及解的概念

《之图解法及解的概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、此组片的内容讲三节课*第一节  基本概念*第二节线性规划问题的图解法*第三节线性规划模型的解及性质*第四节单纯形法第五节对偶规划第六节运输问题及表上作业法第一章线性规划第二节线性规划问题的图解法一、图解法解极大化问题二、图解法求解极小化问题三、线性规划模型的解的各种情况四、解法的优点及局限性一、用图解法解极大化问题例1．MaxZ＝60x＋50y2x＋4y≤803x＋2y≤60x,y≥0(1)以x、y作为坐标轴，建立平面直角坐标系，根据x、y非负的约束，可行解区域位于坐标图的第一象限（见图（a））1．图示全部约束条件，确定可行解区域（2）用等式约束代替非等式约束，画出直线2x＋4y＝8

2、0和3x＋2y＝60（见图（b））2．从可行解中找出最优解（1）等直线法（2）试算法（1）等直线法：把目标函数Z＝60x＋50y看成是随着Z的取值不同而产生的一族直线。令目标函数值分别为0、600、1200作平行线族（见图（2））.从图中可见，Z值越高，目标函数直线离原点越远。所以，寻找最优解问题可归结为：找出离原点最远的一条直线与可行解集的交点。（2）试算法：（a）线性规划的可行域是凸多边形或凸集；（b）线性规划的最优解如果存在，必然在可行解集的某个顶点上达到。*试算法是根据下面线性规划解的性质而得出的一种算法：*根据线性规划解的性质，先求出可行解集各顶点的坐标，然后试算目标函数之值，

3、使目标函数达到极值的解，即为最优解（见下面表1－3）表1－3例1试算结果目标函数可行解集顶点顶点的坐标目标函数之值Ｏ0Ａ1200Ｂ1350(最优解)Ｃ1000最优解为（x，y）＝（10，15）最优值为ZMax＝1350返回二、图解法求解极小化问题例２MinZ＝50x＋80y4x+10y≥4010x＋5y≥5035x+35y≥245x，y≥0解：1、图示全部约束条件，确定可行解区域2．可行解中找出最优解（1）用等直线法求最优解。本例是极小值问题，因此目标函数值应该取离原点尽可能近的等直线的值（见图（4））。通过p2点的等直线离原点最近，p2点的坐标既满足全部约束条件又能使目标函数取得最小

4、值，故为最优解。（2）用试算法求最优解（见表1－4）表1-4例2试算结果目标函数可行解集顶点顶点的坐标目标函数之值Ｐ1500Ｐ2410(最优解)Ｐ3470Ｐ4800最优解为（x，y）＝（5，2）最优值为ZMin＝410返回三、线性规划模型的解的各种情况例3解：在本例中，由于目标函数（Z＝2x＋4y）的等直线与约束条件（x＋2y≤8）的直线相平行，故最优解同时在两个顶点上达到。则在此两顶点连线上的任何一点都是最优解，即有无限多个最优解。从图（6）可见，本例的可行域无上界，目标函数的值可趋于无穷大。在这种情况下无法确定最优解。解：例4从图（7）可以看出，本题的可行域是一个空集，因此，无可行

5、解。这是由于本题中包括了相互矛盾的约束条件的缘故。解：例5线性规划问题解的几种情况（1）有唯一的最优解。这时最优解一定在可行域的某个顶点达到；（2）有最优解，但不唯一。这时最优解一定充满一个线段，此线段是可行域的一条边；（3）有可行解，但没有最优解。这时可行域上的点能使目标函数趋向无穷大；（4）没有可行解（空集）。即线性规划问题是不可行的。返回图解法的优点及局限性图解法的优点：直观、形象，它容易使人具体地认识线性规划模型的求解过程。图解法的局限性：一般仅适用于只有两个变量的。对于三维以上的模型，约束条件表现为平面，这就难用图解法去求解了。返回第三节线性规划模型的解及有关概念一、线性规划问

6、题的标准型二、线性规划模型的解（性质略，见P16）线性规划的标准形有如下四个特点：目标最大化、约束为等式、变量均非负、右端项非负。一、线性规划问题的标准型返回二、线性规划模型的解（1－2）（1－3）（1－4）我们把满足约束条件（1-3）、（1-4）的解称为线性规划模型的可行解。当m＜n时，约束方程组（1-3）可以有无穷多个解。全部可行解的集合，称为可行域。线性规划模型的最优解，就是指能满足（1-2），即能使目标函数达到最大值的可行解。1．线性规划的解2．线性规划标准形式的基、基本解、基本可行解我们称这个解为基本解，若这个解能同时满足线性规划模型的非负约束条件，则把这个基本解称为基本可行

7、解。基基变量非基变量称变量在约束方程组对应的系数列向量为线性规划模型的一个基。基对应的变量称为基变量，其它变量称为非基变量。即：任取A中的3个线性无关列向量构成矩阵B，那么B为线性规划的一个基。如果B为单位矩阵，则称B为一个单位基。线性规划的任一个基，总可以通过线性方程组的变换化成单位基。基基变量非基变量一般形式：对于线性规划的约束条件系数矩阵A,设B是A矩阵中的一个非奇异（可逆）的子矩阵，则称B为线性规划的一个基。任取A中的m个线