对偶单纯形法(对偶单纯形法例题)

对偶单纯形法是什么?

对偶单纯形法是指从对偶可行性逐步搜索出原始问题最优解的方法。

由线性规划问题的对偶理论，原始问题的检验数对应于对偶问题的一组基本可行解或最优解；原始问题的一组基本可行解或最优解对应于对偶问题的检验数；原始问题约束方程的系数矩阵的转置是对偶问题约束条件方程的系数矩阵。所以，在求解常数项小于零的线性规划问题时，可以把原始问题的常数项视为对偶问题的检验数，原始问题的检验数视为对偶问题的常数项。

优缺点：

对偶单纯形法的优点： 不需要人工变量；当变量多于约束时，用对偶单纯形法可减少迭代次数；在灵敏度分析中，有时需要用对偶单纯形法处理简化。

对偶单纯形法缺点： 在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。 因此，对偶单纯形法一般不单独使用。

对偶单纯形法怎么回事啊？

对偶单纯形法 　1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y＝cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。

对偶单纯形法的计算步骤

单纯形法的一般解题步骤可归纳如下：

①把线性规划问题的约束方程组表达成典范性方程组，找出基本可行解作为初始基本可行解。

②若基本可行解不存在，即约束条件有矛盾，则问题无解。

③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。

④按步骤3进行迭代直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。

⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

基本信息：

单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。

在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题（Dual Problem）为max{yb|yA≤c}。

当原始问题的一个基解满足最优性条件时，其检验数cBB-1A-c≤0。即知y=cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。

对偶单纯形法前提条件

始终保持对偶问题的解的可行性，并不断改善原问题解的可行性，直至满足原问题。

所谓满足对偶可行性，即指其检验数满足最优性条件。只要保持检验数满足最优性条件前提下，一旦基解成为可行解时，对偶问题和原问题均可行，由强对偶性证明，二者均有最优解。

对偶单纯形法的优点：

1、不需要人工变量；

2、当变量多于约束时，用对偶单纯形法可减少迭代次数；

3、在灵敏度分析中，有时需要用对偶单纯形法处理简化。

扩展资料

为了用选代法求出线性规划的最优解，需要解决以下三个问题；

1、最优解判别准则，即迭代终止的判别标准；

2、换基运算，即从一个基可行解迭代出另一个基可行解的方法；

3、进基列的选择，即选择合适的列以进行换基运算，可以使目标函数值有较大下降。

参考资料来源：百度百科——单纯形法

参考资料来源：百度百科——对偶单纯形法

对偶单纯形法和单纯形法的区别

单纯形法是求解线性规划问题的主要方法，而对偶单纯形方法是将单纯形方法应用于对偶问题的计算，对偶单纯性方法则提高了对求解线性规划问题的效率。
初始基解可以是非可行解，当检验数都为负值时，就可以进行基的变换，不需加入人工变量，从而简化计算。
对于变量多于约束条件的线性规划问题，用对偶单纯形法可以减少计算量，在灵敏度分析及求解整数规划的割平面法中，有时适宜用对偶规划单纯形法。

对偶单纯形法检验数大于0怎么办

1、对偶单纯形法检验数大于0就找到检验数大于0的，且最大的。
2、单纯形法在整个迭代过程中，始终保持原问题的可行性，即常数列大于等于0。
3、对偶单纯形法则是在整个迭代过程中，始终保持对偶问题的可行性，即全部检验数大于等于0。