对偶单纯形法和单纯形法都是线性规划中常用的求解方法，但在一些方面存在一些异同。

首先，它们的相同之处在于两种方法都是基于线性规划模型的求解算法。它们都使用了面向限制条件的算法，以确定使目标函数最优化的变量值。在求解过程中，两种方法都通过迭代来逼近最优解。

然而，两种方法的不同之处在于它们的求解策略和重点。单纯形法通过迭代调整基变量和非基变量的值，以逐步改进解的质量，直到找到最优解。它主要关注的是基变量的选择和基变量和非基变量之间的相互转换。

相比之下，对偶单纯形法注重的是对偶的约束条件和松弛变量之间的关系。它通过对原始问题和对偶问题之间的对偶关系进行迭代求解，以获得最优解。

另一个不同之处在于两个方法的适用性。单纯形法适用于标准形式的线性规划问题，即目标函数为最大化，且约束条件为等式形式。而对偶单纯形法主要适用于将原始问题转换为对偶形式的情况。

综上所述，对偶单纯形法和单纯形法在求解线性规划问题上有很多相似之处，但又有一些显著的差异。选择使用哪种方法取决于具体的问题形式和求解的要求。

对偶单纯形法max变min

『运筹OR帷幄』原创

作者：翁欣 （中科院管理科学与工程研究生在读）

编者按：

作者在上一期的文章中给我们解释了「为何引入对偶问题」，可见对偶问题对原问题的求解有很大的帮助。那么，如何写出对偶问题呢？这篇文章介绍的方法能帮助你快速准确无误地写出任意线性规划的对偶问题。

我们先以一般形式的对偶问题写法入手，给出表格法写对偶问题的思路；至于非一般形式线性规划可以先转换成一般形式，再写对偶问题。最后，我们将其中的技巧整理成一张表格，方便查询。

一般形式的对偶问题写法

以目标函数最大化问题为例，原问题的一般形式指的是变量全部非负、约束全部为小于等于约束的线性规划，向量形式如 (1)：

根据上一节内容，其对偶问题的含义是：在原问题目标函数的所有上界中，找到最小的一个（推导过程见上一节「为何引入对偶问题」）。相应对偶问题的一般形式，指的是变量全部非负、约束全部为大于等于约束的线性规划，向量形式如：

在向量形式中，可以直观看出原问题和对偶问题的系数存在对应关系，例如：原问题目标函数的系数向量的转置

，是对偶问题约束的右侧向量；原问题约束的系数矩阵的转置

，是对偶问题约束的系数矩阵。

我们也可以通过上一节企业出售产品和收购资源的实例，让对应的感受更直观一些：

如果我们面对的是一般形式问题，可以使用表格法便捷地写出对偶问题。图 1[1]中，由上至下按行读是原问题的约束和目标函数，由左至右按列读是对偶问题的约束和目标函数。

图 1 表格法写对偶问题（图片摘自[1]）

简单标示如下：

图 2 表格法写对偶问题（标示max问题）

图 3 表格法写对偶问题（标示min问题）

非一般形式的对偶问题写法

上一节阐述了原问题是一般形式时，如何写出对偶问题。实际中我们常常会遇到非一般形式的线性规划问题，在应用表格法之前需要先对变量和约束的形式进行转化（仍以目标函数最大化问题为例）：

①如果有 ≥ 约束，则左右同乘- 1，转化为 ≤ 约束；

②如果有 = 约束，则先转换为一个 ≤ 约束和一个 ≥ 约束，再按①把 ≥ 约束转换为 ≤ 约束。例如，如果存在约

，等价于同时满足

和

，后者再写

。

③如果有无符号限制(unrestricted in sign, urs) 的变量，用两个符号限制为 ≥0 的变量相减表示，转换关系为

。

总结

根据前两节，可以将「写对偶问题」的通用步骤归纳如下：

①将原问题转换为一般形式；

②由上至下逐行写原问题一般形式的变量及符号限制、约束和目标函数；

③根据对应关系表确定对偶问题的约束符号和变量符号；

④由左至右逐列读，得到对偶问题的变量及符号限制、约束和目标函数。

表格法中，原问题和对偶问题的符号对应关系可参考表 1。

（由于对偶的对偶是原问题，所以当原问题是最小化问题时，对应关系同样适用）：

表 1 原问题和对偶问题对应关系

本文是电子书线性规划专题的约稿文。继上回探讨为何引入对偶问题后，本文讲述了如何写对偶问题。接下来，我们将继续针对对偶原理，回答「为什么原问题和对偶问题具有相同的最优解（在有最优解的前提下）」，在证明的过程中，也会发现线性规划的一些其他性质。希望大家继续关注【优化】板块，电子书线性规划专题的科普文。

参考文献：

[1] L Winston, Wayne & B Goldberg, Jeffrey. (2004). Operations research: applications and algorithms