一種定義對偶線性規(guī)劃的新方法

涂建華，火博豐

(1.北京工商大學 數(shù)學與統(tǒng)計學院，北京 100048；2.青海師范大學 數(shù)學與統(tǒng)計學院，青海 西寧 810016；3.青海師范大學藏語智能信息處理及應用國家重點實驗室，青海 西寧 810016)

最優(yōu)化方法是數(shù)學及管理等專業(yè)的重要基礎課程之一，所研究的問題是討論在眾多的方案中什么樣的方案最優(yōu)以及怎樣找出最優(yōu)方案.線性規(guī)劃是最優(yōu)化理論中最重要的組成部分之一，人們發(fā)現(xiàn)一個線性規(guī)劃都有一個與之配對，兩者有著密切聯(lián)系的另一個線性規(guī)劃，即對偶線性規(guī)劃.對偶理論深刻揭示了原線性規(guī)劃與對偶規(guī)劃之間的內(nèi)在聯(lián)系，在線性規(guī)劃的應用方面起著非常重要的作用.目前，國內(nèi)外的教材[1-4]往往都是先定義對稱形式線性規(guī)劃的對偶，對于一般形式的線性規(guī)劃，首先需要轉(zhuǎn)化為對稱形式，給出對偶后再做形式上的整理，最后得到原線性規(guī)劃的對偶.這個過程非常的繁瑣，因此一些教材[2]會把各種形式的線性規(guī)劃的對偶總結(jié)出一個表格，給出線性規(guī)劃與對偶規(guī)劃相關(guān)數(shù)據(jù)之間的聯(lián)系.這種求對偶的方法使得學生很難真正理解對偶的本質(zhì)，求對偶時只能對照表格硬套，無法真正掌握求對偶的方法.

因此，我們結(jié)合對偶的實際意義，引入了預設不等式給出了一種定義對偶規(guī)劃的新方法，這種方法不需要把一般形式的線性規(guī)劃轉(zhuǎn)化為對稱形式也能快速直接求出對偶.近幾年的課堂實踐表明，學生能很好的掌握這種方法，并在后續(xù)課程中能快速準確地寫出各類線性規(guī)劃問題的對偶.

1 對稱形式線性規(guī)劃的對偶

一般的教材[1-4]都是通過定義直接給出對稱形式線性規(guī)劃的對偶.

定義對稱形式的對偶定義如下：

原問題 對偶問題

max.cxmin.wb

s.t.Ax≤b,s.t.wA≥c,

x≥0.w≥0.

這里A是m×n矩陣，b是m維列向量，c是n維的行向量，x是由原問題的決策變量組成的n維列向量，w是由對偶決策變量組成的m維行向量.

對稱形式的對偶的數(shù)學意義在很多教材上都有闡述.為了文章的完整性，我們通過一個例子介紹對偶的意義，并結(jié)合此，引入預設不等式，給出一種定義對偶規(guī)劃的新方法.

例1：求下列線性規(guī)劃的對偶

maxz=56x1+30x2;

s.t.4x1+3x2≤120,

(1)

2x1+x2≤50,

(2)

x1≥0,x2≥0

這是一個最大化問題，目標函數(shù)的取值當然越大越好，但一般情況下，這是不可能的.我們來考慮目標函數(shù)值的上界.由決策變量都非負，及

56x1+30x2≤14·(4x1+3x2)≤14·120=1680.

可知1680是目標函數(shù)值的一個上界.同樣地，因為

56x1+30x2≤30·(2x1+x2)≤30·50=1500，

1500是目標函數(shù)值的另一個上界.顯然，1500是更好的上界.同樣地，由

56x1+30x2≤2·(4x1+3x2)+24·(2x1+x2)≤2·120+24·50=1440，

(3)

可以得到一個更好的上界1440.可以看到，(3)式中第一個不等式是對每個約束乘以一個因子，使得求和后每個xi前面的系數(shù)均大于等于目標函數(shù)中xi的系數(shù)，第二個不等號右面的數(shù)值即是目標函數(shù)值的一個上界.很自然地，我們會問如何來求目標函數(shù)值的最小上界.為了回答這兩個問題，我們分別給約束(1)與(2)乘以因子w1與w2，并考慮下列不等式：

56x1+30x2≤w1·(4x1+3x2)+w2·(2x1+x2)=(4w1+2w2)·x1+(3w1+w2)·x2≤120w1+50w2

(4)

我們稱(4)為預設不等式.如果(4)成立，那么120w1+50w2是原問題目標函數(shù)值的上界.現(xiàn)在我們來建立原問題的對偶，對偶的目標函數(shù)是使得上界120w1+50w2達到最小，約束是用來保證上述預設不等式成立.因此，對偶規(guī)劃的目標為min.120w1+50w2.(4)的第一個不等式為

56x1+30x2≤(4w1+2w2)·x1+(3w1+w2)·x2

(5)

為了使這個不等式成立，我們指定如下兩個約束56x1≤(4w1+2w2)·x1與30x2≤(3w1+w2)·x2.因為x1≥0，x2≥0,因此只需在對偶規(guī)劃中建立如下兩個約束就能保證不等式(5)成立：

4w1+2w2≥56， 3w1+w2≥30

(4)中第二個不等式為

w1·(4x1+3x2)+w2·(2x1+x2)≤120w1+50w2

(6)

為了使這個不等式成立，我們指定如下約束w1·(4x1+3x2)≤120w1與w2·(2x1+x2)≤50w2.根據(jù)原問題中的約束(1)與(2)，需要在對偶規(guī)劃中要求w1≥0，w2≥0.至此，我們建立了原問題的對偶規(guī)劃：

把上述利用預設不等式求對偶的方法進行總結(jié)和推廣，得到一般形式的對偶規(guī)劃的定義，也即本文介紹的新方法.下面以最大化的原問題為例進行闡述，

(1)對于一個最大化的原問題，對偶是求原問題目標函數(shù)值的最小上界，這個最小上界由原問題的約束來決定，給每個約束Aix≤(≥,=)bi一個因子wi，設w是由對偶決策變量組成的m維行向量.

(3)比較決策變量xj前面的系數(shù)，指定約束不等式cjxj≤(wpj)xj，并根據(jù)xj的取值范圍來得到對偶的第j個約束，若xj≥0，則為wpj≥cj；若xj≤0，則為wpj≤cj;若xj無限制，則為wpj=cj；

(4)指定約束不等式wi(Aix)≤wibi，根據(jù)原問題的第i個約束來決定決策變量wi的取值范圍，若Aix≤bi，則wi≥0；若Aix≥bi，則wi≤0；若Aix=bi，則wi無限制.

求解最大化原問題時，目標函數(shù)值不斷改進，不斷增大，直到最大；求解對偶規(guī)劃，原問題目標函數(shù)值的上界不斷減小，直到最小.圖1說明了原線性規(guī)劃與對偶規(guī)劃的關(guān)系.

圖1 原線性規(guī)劃與對偶規(guī)劃的關(guān)系圖

從圖1很容易得到弱對偶定理.但原問題的最大目標函數(shù)值與對偶問題的最小目標函數(shù)值之間是否有間隙？強對偶定理告訴我們，這種意義下的最小上界確實是真正的最小上界，即原問題的最大目標函數(shù)值與對偶問題的最小目標函數(shù)值之間不存在間隙(最大最小都有限時).

2 一般形式線性規(guī)劃的對偶

我們通過下面的例題來說明對于一般形式的線性規(guī)劃，利用新方法，不需要轉(zhuǎn)化和繁瑣的推導就能快速得到它的對偶.

例2：求下列線性規(guī)劃的對偶

此問題為一個最小化問題，它的對偶規(guī)劃是去求它目標函數(shù)值的最大下界.給約束(1′)、(2′)、(3′)分配因子w1，w2，w3，并寫出預設不等式

25x1+2x2+x3≥w1·(-x1+x2-x3)+w2·(x1+2x2-x3)+w3·(2x1-x2+x3)

=(-w1+w2+2w3)·x1+(w1+2w2-w3)·x2+(-w1-w2+w3)·x3≥1·w1+1·w2+1·w3，

(4′)

對偶規(guī)劃的目標為max.w1+w2+w3.現(xiàn)在需要建立對偶規(guī)劃的約束，使得預設不等式(4′)成立.(4′)的第一個不等式為

25x1+2x2+3x3≥(-w1+w2+2w3)·x1+(w1+2w2-w3)·x2+(-w1-w2+w3)·x3

為了使這個不等式成立，我們分別指定(-w1+w2+2w3)·x1≤25x1，(w1+2w2-w3)·x2≤2x2與(-w1-w2+w3)·x3≤3x3，又因為在原問題中x1≥0,x2≤0,x3無限制，故我們需要在對偶規(guī)劃中加入下列三個約束：

-w1+w2+2w3≤25，w1+2w2-w3≥2， -w1-w2+w3=3

(4′)的第二個不等式為

w1·(-x1+x2-x3)+w2·(x1+2x2-x3)+w3·(2x1-x2+x3)≥1·w1+1·w2+1·w3，

為了使這個不等式成立，我們分別指定

w1·(-x1+x2-x3)≥1·w1，w2·(x1+2x2-x3)≥1·w2，w3·(2x1-x2+x3)≥1·w3.

因為原問題的約束(1′)、(2′)、(3′)，我們得到對偶變量的約束應該為w1≤0，w2≥0，w3無限制.綜上可得，原問題的對偶為：

需要指出的是，當理解和掌握了這種新定義，我們不必寫出預設不等式即可快速直接的寫出對偶問題.如例2中，比較決策變量x1前的系數(shù)，得(-w1+w2+2w3)·x1≤25x1，再由x1≥0得到對偶規(guī)劃的一個約束不等式-w1+w2+2w3≤25；由w1·(-x1+x2-x3)≥1·w1與-x1+x2-x3≤1得到對偶決策變量的要求w1≤0，等等.因此，這個定義的新方法是容易的，簡捷的，不需要記憶的.

3 新的定義方法的正確性

教材[2]總結(jié)出原規(guī)劃與對偶規(guī)劃相關(guān)數(shù)據(jù)之間的聯(lián)系如表1所示.

表1 對偶關(guān)系相互對照表

我們現(xiàn)在說明給定一個線性規(guī)劃，新的定義方法與參照上述表格得到的對偶完全一致，因此也就說明了我們給出的新定義能正確地得到對偶.下面假設原問題約束方程中的系數(shù)矩陣為A，Ai為A的第i行，pj為A的第j列，x為原問題決策變量組成的列向量，w為對偶決策變量組成的行向量，原問題第i個右端項為bi，第j個價值系數(shù)為cj：

(1)如果原問題是一個最大化問題，有m個約束，因此我們利用預設不等式求目標函數(shù)值的最小上界，給每個約束一個因子，因此對偶問題是一個最小化問題，且有m個決策變量；

(2)預設不等式中的兩個不等號都是≤，指定不等式(Aix)wi≤wibi.如果原問題中有約束Aix≥bi，對偶決策變量應該滿足wi≤0；對于約束≤，相應的對偶變量應該≥0，對于約束=，對偶決策變量無限制；

(3)如果原問題有n個變量，我們需要比較每個變量前面的系數(shù)，因此對偶問題中有n個約束；對于原問題中第j個變量xj，指定不等式cjxj≤(wpj)xj成立，因此，如果xj≥0，則相應的對偶約束為wpj≥cj，如果xj≤0，則相應的對偶約束wpj≤cj，如果xj無限制，則相應的對偶約束為wpj=cj.

上面的分析說明，新方法與套用表格得到的對偶完全一致.但新方法直接易懂，不需要記憶復雜的表格，更重要的是，新方法更加體現(xiàn)了對偶的本質(zhì).

4 兩點特別的說明

(1)線性規(guī)劃對偶的約束條件可以根據(jù)Kuhn-Tucker條件得到.但因為講線性規(guī)劃時，一般還沒有講到Kuhn-Tucker條件.在這種情況下如何讓學生理解對偶，容易地寫出對偶是課程教學中的難點.深入分析可以發(fā)現(xiàn)，本文得到對偶約束的新方法本質(zhì)上就是用Kuhn-Tucker條件得到對偶約束.但我們做了改造，使得學生還沒學到Kuhn-Tucker條件時，也能快速直接地寫出對偶，從而克服教學難點.本文遵循的是張景中院士提出的“教育數(shù)學”[5]的思想，即“為教育改造數(shù)學，把數(shù)學變得更容易.要讓概念更平易，推理更簡捷，方法更有力.”

(2)文章完成后，多位同行專家進行了審閱，他們提出了許多寶貴意見，我們表示誠摯的感謝.特別地，他們提到葉蔭宇教授之前在講課中提出過這個方法，但我們在文獻中沒有查到相關(guān)論述，他們的專著[6]中也是按照常規(guī)方法定義的對偶線性規(guī)劃.因此新方法并非我們獨創(chuàng)，寫這篇論文的目的只是想通過文獻傳播的方式，讓更多的學生了解這種新方法，學生能容易地寫出對偶線性規(guī)劃以及理解對偶的本質(zhì).