运筹学—102图解法.ppt

信息系 刘康泽 信息系 刘康泽 两变量图解法 对于仅含两个未知变量的LP问题，用图解法既简单又直观。通过图解法，可以形象地了解多个未知变量的线性规划问题求解的基本原理。 一、约束条件对应的半平面 也就是说： 每一个约束条件都代表一个半平面 两个变量的图解法 在平面直角坐标系中 ： 二元一次不等式 Ax1+Bx2+C 0表示直线 Ax1+Bx2+C = 0某一侧的所有点组成的平面区域。称为半平面。 的法向量 所指的一侧的半平面。 （1）当约束条件为： 时，它表示位于直线： 【注】确定半平面的原则： O x1 x2 即它表示的点 位于直线 的法向量 所指的一侧。 的法向量的反方向 所指的一侧的半平面。 （2）当约束条件为： 时，它表示位于直线： 即它表示的点 位于直线 的法向量 所指的另一侧。 O x1 x2 x1 x2 o 1 -1 －x1＋ x2 1 －x1＋ x2 1 －x1＋ x2 =1 例1：约束－x1＋ x2 ≤ 1 x1 例2：约束 3x1+2x2 ≤ 12 3x1+2x2 12 3x1+2x2 = 12 3x1+2x2 12 x2 O 6 4 例3： 0 代表 轴的右侧半平面； 代表 轴的上侧半平面。 区域 中的每一个点（包括边界点）都是这个线性规划问题的一个可行解，这个区域就是此问题的可行解域。 0 代表以直线 为界的左下半平面； 代表以直线 为界的右下半平面 ; 代表以直线 为界的下半平面； 代表以直线 为界的左半平面； 如何在可行集中找到目标函数的最优解？ 就上例而言： ，当 h 取不同的值时，在坐标平面上，目标函数就表示成为以h为参数，以 为斜率的一族平行线： 位于同一直线上的点，具有相同的目标函数值，因而称它为“目标函数等值线”。 显然当直线沿其法方向移动时。h 的值由小变到大，当移动到可行解域的某个边界点时， h 的值便达到了满足约束条件的最大值，这样就得到了问题的最优解。 二、目标函数的等值线 另一方面，由于LP问题是在可行解集上寻求使目标函数值最小（最大）值点。因而我们考虑在可行解集内沿着目标函数的梯度方向(或梯度方向的反方向) ，用一族运动的目标函数等值线来寻求最小（或最大）的值。 由于可行解集是一个凸多边形。故当最小（或最大）值点存在时，这个最小（最大）值点必在可行解集的边界上，并且至少有一点是该凸 多边形的顶点。 最小（最大）值点一定是距某条穿越可行解域的等值线L最远的点。 三、图解法的步骤 1、求可行解集合 　　分别画出满足每个约束（包括变量非负要求）的半平面，其交集就是可行域（凸多边形） 。 “≤”号 选择 所指一侧； “≥”号 选择 所指一侧。 　　2、绘制目标函数等直线 　　画出目标函数等直线（一般将目标函数直线放在可行域中）， 再过原点作出目标函数的法方向　　　　。 　　3、求最优解 　　在可行域中找到距目标函数等直线最远的点，即为所求的最小（或最大）值点。求最大值时沿法方向找最远的点， 求最小值时沿着法方向的反方向找最远的点。 x1 x2 O 10 20 30 40 10 20 30 40 (3,4) 最优解(15,10) 最优解: x=( 15,10 ) 最优值: f ＝85 例4： 四、几个例子 2 4 6 x1 x2 2 4 6 最优解: