哈工大运筹学大作业-对偶 单纯形法对比
标准化文件发布号：（9312-EUATWW-MWUB-WUNN-INNUL-DQQTY-
运筹学课程
运筹学对偶单纯形法与单纯形法 对比分析大作业
哈尔滨工业大学工业工程系
学 生 姓 名:
学
号：
指 导 教 师：
成
绩：
评
语：
运筹学对偶单纯形法与单纯形法对比分析
摘要：这篇论文主要介绍了对偶单纯形法的实质、原理、流程和适 用条件等。将对偶单纯形法与单纯形法的基本思想进行对比分析，从而 说明对偶单纯形法的优点和适用范围。
Min z=5x1+2x2+4x3
.
1.化为标准型
Max z’=-5x1-2x2-4x3+0x4+0x5
.
2.列出原始单纯形表
cj→
-5
-2
-4
0
0
CB 基 b
x1
x2
x3
x4
x5
0 x4 -4
-3
-1
-2
1
0
0 x5 -10
-6
[-3]
-5
0
1
cj-zj-5来自-2-40
0
3.找出最小的 bi，即 b5=-10.选择 x5 作为换出变量。
是 bi 都≥0
否 确定换出和换入的基变量： 换出最小的“右端项”bi 所对应的基变 量； 按公式θ=min｛σj/a’ij ，a’ij ≤0｝=σ s/a’ij 计算最小比值θ，所对应的基变量为 换入
计算检验数，列 出新的单纯形表
已找到最优解
结束
五、对偶单纯形法例题 下面用一个例子来说明对偶单纯形法的解题过程。
关键词：对偶单纯形法；对偶理论；单纯形法；基本思想
在线性规划早期发展阶段的众多重要发现中，对偶的概念及其分支 是其中最重要的内容之一。这个发现指出，对于任何一个线性规划问题 都具有对应的称为对偶问题的线性规划问题。对偶问题与原问题的关系 在众多领域都非常有用。
（一）教学目标： 通过对偶单纯形法的学习，加深对对偶问题的理解。掌握对偶单纯 形法的解题过程，理解对偶理论的其原理，了解对偶单纯形法的作用和 应用范围
（二）教学内容： 1）对偶单纯形法的思想来源 2）对偶单纯形法原理 3）对偶理论的实质 4）单纯形法和对偶单纯形法的比较
（三）教学进程： 一、对偶单纯形法的思想来源
所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方 法是由美国数学家 C.莱姆基于 1954 年提出的，它并不是求解对偶问题解 的方法，而是利用对偶理论求解原问题的解的方法。
二、对偶问题的实质
下面是原问题的标准形式以及其对应的对偶问题：
原问题
对偶问题
从而可以发现如下规律：
1.原问题目标函数系数是对偶问题约束方程的右端项。
2.原问题约束方程的右端项是对偶问题目标函数的系数。
3.原问题一个变量在所有约束方程中的系数是对偶问题一个约束方程
中的所有系数。
三、对偶单纯形法原理
对偶单纯形法是通过寻找原问题的对偶问题的可行解来求解原问题
四、对偶单纯形算法流程 在上述的理论基础上，可知用单纯形法求解线性规划问题时，在得 到原问题的一个基可行解问题同时，在检验数行得到对偶问题的一个基 解。单纯形法的基本思想是保持原问题为可行解的基础上，通过迭代增 大目标函数，当其对偶问题也为可行解时，就达到了目标函数的最优 值。 而对偶单纯形法的基本思想则是保持对偶问题为可行解的前提下 （即单纯性表最后一行检验数都小于零），通过迭代减小目标函数，当 原问题也是可行解时，就得到了目标函数的最优解。 故我们可以得到对偶单纯形法求解过程如下： 1.将原问题化为标准型，找到一个检验数都小于等于零的对偶问题的 初始可行基。 2.确定换出基的变量 对于小于零的 bi，找到最小的一个 br，其对应的 xr 为换出基的变量 3.确定换入基的变量 （1）为了使迭代后表中的第 r 行基变量为正值，因而只有对应 aij 小 于零的非基变量才可以作为换入基的变量； （2）为了使迭代后表中对偶问题仍为可行解，令
由于 CX CB X B CN X N CB B1b ，而 Yb CB B1b ，从而 有 CX Yb 。根据最 优性，命题得证。
4.线性规划的问题原问题及对偶问题之间存在一对互补的基解，其中 原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问 题的变量；这些相互对应的变量如果在一个问题中是基变量，则在另一 问题中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目 标函数有 z=w。
的最优解的方法，它的应用包括影子价格和灵敏度分析等。为了理解对
偶单纯形法为什么能够解出原方程的最优解，我们需要对对偶理论的几
个基本原理有所了解。
1.弱对偶性
如果
是原问题的可行解，
是其对偶问题的
可行解，则恒有
证明：由于对偶方程中原问题的约束条件是各行的 aijxj 之和小于等
于 yi 的系数 bi，而对偶问题的约束条件是各行的 aijyi 之和小于等于 xj 的
故选择 a22 为主元素，x2 为换入变量，得到新的单纯形表：
cj→ CB 基 b
-5
-2
-4
0
0
系数 cj，故将
和
分别和
比较，可得上述结
论。
2.最优性
如果
是原问题的可行解，
是其对偶问题的
可行解，且有
则 优解。
证明：由
是原问题的最优解，
可得
是其对偶问题的最
故可知
是原问题的最优解，
是其对偶问题
的最优解。
3.强对偶性 如果原问题有最优解，那么其对偶问题也有最优解，且有
maxz=minw. 证明：设 B 为原问题式(1)的最优基，那么当基为 B 时的检验数为
称 ars 为主元素，xs 为换入基的变量。 4.用换入变量替换换出变量，得到一个新的基。再次检查是否所有的 bi 大于等于零。如果是，则找到了最优解，如果否，则再次进行变换。
对偶单纯形法的算法流程图 开始
化原问题为标准 型
找出一个对偶问题的初始可行基 B0，计算非基变量检验数（全部检 验数σj ≤0）并列出初始单纯形表
C CB B1A ，其中 CB 为由基变量的 价值系数组成的价值向量。 既然 B 为原问题式 (1 )的最优基，那么有 C CBB1A 0 。
令 Y CB B1 ，那么 有 C YA 0 YA C ，从而 Y CB B1 是对偶问题 式 (2 ) 的可行解。
这样一来 ， Y CB B1 是对偶问 题的可行 解， X B B1b 是原问 题的最优 基可行解。