第三章线性规划的解法习题解答y.doc

第三章 线性规划的解法 §3.1重点、难点提要 一、线性规划问题的图解法及几何意义 1．图解法。 线性规划问题采用在平面上作图的方法求解，这种方法称为图解法。图解法具有简单、直观、容易理解的特点，而且从几何的角度说明了线性规划方法的思路，所以，图解法还有助于了解一般线性规划问题的实质和求解的原理。 （1）图解法适用于求解只有两个或三个变量的线性规划问题，求解的具体步骤为： 1）在平面上建立直角坐标系； 2）图示约束条件，找出可行域。具体做法是画出所有约束方程(约束条件取等式)对应的直线，用原点判定直线的哪一边符合约束条件，从而找出所有约束条件都同时满足的公共平面区域，即得可行域。求出约束直线之间，以及约束直线与坐标轴的所有交点，即可行域的所有顶点； 3）图示目标函数直线。给定目标函数Z一个特定的值k，画出相应的目标函数等值线； 4）将目标函数直线沿其法线方向向可行域边界平移，直至与可行域边界第一次相切为止，这个切点就是最优点。具体地，当k值发生变化时，等值线将平行移动。对于目标函数最大化问题，找出目标函数值增加的方向(即坐标系纵轴值增大的方向)，等值线平行上移到可行域(阴影部分)的临界点，最终交点就是取得目标函数最大值的最优解；对于目标函数最小化问题，找出目标函数值减少的方向(即坐标系纵轴值减少的方向)，等值线平行下移到可行域(阴影部分)的临界点，最终交点就是取得目标函数最小值的最优解。 （2）线性规划问题的几种可能结果： 1）有唯一最优解； 2）有无穷多个最优解； 3）无最优解(无解或只有无界解)。 2．重要结论。 （1）线性规划的可行域为一个凸集，每一个可行解对应该凸集中的一个点； （2）每一个基可行解对应可行域的一个顶点。若可行解集非空，则必有顶点存在，从而，有可行解必有基可行解。 （3）一个基可行解对应约束方程组系数矩阵中一组线性无关的列向量，对于n个变量m个约束方程的线性规划问题，基可行解的个数不会超过 3-1 其中， 标准形式(3-1)具有几种等价的表示形式。 （1）一般形式 （2）矩阵形式 （3）向量形式 其中 ， ，， 线性规划模型标准形式中的一般形式、矩阵形式和向量形式等三种表达形式是等价的，在应用中可根据需要灵活使用。 2．线性规划模型的标准形式的特点 线性规划模型的标准形式具有四个特点： （1）目标函数是最大化类型： （2）约束条件均由等式组成： （3）决策变量均为非负： （4）资源常数项非负： 3．线性规划模型的标准化 根据线性规划模型标准形式的特点，我们可以将其它形式的线性规划模型转化为标准形式，这种转化过程称为线性规划模型的标准化。 （1）目标函数的转化。 若原问题的目标函数是最小化，即 则可将原目标函数乘以(1，等价转化为最大化问题 转化后的问题与原问题有相同的最优解。 （2）约束条件的转化。 约束条件的转化是将不等式约束转化为等式约束。如果约束条件为 则引入松弛变量，将其转化为等价的等式约束条件 如果约束条件为 则引入剩余变量，将其转化为等价的等式约束条件 总之，若原问题的约束条件中，约束为“(”型，则左边+松驰变量转化为等式约束；若约束为“(”型，则左边－剩余变量转化为等式约束。 （3）变量约束的转化。 如果原问题中某变量非正，即，则令； 如果原问题中某变量是自由变量(即无非负限制)，则可令 将变换后的变量代入原问题，得到的转化后的问题与原问题具有相同的最优解。 （4）资源常量的转化。 如果某个资源常量，则先将所在的约束式两边乘以－1使得后，再将不等约束化为等式约束。 三、单纯形法原理与基本思路 丹捷格（G．B．Dantzig）在1947年提出的求解线性规划问题的单纯形法，使线性规划在理论上渐趋成熟，在实际应用中日益广泛和深入。 单纯形法的原理：如果线性规划问题的可行域D非空，则可从D的某一顶点X 0出发，判断它是否最优；如果不是，则沿着边界找其邻近的另一个顶点，新顶点应该比原顶点更优，再次判优；如果不是，再次沿着边界找其邻近的顶点，再判优。通过逐次迭代，直至找出最优解或判定问题无解。 单纯形法的原理表明，单纯形法是一种迭代算法。 根据单纯形法的原理，可得出单纯形法求解的基本思路： （1）求线性规划问题（LP）的初始基可行解X 0，并将线性规划问题的相关数据简单明了、恰当地表示出来(制成单纯形表)； （2）判别X 0是否为最优解。为此，需要给出一个基可行解是否为最优的判别准则； （3）如果X 0不是最优解，则应另求基可行解X 1，且使得 CT X 1( CT X 0（至少CT X 1( CT X 0）。同时，由X 0相应的单纯形表给出X 1相应的单纯形表。这里，需要给出X 1迭代X 0的换基迭代(进基、出基)原则 （4）若X 1仍非最优解，则视X 1为X 0重复步骤（3），直至线性规划问