2021年运筹学大作业单纯性法与对偶单纯性法的比较.docVIP

2021年运筹学大作业单纯性法与对偶单纯性法的比较 2021年运筹学大作业单纯性法与对偶单纯性法的比较 PAGE / NUMPAGES 2021年运筹学大作业单纯性法与对偶单纯性法的比较 对偶单纯形法与单纯形法对比分析 1．教学目标: 经过对偶单纯形法学习, 加深对对偶问题了解 教学内容: 对偶单纯形法思想起源 对偶单纯形法原理 教学进程: 讲述对偶单纯形法解法起源: 所谓对偶单纯形法, 就是将单纯形法应用于对偶问题计算, 该方法是由美国数学家C.莱姆基于1954年提出, 它并不是求解对偶问题解方法, 而是利用对偶理论求解原问题解方法。 为何要引入对偶单纯形法: 单纯形法是解线性计划关键方法, 对偶单纯形法则提升了求解线性计划问题效率, 因为它含有以下优点: （1）初始基解能够是非可行解, 当检验数都为负值时, 就能够进行基变换, 不需加入人工变量, 从而简化计算; （2）对于变量多于约束条件线性计划问题,用对偶单纯形法能够降低计算量,在灵敏度分析及求解整数计划割平面法中,有时适宜用对偶计划单纯形法。 由对偶问题基础性质能够知道, 线性计划原问题及其对偶问题之间存在一组互补基解, 其中原问题松弛变量对应对偶问题变量, 对偶问题剩下变量对应原问题变量; 这些相互对应变量假如在一个问题解中是基变量, 则在另一问题解中是非基变量; 将这对互补基解分别代入原问题和对偶问题目标函数有z=w。据此可知, 用单纯形法求解线性计划问题时, 在得到原问题一个基可行解同时, 在检验数行得到对偶问题一个基解, 而且将两个解分别代入各自目标函数时其值相等。 我们知道, 单纯形法计算基础思绪是保持原问题为可行解（这时通常其对偶问题为非可行解）基础上, 经过迭代, 增大目标函数, 当其对偶问题解也为可行解时, 就达成了目标函数最优值。那么对偶单纯形法基础思想能够了解为保持对偶问题为可行解（这时通常原问题为非可行解）基础上, 经过迭代, 减小目标函数, 当原问题也达成可行解时, 即达成了目标函数最优值。其实对偶单纯形法本质上就是单纯形法, 只不过在利用时需要将单纯形表旋转一下而已。 一.单纯形法和对偶单纯性法 单纯形法是求解线性计划关键方法, 单纯形表则是单纯形法和对偶单纯形法运算工具。设线性计划问题为 Max = 1 \* GB2 ⑴ 将其化为标准形式, 得 Max Z= s.t. = 2 \* GB2 ⑵ 其中, , , , 则其对应线性约束转换为, , 代入目标函数得, 对应一个基解为, , 。显然, 若, 且, , 则基解为该线性计划最优解, 此时检验数均大于零, 见表1。 经过上面分析, 我们知道单纯形表检验数实际上是目标函数中基变量、 非基变量价值系数,又由对偶理论知道它们是对应对偶问题一个( 加一个负号) 基解。那么表中b列数字仅仅表示是取值吗? 我们能够猜想 很可能是对偶问题检验数。这里首先给出问题(1) 对偶问题通常形式 Min s.t. = 3 \* GB2 ⑶ 将问题（3）化为标准形式, 得 Min s.t. = 4 \* GB2 ⑷ 由, , 为松弛变量, 对应分解为、 , 其中, 。得: = 5 \* GB2 ⑸ = 6 \* GB2 ⑹ 由式 = 5 \* GB2 ⑸得到 = 7 \* GB2 ⑺ 经过令, 由式(5)得对偶问题基解,代入式(6)得,将式(7)对偶问题目标函数得。显然若目标函数达成最小,非基变量价值系数要求大于等于零,单纯形表b列, 即实际上是对偶问题非基变量检验数。 二．对偶单纯形法算法步骤 (1)确定换出基变量 设原问题为（1）, 对偶问题为（3）。由, 不等式则可分解为 (8) 深入添加松弛变量有等式（5）、 （6）, 对等式（5）两端同时左乘有