第五节 LP问题的几何解释,一、二个决策变量LP问题的图解法,x1,x2,50 100 150,150 100 50,l1,l2,可行域,O,A,B,C,z=500,z=1000,z=1260,(30,80),最优解,结论：若LP问题存在最优解，则必在 可行域的某个极点(角点)上找到。,极点基可行解 前提：可行域是个凸集。 凸集：设K是n维欧氏空间的一点集，若任 意两点,可行域的性质,线性规划的可行域是凸集 线性规划的最优解在极点上,凸集,凸集,不是凸集,极点,二、几种特殊情况,1、LP存在多个解,2、LP问题无可行解,3、LP问题存在无界解,判断：若LP的可行域无界，则该LP存在 无界解。,错！,小结,1、可行域为封闭的有界区域,唯一最优解,多个最优解,2、可行域为非封闭的无界区域,唯一最优解,多个最优解,无界解,3、可行域为空集,无可行解,O,4,5,1,-1,2,4,3,1,2,3,A,B,D,C,E,H,F,I,G,x1,Min z=2x1+3x2 s.t. x1+ x24 （1） 2x1+5x2 10 （2） -x1+ x2 1 （3） x1，x2 0 约束条件（1）、（2）、（3）的松弛变量或剩余 变量分别为x3、x4、x5,x2=0,x3=0,x4=0,x5=0,x1=0,以上问题中，有 个基变量， 个非基变量； 基解为 ；基可行解为 ； 最优解为 。,3,2,Z=9,Z=6,A B C D E F G H I O,C D H,D,x2,思考题,