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

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

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

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

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

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

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

原問(wèn)題：

max z=cx+cx+…+cx

s.t.ax+ax+…+ax≤bax+ax+…+ax≤b…ax+ax+…+ax≤bx≥0 ?（j=1，…，n）

對(duì)偶問(wèn)題：

min w=by+by+…+by

s.t.ay+ay+…+ay≥cay+ay+…+ay≥c…ay+ay+…+ay≥cy≥0? （i=1，…，m）

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

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

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

原問(wèn)題：

max（或min）z=cx+cx+…+cx

s.t.ax+ax+…+ax≤（或=，≥）bax+ax+…+ax≤（或=，≥）b…ax+ax+…+ax≤（或=，≥）bx≥（或=，≥）0? （j=1，…，n）

對(duì)偶問(wèn)題：

min（或max）w=by+by+…+by

s.t.ay+ay+…+ay≤（或=，≥）cay+ay+…+ay≤（或=，≥）c…ay+ay+…+ay≤（或=，≥）cy≤（或=，≥）0? （i=1，…，m）

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

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

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

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

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

變化僅一次：原問(wèn)題的約束條件決定的對(duì)偶變量不等號(hào)反向后，原問(wèn)題的變量決定對(duì)偶約束的不等號(hào)就不變了。反之亦然。

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

例1：寫出下面原問(wèn)題的對(duì)偶問(wèn)題。

min z=7x+4x-3x

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

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

解：（1）原問(wèn)題求極小，則對(duì)偶問(wèn)題求極大，得對(duì)偶問(wèn)題的目標(biāo)函數(shù)：max w=24y+15y+30y

（2）由小約不變：第一個(gè)條件為“≤”，得y≤0;第二個(gè)條件為“≥”，得y≥0;第三個(gè)條件為“=”，得y取值無(wú)約束。

（3）變化僅一次：由（2）知，原問(wèn)題約束條件與對(duì)偶變量的不等號(hào)同向，則原問(wèn)題變量與對(duì)偶問(wèn)題的約束條件的不等號(hào)反向。

x≤0，故第一個(gè)約束為“≥”，得：-4y-3y≥7

x≥0，故第三個(gè)約束為“≤”，得：-6y-4y+3y≤-3

（4）等號(hào)與無(wú)約束關(guān)聯(lián)：x2取值無(wú)約束，故第二個(gè)約束為“=”，得：2y-6y+5y=4

綜上，得到原問(wèn)題的對(duì)偶問(wèn)題：

max w=24y+15y+30y

s.t.-4y-3y≥72y-6y+5y=4-6y-4y+3y≤-3y≤0，y≥0，y取值無(wú)約束

例2：寫出下面原問(wèn)題的對(duì)偶問(wèn)題。

max z=2x-3x+4x

s.t.2x+3x-5x≥23x+x+7x≤3-x+4x+6x≥5x≥0，x≤0，x無(wú)約束

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

解：（1）原問(wèn)題求極大，則對(duì)偶問(wèn)題求極小，得對(duì)偶問(wèn)題的目標(biāo)函數(shù)：min w=2y+3y+5y

（2）由大約變：第一個(gè)條件為“≥”，得y≤0;第二個(gè)條件為“≤”，得y≥0;第三個(gè)條件為“≥”，得y≤0。

（3）變化僅一次：由（2）知，原問(wèn)題約束條件與對(duì)偶變量的不等號(hào)反向，則原問(wèn)題變量與對(duì)偶問(wèn)題的約束條件的不等號(hào)同向。

x≥0，故第一個(gè)約束為“≥”，得：2y+3y-y≥2

x≤0，故第二個(gè)約束為“≤”，得：3y+y+4y≤-3

（4）等號(hào)與無(wú)約束關(guān)聯(lián)：x取值無(wú)約束，故第三個(gè)約束為“=”，得：-5y+7y+6y=4

綜上，得到原問(wèn)題的對(duì)偶問(wèn)題：

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ǔ)

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

參考文獻(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