對偶關(guān)系的進(jìn)一步思考

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

摘要：每個線性規(guī)劃問題總有一個與它對應(yīng)的對偶線性規(guī)劃問題?；趯ε缄P(guān)系表，可以由原問題得出對偶問題，但由于變量、約束的復(fù)雜關(guān)系而使對應(yīng)關(guān)系容易出錯。為此，論文總結(jié)了“大約變，小約不變，變化僅一次，等號與無約束關(guān)聯(lián)”的口訣，使得能準(zhǔn)確無誤地寫出對偶問題。

關(guān)鍵詞：原問題;對偶問題;對偶關(guān)系

中圖分類號：G642???? 文獻(xiàn)標(biāo)志碼：A???? 文章編號：1674-9324（2019）13-0213-02

伴隨著線性規(guī)劃問題及其解法的提出，人們發(fā)現(xiàn)，對于任何一個線性規(guī)劃問題，都伴隨著另一個線性規(guī)劃問題，二者之間存在著密切的關(guān)系，這個伴隨的線性規(guī)劃問題就是對偶問題。

一、對稱形式線性規(guī)劃的原—對偶問題

原問題：

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）

對于這種對稱形式的線性規(guī)劃原—對偶問題，只要遵循以下準(zhǔn)則就可以輕松求出原問題的對偶問題了：（1）一個問題中的約束條件個數(shù)等于另一個問題中的變量數(shù);（2）一個問題中目標(biāo)函數(shù)的系數(shù)是另一個問題中約束條件的右端項(xiàng);（3）約束條件在一個問題中為“≤”，在另一個問題中為“≥”;（4）目標(biāo)函數(shù)在一個問題中求極大值，在另一個問題中則為極小值。

二、非對稱形式線性規(guī)劃的原—對偶問題

（一）非對稱形式線性規(guī)劃的原—對偶問題的對偶關(guān)系

原問題：

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）

我們可以借助對偶關(guān)系求一般線性規(guī)劃原問題的對偶問題。但是，原問題和對偶問題的對應(yīng)關(guān)系比較復(fù)雜：原問題的約束條件有3種情況，對應(yīng)的對偶變量也有3種可能;原問題的變量有3種情況，對應(yīng)的約束條件也有3種可能。總共有18種組合關(guān)系，對偶關(guān)系只是其中的6種，學(xué)生容易記混，導(dǎo)致非對稱形式的對偶問題往往出錯。

（二）對偶關(guān)系的口訣

口訣：大約變，小約不變，變化僅一次，等號與無約束關(guān)聯(lián)。

大約變：“大”即為原問題的目標(biāo)函數(shù)求極大;“約”即為原問題的約束條件;“變”有兩層意思：一層意思是對偶變量，另一層意思是指由原問題的約束條件來對應(yīng)對偶問題的變量時，不等號發(fā)生變化，即當(dāng)原問題的目標(biāo)函數(shù)求極大時，其m個約束條件對應(yīng)于對偶問題的m個對偶變量，若原問題的約束為“≤”，則對應(yīng)的對偶變量≥0;若原問題的約束為“≥”，則對應(yīng)的對偶變量≤0。

小約不變：“小”即為原問題的目標(biāo)函數(shù)求極小，“約”即為原問題的約束條件，“變”指對偶變量，“不變”是指由原問題的約束條件來對應(yīng)對偶問題的變量時，不等號不發(fā)生變化，即當(dāng)原問題的目標(biāo)函數(shù)求極小時，其m個約束條件對應(yīng)于對偶問題的m個對偶變量，若原問題的約束為“≤”，則對應(yīng)的對偶變量≤0;若原問題的約束為“≥”，則對應(yīng)的對偶變量≥0。

變化僅一次：原問題的約束條件決定的對偶變量不等號反向后，原問題的變量決定對偶約束的不等號就不變了。反之亦然。

等號與無約束關(guān)聯(lián)：當(dāng)原問題的約束為“=”，則對應(yīng)的對偶變量就是無約束變量，并且當(dāng)原問題的變量為無約束時，則對應(yīng)的對偶約束為“=”。

例1：寫出下面原問題的對偶問題。

min z=7x+4x-3x

s.t.-4x+2x-6x≤24-3x-6x-4x≥155x+3x=30x≤0，x取值無約束，x≥0

分析：原問題的目標(biāo)函數(shù)求極小，故遵循“小約不變，等號與無約束關(guān)聯(lián)，變化僅一次”的準(zhǔn)則。

解：（1）原問題求極小，則對偶問題求極大，得對偶問題的目標(biāo)函數(shù)：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）等號與無約束關(guān)聯(lián)：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無約束

分析：原問題的目標(biāo)函數(shù)求極大，故遵循“大約變，變化僅一次，等號與無約束關(guān)聯(lián)”的準(zhǔn)則。

解：（1）原問題求極大，則對偶問題求極小，得對偶問題的目標(biāo)函數(shù)：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）等號與無約束關(guān)聯(lián)：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

三、結(jié)語

在運(yùn)籌學(xué)課程中，雖然原問題和對偶問題的對應(yīng)關(guān)系表為我們寫原—偶問題提供了方便，但是對應(yīng)關(guān)系比較復(fù)雜，學(xué)生容易混淆，導(dǎo)致非對稱形式的對偶問題往往出錯。

參考文獻(xiàn)：

[1]胡運(yùn)權(quán).運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用[M].哈爾濱工業(yè)大學(xué)出版社，2009.

[2]熊偉.運(yùn)籌學(xué)[M].北京：機(jī)械工業(yè)出版社，2011.

A Rule of Dual Relation between Original Problem and Dual Problem

PAN Mei-qin1，DING Zhi-jun2，HAN Yao-jun1，F(xiàn)U 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