线性规划解的概念.ppt

1 2线性规划解的概念 图解法 对二维问题 可作出约束的图 简单直观地理解线性规划的解 例考察线性规划问题 等值线x 3y C 继续 解的概念 可行解 feasiblesolution 满足线性规划问题 LP 的所有约束条件的解 称为线性规划问题的一个可行解 可行域 LP 的所有可行解组成的集合K称为 LP 的可行域 若可行域为空 则称不可行 对标准型线性规划问题 其可行域为最优解 optimalsolution 可行域中每个可行解都对应一个目标值 其中对应的目标函数值最小的可行解x 称为 LP 的最优解 也称为 LP 的解 即最优值 最优解对应的目标值称为最优值 基设为满秩矩阵 秩为m 是A中的非奇异子矩阵 则称B为 LP 的一个基 基变量与非基变量B是由A的m个线性无关的列组成 对应的变量称为基变量 剩下的变量称为非基变量 基解令非基变量变量等于0 可得线性方程组的一个解 称为基解 basicsolution 基可行解若基解还是可行的 即满足非负性条件 则称为基可行解 basicfeasiblesolution简记为bfs 基解的个数非退化的基可行解 若基变量全部为正 否则称为退化的基可行解 即有基变量为0 基可行解 非可行解 例求出线性规划问题的全部基解 指出哪些是可行的 图解法 线性规划解的几种可能情况 无可行解可行域为空集 约束中存在矛盾方程 有唯一的最优解 通常的情况 必是可行域的顶点 有无穷多个最优解 有可行解但无最优解可行域必无界 1 3线性规划问题的几何意义 基本概念 凸集设K为n维线性空间的一点集 若对K中任意两点x y 及任意的 有则称K为凸集 规定空集和单点集为凸集 例超平面和半空间都是凸集 凸组合设为中的点 为满足下列条件的一组实数则称为的凸组合 极点设K为凸集 若x不能表示成K中不同的两点的凸组合 则称x为K的一个极点 顶点 基本定理 定理1任意一组凸集的交集仍为凸集 定理2线性规划问题的可行域是凸集 引理1线性规划问题的可行解为基可行解的充要条件是其正分量所对应的系数列向量是线性无关的 证明 必要性若x是基解 由定义 正分量对应的列线性无关 充分性若正分量对应的列线性无关 则个数不超过m 若 m 则是基 若 m 可扩充成基 定理3线性规划问题的基可行解对应于可行域的顶点 证明 若x是基可行解 设前m个分量为基变量 但不是极点 则存在x1 x2 0 1 x x1 1 x2 x1 x2的后n m个分量为0 若x是极点 但不是基可行解 正分量对应的列线性相关 对任意的实数取充分小的得两可行解x1 x2 使x x1 2 x2 2 推论线性规划可行域的顶点个数有限 引理2若K为有界闭凸集 则其中任何一点可表示为其顶点的凸组合 不证明 举例说明 定理4若可行域有界 线性规划问题的目标函数一定可以在其可行域的顶点达到最优 证明 另外 若可行域无界 但有最优解 则一定也可在顶点处达到最优 定理4换成代数说法就是 线性规划问题若存在最优解 则一定存在最优的基可行解 第二章单纯形法 穷举法的困难已知线性规划问题的一基可行解 问题此基可行解是否最优 该问题是否无最优解 如何改进 求一更好的基可行解 算法是否会有限步结束 如何找一基可行解 2 1单纯形表 为计算方便 将系数提出来 形成表格 设有一可行基 不妨设是前m个向量 则线性方程组可化为如下形式其中目标函数可表成非基变量的函数将系数提出列成表 称为对应于基B的单纯形表 单纯形表 最优性检验与解的判别 定理1 最优解的判别定理 设为 LP 的一基可行解 若对任意的非基变量 都有 则为最优解 称为检验数 定理2若对某非基变量 有那么 该线性规划问题无最优解 基可行解的改进 进基变量的选择出基变量的选择最小比值原则证明新的解是基可行解 在非退化假设下 新解目标值下降 单纯形法的计算步骤 算法 单纯形法 1 找出初始可行基 确定初始可行解 建立初始单纯形表 2 检验各非基变量的检验系数 若全部非正 结束 得到最优解 3 若某非基变量检验数为正 且其对应的系数列向量全部非正 结束 问题无最优解 4 选某个检验数为正的非基变量进基 计算最小比值 确定出基变量 5 以所选元素为主元进行消元 得新单纯形表 转2 例1用单纯形法求线性规划问题的解化为标准型 列初始单纯形表