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

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

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

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

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

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

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

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

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

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

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

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

12、原問題與對偶問題的對應(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為空集，則無符號約束（即自變量無限制）若J1=J，則所有xj≥0目標函數(shù),§2原問題與對

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

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

15、限 目標函數(shù)則相應(yīng)的對偶問題形式為 約束 Y ? 0 或不限 目標函數(shù),,,,,§3 線性規(guī)劃的規(guī)范型（3）,下面主要介紹新規(guī)范型之變換及如何寫出對偶規(guī)則。本文不加說明，規(guī)范型是指新型范型。 舉例，寫出下述線性規(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)的對偶形式為：,,,,,§4 對偶線性規(guī)劃規(guī)范型及其變換（略）,,,,,§5 線性規(guī)劃的標準型及其轉(zhuǎn)換（1）,為適應(yīng)單純形法求解，必須把線性模型變?yōu)橄率鰳藴市问剑?AX=b, X≥0, CTX=min 或

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

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

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

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

21、能性 （3）,,3．存在最優(yōu)解，但不是唯一的。例如規(guī)劃x1+x2=1x1，x2≥ox1+ x2=min 顯然 兩點連線上的所有點 都是最優(yōu)解，（見圖1-1）4．一般情況有無窮多可行解，但有唯一最優(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 移項得：2x1+x2≥4于是變?yōu)閮删S線性規(guī)劃問題，其約束可行域可用直角坐標系表示,如圖1-2。,§2 線性規(guī)劃解的求解方法之一：圖解法 （2）,圖1-2中，陰影部分為可行域，若要求出最優(yōu)點，必須作出目標函數(shù)的等值線，然后令等值線向最小值方向（即最優(yōu)方向）移動，直到離開可行域

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

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

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

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

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

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

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

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

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