（1） 線性規(guī)劃及其對(duì)偶

1、第二講(1) 線性規(guī)劃及其對(duì)偶,對(duì)偶特性是線性規(guī)劃的最重要特征，有人稱對(duì)偶是線性規(guī)劃的心臟，本書(shū)將把對(duì)偶問(wèn)題貫徹于線性規(guī)劃之始終。 §1 對(duì)偶問(wèn)題的現(xiàn)實(shí)來(lái)源§2 原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系§3 線性規(guī)劃的規(guī)范型§4 對(duì)偶規(guī)劃規(guī)范型及其轉(zhuǎn)換§5 線性規(guī)劃的標(biāo)準(zhǔn)型及其轉(zhuǎn)換,§1 對(duì)偶問(wèn)題的現(xiàn)實(shí)來(lái)源（1）,設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備按A，B，

2、C，D順序加工，每件產(chǎn)品加工所需的機(jī)時(shí)數(shù)、每件產(chǎn)品的利潤(rùn)值及每種設(shè)備的可利用機(jī)時(shí)數(shù)列于表１。 表1 產(chǎn)品數(shù)據(jù)表,,§1 對(duì)偶問(wèn)題的現(xiàn)實(shí)來(lái)源（2）,1、問(wèn)：充分利用設(shè)備機(jī)時(shí)，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤(rùn)？試列出相應(yīng)線性規(guī)劃數(shù)學(xué)模型。 設(shè)，甲及乙型產(chǎn)品各生產(chǎn)x1及x2件，則數(shù)學(xué)模型為： 2x1＋2x2 ≤12

3、 x1+2x2 ≤8 (機(jī)時(shí)限制) 4x1 ≤16 4x2 ≤12 xj≥0 j=1,2 (變量限制，產(chǎn)品量必為正) ｚ＝2x1＋3x2＝max （目標(biāo)函數(shù)，使利潤(rùn)最大）

4、,§1 對(duì)偶問(wèn)題的現(xiàn)實(shí)來(lái)源（3）,2、反過(guò)來(lái)問(wèn)：若廠長(zhǎng)決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機(jī)器用于接受外加工，只收加工費(fèi)，那未４種機(jī)器的機(jī)時(shí)如何定價(jià)才是最佳決策？ 也許有人會(huì)馬上回答，定價(jià)愈高，收益愈大，故必是最佳決策。然而這是錯(cuò)誤的，因?yàn)槎▋r(jià)太高，勢(shì)必失去顧客，從而也必減少收益，在市場(chǎng)競(jìng)爭(zhēng)的時(shí)代，廠長(zhǎng)的最佳決策顯然應(yīng)符合兩條： （1）不吃虧原則。即機(jī)時(shí)定價(jià)所賺利潤(rùn)不能低于加工甲、乙型產(chǎn)品所獲利潤(rùn)。由此原則，便構(gòu)

5、成了新規(guī)劃的不等式約束條件。,§1 對(duì)偶問(wèn)題的現(xiàn)實(shí)來(lái)源（4）,（2）競(jìng)爭(zhēng)性原則，即在上述不吃虧原則下，盡量降低機(jī)時(shí)總收費(fèi)，以便爭(zhēng)取更多用戶。 設(shè)A、B、C、D設(shè)備的機(jī)時(shí)價(jià)分別為y1、y2、y3、y4，則新的線性規(guī)劃數(shù)學(xué)模型為： （不吃虧原則） yj ? 0， j=1,2,3,4 （定價(jià)必為正）

6、 (目標(biāo)函數(shù)，使收費(fèi)最低),,§1 對(duì)偶問(wèn)題的現(xiàn)實(shí)來(lái)源（5）,把同種問(wèn)題的兩種提法所獲得的數(shù)學(xué)模型用表2表示，將會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象。表2 原問(wèn)題與對(duì)偶問(wèn)題對(duì)比表,表2，直接去看是原問(wèn)題，將它轉(zhuǎn)900看便是對(duì)偶問(wèn)題。當(dāng)然，對(duì)偶是相互的，若把表轉(zhuǎn)900看成是問(wèn)題，則原表亦可看成是相應(yīng)的對(duì)偶問(wèn)題。,§2原問(wèn)題與對(duì)偶問(wèn)

7、題的對(duì)應(yīng)關(guān)系（1）,1、原問(wèn)題表達(dá)式(結(jié)合實(shí)例)，不對(duì)稱 例如，給定一線性規(guī)劃為 (約束) x1?0，x2 ? 0， x3 ? 0

8、 (目標(biāo)函數(shù)) 寫(xiě)成矩陣形式為,,,,,§2原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系（2）,其中，,,,,,,§2原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系（3）,2、相應(yīng)的對(duì)偶問(wèn)題表達(dá)式為： （約束）y1，y2不限制

9、 （目標(biāo)函數(shù)）寫(xiě)成矩陣形式,,,,,,,,,§2原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系（4）,其中， 由此例看出，線性規(guī)劃AX=b，X ≥0， 的對(duì)偶問(wèn)題，即為 ， 。 3、原問(wèn)題與對(duì)偶問(wèn)題的轉(zhuǎn)換，對(duì)稱若把上例原問(wèn)題的約束條件由等式變?yōu)椴坏仁?，則對(duì)偶問(wèn)題的自變量取值由無(wú)限制變?yōu)橛邢拗?，即原?wèn)題變?yōu)?

10、 （約束） （目標(biāo)函數(shù)）,,,,,,,,,,,,,,,§2原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系（5）,則對(duì)偶問(wèn)題變?yōu)椋?

11、 （約束） （目標(biāo)函數(shù)）于是作為一般形式，二者關(guān)系可歸納如下。對(duì)于原問(wèn)題定義為： 約束條件 當(dāng)i?I1,,,,,,,,,,,,§2

12、原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系（6）,,,,,,,,,,,,= bi 當(dāng)i?I2其中，I1­，I2­是整集I中的拆集，I=I1∪I2={1,2,…，m}。自變量限制xj≥0 當(dāng) j ? J1 J1 ? J ={1,2,…,n}若J1為空集，則無(wú)符號(hào)約束（即自變量無(wú)限制）若J1=J，則所有xj≥0目標(biāo)函數(shù),§2原問(wèn)題與對(duì)

13、偶問(wèn)題的對(duì)應(yīng)關(guān)系（7）,,,,,,,,,,,,則，相應(yīng)的對(duì)偶問(wèn)題定義為：令對(duì)偶變量 Y=y1,…,ym 約束條件 當(dāng)j?J1 =cj 當(dāng)j?J2自變量限制

14、 yi≥0 當(dāng)i?I1 yi不限 當(dāng)i?I2目標(biāo)函數(shù),§3 線性規(guī)劃的規(guī)范型（1）,舊規(guī)范型：其相應(yīng)的對(duì)偶問(wèn)題必為：,,,,,§3 線性規(guī)劃的規(guī)范型（2）,特定義一個(gè)新的線性規(guī)劃規(guī)范型如下： 約束 X ? 0 或不

15、限 目標(biāo)函數(shù)則相應(yīng)的對(duì)偶問(wèn)題形式為 約束 Y ? 0 或不限 目標(biāo)函數(shù),,,,,§3 線性規(guī)劃的規(guī)范型（3）,下面主要介紹新規(guī)范型之變換及如何寫(xiě)出對(duì)偶規(guī)則。本文不加說(shuō)明，規(guī)范型是指新型范型。 舉例，寫(xiě)出下述線性規(guī)劃的規(guī)范型： 變換為規(guī)范型如下： 令x’3= -x3把“≤”變?yōu)椤啊荨?，把“max”變?yōu)椤癿in”，

16、則得,,,,,§3 線性規(guī)劃的規(guī)范型（4）,按照前面定義，知：I={1,2,3}，J={1,2,3}，I1={1,2}，I2={3}，J1={1,3}，J2={2}于是相應(yīng)的對(duì)偶形式為：,,,,,§4 對(duì)偶線性規(guī)劃規(guī)范型及其變換（略）,,,,,§5 線性規(guī)劃的標(biāo)準(zhǔn)型及其轉(zhuǎn)換（1）,為適應(yīng)單純形法求解，必須把線性模型變?yōu)橄率鰳?biāo)準(zhǔn)形式： AX=b, X≥0, CTX=min 或

17、AX=b, X≥0，CTX=max不加說(shuō)明，本文指前一種形式,,,,,§5 線性規(guī)劃的標(biāo)準(zhǔn)型及其轉(zhuǎn)換（2）,由線性規(guī)劃一般型變?yōu)橐?guī)范型（新規(guī)范型）方法前已闡明，現(xiàn)介紹如何把規(guī)范型變?yōu)闃?biāo)準(zhǔn)型。1．若出現(xiàn) 則增加剩余變量zi, 使“≥”變?yōu)椤?”得 xj≥0，zi≥0,,,,,§5 線性規(guī)劃的標(biāo)準(zhǔn)型及其轉(zhuǎn)換（3）,2．若出現(xiàn)xj不限，即－∞<xi<∞,

18、(j?J2) 則令 xj=uj－vj (j?J2),uj≥0，vj≥0這樣，便使所有約束變?yōu)榈仁?，且自變量全大于或等?。綜合上述，線性規(guī)劃主要有三種表達(dá)形式：便于從實(shí)際問(wèn)題中提煉數(shù)學(xué)模型的一般型（General）；便于轉(zhuǎn)化為對(duì)偶問(wèn)題的規(guī)范型（Standard），以及用于單純形法求解的標(biāo)準(zhǔn)型（Canonical）。要知道了一般型，便很容易變換為規(guī)范型及標(biāo)準(zhǔn)型。,第二講（2） 用對(duì)偶分析原問(wèn)題最優(yōu)解,&#

19、167;1 初步分析線性規(guī)劃解的幾種可能性 §2 線性規(guī)劃解的求解方法之一：圖解法 §3 對(duì)偶性質(zhì)及平衡定理,§1 初步分析線性規(guī)劃解的幾種可能性 （1）,已知線性規(guī)劃的標(biāo)準(zhǔn)形式為AX=b, X≥O, CTX=min滿足前2條的解為可行解，同時(shí)又滿足第3條的為最優(yōu)解。從解的性質(zhì)看，線性規(guī)劃有下述幾種可能：1．不存在可行解或無(wú)解，例如規(guī)劃x1=－１ x

20、1≥ 0 無(wú)可行解3 x1=min,,§1 初步分析線性規(guī)劃解的幾種可能性 （2）,2．存在可行解，但找不到最優(yōu)解，例如規(guī)劃x1－x2=0x1，x2≥0－2 x1=min 顯然，令x1=x2=λ,λ為任意非負(fù)值都是可行解， 當(dāng)λ→+∞，則目標(biāo)函數(shù)－2 x1→∞，故找不出使目標(biāo)函數(shù) 取極小值的具體解X。,,§1 初步分析線性規(guī)劃解的幾種可

21、能性 （3）,,3．存在最優(yōu)解，但不是唯一的。例如規(guī)劃x1+x2=1x1，x2≥ox1+ x2=min 顯然 兩點(diǎn)連線上的所有點(diǎn) 都是最優(yōu)解，（見(jiàn)圖1-1）4．一般情況有無(wú)窮多可行解，但有唯一最優(yōu)解。,§2 線性規(guī)劃解的求解方法之一：圖解法 （1）,[例1-3] 求解下述線性規(guī)劃2x1+x2－x3=4(1)xj≥0 j=1,2,3

22、(2)3x1+5x2=min(3)將(1)式中的x3移至右邊，常數(shù)4移至左邊，得： 2x1+x2－4=x3≥0 移項(xiàng)得：2x1+x2≥4于是變?yōu)閮删S線性規(guī)劃問(wèn)題，其約束可行域可用直角坐標(biāo)系表示,如圖1-2。,§2 線性規(guī)劃解的求解方法之一：圖解法 （2）,圖1-2中，陰影部分為可行域，若要求出最優(yōu)點(diǎn)，必須作出目標(biāo)函數(shù)的等值線，然后令等值線向最小值方向（即最優(yōu)方向）移動(dòng)，直到離開(kāi)可行域

23、的瞬間為止，此時(shí)的交點(diǎn)即為最優(yōu)點(diǎn)。圖中直線L1，L2，L3即為目標(biāo)值分別為12，9及6的等值線，L3與可行域的頂點(diǎn)B（x1＝2，x2＝0），L3再向左下方移動(dòng)，必離開(kāi)可行域，于是該點(diǎn)即為線性規(guī)劃之最優(yōu)解，即：X ＝（x1，x2，x3）=(2,0,0)，目標(biāo)值為3x1+5x2＝6。圖解法簡(jiǎn)單易行，但只適于兩維問(wèn)題（本題雖是三維，但很容易變?yōu)閮删S）。對(duì)于高維問(wèn)題，只能采用其它的辦法求解。很幸運(yùn)，該法已經(jīng)找到，這就是以后將要介紹

24、的單純形法。,,§3 對(duì)偶性質(zhì)及平衡定理 （1）,1．弱對(duì)偶性（不等式性質(zhì)）設(shè)原線性規(guī)劃為AX=b，X≥0，CTX=min其對(duì)偶規(guī)劃為YTA≤CT, YT b=max若X、Y分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，則必存在關(guān)系式CTX≥YTb 證明：因?yàn)閄、Y分別是原問(wèn)題及對(duì)偶問(wèn)題的可行解，因此YTAX=YT(AX)=YTb及 YTAX =(YTA)X≤CTX故 CTX≥YTb這

25、是一個(gè)很有用的性質(zhì)，因?yàn)橛袝r(shí)并不需要精確求出線性規(guī)劃問(wèn)題最優(yōu)解，只需了解最優(yōu)目標(biāo)值的范圍，那么采用求解對(duì)偶可行解就顯得十分方便。,,§3 對(duì)偶性質(zhì)及平衡定理 （2）,2．強(qiáng)對(duì)偶性（對(duì)偶最優(yōu)性） 若 分別是原問(wèn)題與對(duì)偶問(wèn)題可行解，且 ，則 必分別是原問(wèn)題及對(duì)偶問(wèn)題的最優(yōu)解。證明：設(shè)X是原向題任一可行解，則從弱對(duì)偶性知，

26、 ，可見(jiàn) 是原問(wèn)題最優(yōu)解。同理，設(shè)Y是對(duì)偶問(wèn)題任一可行解，則 ，故 是對(duì)偶問(wèn)題最優(yōu)解。,,§3 對(duì)偶性質(zhì)及平衡定理 （3）,1．平衡定理設(shè)原問(wèn)題為 (4) xj≥0 (j=1,2,…，n) (5)

27、(6)其對(duì)偶形式為 (7)(8),,§3 對(duì)偶性質(zhì)及平衡定理 （4）,則平衡定理闡述如下：若xj(j=1,2…，n)和yi（i=1,2,…，m）分別是原問(wèn)題和對(duì)偶問(wèn)題之可行解，必存在下述關(guān)系：（即弱對(duì)偶性） 上式中兩邊相等的充分必要條件是： 或 xj=0 或 xj>0,但,,①,②,

28、7;3 對(duì)偶性質(zhì)及平衡定理 （5）,證明①：根據(jù)(5)式和(7)式可得：(9),,,§3 對(duì)偶性質(zhì)及平衡定理 （6）,證明②：若使 ，即表明(9)式左邊為0（不等式 變?yōu)榈仁剑?，而該式是由n 項(xiàng)和組成，每一項(xiàng) 是兩因子乘積，每個(gè)因子都≥0。 故每一項(xiàng)都≥0。若使n項(xiàng)為0，勢(shì)必使每一項(xiàng)為0，即：則其中至少有一

29、個(gè)因子為0。 于是得出，或xj=0；或xj>0，必使 。,§3 對(duì)偶性質(zhì)及平衡定理 （7）,從強(qiáng)對(duì)偶性知，符合平衡定理第②條時(shí)的可行解X，Y必是最優(yōu)解，于是，平衡定理為尋找線性規(guī)劃最優(yōu)解提供了一種方法。亦即，在若干個(gè)問(wèn)題的可行解X中，若是有一組解所對(duì)應(yīng)的對(duì)偶可行解，使得Xj>0所對(duì)應(yīng)的對(duì)偶約束條件為等式，則此時(shí)的解必為最優(yōu)解。[例1-4] 應(yīng)用平衡定理解下述

30、規(guī)劃,,§3 對(duì)偶性質(zhì)及平衡定理 （8）,其對(duì)偶形式為 首先令原問(wèn)題中任兩個(gè)變量為0（因有2個(gè)約束條件，這樣可求出唯一解），試探求出一組原問(wèn)題可行解。例如，令x1=x4=0，則得：,,,§3 對(duì)偶性質(zhì)及平衡定理 （9）,故此時(shí)X=(0,2,3,0)T是原問(wèn)題可行解。 為檢驗(yàn)是否為最優(yōu)解，令非零xj對(duì)應(yīng)的對(duì)偶約束為等式，求平衡解Y。即令將y1,y2值代入式(12)及式(15)，看是否滿足

31、。-5+1=-4≤12+9=11≤13全滿足，可見(jiàn)Y是符合平衡定理的對(duì)偶解，因此，X=(0,2,3,0)T及Y=(-1,1)T分別是原問(wèn)題及對(duì)偶問(wèn)題的最優(yōu)解。此時(shí)目標(biāo)函數(shù)值CTX=YTb=16。,,,,§3 對(duì)偶性質(zhì)及平衡定理 （10）,顯然，一次成功是一咱巧合。最壞情況，本例需次才能找到。當(dāng)維數(shù)增大，這種枚舉法的計(jì)算量會(huì)呈現(xiàn)指數(shù)般急劇增長(zhǎng)而變?yōu)椴滑F(xiàn)實(shí)。以后將重點(diǎn)闡述有實(shí)用價(jià)值的單純形法。,