文档介绍：??图解法图解法??线性规划问题求解的几种可能结果线性规划问题求解的几种可能结果??由图解法得到的启示由图解法得到的启示??线性规划解的概念线性规划解的概念??凸集的概念凸集的概念??线性规划的基本定理线性规划的基本定理第二节第二节线性规划问题的解线性规划问题的解继续继续返回返回上页上页下页下页返回返回(二维)线性规划问题图解法:(二维)线性规划问题图解法:((11)满足约束条件的变量的值,称为可)满足约束条件的变量的值,称为可行解。行解。((22)使目标函数取得最优值的可行解,)使目标函数取得最优值的可行解,称为最优解。称为最优解。例例11 max S = 50 x max S = 50 x1 1 + 30 x+ 30 x2 2 . 4 x . 4 x1 1 + 3 x+ 3 x2 2 ?? 120 120 2 x 2 x1 1 + x+ x22?? 50 50 x x11,,xx22?? 0 0上页上页下页下页返回返回x2504030201010203040x14x4x11+3x+3x2 2 ?? 120 120由由4x4x11+3x+3x2 2 ?? 120 120 x x1 1 ?? 0 x 0 x2 2 ?? 0 0围成的区域围成的区域上页上页下页下页返回返回x2504030201010203040x12x2x11+x+x2 2 ?? 50 50由由2x2x11+x+x2 2 ?? 50 50 x x1 1 ?? 0 x 0 x22?? 0 0围成的区域围成的区域上页上页下页下页返回返回x2504030201010203040x12x1+x2 ? 504x1+3x2 ? 120可行域可行域同时满足:同时满足:2x2x11+x+x22?? 50 504x4x11+3x+3x2 2 ?? 120 120xx1 1 ?? 0 x 0 x2 2 ?? 0 0的区域的区域————可行域可行域上页上页下页下页返回返回x2504030201010203040x1可行域可行域O(0,0)Q1(25,0)Q2(15,20)Q3(0,40)可行域是由约束条件围成的区域,该区域可行域是由约束条件围成的区域,该区域内的每一点都是可行解,它的全体组成问内的每一点都是可行解,它的全体组成问题的解集合。题的解集合。该问题的可行域是由该问题的可行域是由OO,,QQ11,,QQ22,,QQ33作为顶作为顶点的凸多边形点的凸多边形上页上页下页下页返回返回x2504030201010203040x1可行域可行域目标函数是以目标函数是以SS作为参数的一组平行线作为参数的一组平行线xx2 2 ==S/30-S/30-((5/35/3))xx11上页上页下页下页返回返回x2504030201010203040x1可行域可行域当当SS值不断增加时,该直线值不断增加时,该直线xx2 2 ==S/30-S/30-((5/35/3))xx11沿着其法线方向向右上方移动沿着其法线方向向右上方移动。。上页上页下页下页返回返回x2504030201010203040x1可行域可行域当该直线移到当该直线移到QQ22点时,点时,SS(目标函数)值达到最大:(目标函数)值达到最大:Max S=50Max S=50??15+30 15+30 ?? 20=1350 20=1350此时最优解此时最优解==((1515,,2020))Q2(15,20)上页上页下页下页返回返回二个重要结论:二个重要结论:??满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。的场合。??最优解必定能在凸多边形的某一个顶点上取得,这一事实也可以推广到更多最优解必定能在凸多边形的某一个顶点上取得,这一事实也可以推广到更多变量的场合。变量的场合。