第三章 线性规划的解法
§3.1重点、难点提要
一、线性规划问题的图解法及几何意义
1．图解法。
线性规划问题采用在平面上作图的方法求解，这种方法称为图解法。图解法具有简单、直观、容易理解的特点，而且从几何的角度说明了线性规划方法的思路，所以，图解法还有助于了解一般线性规划问题的实质和求解的原理。
（1）图解法适用于求解只有两个或三个变量的线性规划问题，求解的具体步骤为：
1）在平面上建立直角坐标系；
2）图示约束条件，找出可行域。具体做法是画出所有约束方程(约束条件取等式)对应的直线，用原点判定直线的哪一边符合约束条件，从而找出所有约束条件都同时满足的公共平面区域，即得可行域。求出约束直线之间，以及约束直线与坐标轴的所有交点，即可行域的所有顶点；
3）图示目标函数直线。给定目标函数Z一个特定的值k，画出相应的目标函数等值线；
4）将目标函数直线沿其法线方向向可行域边界平移，直至与可行域边界第一次相切为止，这个切点就是最优点。具体地，当k值发生变化时，等值线将平行移动。对于目标函数最大化问题，找出目标函数值增加的方向(即坐标系纵轴值增大的方向)，等值线平行上移到可行域(阴影部分)的临界点，最终交点就是取得目标函数最大值的最优解；对于目标函数最小化问题，找出目标函数值减少的方向(即坐标系纵轴值减少的方向)，等值线平行下移到可行域(阴影部分)的临界点，最终交点就是取得目标函数最小值的最优解。
（2）线性规划问题的几种可能结果： 1）有唯一最优解； 2）有无穷多个最优解；
3）无最优解(无解或只有无界解)。 2．重要结论。
（1）线性规划的可行域为一个凸集，每一个可行解对应该凸集中的一个点； （2）每一个基可行解对应可行域的一个顶点。若可行解集非空，则必有顶点存在，从而，有可行解必有基可行解。
（3）一个基可行解对应约束方程组系数矩阵中一组线性无关的列向量，对
1
于n个变量m个约束方程的线性规划问题，基可行解的个数不会超过
Cnm?n!m!(n?m)!。
（4）如果最优解存在，则最优解或最优解之一（具有无穷多个解的情形），一定可在可行域的凸集的某个顶点上找到。
二、线性规划模型的标准形式与标准化
线性规划模型的形式有多种多样，这给求解线性规划问题带来不便。虽然图解法对线性规划模型的形式没有限制，但它对变量个数有约束。为寻求统一规范的求解方法，我们定义线性规划模型的标准形式，将线性规划模型的所有形式都转化为标准形式进行研究。
1．线性规划模型的标准形式
maxz?c1x1?c1x2??cnxn?a11x1?a12x2??a1nxn?b1?ax?ax??ax?b2112222nn2?s..t???ax?ax??ax?bmnnm?m11m22??x1,x2,,xn?0其中，bi?0,i?1,2,（1）一般形式
3-1
,m
标准形式(3-1)具有几种等价的表示形式。
nmaxz??cjxjj?1?ni?1,2,??aijxj?bis..t?j?1?x?0j?1,2,,n?j（2）矩阵形式
,m
maxz?cX?AX?b
s.t??X?0（3）向量形式
2
maxz?cX?n??Pjxj?b s..t?j?1?X?0?其中
?a11?A??a21???am1?aaa1222m2??2n?， ???amn?1naac?(c1,c1,?b1??x1??b??x?2??X??2?b?,cn)，??，
??
????b?m??xn??a1j???a2j??Pj???,j?1,2,????amj??是等价的，在应用中可根据需要灵活使用。
2．线性规划模型的标准形式的特点 线性规划模型的标准形式具有四个特点： （1）目标函数是最大化类型：maxz?cX （2）约束条件均由等式组成：AX?b （3）决策变量均为非负：X?0 （4）资源常数项非负：b?0 3．线性规划模型的标准化
,n
线性规划模型标准形式中的一般形式、矩阵形式和向量形式等三种表达形式
根据线性规划模型标准形式的特点，我们可以将其它形式的线性规划模型转化为标准形式，这种转化过程称为线性规划模型的标准化。
（1）目标函数的转化。
若原问题的目标函数是最小化，即
nminz??cjxj
j?1则可将原目标函数乘以?1，等价转化为最大化问题
maxz??min(?z)???cjxj
j?1n转化后的问题与原问题有相同的最优解。
（2）约束条件的转化。
约束条件的转化是将不等式约束转化为等式约束。如果约束条件为
3
?axijj?1nj?bi
则引入松弛变量xn?i?0，将其转化为等价的等式约束条件
?axijj?1nj?xn?i?bi
如果约束条件为
?axijj?1nj?bi
则引入剩余变量xn?i?0，将其转化为等价的等式约束条件
?axijj?1nj?xn?i?bi
总之，若原问题的约束条件中，约束为“?”型，则左边+松驰变量转化为等式约束；若约束为“?”型，则左边－剩余变量转化为等式约束。
（3）变量约束的转化。
如果原问题中某变量非正，即xj?0，则令x?j??xj?0； 如果原问题中某变量xj是自由变量(即无非负限制)，则可令
xj?x?j?x?j?,x?j?0,x?j??0
将变换后的变量代入原问题，得到的转化后的问题与原问题具有相同的最优解。
（4）资源常量的转化。
如果某个资源常量bi?0，则先将bi?0所在的约束式两边乘以－1使得
bi???bi?0后，再将不等约束化为等式约束。
三、单纯形法原理与基本思路
丹捷格（G．B．Dantzig）在1947年提出的求解线性规划问题的单纯形法，使线性规划在理论上渐趋成熟，在实际应用中日益广泛和深入。
单纯形法的原理：如果线性规划问题的可行域D非空，则可从D的某一顶点X 0出发，判断它是否最优；如果不是，则沿着边界找其邻近的另一个顶点，新顶点应该比原顶点更优，再次判优；如果不是，再次沿着边界找其邻近的顶点，再判优。通过逐次迭代，直至找出最优解或判定问题无解。
单纯形法的原理表明，单纯形法是一种迭代算法。 根据单纯形法的原理，可得出单纯形法求解的基本思路：
（1）求线性规划问题（LP）的初始基可行解X 0，并将线性规划问题的相关
4
相关推荐：
loading