第一章线性规划辩析.ppt

2.线性规划的图解法 线性规划的图解法(解的几何表示)： 对于只有两个决策变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。 图解法求解线性规划问题的步骤如下： 2.线性规划的图解法 (1)建立直角坐标系： 分别取决策变量x1 ,x2 为坐标向量。 2.线性规划的图解法 （2）绘制可行域： 对每个约束（包括非负约束）条件，作出其约束半平面（不等式）或约束直线（等式）。 各半平面与直线交出来的区域若存在，其中的点为此线性规划的可行解。称这个区域为可行集或可行域。然后进行下步。否则若交为空，那么该线性规划问题无可行解。 2.线性规划的图解法 （3）绘制目标函数等值线，并移动求解： 目标函数随着取值不同，为一族相互平行的直线。 首先，任意给定目标函数一个值，可作出一条目标函数的等值线（直线）； 然后，确定该直线平移使函数值增加的方向； 最后，依照目标的要求平移此直线。 2.线性规划的图解法 结果 若目标函数等值线能够移动到既与可行域有交点又达到最优的位置，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。 否则，目标函数等值线与可行域将交于无穷远处，此时称无有限最优解。 2.线性规划的图解法 Max z = 1500 x1 + 2500 x2 s.t. 3x1+ 2x2 ≤ 65 (A) 2x1+ x2 ≤ 40 (B) 3x2 ≤ 75 (C) x1 , x2 ≥ 0 (D, E) 2.线性规划的图解法 例题作图（1） 按照图解法的步骤： （1）以决策变量x1 ，x2 为坐标向量作平面直角坐标系； 2.线性规划的图解法 （2）对每个约束（包括非负约束）条件作出直线（A、B、C、D、E），并通过判断确定不等式所决定的半平面。 各约束半平面交出来的区域即可行集或可行域如下图阴影所示。 2.线性规划的图解法 例题作图（2） 第2步图示(1) 分别作出各约束半平面 2.线性规划的图解法 例题作图（3） 第2步图示(2) 各约束半平面的交－可行域 2.线性规划的图解法 （3）任意给定目标函数一个值（例如37500）作一条目标函数的等值线，并确定该等值线平移后值增加的方向（向上移动函数值增大），平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置，得到交点 (5,25)T ，即最优解。此目标函数的值为70000。 2.线性规划的图解法 例题作图（4） 2.线性规划的图解法 例题作图（5） 第3步图示(2) 求出最优解 2.线性规划的图解法 2.线性规划的图解法 线性规划的解有如下几种情况： 1、存在有限最优解： 惟一最优解；无穷多个最优解 2、无有限最优解（无界解） 3、无可行解（可行域空） 2.线性规划的图解法 例2.5：在例2.4的线性规划模型中，如果目标函数变为： Max z = 1500 x1 + 1000 x2 那么，最优情况下目标函数的等值线与直线（A）重合。这时，最优解有无穷多个，是从点 (5,25)T到点 (15,10)T 线段上的所有点，最优值为32500。如下图所示： ? 2.线性规划的图解法 2.线性规划的图解法 2.线性规划的图解法 2、线性规划的图解法 2.线性规划的图解法 根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况 1.可行域为封闭的有界区域 (a)有唯一的最优解； (b)有无穷多个最优解； 2.可行域为封闭的无界区域 (c)有唯一的最优解； (d)有无穷多个最优解； (e)目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少)，因而没有有限最优解。 3.可行域为空集 (f)没有可行解，原问题无最优解 我们把由（1.3-11）和(1.3-13)式结合成 (1.3-14) , (1.3-15) , (1.3-16)式称为线性规划对应于基 的典式．表1