对偶线性规划 2－算法.ppt

第6节?对偶单纯形法 说明: 在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。 判别: 通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，根据性质(2)、(3)可知，已得到最优解。即原问题与对偶问题都是最优解。 对偶单纯形法的计算步骤如下： (1) 根据线性规划的原问题，列出初始单纯形表。 检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。 若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。 (2)确定换出变量 按照公式 min｛(B-1b)i｜(B-1b)i＜0＝(B-1b)l 对应的基变量xi为换出变量 (3) 确定换入变量 在单纯形表中检查xl所在行的各系数αlj(j=1,2,…，n)。若所有αlj≥0，则无可行解，停止 计算。 若存在αlj＜0 ( j=1, 2, …，n), 计算 例6 用对偶单纯形法求解 min ω=2x1+3x2+4x3 x1+2x2+x3≥3 2x1-x2+3x3≥4 x1，x2，x3≥0 解： 先将此问题化成下列形式，以便得到对偶 问题的初始可行基 max z=-2x1-3x2-4x3 -x1-2x2-x3+x4 =-3 -2x1+x2-3x3 +x5=-4 xj≥0，j=1,2,…,5 例6的初始单纯形表，见表2-6。 换入变量的确定： 按上述对偶单纯形法计算步骤(3)，即在单纯形表中检查xl所在行的各系数αlj(j=1,2,…，n)。若所有αlj≥0，则无可行解，停止 计算。 计算故x1为换入变量。换入、换出变量的所在列、行的交叉处“-2”为主元素。按单纯形法计算步骤进行迭代，得表2-7。 表 2-7 对偶单纯形法有以下优点： (1) 初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。 (2) 当变量多于约束条件，使用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。 (3) 在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法。 对偶单纯形法的局限性：对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。 * 设原问题 max z=CXs.t. AX=b, X≥0, 又设B是一个基。 如何理解？ 按θ规则所对应的列的非基变量xk为换入变量， 这样才能保持得到的对偶问题解仍为可行解。 (4)以αlk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。 重复步骤(1)～(4)。 注意:根据对偶性，上述过程也可以这样考虑: 保持对偶问题的解可行，然后把原问题从不可解迭代转换成可行解. 优点是原问题初始解不必可行 从表2-6看到，检验数行对应的对偶问题的解是可行解. 因b列数字为负，故需进行迭代运算。 换出变量的确定： 按上述对偶单纯形法计算步骤(2)，即按min｛(B-1b)i｜(B-1b)i＜0＝(B-1b)l对应的基变量xi为换出变量。计算 min(-3,-4)=-4 故x5为换出变量。 表 2-8 表2-8中，b列数字全为非负，检验数全为非正，故问题的最优解为 X*=(11/5，2/5，0，0，0)T 若对应两个约束条件的对偶变量分别为y1和y2， 则对偶问题的最优解为：Y*=(y1*,y2*)=(8/5,1/5) *