第05次课第一章线性规划详解.pptVIP

第二节 线性规划问题的几何理论 第三节 单纯形法 单纯形法的思路 第三节 单纯形法 单纯形法步骤 步骤1 确定初始基可行解 步骤2 建立单纯形表 步骤3 解的判别 步骤4 基变换 步骤5 旋转运算 第三节 单纯形法 结合一个例子介绍以上步骤 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第三节 单纯形法 第四节 单纯形法的进一步讨论 第四节 单纯形法的进一步讨论 单纯形法进一步讨论的几个问题 大M法 大M法 大M法 大M法 人工变量在目标函数中的系数为-M（M为任意大的正数）。 必须把人工变量从基变量中换出,或者使基变量中的人工变量为0，否则目标函数不可能实现最大化。 大M法 大M法 大M法 大M法 大M法 大M法 大M法 无穷多最优解判别的例子 大M法 无可行解判别的例子 第四节 单纯形法的进一步讨论 单纯形法进一步讨论的几个问题 第四节 单纯形法的进一步讨论 第一阶段： 不考虑原问题是否存在基可行解，给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数（人工变量加和）并要求实现最小化，代替原问题目标函数，得到新的线性规划问题。 用单纯形法求解此新的线性规划问题，若目标函数不为零，则原问题无可行解，应停止计算，否则进入第二阶段。 第二阶段： 对第一阶段计算得到的最终表：①去掉人工变量；②目标函数行的系数换成原问题的目标函数系数。作为第二阶段计算的初始表，再求解。 第四节 单纯形法的进一步讨论 第四节 单纯形法的进一步讨论 第四节 单纯形法的进一步讨论 第四节 单纯形法的进一步讨论 第四节 单纯形法的进一步讨论 第四节 单纯形法的进一步讨论 第四节 单纯形法的进一步讨论 无可行解判别的例子 第四节 单纯形法的进一步讨论 第一阶段： 不考虑原问题是否存在基可行解，给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数（人工变量加和）并要求实现最小化，代替原问题目标函数，得到新的线性规划问题。 用单纯形法求解此新的线性规划问题，若目标函数不为零，则原问题无可行解，应停止计算，否则进入第二阶段。 第二阶段： 对第一阶段计算得到的最终表：①去掉人工变量；②目标函数行的系数换成原问题的目标函数系数。作为第二阶段计算的初始表，再求解。 第四节 单纯形法的进一步讨论 单纯形法进一步讨论的几个问题 第四节 单纯形法的进一步讨论 第四节 单纯形法的进一步讨论 退化问题 第四节 单纯形法的进一步讨论 退化问题 第四节 单纯形法的进一步讨论 第四节 单纯形法的进一步讨论 第四节 单纯形法的进一步讨论 第四节 单纯形法的进一步讨论 单纯形法进一步讨论的几个问题 第四节 单纯形法的进一步讨论 第四节 单纯形法的进一步讨论 单纯形法进一步讨论的几个问题 第四节 单纯形法的进一步讨论 算法复杂性讨论——单纯形法是“好”的算法吗？ 第四节 单纯形法的进一步讨论 算法复杂性讨论——单纯形法是“好”的算法吗？ 第四节 单纯形法的进一步讨论 算法复杂性讨论——单纯形法不是“好”的算法! 第四节 单纯形法的进一步讨论 算法复杂性讨论——单纯形法真是不好吗？ 第一章 线性规划 这里其实是避免退化的方法之一，因为简单，应用较多。 同阶O(n的k次方)，这样的要求不算过分 上例系有3n个变元、2n个约束的LP问题。关于其算法不是“好的” 那么我们今天为什么还要学单纯形法，而不是别的？ 那么我们今天为什么还要学单纯形法，而不是别的？ 结合上面的例1.5，要提到这样几个概念：基变换，计算表（单纯形表）设计形式，判断准则（停止条件），能够判断所有四种界的情况。 讲清楚这里有四个要素：1、初始基可行解的获取（从哪里开始？）2、判断法则的有效性（什么时候不要再找了？）3、基变换（更换顶点）的方法（怎么换顶点？）4，计算表格的设计（复杂，简便的形式方便计算）。 单纯形法的异常情况处理—退化问题 大M法 人工变量的两种处理方法 两阶段法 算法复杂性讨论 检验数的几种表示形式 评价一个算法好坏的标准是：如果它的运算次数是以多项式函数（函数自变量是问题的维数）为上界，则称它是“好”的，这类问题称为P问题；若是指数函数