1、上页上页上页上页下页下页下页下页返回返回返回返回第三节第三节 线性规划解的性质线性规划解的性质v线性规划解的概念线性规划解的概念v凸集及其顶点凸集及其顶点 v几个基本定理的证明几个基本定理的证明继续继续继续继续返回返回返回返回上页上页上页上页下页下页下页下页返回返回返回返回线性规划问题解的概念线性规划问题解的概念线性规划问题解的概念线性规划问题解的概念标准型可行解:满足AX=b,X=0的解X称为线性规划问题的可行解。全部可行解的集合称为可行域。最优解：使目标函数Z=CX达到最大值的可行解称为最优解。上页上页上页上页下页下页下页下页返回返回返回返回 基：若B是矩阵A中mm阶非奇异子矩阵（|B|0
2、），则B是线性规划问题的一个基。不妨设：,j=1，2，,m 基向量。，j=1，2，,m 基变量。,j=m+1,n 非基变量。线线性性规规划划问问题题解解的的概概念念上页上页上页上页下页下页下页下页返回返回返回返回 求解 线线性性规规划划问问题题解解的的概概念念上页上页上页上页下页下页下页下页返回返回返回返回基解：称上面求出的X解为基解,基解个数不超过Cnm个基可行解：非负的基解X称为基可行解,每一个基可行解的非零分量个数不会超过m个.可行基：对应基可行解的基称为可行基线线性性规规划划问问题题解解的的概概念念T基变量令 可求出：0.21=+nmmxxx上页上页上页上页下页下页下页下页返回返回返回
3、返回 线性规划解的关系图 非可行解非可行解非可行解非可行解可行解可行解 基可行解基可行解 基解基解基解基解线线性性规规划划问问题题解解的的概概念念 最优解？最优解？上页上页上页上页下页下页下页下页返回返回返回返回 例：求基解、基可行解、最优解。线线性性规规划划问问题题解解的的概概念念上页上页上页上页下页下页下页下页返回返回返回返回1 0 0 5 10 4 5 Y 2 0 4 5 2 0 17 Y 3 5 0 0 5 4 10 Y 4 0 5 5 0 -1 20 N5 10 0 -5 0 4 15 N6 5 2.5 0 0 1.5 17.5 Y 7 5 4 0 -3 0 22 N8 2 4 3
4、0 0 19 Y 9 0 010 0 0是否基是否基可行解可行解最优解最优解线线性性规规划划问问题题解解的的概概念念解：解：上页上页上页上页下页下页下页下页返回返回返回返回 ：求基解、基可行解、最优解。练习：线线性性规规划划问问题题解解的的概概念念上页上页上页上页下页下页下页下页返回返回返回返回凸集及其顶点凸集及其顶点凸集：凸凸凸凸集集集集及及及及其其其其顶顶顶顶点点点点上页上页上页上页下页下页下页下页返回返回返回返回 顶点:若K是凸集，XK；若X不能用不同的两点 的线性组合表示为：则X为顶点.凸集凸集凸凸凸凸集集集集及及及及其其其其顶顶顶顶点点点点上页上页上页上页下页下页下页下页返回返回返回
5、返回定理1:若线性规划问题存在可行域,则其可行域:是凸集.几个基本定理的证几个基本定理的证明明证明:几个基本定理的证明)0,=XbAXXD上页上页上页上页下页下页下页下页返回返回返回返回 只要验证只要验证X X在在D D中即可中即可上页上页上页上页下页下页下页下页返回返回返回返回 引理：可行解X为基可行解 X的正分量对应的系数列向量线性无关定理3：若线性规划问题有最优解，则一定存在一个基可行解是最优解。定理2：线性规划问题的基可行解X 对应于可行域D的顶点。证明：反证法。分两步。上页上页上页上页下页下页下页下页返回返回返回返回几点结论：线性规划问题的可行域是凸集。基可行解与可行域的顶点一一对应
6、，可行域有有限多个顶点。最优解必在顶点上得到。上页上页上页上页下页下页下页下页返回返回返回返回图解法图解法9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1+2x2 84x1 164 x2 16可行域可行域BCDEA可行域为凸集可行域为凸集目标函数不同时目标函数不同时等值线的斜率不同等值线的斜率不同最优解在顶点产生最优解在顶点产生 目标函数等目标函数等值线的斜率值线的斜率最优解最优解上页上页上页上页下页下页下页下页返回返回返回返回图解法图解法9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1+2x2 84x1 164 x2 16可行域可行域BCDEA
7、可行域为凸集可行域为凸集目标函数不同时目标函数不同时等值线的斜率不同等值线的斜率不同最优解在顶点产生最优解在顶点产生 目标函数等目标函数等值线的斜率值线的斜率最优解最优解上页上页上页上页下页下页下页下页返回返回返回返回图解法图解法9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1+2x2 84x1 164 x2 16可行域可行域BCDEA可行域为凸集可行域为凸集目标函数不同时目标函数不同时等值线的斜率不同等值线的斜率不同最优解在顶点产生最优解在顶点产生 目标函数等目标函数等值线的斜率值线的斜率最优解最优解上页上页上页上页下页下页下页下页返回返回返回返回求解LP的基本思路1、构造初始可行基；2、求出一个基可行解（顶点）3、最优性检验：判断是否最优解；4、基变化，转2。要保证目标函数值比 原来更优。上页上页上页上页下页下页下页下页返回返回返回返回第三节第三节 线性规划解的性质线性规划解的性质
