对偶关系的进一步思考
来源:用户上传
作者:
摘要：每个线性规划问题总有一个与它对应的对偶线性规划问题。基于对偶关系表，可以由原问题得出对偶问题，但由于变量、约束的复杂关系而使对应关系容易出错。为此，论文总结了“大约变，小约不变，变化仅一次，等号与无约束关联”的口诀，使得能准确无误地写出对偶问题。
关键词：原问题;对偶问题;对偶关系
中图分类号：G642 文献标志码：A 文章编号：1674-9324（2019）13-0213-02
伴随着线性规划问题及其解法的提出，人们发现，对于任何一个线性规划问题，都伴随着另一个线性规划问题，二者之间存在着密切的关系，这个伴随的线性规划问题就是对偶问题。
一、对称形式线性规划的原—对偶问题
原问题：
max z=cx+cx+…+cx
s.t.ax+ax+…+ax≤bax+ax+…+ax≤b…ax+ax+…+ax≤bx≥0 （j=1，…，n）
对偶问题：
min w=by+by+…+by
s.t.ay+ay+…+ay≥cay+ay+…+ay≥c…ay+ay+…+ay≥cy≥0 （i=1，…，m）
对于这种对称形式的线性规划原—对偶问题，只要遵循以下准则就可以轻松求出原问题的对偶问题了：（1）一个问题中的约束条件个数等于另一个问题中的变量数;（2）一个问题中目标函数的系数是另一个问题中约束条件的右端项;（3）约束条件在一个问题中为“≤”，在另一个问题中为“≥”;（4）目标函数在一个问题中求极大值，在另一个问题中则为极小值。
二、非对称形式线性规划的原—对偶问题
（一）非对称形式线性规划的原—对偶问题的对偶关系
原问题：
max（或min）z=cx+cx+…+cx
s.t.ax+ax+…+ax≤（或=，≥）bax+ax+…+ax≤（或=，≥）b…ax+ax+…+ax≤（或=，≥）bx≥（或=，≥）0 （j=1，…，n）
对偶问题：
min（或max）w=by+by+…+by
s.t.ay+ay+…+ay≤（或=，≥）cay+ay+…+ay≤（或=，≥）c…ay+ay+…+ay≤（或=，≥）cy≤（或=，≥）0 （i=1，…，m）
我們可以借助对偶关系求一般线性规划原问题的对偶问题。但是，原问题和对偶问题的对应关系比较复杂：原问题的约束条件有3种情况，对应的对偶变量也有3种可能;原问题的变量有3种情况，对应的约束条件也有3种可能。总共有18种组合关系，对偶关系只是其中的6种，学生容易记混，导致非对称形式的对偶问题往往出错。
（二）对偶关系的口诀
口诀：大约变，小约不变，变化仅一次，等号与无约束关联。
大约变：“大”即为原问题的目标函数求极大;“约”即为原问题的约束条件;“变”有两层意思：一层意思是对偶变量，另一层意思是指由原问题的约束条件来对应对偶问题的变量时，不等号发生变化，即当原问题的目标函数求极大时，其m个约束条件对应于对偶问题的m个对偶变量，若原问题的约束为“≤”，则对应的对偶变量≥0;若原问题的约束为“≥”，则对应的对偶变量≤0。
小约不变：“小”即为原问题的目标函数求极小，“约”即为原问题的约束条件，“变”指对偶变量，“不变”是指由原问题的约束条件来对应对偶问题的变量时，不等号不发生变化，即当原问题的目标函数求极小时，其m个约束条件对应于对偶问题的m个对偶变量，若原问题的约束为“≤”，则对应的对偶变量≤0;若原问题的约束为“≥”，则对应的对偶变量≥0。
变化仅一次：原问题的约束条件决定的对偶变量不等号反向后，原问题的变量决定对偶约束的不等号就不变了。反之亦然。
等号与无约束关联：当原问题的约束为“=”，则对应的对偶变量就是无约束变量，并且当原问题的变量为无约束时，则对应的对偶约束为“=”。
例1：写出下面原问题的对偶问题。
min z=7x+4x-3x
s.t.-4x+2x-6x≤24-3x-6x-4x≥155x+3x=30x≤0，x取值无约束，x≥0
分析：原问题的目标函数求极小，故遵循“小约不变，等号与无约束关联，变化仅一次”的准则。
解：（1）原问题求极小，则对偶问题求极大，得对偶问题的目标函数：max w=24y+15y+30y
（2）由小约不变：第一个条件为“≤”，得y≤0;第二个条件为“≥”，得y≥0;第三个条件为“=”，得y取值无约束。
（3）变化仅一次：由（2）知，原问题约束条件与对偶变量的不等号同向，则原问题变量与对偶问题的约束条件的不等号反向。
x≤0，故第一个约束为“≥”，得：-4y-3y≥7
x≥0，故第三个约束为“≤”，得：-6y-4y+3y≤-3
（4）等号与无约束关联：x2取值无约束，故第二个约束为“=”，得：2y-6y+5y=4
综上，得到原问题的对偶问题：
max w=24y+15y+30y
s.t.-4y-3y≥72y-6y+5y=4-6y-4y+3y≤-3y≤0，y≥0，y取值无约束
例2：写出下面原问题的对偶问题。
max z=2x-3x+4x
s.t.2x+3x-5x≥23x+x+7x≤3-x+4x+6x≥5x≥0，x≤0，x无约束
分析：原问题的目标函数求极大，故遵循“大约变，变化仅一次，等号与无约束关联”的准则。 解：（1）原问题求极大，则对偶问题求极小，得对偶问题的目标函数：min w=2y+3y+5y
（2）由大約变：第一个条件为“≥”，得y≤0;第二个条件为“≤”，得y≥0;第三个条件为“≥”，得y≤0。
（3）变化仅一次：由（2）知，原问题约束条件与对偶变量的不等号反向，则原问题变量与对偶问题的约束条件的不等号同向。
x≥0，故第一个约束为“≥”，得：2y+3y-y≥2
x≤0，故第二个约束为“≤”，得：3y+y+4y≤-3
（4）等号与无约束关联：x取值无约束，故第三个约束为“=”，得：-5y+7y+6y=4
综上，得到原问题的对偶问题：
min w=2y+3y+5y
s.t.2y+3y-y≥23y+y+4y≥-3-5y+7y+6y=4y≤0，y≥0，y≤0
三、结语
在运筹学课程中，虽然原问题和对偶问题的对应关系表为我们写原—偶问题提供了方便，但是对应关系比较复杂，学生容易混淆，导致非对称形式的对偶问题往往出错。
参考文献：
[1]胡运权.运筹学基础及应用[M].哈尔滨工业大学出版社，2009.
[2]熊伟.运筹学[M].北京：机械工业出版社，2011.
A Rule of Dual Relation between Original Problem and Dual Problem
PAN Mei-qin1，DING Zhi-jun2，HAN Yao-jun1，FU Jun-he1
（1.School of Business and Management，Shanghai International Studies University，Shanghai 200083，China;
2.School of Electronics and Information Engineering，Tongji University，Shanghai 201804，China）
Abstract：There is always a dual linear programming problem corresponding to each linear programming problem. But it is very easy to get wrong dual problem because of the complicated relationship between variables and constraints. This paper proposes a rule that can help people to get the dual problem easily and correctly. The rule is， maximize-constraint-change， minimize-constraint-same， change is only one time， equal is associated with unconstrained.
Key words：original problem;dual problem;dual relation
转载注明来源:https://www.xzbu.com/9/view-14736527.htm
