第2章-线性规划与单纯形法-第6节.ppt

《第2章-线性规划与单纯形法-第6节.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6节对偶单纯形法单纯形法是在保持原问题基可行解(b列非负)的前提下，使对偶问题由非可行的基解转变为基可行解(检验数行转变为非正)，一旦完成转化，两个问题同时达到最优解从另一角度考虑，在保持对偶问题基可行解(检验数行非正)前提下，使原问题由非可行的基解向基可行解转化(b列转变为非负)，则可以同时得到两个问题的最优解，这就是对偶单纯形法计算步骤：(1)列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。(

2、2)确定换出变量按min{(B-1b)i｜(B-1b)i＜0}＝(B-1b)l}对应的基变量xl为换出变量(3)确定换入变量在单纯形表中检查xl所在行的各系数alj(j=1,2,…，n)。若所有alj≥0，则无可行解，停止计算。若存在alj＜0(j=1,2,…，n),计算按θ规则所对应的列的非基变量xk为换入变量，这样才能保持得到的对偶问题解仍为可行解。(4)以alk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复步骤(1)～(4)。例6用对偶单纯形法求解minw=2x1+3x2+4x3x1+2

3、x2+x3≥32x1−x2+3x3≥4x1，x2，x3≥0解：先将此问题化成下列形式，以便得到对偶问题的初始可行基maxz=−2x1−3x2−4x3−x1−2x2−x3+x4=−3−2x1+x2−3x3+x5=−4xj≥0，j=1,2,…,5例6的初始单纯形表，见表2-6。从表2-6看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。换出变量的确定：换入变量的确定：按上述对偶单纯形法计算步骤(3)，即在单纯形表中检查xl所在行的各系数αlj(j=1,2,…，n)。若所有αlj≥0，则无可

4、行解，停止计算。按上述对偶单纯形法计算步骤(2)，即按min｛(B-1b)i｜(B-1b)i＜0＝(B-1b)l对应的基变量xi为换出变量。计算min(−3,−4)=−4故x5为换出变量。若存在αlj＜0(j=1,2,…，n),计算故x1为换入变量。换入、换出变量的所在列、行的交叉处“−2”为主元素。按单纯形法计算步骤进行迭代，得表2-7。表2-8中，b列数字全为非负，检验数全为非正，故问题的最优解为X*=(11/5，2/5，0，0，0)T若对应两个约束条件的对偶变量分别为y1和y2，则对偶问题的最优解为Y*=

5、(y1*,y2*)=(8/5,1/5)例用对偶单纯形法求解(作业）对偶单纯形法的优点：(1)初始解可以是非可行解，不需要加入人工变量(2)当变量多于约束条件，用对偶单纯形法计算可以减少计算工作量(3)在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法对偶单纯形法的局限性：对偶问题的初始基解是可行解，有时很难做到