哈工大运筹学大作业对偶单纯形法对比.pdf
运筹学课程运筹学课程运筹学对偶单运筹学对偶单纯形法与单纯形纯形法与单纯形法法对比分析大作业对比分析大作业哈尔滨工业大学工业工程系哈尔滨工业大学工业工程系学学 生生 姓姓 名名:学学号号：指指 导导 教教 师师：成成绩：绩：评评语：语：运筹学对偶单纯形法与单纯形法对比分析运筹学对偶单纯形法与单纯形法对比分析摘摘 要要：这篇论文主要介绍了对偶单纯形法 的实质、原理、流程 和适用条件等。将对偶单纯形法与单纯形法的基本思想进行对比分析，从而说明对偶单纯形法的优点和适用范围。关关键键词词：对偶单纯形法；对偶理论；单纯形法；基本思想在线性规划早期发展阶段的众多重要发现中，对偶的概念及其分支是其中最重要的内容之一。这 个发现指出，对 于任何一个线性规划问题都具有对应的称为对偶问题的线性规划问题。对偶问题与原问题的关系在众多领域都非常有用。（一一）教教学学目目标标：通过对偶单纯形法的学习，加 深对对偶问题的理解。掌 握对偶单纯形法的解题过程，理解对偶理论的其原理，了解对偶单纯形法的作用和应用范围（二二）教教学学内内容容：1）对偶单纯形法的思想来源2）对偶单纯形法原理3）对偶理论的实质4）单纯形法和对偶单纯形法的比较（三三）教教学学进进程程：一一、对对偶偶单单纯纯形形法法的的思思想想来来源源所谓对偶单纯形法，就 是将单纯形法应用于对偶问题的计算，该 方法是由美国数学家 C.莱姆基于 1954 年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。二二、对对偶偶问问题题的的实实质质下面是原问题的标准形式以及其对应的对偶问题：原问题对偶问题从而可以发现如下规律：1.原问题目标函数系数是对偶问题约束方程的右端项。2.原问题约束方程的右端项是对偶问题目标函数的系数。3.原问题一个变量在所有约束方程中的系数是对偶问题一个约束方程中的所有系数。三三、对对偶偶单单纯纯形形法法原原理理对 偶 单 纯 形 法 是 通 过 寻 找 原 问 题 的 对 偶 问 题 的 可 行 解 来 求 解 原 问 题 的 最 优 解的方法，它 的应用包括影子价格和灵敏度分析等。为 了理解对偶单纯形法为什么能够解出原方程的最优解，我们需要对对偶理论的几个基本原理有所了解。1.弱对偶性如果是原问题的可行解，是其对偶问题的可行解，则恒有证明：由于对偶方程中原问题的约束条件是各行的 aijxj之和小于等于 yi的系数bi，而对偶问题的约束条件是各行的 aijyi之和小于等于 xj的系数 cj，故将和分别和比较，可得上述结论。2.最优性如果是原问题的可行解，是其对偶问题的可行解，且有则是原问题的最优解，是其对偶问题的最优解。证明：由可得故可知是原问题的最优解，是其对偶问题的最优解。3.强对偶性如果原问题有最优解，那么其对偶问题也有最优解，且有 maxz=minw.1证明：设 B 为原问题式(1)的最优基，那么当基为 B 时的检验数为C CBB A，其中CB为由基变量的价值系数组成的价值向量。1 0。既然 B 为原问题式(1)的最优基，那么有C CBBA11令Y CBB，那么有C YA 0 YA C，从而Y CBB是对偶问题式(2)的可行解。11这样一来，Y CBB是对偶问题的可行解，XB B b是原问题的最优基可行解。11CbYb CBB b，从 而有CX Yb。根 据最优性，命BXB CNXNBB，而由于CX C题得证。4.线性规划的问题原问题及对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对 偶问题的剩余变量对应原问题的变量；这 些相互对应的变量如果在一个问题中是基变量，则 在另一问题中是非基变量；将 这对互补的基解分别代入原问题和对偶问题的目标函数有 z=w。四四、对对偶偶单单纯纯形形算算法法流流程程在上述的理论基础上，可 知用单纯形法求解线性规划问题时，在 得到原问题的一个基可行解问题同时，在 检验数行得到对偶问题的一个基解。单 纯形法的基本思想是保持原问题为可行解的基础上，通 过迭代增大目标函数，当 其对偶问题也为可行解时，就达到了目标函数的最优值。而对偶单纯形法的基本思想则是保持对偶问题为可行解的前提下（即单纯性表最后一行检验数都小 于零），通过迭代减 小 目标函数，当原问题 也是可行解时，就得到了目标函数的最优解。故我们可以得到对偶单纯形法求解过程如下：1.将原问题化为标准型，找到一个检验数都小于等于零的对偶问题的初始可行基。2.确定换出基的变量对于小于零的 bi，找到最小的一个 br，其对应的 xr为换出基的变量3.确定换入基的变量（1）为了使迭代后表中的第 r 行基变量为正值，因而只有对应 aij小于零的非基变量才可以作为换入基的变量；（2）为了使迭代后表中对偶问题仍为可行解，令称 ars为主元素，xs为换入基的变量。4.用换入变量替换换出变量，得 到一个新的基。再 次检查是否所有的 bi大于等于零。如果是，则找到了最优解，如果否，则再次进行变换。对偶单纯形法的算法流程图开始化原问题为标准型找出一个对偶问题的初始可行基B0，计算非基变量检验数（全部检验数列出初始单纯形表bi都0？否确定换出和换入的基变量：换出最小的“右端项”bi所对应的基变量；按公计算检验数，列出新式=min已找到最优解j/aij?，aij?0=s/aij?计算最小比的单纯形表值，所对应的基变量为换入结束五五、对对偶偶单单 纯纯下面用一个例子来说明对偶单纯形法的解题过程。形形法法例例题题并j?0）是Min z=5x1+2x2+4x3s.t.1.化为标准型Max z=-5x1-2x2-4x3+0 x4+0 x5s.t.2.列出原始单纯形表cjC CB B-5x1-3-6-5-4-2x2-1-3-2-4x3-2-5-40 x41000 x5010基基b b0 x40 x5-10cj-zj3.找出最小的 bi，即 b5=-10.选择 x5 作为换出变量。故选择 a22 为主元素，x2 为换入变量，得到新的单纯形表：cjC CB B-5x1-12-1-5x11002/32-2/310/3-2x2010-2x2010-4x3-1/35/3-2/3-4x31/31-1/30 x41000 x4-12-10 x5-1/3-1/3-2/30 x51/3-1-1/3基基b b0 x4-2x2cj-zj再次换入换出：cjC CB B基基b b-5x1-2x2cj-zjX=（2/3,2,0）T4.所有的 bi 都大于零，说明找到了最优解。Max z =-10/3-4=-22/3Min z=22/3.但是，对 偶单纯形法并不是一种普遍算法，它 有一定的局限性，不 是任何线性规划问题都能用对偶单纯形法计算的。当 线性规划问题具备下面条件时，可 以用对偶单纯形法求解：问题标准化后，价值系数全非正；所有约束全是不等式。六六、对对偶偶单单纯纯形形法法的的应应用用1.从上面的例题可以看出，原问题是求最小值，并且目标函数各项系数都不小于零。所 以在转化成标准型后各项系数不大于零，从 而以松弛变量为基列出的单纯形表满足检验数都不大于零，是 其对偶问题的一个可行解。如 果原问题的标准形式中各项系数不都小于零，则 不容易找到对偶问题的一个初始可行解，就 不适合使用对偶单纯形法求解。所 以 对 偶 单 纯 形 法 适 用 于 不 易 找 到 原 方 程 的 可 行 解 而 容 易 找 到 其 对 偶 问 题 的可行解的线性规划问题。2.我们知道，约束方程的数量对单纯形法的计算过程要远远大于变量个数的影响。如 果 mn，那 么对偶问题有 n 个约束方程，而 原问题有 m 个约束方程，所 以对偶问题有更少的约束方程数量，那么通过对偶单纯形法的运用比起直接只用单纯形法将会显着的减少计算量。3.弱对偶性和强对偶性是对偶理论的关键原理。对偶问题可以用来对原问题的计划方案进行评价。我们可以用一个对偶问题的可行解和目前原问题的计划方案进行比较，如 果两个目标函数值相等或比较接近，则 可以说明原问题的计划方案已经是可以看做最优了。4.对偶理论在灵敏度分析和影子价格计算中有着重要的作用。七七、单单纯纯形形法法和和对对偶偶单单纯纯形形法法的的基基本本思思想想比比较较通过以上的分析可知，对 偶单纯形法其实相当于单纯形法的一种变形，只 不过在运用对偶单纯形法解线性规划时需要将单纯形表旋转一下。单纯形表中的 b 列实际 上 是 对 偶 问 题 的 非 基 变 量 的 检 验 数,而 原 单 纯 形 表 的 检 验 数 为 对 偶 问 题 的 基 解,这样可以理解为通过旋转 90运 用单纯形法求解线性规划。从求解思路上来说，单 纯形法是首先保证基解是原问题的基可行解（bi 不小于零），然后通过变量 的 换入换出 增大目标函 数值，直到其同时成 为对偶问题的可行解，根 据强对偶性原理，可 知这个解就是最优解。而 对偶单纯形法则是首先保证基解是对偶问题的可行 解（检验数都不大于 零），然后 逐步减小 对 偶标准化的目标函数值，使其成为原问题的可行解。两种方法殊途同归，其本质是一样的。
