对偶单纯形法详解

16.对偶理论（三）对偶单纯形法⼉童节快乐呀这⼀部分我们考虑原问题是标准型的问题，并且介绍对偶单纯形法。

在上⼀节的强对偶定理的证明中，对标准型问题使⽤单纯形法，定义了对偶变量p为p T=c T B B−1。

然后由原问题最优性条件c T−c T B B−1A≥0T得到了等价表达的对偶可⾏性条件p T A≤c T。

那么我们之前介绍的单纯形法可以看作是在保证原问题可⾏的前提下去寻找对偶可⾏的解。

那么反过来，我们也可以从对偶可⾏的前提下去寻找原问题可⾏的解，这种算法称为对偶算法。

在接下来，将介绍对偶单纯形法。

并且说明这个算法事实上求解了对偶问题，更近⼀步，它是从对偶问题的⼀个基本可⾏解移动到另⼀个。

对偶单纯形法考虑⼀个标准型的线性规划问题，假设矩阵A是⾏满秩（为什么这个假设具有⼀般性，可参考线性规划中的⼏何（三））。

记B为基本矩阵，它包含了矩阵A的m个线性⽆关的列。

考虑下表(与之前介绍的单纯形法中的表⼀样)更详细的有不过，在这⾥不再要求B−1b是⾮负的，那就说明此时的解是⼀个原问题的基本解但不⼀定是可⾏解。

但是，我们要求¯c≥0成⽴，也相当于p T A≤c T成⽴（具体见上⼀节强对偶定理证明）。

这说明现在有了⼀个对偶问题的可⾏解，并且对偶问题的⽬标函数值为p T b=c T B B−1b=c T B x B，这恰好就是上表中的左上⾓元素的相反数。

如果不等式B−1b≥0也成⽴，那么这个解也将是⼀个原问题的可⾏解，并且⽬标函数值相同，这说明我们找到了原问题和对偶问题的最优解。

如果不等式B−1b≥0并不成⽴，那么我们将寻找下⼀个基矩阵。

找到满⾜x B(l)<0的l，考虑表中的第l⾏为pivot ⾏(x B(l)),v1,⋯,v n)，其中v i为B−1A i的第l个元素。

对于满⾜v i<0的所有i（如果存在的话），我们计算⽐率¯c i/|v i|，然后记j为这些⽐率中最⼩的那个的下标（为什么这么选呢，后⾯会说），也就是说v j<0且¯cj|v j|=min{i∣v i<0}¯ci|v i|.称v j为pivot 元素。

第4章05对偶单纯形法同学们，大家好，今天我们来学习对偶单纯形法。

我们先看一下对偶单纯形法的原理。

前面讲单纯形法的时候，我们知道，一个基B 如果是最优基，那么它必须满足下面的三个条件：（1）B 是可逆的；（2）B -1b ≥0；（3）C−C B B -1A ≤0。

（1）B 可逆；（2）10B b -≥；（3）10B C C B A --≤我们在用单纯形法进行求解的时候，是先找到一个满足了前两个条件的可行基，然后在迭代过程中再逐步满足第三个条件，从而找到最优解。

而对偶单纯形法是先找到一个基满足第一个和第三个条件，然后在迭代过程中逐步满足第二条，最后也同样找到最优解。

我们把满足第一和第三个条件的基称为正则基。

也就是说，单纯形法是先找一个可行基，然后逐步迭代找到最优基；而对偶单纯形法是先找一个正则基，然后再逐步迭代找到最优基。

关于对偶单纯形法，我们还需要注意下面三点：首先，在判定最优解时，单纯形法中根据的是检验数行，而对偶单纯形法中根据的是检验数列，也就是单纯形表中右端项的列。

第二，对偶单纯形法是求解线性规划模型的另一种方法，而不要简单的理解为对偶单纯形法就是求解对偶线性规划模型。

第三，使用对偶单纯形法时，需要先找到正则基，但实际上找一个正则基并不容易，所以，对偶单纯形法往往不单独使用，而是与第五章的灵敏度分析配合使用。

下面我们通过例4-7来说明对偶单纯形法是如何操作的。

例4-71212121212min 233436st.22,0z x x x x x x x x x x =+--≤-⎧⎪--≤-⎪⎨--≤-⎪⎪≥⎩第一步，先把它化成标准型，写出约束矩阵A ，右端项b ，以及价值向量C ，如下所示。

1234512312412512345max 200033436st.22,,,,0z x x x x x x x x x x x x x x x x x x x =--++++-=⎧⎪+-=⎪⎨+-=⎪⎪≥⎩311004*********-⎛⎫ ⎪=- ⎪ ⎪-⎝⎭A ，362⎛⎫⎪= ⎪ ⎪⎝⎭b ，()21000=--C 第二步，找初始基。

2013-2014（1）专业课程实践论文对偶单纯形法对偶单纯形法是解决线性规划问题的一种方法。

考虑线性规划：123231231,2,3min z=15245.. 62 5210x x x s t x x x x x x x x ++⎧⎪+≥⎪⎨++≥⎪⎪≥⎩引进剩余变量45,x x ，将其化为标准形并列成表格为0 6 1 -1 0 5 2 1 0 -1 2115 24 5 0 0 0为使中心部位具有单位子块，易想到把底线以上部分均变号，于是有0 -6 -1 1 0 - 5 -2 -1 0 1 -2-115 24 5 0 0 0可见此表以具备特点1、3、4。

当一个线性规划问题具有特点1-中心部位具有单位子块，特点3-底行相应于单位子块位置元素为0，特点4-底行其他元素非负等三个特点而同时又不具有特点2-右行列元素非负特点，即满足特点1、3、4时可使用此方法求出最优解。

此方法运用所允许的运算，始终不破坏第1、3、4三个特点，而逐步调出第2个特点的办法，以解出最优解。

其具体的步骤为：1. 从右列负元素中任选一个。

如上例选-2；2. 从所选行位于中心部位的负元素中确定一个，由于要保持第3、4的特点不被破坏，理应取相应底行的元素与该负元素之比中最大者。

如上例中由24524max ,,616⎧⎫=⎨⎬---⎩⎭所以选-6.3. 进行旋转运算。

如上例旋转以后得0 1 1/6 -1/6 0 - 5 0 -2/3 -1/3 1 1/3- 1/315 0 1 4 0 -8如此往复直至第2个特点也被满足，并得到最优解。

该matlab 程序可以解决在标准形下满足第1、3、4特点的线性规划问题。

建立函数function x=lindual(c,A,b)[n1,n2]=size(A);A=[-A,eye(n1)];c=[-c,zeros(1,n1)];x1=[zeros(1,n2),b'];lk=[n2+1:n1+n2]; b=-b;while(1)x=x1(1:n2);s1=[lk',b,A];c;x1;cc=[];ci=[];for i=1:n1if b(i)<0cc=[cc,b(i)];ci=[ci,i];endendnc=length(cc);if nc==0fprintf('达到最优解');breakendcliu=cc(1);cl=ci(1);for j=1:ncif abs(cc(j))>abs(cliu)cliu=cc(j);cl=j;endendcc1=[];ci1=[];for i=1:n1+n2if A(cl,i)<0cc1=[cc1,A(cl,i)];ci1=[ci1,i];endendnc1=length(cc1);if nc1==0fprintf('无可行解');breakendcliu=c(ci1(1))/cc1(1);cl1=ci1(1);for j=1:nc1if c(ci1(j))/cc1(j)<cliucliu=c(ci1(j))/cc1(j);cl1=ci1(j);endendb(cl)=b(cl)/A(cl,cl1);A(cl,:)=A(cl,:)/A(cl,cl1);for k=1:n1if k~=clb(k)=b(k)-b(cl)*A(k,cl1);A(k,:)=A(k,:)-A(cl,:).*A(k,cl1);endendc=c-c(cl1).*A(cl,:);x1(lk(cl))=0;lk(cl)=cl1;for kk=1:n1x1(lk(kk))=b(kk);endx=x1(1:n2);end四、算法实现例1. 用对偶单纯形法解下列线性规划123231231,2,3min z=15245.. 62 5+210x x x s t x x x x x x x x ++⎧⎪+≥⎪⎨+≥⎪⎪≥⎩解：利用matlab 数学软件的解答方法为：（1）输入题中已知条件：>>c=[15 24 5];A=[0 6 1;5 2 1];b=[2;1];（2）调用函数求出最优解：>>x=lindual(c,A,b)（3）求最优值：>>z=c*x ’运行结果如下：例2. 用对偶单纯形法解下列线性规划1212121,2min z=.. 24 +770x x s t x x x x x x +⎧⎪+≥⎪⎨≥⎪⎪≥⎩解：利用matlab 数学软件的解答方法为：（1）输入题中已知条件：>> c=[1 1];A=[2 1;1 7];b=[4;7];（2）调用函数求出最优解：>>x=lindual(c,A,b)（3）求最优值：>>z=c*x ’运行结果如下：例3. 用对偶单纯形法解下列线性规划12341234123412341,2,3,4min z=324.. 2450 372252615 0x x x x s t x x x x x x x x x x x x x x x x +++⎧⎪+++≥⎪⎪-+-≥⎨⎪+++≥⎪≥⎪⎩解：利用matlab 数学软件的解答方法为：（1）输入题中已知条件：>> c=[3 2 1 4];A=[2 4 5 1;3 -1 7 -2;5 2 1 6];b=[0;2;15];（2）调用函数求出最优解：>>x=lindual(c,A,b)（3）求最优值：>>z=c*x ’运行结果如下：例4. 用对偶单纯形法解下列线性规划1234123412341341,2,3,4min z=-235.. 246 23124 0x x x x s t x x x x x x x x x x x x x x x -+-⎧⎪++-≤⎪⎪+-+≤⎨⎪++≤⎪≥⎪⎩解：利用matlab 数学软件的解答方法为：（1）输入题中已知条件：>> c=[-2 -1 3 -5];A=[-1 -2 -4 1;-2 -3 1 -1;-1 0 -1 -1];b=[6;12;4];（2）调用函数求出最优解：>>x=lindual(c,A,b)（3）求最优值：>>z=c*x ’运行结果如下：。