运筹学课件第1章线性规划与单纯形法-第3节.ppt

第三版 运筹学 教材编写组编清华大学出版社 运筹学 第1章线性规划与单纯形法第3节单纯形法钱颂迪制作 第1章线性规划与单纯形法 第3节单纯形法3 1举例3 2初始基可行解的确定3 3最优性检验与解的判断3 4基变换3 5迭代 旋转运算 单纯形法求解线性规划的思路 一般线性规划问题具有线性方程组的变量数大于方程个数 这时有不定的解 但可以从线性方程组中找出一个个的单纯形 每一个单纯形可以求得一组解 然后再判断该解使目标函数值是增大还是变小 决定下一步选择的单纯形 这就是迭代 直到目标函数实现最大值或最小值为止 这样问题就得到了最优解 先举一例来说明 注 单纯形是指0维中的点 一维中的线段 二维中的三角形 三维中的四面体 n维空间中的有n 1个顶点的多面体 例如在三维空间中的四面体 其顶点分别为 0 0 0 1 0 0 0 1 0 0 0 1 具有单位截距的单纯形的方程是 xi 1 并且xi 0 i 1 2 m 3 1举例 例6试以例1来讨论如何用单纯形法求解 例1的标准型为 约束方程 1 12 式的系数矩阵 从 1 12 式中可以看到x3 x4 x5的系数列向量 P3 P4 P5是线性独立的 这些向量构成一个基对应于B的变量x3 x4 x5为基变量 从 1 12 式中可以得到 1 13 将 1 13 式代入目标函数 1 11 得到当令非基变量x1 x2 0 便得到z 0 这时得到一个基可行解X 0 X 0 0 0 8 16 12 T这个基可行解表示 工厂没有安排生产产品 资源都没有被利用 所以工厂的利润指标z 0 从分析目标函数的表达式 1 14 可以看到 非基变量x1 x2 即没有安排生产产品 的系数都是正数 因此将非基变量变换为基变量 目标函数的值就可能增大 从经济意义上讲 安排生产产品 或 就可以使工厂的利润指标增加 所以只要在目标函数 1 14 的表达式中还存在有正系数的非基变量 这表示目标函数值还有增加的可能 就需要将非基变量与基变量进行对换 如何确定换入 换出变量 一般选择正系数最大的那个非基变量x2为换入变量 将它换入到基变量中去 同时还要确定基变量中有一个要换出来成为非基变量 可按以下方法来确定换出变量 现分析 1 13 式 当将x2定为换入变量后 必须从x3 x4 x5中确定一个换出变量 并保证其余的都是非负 即x3 x4 x5 0 当x1 0 由 1 13 式得到 x2取何值时 才能满足非负要求 从 1 15 式中可以看出 只有选择x2 min 8 2 12 4 3时 才能使 1 15 式成立 因当x2 3时 基变量x5 0 这就决定用x2去替换x5 以上数学描述说明了每生产一件产品 需要用掉各种资源数为 2 0 4 由这些资源中的薄弱环节 就确定了产品 的产量 这里就是由原材料B的数量确定了产品 的产量x2 12 4 3件 为了求得以x3 x4 x2为基变量的一个基可行解和进一步分析问题 需将 1 13 中x2的位置与x5的位置对换 得到 用高斯消去法 将 1 16 式中x2的系数列向量变换为单位列向量 其运算步骤是 4 2 并将结果仍按原顺序排列有 再将 1 17 式代入目标函数 1 11 式得到 从目标函数的表达式 1 18 中可以看到 非基变量x1的系数是正的 说明目标函数值还可以增大 X 1 还不是最优解 于是再用上述方法 确定换入 换出变量 继续迭代 再得到另一个基可行解X 2 X 2 2 3 0 8 0 T再经过一次迭代 再得到一个基可行解X 3 X 3 4 2 0 0 4 T而这时得到目标函数的表达式是 z 14 1 5x3 0 125x4 1 19 再检查 1 19 式 可见到所有非基变量x3 x4的系数都是负数 这说明若要用剩余资源x3 x4 就必须支付附加费用 所以当x3 x4 0时 即不再利用这些资源时 目标函数达到最大值 所以X 3 是最优解 即当产品 生产4件 产品 生产2件 工厂才能得到最大利润 通过上例 可以了解利用单纯形法求解线性规划问题的思路 现将每步迭代得到的结果与图解法做一对比 其几何意义就很清楚了 原例1的线性规划问题是二维的 即两个变量x1 x2 当加入松弛变量x3 x4 x5后 变换为高维的 这时可以想象 满足所有约束条件的可行域是高维空间的凸多面体 凸集 这凸多面体上的顶点 就是基可行解 初始基可行解X 0 0 0 8 16 12 T就相当于图1 2中的原点 0 0 X 1 0 3 2 16 0 T相当于图1 2中的Q4点 0 3 X 2 2 3 0 8 0 T相当于图1 2中的Q3点 2 3 最优解X 3 4 2 0 0 4 T相当于图1 2中的Q2点 4 2 从初始基可行解X 0 开始迭代 依次得到X 1 X 2 X 3 这相当于图1 2中的目标函数平移时 从0点开始 首先碰到Q4 然后碰到Q3 最后达到Q2 下面讨论一般线性规划问题的求解 一般线性规划问题的求解3 2初始基可行解的确定 为了确定初始基可行解 要首先找出初始可行基 其方法如下 1 直接观察 2 加松弛变量 3 加非负的人工变量 1 直接观察 若线性规划问题 从Pj j 1 2 n 中一般能直接观察到存在一个初始可行基 2 加松弛变量 对所有约束条件是 形式的不等式 可以利用化为标准型的方法 在每个约束条件的左端加上一个松弛变量 经过整理 重新对xj及aij i 1 2 m j 1 2 n 进行编号 则可得下列方程组 x1 x2 xm为松弛变量 于是含有m m单位矩阵 以B作为可行基 将 1 22 式每个等式移项得 令xm 1 xm 2 xn 0 由 1 23 式可得xi bi i 1 2 m 得到一个初始基可行解 又因bi 0 在1 3节中已做过规定 所以得到一个初始基可行解X x1 x2 xm 0 0 Tn m个 b1 b2 bm 0 0 Tn m个 3 加非负的人工变量 对所有约束条件是 形式的不等式及等式约束情况 若不存在单位矩阵时 就采用人造基方法 即对不等式约束减去一个非负的剩余变量后 再加上一个非负的人工变量 对于等式约束再加上一个非负的人工变量 总能得到一个单位矩阵 关于这个方法将在本章第5节中进一步讨论 3 3最优性检验与解的判别 对线性规划问题的求解结果可能出现唯一最优解 无穷多最优解 无界解和无可行解四种情况 为此需要建立对解的判别准则 一般情况下 经过迭代后 1 23 式变成 将代入目标函数 1 20 式 整理后得 令 1 最优解的判别定理 若为对应于基B的一个基可行解 且对于一切j m 1 n 有 j 0 则X 0 为最优解 称 j为检验数 当所有非基变量的 j 0时 由 1 27 式可知已不存在任一可换入的非基变量 使目标函数继续增大 所以以 j 0 为最优解的判别准则 2 无穷多最优解判别定理 若为一个基可行解 对于一切j m 1 n 有 j 0 又存在某个非基变量的检验数 m k 0 则线性规划问题有无穷多最优解 证 只需将非基变量xm k换入基变量中 找到一个新基可行解X 1 因 m k 0 由 1 27 知z z0 故X 1 也是最优解 由2 2节的定理3可知X 0 X 1 连线上所有点都是最优解 3 无界解判别定理 若为一基可行解 有一个 m k 0 并且对i 1 2 m 有存在 那么该线性规划问题具有无界解 或称无最优解 证 构造一个新的解X 1 它的分量为 因 所以对任意的 0都是可行解 把x 1 代入目标函数内得z z0 m k因 m k 0 故当 则z 故该问题目标函数无界 以上讨论都是针对标准型 即求目标函数极大化时的情况 当求目标函数极小化时 一种情况如前所述 将其化为标准型 如果不化为标准型 只需在上述1 2点中把 j 0改为 j 0 第3点中将 m k 0改写为 m k 0即可 3 4基变换 若初始基可行解X 0 不是最优解及不能判别无界时 需要找一个新的基可行解 具体做法是从原可行解基中换一个列向量 当然要保证线性独立 得到一个新的可行基 这称为基变换 为了换基 先要确定换入变量 再确定换出变量 让它们相应的系数列向量进行对换 就得到一个新的基可行解 1 换入变量的确定 由 1 27 式看到 当某些 j 0时 xj增大 则目标函数值还可以增大 这时要将某个非基变量xj换到基变量中去 称为换入变量 若有两个以上的 j 0 那么选哪个非基变量作为换入变量呢 为了使目标函数值增加得快 从直观上一般选 j 0中的大者 即 则对应的xk为换入变量 但也可以任选或按最小足码选 2 换出变量的确定 设P1 P2 Pm是一组线性独立的向量组 它们对应的基可行解是X 0 将它代入约束方程组 1 21 得到 其他的向量Pm 1 Pm 2 Pm t Pn都可以用P1 P2 Pm线性表示 若确定非基变量Pm t为换入变量 必然可以找到一组不全为0的数 i 1 2 m 使得 在 1 29 式两边同乘一个正数 然后将它加到 1 28 式上 得到 新的基可行解 由此得到由X 0 转换到X 1 的各分量的转换公式 这里是原基可行解X 0 的各分量 是新基可行解X 1 的各分量 i m t是换入向量Pm t的对应原来一组基向量的坐标 现在的问题是 这个新解X 1 的m个非零分量对应的列向量是否性独立 事实上 因X 0 的第l个分量对应于X 1 的相应分量是零 即 成立 又因 将 1 32 式减 1 31 式得到 由于上式中至少有 l m t 0 所以上式表明P1 P2 Pm是线性相关 这与假设相矛盾 由此可见 X 1 的m个非零分量对应的列向量Pj j 1 2 m j l 与Pm t是线性独立的 即经过基变换得到的解是基可行解 实际上 从一个基可行解到另一个基可行解的变换 就是进行一次基变换 从几何意义上讲 就是从可行域的一个顶点转向另一个顶点 见1 2图解法 3 5迭代 旋转运算 上述讨论的基可行解的转换方法是用向量方程来描述 在实际计算时不太方便 因此采用系数矩阵法 现考虑以下形式的约束方程组 一般线性规划问题的约束方程组中加入松弛变量或人工变量后 很容易得到上述形式 设x1 x2 xm为基变量 对应的系数矩阵是m m单位阵I 它是可行基 令非基变量xm 1 xm 2 xn为零 即可得到一个基可行解 若它不是最优解 则要另找一个使目标函数值增大的基可行解 这时从非基变量中确定xk为换入变量 显然这时 为 在迭代过程中 可表示为 其中是经过迭代后对应于的元素值 按 规则确定xl为换出变量 xk xl的系数列向量分别为 为了使xk与xl进行对换 须把Pk变为单位向量 这可以通过 1 33 式系数矩阵的增广矩阵进行初等变换来实现 变换的步骤是 1 将增广矩阵 1 34 式中的第l行除以alk 得到 2 将 1 34 式中xk列的各元素 除alk变换为1以外 其他都应变换为零 其他行的变换是将 1 35 式乘以aik i l 后 从 1 34 式的第i行减去 得到新的第i行 由此可得到变换后系数矩阵各元素的变换关系式 是变换后的新元素 3 经过初等变换后的新增广矩阵是 4 由 1 36 式中可以看到x1 x2 xk xm的系数列向量构成m m单位矩阵 它是可行基 当非基变量xm 1 xl xn为零时 就得到一个基可行解X 1 在上述系数矩阵的变换中 元素alk称为主元素 它所在列称为主元列 它所在行称为主元行 元素alk位置变换后为1 例7试用上述方法计算例6的两个基变换 解例6的约束方程组的系数矩阵写成增广矩阵 当以x3 x4 x5为基变量 x1 x2为非基变量 令x1 x2 0 可得到一个基可行解X 0 0 0 8 16 12 T 现用x2去替换x5 于是将x3 x4 x2的系数矩阵变换为单位矩阵 经变换后为 令非基变量x1 x5 0 得到新的基可行解X 1 0 3 2 16 0 T 第3节结束