102图解法.ppt

1、,信息系,刘康泽,两变量图解法,对于仅含两个未知变量的LP问题，用图解法既简单又直观。通过图解法，可以形象地了解多个未知变量的线性规划问题求解的基本原理。,一、约束条件对应的半平面,也就是说： 每一个约束条件都代表一个半平面,两个变量的图解法,在平面直角坐标系中 ：,二元一次不等式 Ax1+Bx2+C 0表示直线 Ax1+Bx2+C = 0某一侧的所有点组成的平面区域。称为半平面。,【注】确定半平面的原则：,即它表示的点 位于直线 的法向量 所指的一侧。,即它表示的点 位于直线 的法向量 所指的另一侧。,x1 x2 1,x1 x2 1,x1 x2 =1,例1：约束x1 x2 1,x1,例2：约

2、束 3x1+2x2 12,3x1+2x2 12,3x1+2x2 = 12,3x1+2x2 12,例3：,0,区域 中的每一个点（包括边界点）都是这个线性规划问题的一个可行解，这个区域就是此问题的可行解域。,如何在可行集中找到目标函数的最优解？,就上例而言： ，当 h 取不同的值时，在坐标平面上，目标函数就表示成为以h为参数，以 为斜率的一族平行线：,位于同一直线上的点，具有相同的目标函数值，因而称它为“目标函数等值线”。,显然当直线沿其法方向移动时。h 的值由小变到大，当移动到可行解域的某个边界点时， h 的值便达到了满足约束条件的最大值，这样就得到了问题的最优解。,二、目标函数的等值线,另一

3、方面，由于LP问题是在可行解集上寻求使目标函数值最小（最大）值点。因而我们考虑在可行解集内沿着目标函数的梯度方向(或梯度方向的反方向) ，用一族运动的目标函数等值线来寻求最小（或最大）的值。,由于可行解集是一个凸多边形。故当最小（或最大）值点存在时，这个最小（最大）值点必在可行解集的边界上，并且至少有一点是该凸 多边形的顶点。,最小（最大）值点一定是距某条穿越可行解域的等值线L最远的点。,三、图解法的步骤,2、绘制目标函数等直线 画出目标函数等直线（一般将目标函数直线放在可行域中）， 再过原点作出目标函数的法方向。,3、求最优解 在可行域中找到距目标函数等直线最远的点，即为所求的最小（或最大）

4、值点。求最大值时沿法方向找最远的点， 求最小值时沿着法方向的反方向找最远的点。,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,最优解: x =(3,1) 最优值: f = 5,(3,1),min f = x1+2x2,例5 :,2,4,6,x1,x2,2,4,6,有无穷多个最优解， 即具有多重解，通解为：,x （2）（3, 1）,x（1）（1, 3）,01,当=0.5时 x= (x1,x2) = 0.5(1, 3)+0.5(3,1)=(2 ,2 ),min f = 5 x1+5 x2,例6 :,2,4,6,x1,x2,2,4,6,无界解(无最优解),max f =x1+2x2,例7 :,x1,x2,O,10,20,30,40,10,20,30,40,50,50,无可行解, 即:无最优解,max f=3x1+4x2,例8 :,从图解法中我们能直观地见到：,（1）当线性规划问题的可行域非空时，它是有界或无界的凸多边形。,（2）若线性规划问题存在最优解，则最优解一定在可行解域的某个顶点达到；若最优解在两个顶点同时达到，则这两个顶点连线上的任意一点都是最优解，即存在无穷多个最优解。,以上两点对多个变量的线性规划问题也