一种定义对偶线性规划的新方法

涂建华，火博丰

(1.北京工商大学 数学与统计学院，北京 100048；
2.青海师范大学 数学与统计学院，青海 西宁 810016；
3.青海师范大学藏语智能信息处理及应用国家重点实验室，青海 西宁 810016)

最优化方法是数学及管理等专业的重要基础课程之一，所研究的问题是讨论在众多的方案中什么样的方案最优以及怎样找出最优方案.线性规划是最优化理论中最重要的组成部分之一，人们发现一个线性规划都有一个与之配对，两者有着密切联系的另一个线性规划，即对偶线性规划.对偶理论深刻揭示了原线性规划与对偶规划之间的内在联系，在线性规划的应用方面起着非常重要的作用.目前，国内外的教材[1-4]往往都是先定义对称形式线性规划的对偶，对于一般形式的线性规划，首先需要转化为对称形式，给出对偶后再做形式上的整理，最后得到原线性规划的对偶.这个过程非常的繁琐，因此一些教材[2]会把各种形式的线性规划的对偶总结出一个表格，给出线性规划与对偶规划相关数据之间的联系.这种求对偶的方法使得学生很难真正理解对偶的本质，求对偶时只能对照表格硬套，无法真正掌握求对偶的方法.

因此，我们结合对偶的实际意义，引入了预设不等式给出了一种定义对偶规划的新方法，这种方法不需要把一般形式的线性规划转化为对称形式也能快速直接求出对偶.近几年的课堂实践表明，学生能很好的掌握这种方法，并在后续课程中能快速准确地写出各类线性规划问题的对偶.

一般的教材[1-4]都是通过定义直接给出对称形式线性规划的对偶.

定义对称形式的对偶定义如下：

原问题 对偶问题

max.cxmin.wb

s.t.Ax≤b,s.t.wA≥c,

x≥0.w≥0.

这里A是m×n矩阵，b是m维列向量，c是n维的行向量，x是由原问题的决策变量组成的n维列向量，w是由对偶决策变量组成的m维行向量.

对称形式的对偶的数学意义在很多教材上都有阐述.为了文章的完整性，我们通过一个例子介绍对偶的意义，并结合此，引入预设不等式，给出一种定义对偶规划的新方法.

例1：求下列线性规划的对偶

maxz=56x1+30x2;

s.t.4x1+3x2≤120,

(1)

2x1+x2≤50,

(2)

x1≥0,x2≥0

这是一个最大化问题，目标函数的取值当然越大越好，但一般情况下，这是不可能的.我们来考虑目标函数值的上界.由决策变量都非负，及

56x1+30x2≤14·(4x1+3x2)≤14·120=1680.

可知1680是目标函数值的一个上界.同样地，因为

56x1+30x2≤30·(2x1+x2)≤30·50=1500，

1500是目标函数值的另一个上界.显然，1500是更好的上界.同样地，由

56x1+30x2≤2·(4x1+3x2)+24·(2x1+x2)≤2·120+24·50=1440，

(3)

可以得到一个更好的上界1440.可以看到，(3)式中第一个不等式是对每个约束乘以一个因子，使得求和后每个xi前面的系数均大于等于目标函数中xi的系数，第二个不等号右面的数值即是目标函数值的一个上界.很自然地，我们会问如何来求目标函数值的最小上界.为了回答这两个问题，我们分别给约束(1)与(2)乘以因子w1与w2，并考虑下列不等式：

56x1+30x2≤w1·(4x1+3x2)+w2·(2x1+x2)=(4w1+2w2)·x1+(3w1+w2)·x2≤120w1+50w2

(4)

我们称(4)为预设不等式.如果(4)成立，那么120w1+50w2是原问题目标函数值的上界.现在我们来建立原问题的对偶，对偶的目标函数是使得上界120w1+50w2达到最小，约束是用来保证上述预设不等式成立.因此，对偶规划的目标为min.120w1+50w2.(4)的第一个不等式为

56x1+30x2≤(4w1+2w2)·x1+(3w1+w2)·x2

(5)

为了使这个不等式成立，我们指定如下两个约束56x1≤(4w1+2w2)·x1与30x2≤(3w1+w2)·x2.因为x1≥0，x2≥0,因此只需在对偶规划中建立如下两个约束就能保证不等式(5)成立：

4w1+2w2≥56， 3w1+w2≥30

(4)中第二个不等式为

w1·(4x1+3x2)+w2·(2x1+x2)≤120w1+50w2

(6)

为了使这个不等式成立，我们指定如下约束w1·(4x1+3x2)≤120w1与w2·(2x1+x2)≤50w2.根据原问题中的约束(1)与(2)，需要在对偶规划中要求w1≥0，w2≥0.至此，我们建立了原问题的对偶规划：

把上述利用预设不等式求对偶的方法进行总结和推广，得到一般形式的对偶规划的定义，也即本文介绍的新方法.下面以最大化的原问题为例进行阐述，

(1)对于一个最大化的原问题，对偶是求原问题目标函数值的最小上界，这个最小上界由原问题的约束来决定，给每个约束Aix≤(≥,=)bi一个因子wi，设w是由对偶决策变量组成的m维行向量.

(3)比较决策变量xj前面的系数，指定约束不等式cjxj≤(wpj)xj，并根据xj的取值范围来得到对偶的第j个约束，若xj≥0，则为wpj≥cj；
若xj≤0，则为wpj≤cj;若xj无限制，则为wpj=cj；

(4)指定约束不等式wi(Aix)≤wibi，根据原问题的第i个约束来决定决策变量wi的取值范围，若Aix≤bi，则wi≥0；
若Aix≥bi，则wi≤0；
若Aix=bi，则wi无限制.

求解最大化原问题时，目标函数值不断改进，不断增大，直到最大；
求解对偶规划，原问题目标函数值的上界不断减小，直到最小.图1说明了原线性规划与对偶规划的关系.

图1 原线性规划与对偶规划的关系图

从图1很容易得到弱对偶定理.但原问题的最大目标函数值与对偶问题的最小目标函数值之间是否有间隙？强对偶定理告诉我们，这种意义下的最小上界确实是真正的最小上界，即原问题的最大目标函数值与对偶问题的最小目标函数值之间不存在间隙(最大最小都有限时).

我们通过下面的例题来说明对于一般形式的线性规划，利用新方法，不需要转化和繁琐的推导就能快速得到它的对偶.

例2：求下列线性规划的对偶

此问题为一个最小化问题，它的对偶规划是去求它目标函数值的最大下界.给约束(1′)、(2′)、(3′)分配因子w1，w2，w3，并写出预设不等式

25x1+2x2+x3≥w1·(-x1+x2-x3)+w2·(x1+2x2-x3)+w3·(2x1-x2+x3)

=(-w1+w2+2w3)·x1+(w1+2w2-w3)·x2+(-w1-w2+w3)·x3≥1·w1+1·w2+1·w3，

(4′)

对偶规划的目标为max.w1+w2+w3.现在需要建立对偶规划的约束，使得预设不等式(4′)成立.(4′)的第一个不等式为

25x1+2x2+3x3≥(-w1+w2+2w3)·x1+(w1+2w2-w3)·x2+(-w1-w2+w3)·x3

为了使这个不等式成立，我们分别指定(-w1+w2+2w3)·x1≤25x1，(w1+2w2-w3)·x2≤2x2与(-w1-w2+w3)·x3≤3x3，又因为在原问题中x1≥0,x2≤0,x3无限制，故我们需要在对偶规划中加入下列三个约束：

-w1+w2+2w3≤25，w1+2w2-w3≥2， -w1-w2+w3=3

(4′)的第二个不等式为

w1·(-x1+x2-x3)+w2·(x1+2x2-x3)+w3·(2x1-x2+x3)≥1·w1+1·w2+1·w3，

为了使这个不等式成立，我们分别指定

w1·(-x1+x2-x3)≥1·w1，w2·(x1+2x2-x3)≥1·w2，w3·(2x1-x2+x3)≥1·w3.

因为原问题的约束(1′)、(2′)、(3′)，我们得到对偶变量的约束应该为w1≤0，w2≥0，w3无限制.综上可得，原问题的对偶为：

需要指出的是，当理解和掌握了这种新定义，我们不必写出预设不等式即可快速直接的写出对偶问题.如例2中，比较决策变量x1前的系数，得(-w1+w2+2w3)·x1≤25x1，再由x1≥0得到对偶规划的一个约束不等式-w1+w2+2w3≤25；
由w1·(-x1+x2-x3)≥1·w1与-x1+x2-x3≤1得到对偶决策变量的要求w1≤0，等等.因此，这个定义的新方法是容易的，简捷的，不需要记忆的.

教材[2]总结出原规划与对偶规划相关数据之间的联系如表1所示.

表1 对偶关系相互对照表

我们现在说明给定一个线性规划，新的定义方法与参照上述表格得到的对偶完全一致，因此也就说明了我们给出的新定义能正确地得到对偶.下面假设原问题约束方程中的系数矩阵为A，Ai为A的第i行，pj为A的第j列，x为原问题决策变量组成的列向量，w为对偶决策变量组成的行向量，原问题第i个右端项为bi，第j个价值系数为cj：

(1)如果原问题是一个最大化问题，有m个约束，因此我们利用预设不等式求目标函数值的最小上界，给每个约束一个因子，因此对偶问题是一个最小化问题，且有m个决策变量；

(2)预设不等式中的两个不等号都是≤，指定不等式(Aix)wi≤wibi.如果原问题中有约束Aix≥bi，对偶决策变量应该满足wi≤0；
对于约束≤，相应的对偶变量应该≥0，对于约束=，对偶决策变量无限制；

(3)如果原问题有n个变量，我们需要比较每个变量前面的系数，因此对偶问题中有n个约束；
对于原问题中第j个变量xj，指定不等式cjxj≤(wpj)xj成立，因此，如果xj≥0，则相应的对偶约束为wpj≥cj，如果xj≤0，则相应的对偶约束wpj≤cj，如果xj无限制，则相应的对偶约束为wpj=cj.

上面的分析说明，新方法与套用表格得到的对偶完全一致.但新方法直接易懂，不需要记忆复杂的表格，更重要的是，新方法更加体现了对偶的本质.

(1)线性规划对偶的约束条件可以根据Kuhn-Tucker条件得到.但因为讲线性规划时，一般还没有讲到Kuhn-Tucker条件.在这种情况下如何让学生理解对偶，容易地写出对偶是课程教学中的难点.深入分析可以发现，本文得到对偶约束的新方法本质上就是用Kuhn-Tucker条件得到对偶约束.但我们做了改造，使得学生还没学到Kuhn-Tucker条件时，也能快速直接地写出对偶，从而克服教学难点.本文遵循的是张景中院士提出的“教育数学”[5]的思想，即“为教育改造数学，把数学变得更容易.要让概念更平易，推理更简捷，方法更有力.”

(2)文章完成后，多位同行专家进行了审阅，他们提出了许多宝贵意见，我们表示诚挚的感谢.特别地，他们提到叶荫宇教授之前在讲课中提出过这个方法，但我们在文献中没有查到相关论述，他们的专著[6]中也是按照常规方法定义的对偶线性规划.因此新方法并非我们独创，写这篇论文的目的只是想通过文献传播的方式，让更多的学生了解这种新方法，学生能容易地写出对偶线性规划以及理解对偶的本质.