对偶单纯形法

对偶单纯形法第一页，共三十一页，2022年，8月28日本节内容安排对偶单纯形法的求解思路对偶单纯形法的求解步骤第二页，共三十一页，2022年，8月28日

对偶单纯形法是根据对偶原理和单纯形法的原理而设计出来求解原LP的一种方法。采用的技术是在原问题的单纯形表格上进行对偶处理。注意:对偶单纯形法不是求解对偶问题的单纯形法。一对偶单纯形法的求解思路（一）什么是对偶单纯形法第三页，共三十一页，2022年，8月28日1单纯形法中原问题(max)的最优解满足的条件:

（1）是基本解（2）可行解（XB=B-1b≥0);

（3)检验数C－CBB-1A0，-CBB-1≤0

即YAC，Y0即对偶解可行

（二）普通单纯形法第四页，共三十一页，2022年，8月28日2普通单纯形法的求解思路:

从满足（1），（2）的一个初始基本可行解出发

(此时原LP问题中，b列保持≥0，对偶的解一般为非可行基解），通过逐步迭代，增大原目标函数值，每一步迭代，都得到一个基本可行解，并且逐步迭代实现检验数行≤0(对偶解可行)。0迭代到（3）得到满足，即所有检验数≤0，此时，原问题的基可行解达到最优时，对偶的基解由不可行达到可行，得到的这个基可行解也是对偶问题的最优解。第五页，共三十一页，2022年，8月28日3普通单纯型法的求解过程：对原问题的一个基可行解，判别是否所有检验数非正cj-zj0(j=1,…,n)；若是，又基变量中无非零人工变量，即找到问题最优解，基变量中含有非零人工变量，则无最优解；若否，再迭代，找出相邻的目标函数值更大的基可行解，并继续判别，只要最优解存在，就一直迭代下去，直到找出最优解为止.第六页，共三十一页，2022年，8月28日

1对偶单纯形法求解思路：换个角度考虑LP求解过程从满足（1）（3）的一个非可行基解（检验数行保持≤0）出发，（此时对偶问题的解一般为可行解），通过逐步迭代直至（2）得到满足，即直到实现到b列所有的值≥0，原问题的解在迭代过程中从非可行解变成可行解，最终达到最优解，此时，对偶问题也达到最优解。单纯形法中原问题的最优解满足的条件:（1）是基本解；（2）可行解（XB=B-1b≥0);（3)检验数C－CBB-1A0，-CBB-1≤0

即YAC，Y0即对偶解可行（三）对偶单纯形法第七页，共三十一页，2022年，8月28日普通单纯形法对偶单纯形法前提是原问题可行

优化条件两种方法都从原问题的基解出发前提是对偶可行

优化条件2两种方法的联系：YAC，Y0第八页，共三十一页，2022年，8月28日原问题基可行解最优解判断对偶问题的可行解对偶问题最优解判断对偶单纯形法基本思路普通单纯形法基本思路第九页，共三十一页，2022年，8月28日3对偶单纯形法的使用条件：①原问题的初始基解的检验数全部≤0；②b列至少一个元素<0；

4实施对偶单纯形法的基本原则：

在保持对偶可行的前提下进行基变换——

每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量(作为换入变量),

使原始问题的非可行解向可行解靠近。第十页，共三十一页，2022年，8月28日

第一步：构造初始单位阵，确定原问题（max)的初始基B，使所有检验数

Cj-Zj=σj=Cj-CBB-1Pj≤0，即Y=CBB-1

（b列的值）是对偶可行解，建立初始单纯形表。第二步：可行性检验。检验b列和σj行（即检查基变量的取值）若bi≥0

（XB=B-1b≥0）,σj≤0,

则原问题得到最优解，计算停;

若bi<0,σj≤0,

则用对偶单纯形法进行换基迭代.

二对偶单纯形法的步骤：第十一页，共三十一页，2022年，8月28日

第三步

先确定换出变量解答列（b列）中的负元素对应的基变量出基，相应的行为主元行。一般选最小的负元素出基，即若min{(B-1b)i|(B-1b)I<0}=(B–1b)l

则选取xl为换出变量.

检验第l

行中非基变量xj的系数αlj,

若所有的αlj≥0，则LP问题无可行解，（下面进行说明），此时计算结束。否则转下步第十二页，共三十一页，2022年，8月28日当bl<0，而对所有j=1,…,n，有alj0，则原问题无可行解。证明：xl+al,m+1xm+1+…+al,nxn=bl

因alj0(j=m+1,…,n)，又bl<0，故有xl<0，即不可能存在xj0(j=1,…,n)的解，故原问题无可行解，此时对偶问题的目标函数值无界。第十三页，共三十一页，2022年，8月28日若有：Min{cj–zj/αlj|αlj<0,xj为非基变量}=ck–zk/αlk则确定xk为换入变量，相应的列为主元列，标出主元素αlk

,

应用矩阵的初等行变换得到新的单纯形表。第四步：若对于bl<0,且有alj<0,

则确定换入变量应用最小比值原则目的：是在保持下一个对偶问题的基解可行的前提下，减少原始问题的不可行性。下面进行说明根据最小比值原则：第十四页，共三十一页，2022年，8月28日alk为主元素xk为进基变量［］设下一个表中的检验数为(cj-zj)，则第十五页，共三十一页，2022年，8月28日(1)对alj0，因cj－zj0，故，又因主元素alk<0，故有，所以(cj－zj)

0；(2)对alj<0，因，故有(cj－zj)

0；所以，(cj－zj)0(j=1，…，n)则有：第十六页，共三十一页，2022年，8月28日

第五步：用换入变量替换换出变量，得到一个新的基，对新的基再检查是否所有

如果是，得原问题的最优解；如果否，回到第一步再重复计算，直到检验数行非正，基列非负，得到最终表.第十七页，共三十一页，2022年，8月28日例6

应用对偶单纯型法求解下面的线性规划问题第十八页，共三十一页，2022年，8月28日CBXBbx1x2x3x4x5cj-2-3-400-1-2-110-21-301x4x500-2-3-400cj-zj-3-4min{σj/αlj|αlj<0}x5换出变量x1换入变量0-5/21/21-1/21-1/23/20-1/2x4x10-20-4-10-1-12bx5x4x3x2x1XBCBcj00-4-3-2cj-zjmin{σj/αlj|αlj<0}x2换入变量8/52x4换出变量第十九页，共三十一页，2022年，8月28日bx5x4x3x2x1XBCBcj00-4-3-2-2/5-1/57/5011/5-2/5-1/510x1x2-2-3-1/5-8/5-3/500cj-zj11/52/5bi≥0,σj≤0得到最优解为：X*=(11/5,2/5,0,0,0）T对偶问题最优解为：第二十页，共三十一页，2022年，8月28日例:

用对偶单纯形法求解下面线性规划

解:

构造对偶单纯形表进行迭代，第二十一页，共三十一页，2022年，8月28日从最后的表可以看到，B-1b列元素中有-2<0，并且，-2所在行各元素皆非负，因此，原问题没有可行解。第二十二页，共三十一页，2022年，8月28日原问题可以从非可行解开始（即初始解可以是非可行解），在构造初始单位阵时,不需要加人工变量，简化计算．

对偶单纯形法的特点：灵敏度分析和整数规划常借助于对偶单纯形法分析.使问题处理简单.变量多，约束条件少的问题,在迭代过程中计算工作量小,

因此,可以把变量少，约束条件多的LP问题转化成变量多，约束条件少的对偶问题,再用对偶单纯形法求解.第二十三页，共三十一页，2022年，8月28日

对偶单纯形法的局限性:很难找到初始可行基,很少单独使用.初始单纯形表的检验数行很难满足小于或等于零的要求，即满足检验数行对应的对偶问题的解是可行解．第二十四页，共三十一页，2022年，8月28日对于原问题为最小化时,选取换出变量的原则不变,选取换入变量时作相应改变:

σj≥0

min{σj/αlj|αlj>0,xj为非基变量}=σk/αlk注意：若xl为换出变量，所有αlj≤0，则原问题无可行解。第二十五页，共三十一页，2022年，8月28日初始可行基例:

用对偶单纯形法求解线性规划问题：对偶问题的初始可行基第二十六页，共三十一页，2022年，8月28日

换出换出min{σj/αlj|αlj<0}45y2换入变量第二十七页，共三十一页，2022年，8月28日第二十八页，共三十一页，2022年，8月28日最优解第二十九页，共三十一页，2022年，8月28日对偶单纯形法与原始单纯形法内在的对应关系原始单纯形法对偶单纯形法前提条件所有bi≥0所有bi≥0?最优性检验所有所有换入、出基变量的确定先确定换入基变量