涂建華，火博豐

(1.北京工商大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，北京 100048；2.青海師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，青海 西寧 810016；3.青海師范大學(xué)藏語(yǔ)智能信息處理及應(yīng)用國(guó)家重點(diǎn)實(shí)驗(yàn)室，青海 西寧 810016)

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

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

1 對(duì)稱(chēng)形式線(xiàn)性規(guī)劃的對(duì)偶

一般的教材[1-4]都是通過(guò)定義直接給出對(duì)稱(chēng)形式線(xiàn)性規(guī)劃的對(duì)偶.

定義對(duì)稱(chēng)形式的對(duì)偶定義如下：

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

max.cxmin.wb

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

x≥0.w≥0.

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

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

例1：求下列線(xiàn)性規(guī)劃的對(duì)偶

maxz=56x1+30x2;

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

(1)

2x1+x2≤50,

(2)

x1≥0,x2≥0

這是一個(gè)最大化問(wèn)題，目標(biāo)函數(shù)的取值當(dāng)然越大越好，但一般情況下，這是不可能的.我們來(lái)考慮目標(biāo)函數(shù)值的上界.由決策變量都非負(fù)，及

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

可知1680是目標(biāo)函數(shù)值的一個(gè)上界.同樣地，因?yàn)?/p>

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

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

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

(3)

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

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

(4)

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

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

(5)

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

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

(4)中第二個(gè)不等式為

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

(6)

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

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

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

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

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

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

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

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

2 一般形式線(xiàn)性規(guī)劃的對(duì)偶

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

例2：求下列線(xiàn)性規(guī)劃的對(duì)偶

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

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

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

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

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

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

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

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

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

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

因?yàn)樵瓎?wèn)題的約束(1′)、(2′)、(3′)，我們得到對(duì)偶變量的約束應(yīng)該為w1≤0，w2≥0，w3無(wú)限制.綜上可得，原問(wèn)題的對(duì)偶為：

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

3 新的定義方法的正確性

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

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

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

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

(2)預(yù)設(shè)不等式中的兩個(gè)不等號(hào)都是≤，指定不等式(Aix)wi≤wibi.如果原問(wèn)題中有約束Aix≥bi，對(duì)偶決策變量應(yīng)該滿(mǎn)足wi≤0；對(duì)于約束≤，相應(yīng)的對(duì)偶變量應(yīng)該≥0，對(duì)于約束=，對(duì)偶決策變量無(wú)限制；

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

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

4 兩點(diǎn)特別的說(shuō)明

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

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