运筹学复习重点

《运筹学复习重点》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、松一#424友恒打印店第二章线性规划§1线性规划问题的基本模型一、线性规划标准模型线性规划标准模型的一般表达式：化一般型为标准型：①→②≤→左边+松弛变量；≥→左边-剩余变量③变量→；变量无限制→令④→等式两边同乘以（-1）.§2图解法一、线性规划几何解的有关概念考虑线性规划模型一般形式：可行解：凡满足约束条件和非负条件的决策变量的取值称为线性规划可行解。可行域：所有可行解的集合称为线性规划的可行域。最优解：使目标函数达到最优值的可行解称为线性规划的最优解。二、图解法基本步骤在明确线性规划可行解、可行域

2、和最优解的基础上，介绍线性规划的图解法。对于两个或三个变量的线性规划问题，可以通过平面图或立体图进行求解，是线性规划问题解的几何表示。图解法的优点简单、直观，有助于理解线性规划问题求解的基本原理。它的局限性在于只能对两个或三个变量的线性规划问题求解。图解法的基本步骤可以概括如下：（1）建立平面（空间）直角坐标系。取决策变量为坐标向量，标出坐标原点、坐标轴指向及单位长度。32松一#424友恒打印店（2）确定线性规划解可行域。根据非负条件和约束条件画出解的可行域。只有在第一象限的点才满足线性规划非负条件，将

3、以不等式表示的每个约束条件化为等式，在坐标系第一象限作出约束直线，每条约束直线将第一象限划分为两个半平面，通过判断确定不等式所决定的半平面。所有约束直线可能形成或不能形成相交区域，若能形成相交区域，相交区域任意点所表示解称为此线性规划可行解，这些符合约束限制的点集合，称为可行集或可行域。转到第三步；否则该线性规划问题无可行解。（3）绘制目标函数等值线（面）。目标函数等值线（面）就是目标函数取值相同点的集合，通常是一条直线（二维平面）或一个平面（三维空间）。（4）寻找线性规划最优解。对于目标函数的任意等值

4、线（面），确定该等值线（面）平移后值增加的方向，平移此目标函数的等值线（面），使其达到既与可行域相交又不可能使目标函数值再增加的位置。相交位置存在三种情况：若有唯一交点时，目标函数等值线（面）与可行域相切，切点坐标就是线性规划的最优解；若相交于多个点，称线性规划有无穷多最优解；若相交于无穷远处，此时无有限最优解。【例】运用图解法求解线性规划问题三、线性规划问题几何解的讨论利用图解法可以讨论线性规划解的四种情况。（1）唯一最优解。线性规划唯一最优解是指该规划问题有且仅有一个既在可行域内、又使目标值达到最优

5、的解。（2）无穷多最优解。线性规划问题的无穷多解是指，该规划问题有无穷多个既在可行域内、又使目标值达到最优的解。如果例的目标函数变为，目标函数的等值线正好和约束条件相平行。在目标函数向右上方平移的过程中，与可行域相切于上的所有点，此时，该线性规划问题存在无穷多最优解。（3）无有限最优解（无界解）。线性规划问题的无有限最优解是指最大化问题中的目标函数值可以无限增大，或最小化问题中的目标函数值可以无限减少。考虑下述线性规划模型：利用图解法进行求解时，可行域是一个非封闭的无界区域，的取值可以无限增大，同时，目

6、标函数值也可以增大到无穷，如下图所示。在这种情况下，称线性规划无有限最优解或无界解。原因在于建立线性规划模型时，遗漏了某种必要资源的约束。32松一#424友恒打印店4542x2x1+2x2=4x1-2x2=5x1ox2x1（4）无可行解。当线性规划问题中的约束条件不能同时满足时，将出现无可行域的情况，这时不存在可行解，即该线性规划问题无解。考虑下述线性规划模型利用图解法进行求解时，在第一象限内，所有约束条件不能形成一个相交平面区域，如上图。线性规划问题不存在可行域，也就是说，问题没有可行解。其原因是线性

7、规划模型自身的错误，约束条件之间自相矛盾，应根据实际情况进行调整。针对线性规划几何解还有一些重要的性质，这里不加证明叙述如下：（1）线性规划几何解存在四种情况：唯一最优解、无穷多最优解、无有限最优解、无可行解。（2）若线性规划可行域非空，则可行域必定是一个凸集。（3）若线性规划可行域非空，则凸集至多有有限个极点。（4）若线性规划优解存在，则最优解或最优解之一肯定能够在可行域（凸集）的某个极点找到。通过上述的讨论，求线性规划问题最优解，可以转化为在其可行域有限个极点上进行搜索的方法。基本思路是，先找出凸集

8、任意一个极点，计算极点的目标函数值。比较与之相邻的目标函数值是否比该极点的目标函数值更优，如果为否，则该极点就是最优解，如果为是，转到比该点目标函数值更优的另一极点。重复上述过程，直到找出使目标函数值达到最忧的极点为止。可行域空集无界有界解无可行解唯一最优解多重最优解解无界解§3单纯形法一、预备知识32松一#424友恒打印店1、基考虑线性规划标准模型其中：系数矩阵为阶矩阵。若的秩为，为中的任意阶子矩阵，且行列式，则称为线性规划模型式的一个基