對偶關系的進一步思考

潘美芹　丁志軍　韓耀軍　傅軍和

摘要：每個線性規劃問題總有一個與它對應的對偶線性規劃問題。基于對偶關系表，可以由原問題得出對偶問題，但由于變量、約束的復雜關系而使對應關系容易出錯。為此，論文總結了“大約變，小約不變，變化僅一次，等號與無約束關聯”的口訣，使得能準確無誤地寫出對偶問題。

關鍵詞：原問題;對偶問題;對偶關系

中圖分類號：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