利用對偶理論求解線性規(guī)劃問題的策略探討

趙芹，章舜哲，劉慧清，雷琪

(湖北大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院，應(yīng)用數(shù)學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室， 湖北 武漢 430062)

0 引言

對偶理論是線性規(guī)劃問題中非常重要的內(nèi)容之一. 它反映出每一個線性規(guī)劃問題必然與之相伴而生另一個線性規(guī)劃問題，并揭示了兩者之間的密切關(guān)系. 如何利用對偶理論求解線性規(guī)劃問題是教學(xué)中的重點(diǎn)及難點(diǎn)之一. 然而，學(xué)生在練習(xí)中往往不能很好地根據(jù)線性規(guī)劃問題的不同類型來靈活選擇合適的互補(bǔ)松緊條件建立方程. 文獻(xiàn)[3]中關(guān)于具有唯一最優(yōu)解的多個變量兩個約束條件的線性規(guī)劃問題，給出了利用圖解法來求解；文獻(xiàn)[4]中則在此基礎(chǔ)之上，對于一般的多個變量兩個約束條件的線性規(guī)劃問題，給出了結(jié)合互補(bǔ)松弛條件及圖解法來求解的方法. 本研究從例子出發(fā)，詳細(xì)探討利用對偶理論來解線性規(guī)劃問題的多種思路，以期使學(xué)生能夠更好地掌握這一重要理論并靈活運(yùn)用.

給定一個線性規(guī)劃問題

其對偶問題為

則原始的LP問題及其對偶問題之間有如下關(guān)系.

定理1.1[1]如果一個線性規(guī)劃問題有最優(yōu)解，則其對偶問題也有最優(yōu)解，且它們的最優(yōu)值相等.

定理1.2[1](互補(bǔ)松弛定理)設(shè)x和w分別是原始和對偶問題的可行解，則它們分別是原始和對偶問題的最優(yōu)解的充要條件是：對一切i=1, 2, …,m和j=1, 2, …,n有

(1.1)

vj=(cj-wTAj)xj=0

(1.2)

定理1.2中的 (1.1) 式說明，如果原始問題中的一個約束條件取嚴(yán)格不等式，即是“松的”，則對偶問題的最優(yōu)解中對應(yīng)的分量必為0，即為“緊的”；(1.2) 式說明，如果原問題的最優(yōu)解中某個非負(fù)變量取正(松)，則對偶問題中相應(yīng)的約束條件必取等號(緊).

因此，定理1.2可得到以下推論.

推論1.3[2]設(shè)兩個互為對偶的線性規(guī)劃都有可行解，若原規(guī)劃某一約束是某個最優(yōu)解的非臨界約束，則它的對偶約束一定是對偶規(guī)劃所有最優(yōu)解的臨界約束.

1 解題策略及例子

利用互補(bǔ)松弛定理求線性規(guī)劃問題的最優(yōu)解是教學(xué)的重點(diǎn)及難點(diǎn)之一. 在課堂教學(xué)中我們發(fā)現(xiàn)，這類問題可以分為以下兩類情形：

1) 原線性規(guī)劃問題最優(yōu)解中的正分量的個數(shù)大于等于約束條件的個數(shù).

一般情況下，這類問題常常僅需要利用互補(bǔ)松弛定理中的 (1.2) 式就能列出方程組，從而得到最優(yōu)解.

例1已知下列線性規(guī)劃問題的最優(yōu)解為x*=(2,2,4,0)T，試求其對偶問題的最優(yōu)解.

解原問題的對偶線性規(guī)劃問題為

2) 原問題的最優(yōu)解中正分量的個數(shù)小于約束條件的個數(shù).

這類問題常常需要同時考慮互補(bǔ)松弛定理中的 (1.1) 式和 (1.2) 式. 先通過 (1.2) 式列出對偶問題中相應(yīng)的條件約束方程組，由于該方程的個數(shù)小于變量的個數(shù)，因此還需要利用(1.1) 式找到對偶問題最優(yōu)解中的零分量，從而得到最優(yōu)解.

例2若在例1中的線性規(guī)劃問題(P1)中增加約束條件x1+x2+x3≤9，所得的新的線性規(guī)劃問題記作(P2)，其最優(yōu)解仍為：x*=(2,2,4,0)T. 試求(P2)對偶問題的最優(yōu)解.

例2的解法一由題意，線性規(guī)劃問題(P2)及其對偶問題(D2)為

(2.1)

在實(shí)際練習(xí)中，學(xué)生往往能利用互補(bǔ)松弛定理的 (1.2) 式準(zhǔn)確寫出對偶問題中的條件約束等式，但常常忽略運(yùn)用 (1.1) 式來找對偶問題最優(yōu)解中的零分量，以致無法得到最優(yōu)解. 那么，當(dāng)這種情況發(fā)生時，是否還有其他的方法來補(bǔ)救呢？

在例2中，原問題最優(yōu)解中正分量的個數(shù)等于約束條件個數(shù)減1. 對于這類特殊的情形，我們還有以下兩種方法.

(i) 利用變量的非負(fù)性.

例2的解法二由 (2.1) 式解得

將上式代入對偶問題(D2)的目標(biāo)函數(shù)得

z=8w1+6w2+6w3+9w4

(ii) 利用原問題的最優(yōu)值

例2的解法三因?yàn)?P2)的最優(yōu)解為x*=(2,2,4,0)T，故最優(yōu)值

2 結(jié)論

上述研究表明，當(dāng)原線性規(guī)劃問題最優(yōu)解中正分量的個數(shù)與條件約束的個數(shù)滿足不同的大小關(guān)系時，我們所選擇的互補(bǔ)松緊條件具備一定的規(guī)律性.特別地，當(dāng)正分量的個數(shù)等于約束條件個數(shù)減1時，我們還有另外的方法來求線性規(guī)劃對偶問題的最優(yōu)解.這將有助學(xué)生更好的掌握及靈活運(yùn)用對偶理論的相關(guān)知識.