对偶单纯形法

《对偶单纯形法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、对偶单纯形法的思路对偶单纯形法不是解对偶问题的，而是在单纯形表上进行对偶运算的方法。为了了解对偶单纯形法的实质，我们回顾一下单纯形法。单纯形法开始于初始基可行解。如果不满足最优性条件，则要转到能使目标函数值得到改善的邻近顶点上。在这个转换过程中，存在两个原则，一是保持原问题的解仍是可行的，另一个是要求目标函数值有改善。当目标函数值无法改善时（因退化出现循环的情况除外），所有的检验数都≤0（求极大时≤0，求极小时，检验数≥0）。“检验数≤0”意味着在获得原问题最优解的同时，也获得了对偶问题的一个可行解。因为原问题与对偶问题

2、的解都可行，并且目标函数值相同，根据对偶理论，这个对偶可行解就是对偶问题的最优解。单纯形法迭代过程的实质是：在保持原问题可行性的前提下，驱使对偶问题从不可行转变为可行的发展历程。把上述思想移植到对偶问题上。对偶单纯形法迭代过程的实质是：保持对偶问题的可行性（只要检验数≤0即可），通过改变对偶问题的可行基，使原问题由不可行变为可行。根据对偶理论，这两个可行解就是原始和对偶问题的最优解。二、对偶单纯形法的计算步骤使用对偶单纯形法必须满足两个条件：（1）单纯形表中的所有检验数必须符合最优性要求（即对偶可行）；（2）右端常数项列向量

3、必须有负分量（如果原问题可行，则直接用单纯形法）。对偶单纯形法计算步骤：（1）把线性规划问题化为标准形式，找出对偶问题的初始可行基，列出单纯形表。表的格式与第一章的单纯形表完全相同。（2）确定换出基的变量。这一点与单纯形法正好相反，那里是先确定换入变量。因为常数项有负分量，所以令br=min{bi},第r行对应的基变量xr作为换出变量。（3）确定换入基的变量。这里要注意：单纯形法确定换出变量时用的是换入变量列向量与常数项列的最小比值；对偶单纯形法确定换入变量时则用检验数行与换出变量所在行的最小比值。1）如果所有的arj≥0，

4、则原问题没有可行解。停止计算。2）如果存在arj＜0，则计算最小比值。cjzjcszs求极大为标准形式时minarj0（2-22a）jaarjrszjcjzscs求极小为标准形式时minarj0（2-22b）jaarjrs第s列所在的变量xs作为换入变量。(4)选择a为主元素，把该列向量变为单位列向量。rs这里的旋转运算和单纯形法一样，主元素处变为1，其余变为0即可。（5）重复步骤（2）—（4），直至原问题变为可行解为止。例2.4.1用对偶单纯形法求解下列线性规

5、划问题。minz=15x1+24x2+5x36x2+x3≥2st.5x1+2x2+x3≥1x1,x2,x3≥0解：把线性规划问题化为标准形式。maxz′=－15x1－24x2－x3+0x4+0x56x2+x3－x4=2st.5x1+2x2+x3－x5=1x1,x2,x3,x4,x5≥0在标准形式里，目标函数系数满足使用对偶单纯形法的一个条件，但是，约束条件的右端常数项非负，且没有单位矩阵。为此，把约束方程两边都乘以-1，得maxz′=－15x1－24x2－x3+0x4+0x5－6x2－x3+x4=－2st.－5x1－2x2－

6、x3+x5=－1x1,x2,x3,x4,x5≥0以此表达式列出单纯形表并求解。表9cj－15－24－500CBXBbx1x2x3x4x50x4－20[－6]－1100x5－1－5－2－101(cj－zj)或j-15-24-600根据对偶单纯形法，首先选择换出变量：显然常数项列最负的元素是-2，所以第一行的基变量x4作为换出变量。换入变量的确定利用公式（2-22）。第一行与检验数行对应分量比值的最小值为：最小比值={—，-24/-6，-6/-1}=4-6是主元素，x是换入变量。2表10cj－15－24－500CBXBbx1x

7、2x3x4x5-24x21/3011/6-1/600x5-1/3－50[-2/3]-1/31(cj－zj)或j-150-1-40选择换出变量。显然负元素是-1/3，所以第二行的基变量x5作为换出变量。换入变量的确定利用公式（2-22）。第二行与检验数行对应分量比值的最小值为：最小比值={-15/-5，-1/（-2/3），-4/（-1/3）}=3/2-2/3是主元素，x是换入变量。3表11cj－15－24－500CBXBbx1x2x3x4x5-24x21/4-5/410-1/41/45x31/215/2011/2-3/2(c

8、j－zj)或j-15/200-7/2-3/2由于原始，对偶都已经可行，所以，表11对应的解是最优解。注意：具有本例题形式的线性规划问题在求最优解时，可以不使用人工变量，对偶单纯形法能使求解过程更简便。返回