《2对偶单纯形法》由会员分享，可在线阅读，更多相关《2对偶单纯形法（10页珍藏版）》请在金锄头文库上搜索。
1、 对偶单纯形法对偶单纯形法 (Dual Simplex Algorithm)1. 对偶单纯形法思想对偶单纯形法思想原原问问题题对对偶偶问问题题1 对偶单纯形法对偶单纯形法 (Dual Simplex Algorithm)单纯形法思想：单纯形法思想：二二者者模模型型均均为为原原问问题题对偶单纯形法思想：对偶单纯形法思想： X*Y*. X*Y*. (B (0)- 1b 0(B(k)-1b0(B (0)- 1b 0(B(k)-1b022. 对偶单纯形法的计算步骤对偶单纯形法的计算步骤Step 0 (建立初始单纯形表建立初始单纯形表) 给定一个初始正则解给定一个初始正则解 X X(0)(0),对应的正
2、则基对应的正则基 B， 建立相应的初始单纯形表。转下步。建立相应的初始单纯形表。转下步。正则基：正则基： 满足满足 的原问题的基的原问题的基 B正则解正则解: 与正则基与正则基 B 对应的原问题的一个基本解对应的原问题的一个基本解XStep 1 （最优解的判别）计算（最优解的判别）计算 若若 则停止计算则停止计算, 当前的正则解便是最优解当前的正则解便是最优解; 否则转下步。否则转下步。 Step 2 （确定离基变量）令（确定离基变量）令 则则 为离基变量，为离基变量， 是主行。转下步。是主行。转下步。 对偶单纯形法对偶单纯形法3Step 3 (无可行解的判别无可行解的判别) 检查单纯形表的第
3、检查单纯形表的第 r 行系数：行系数： 若所有的若所有的 则原问题无可行解。否则转下步。则原问题无可行解。否则转下步。 Step 4 （确定进基变量）（确定进基变量） 令令则则 xk 为进基变量，转下步。为进基变量，转下步。 Step 5 （迭代）以（迭代）以 为为主元素进行消元变换，得到新的单纯形表，并主元素进行消元变换，得到新的单纯形表，并 迭代到下一个正则解。转迭代到下一个正则解。转 Step 1Step 1。 对偶单纯形法对偶单纯形法4例例 1用对偶单纯形法求解下列线性规划问题用对偶单纯形法求解下列线性规划问题:解解: : 将此问题化为如下等价的形式：将此问题化为如下等价的形式： 对偶
4、单纯形法对偶单纯形法5应用对偶单纯形法求解如下应用对偶单纯形法求解如下: 迭代迭代XB x1 x2 x3 x4 x5 bx4 -1 2 -1 1 0 -4x5 -2 -1 1 0 1 -6-w -1 -2 0 0 0 0XB x1 x2 x3 x4 x5 bx4 0 5/2 -3/2 1 -1/2 -1x1 1 1/2 -1/2 0 -1/2 3-w 0 -3/2 -1/2 0 -1/2 3 对偶单纯形法对偶单纯形法 迭代迭代R 1/2 2 - - - R - - 1/3 - 16因此，原问题的最优解与最优值分别是因此，原问题的最优解与最优值分别是 X*=(10/3, 0, 2/3)T, z*
5、=10/3. XB x1 x2 x3 x4 x5 b x3 0 - 5/3 1 - 2/3 1/3 2/3x1 1 -1/3 0 -1/3 -1/3 10/3-w 0 -7/3 0 -1/3 -1/3 10/3 R 对偶单纯形法对偶单纯形法注：注： 对偶对偶单纯单纯形法形法解之解之 7 对偶单纯形法对偶单纯形法3. 对偶单纯形法的优缺点对偶单纯形法的优缺点 1、运用对偶单纯形法时，初始解可以是非可行解，只要检验数全部非正数、运用对偶单纯形法时，初始解可以是非可行解，只要检验数全部非正数 时，就可以进行基变换。因此不需要引进人工变量，这样可以简化计算。时，就可以进行基变换。因此不需要引进人工变量
6、，这样可以简化计算。2、应用对偶问题与原问题的关系，对变量较少而约束较多的线性规划问题、应用对偶问题与原问题的关系，对变量较少而约束较多的线性规划问题 先变换成对偶问题，再用对偶单纯形法求解，可以减少计算工作量。先变换成对偶问题，再用对偶单纯形法求解，可以减少计算工作量。优点：优点： 3、灵敏度分析中有时需要用到对偶单纯形法，可使问题的处理简化。灵敏度分析中有时需要用到对偶单纯形法，可使问题的处理简化。8 对偶单纯形法对偶单纯形法缺点：缺点： 对于大多数线性规划问题而言很难找到一个初始正则基，即很难满足使对于大多数线性规划问题而言很难找到一个初始正则基，即很难满足使所有的检验数小于等于零（对偶可行性），因而此法很少单独使用。所有的检验数小于等于零（对偶可行性），因而此法很少单独使用。 94 4 一般线性规划问题的计算框图一般线性规划问题的计算框图线线性性规规划划问问题题存在存在单位单位可行可行基？基？ 建建立立数数学学模模型型最最优优解解或或无无解解 建立单纯形表建立单纯形表 NY化化为为标标准准型型用人用人工变工变量量法法求解求解用对偶单纯形法求解用对偶单纯形法求解存在存在单位单位正则正则基？基？ NY 对偶单纯形法对偶单纯形法10
