資源描述：
《對(duì)偶問(wèn)題和對(duì)偶單純形法》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第七章對(duì)偶問(wèn)題和對(duì)偶單純形法一、問(wèn)題的提出二、對(duì)偶問(wèn)題和原問(wèn)題的轉(zhuǎn)換三、對(duì)偶規(guī)劃的性質(zhì)四、對(duì)偶單純形法五、交替單純形法一、問(wèn)題的提出原問(wèn)題：a和b產(chǎn)量各為多少可以使利潤(rùn)最大？25010C40012B30011A資源限量ba產(chǎn)品設(shè)備10050利潤(rùn)一、問(wèn)題的提出原LP模型：Maxz=50x1+100x2s.t：1·x1+1·x2≤300 2·x1+1·x2≤400 0·x1+1·x2≤250 x1≥0，x2≥0一、問(wèn)題的提出若考慮將三種設(shè)備出租，如何合理確定各設(shè)備的租金y1、y2、y3（元/臺(tái)時(shí)）？目標(biāo)函數(shù)：minz=30
2、0y1+400y2+250y3約束條件：y1+2y2≥50y1+y2+y3≥100y1、y2、y3≥0一、問(wèn)題的提出這樣兩個(gè)線(xiàn)性規(guī)劃問(wèn)題就是一對(duì)對(duì)偶問(wèn)題。稱(chēng)其中一個(gè)為原問(wèn)題（LP問(wèn)題），另一個(gè)為對(duì)偶問(wèn)題（DLP問(wèn)題）。由于它們內(nèi)在的聯(lián)系，可以根據(jù)其中一個(gè)模型，寫(xiě)出其對(duì)偶問(wèn)題的模型。二、對(duì)偶問(wèn)題和原問(wèn)題的轉(zhuǎn)換LP問(wèn)題和DLP問(wèn)題的關(guān)系：規(guī)范形(LP)Maxz=cTxs.t.Ax≤bx≥0(DLP)Minf=bTys.t.ATy≥cy≥0二、對(duì)偶問(wèn)題和原問(wèn)題的轉(zhuǎn)換1、對(duì)于規(guī)范型，直接按對(duì)應(yīng)關(guān)系轉(zhuǎn)換例：Maxz=20x1+8
3、x2+6x3s.t：8x1+3x2+2x3≤250 2x1+x2≤50 4x1+3x3≤150 x1，x2，x3≥0寫(xiě)出該線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題。二、對(duì)偶問(wèn)題和原問(wèn)題的轉(zhuǎn)換則對(duì)偶問(wèn)題為：Minf=250y1+50y2+150y3s.t：8y1+2y2+4y3≥203y1+y2≥82y1+3y3≥6y1，y2，y3≥0二、對(duì)偶問(wèn)題和原問(wèn)題的轉(zhuǎn)換2、對(duì)于非規(guī)范形式，先化為規(guī)范形式例：寫(xiě)出線(xiàn)性規(guī)劃模型的對(duì)偶問(wèn)題Minz=3x1+4x2+6x3s.t：x1+3x2-2x3+x4＝252x1+7x3+2x4≥602x1+2x2-
4、4x3≤30x1，x2，x4≥0，x3無(wú)非負(fù)約束二、對(duì)偶問(wèn)題和原問(wèn)題的轉(zhuǎn)換首先轉(zhuǎn)換為規(guī)范形Minz=3x1+4x2+6x3變?yōu)镸ax(-z)=-3x1-4x2-6x3約束條件x1+3x2-2x3+x4＝25等同于x1+3x2-2x3+x4≤25和x1+3x2-2x3+x4≥25聯(lián)立二、對(duì)偶問(wèn)題和原問(wèn)題的轉(zhuǎn)換2x1+7x3+2x4≥60可轉(zhuǎn)化為-2x1-7x3-2x4≤-60x3無(wú)非負(fù)約束，則令x3＝x3’-x3’’x3’-x3’’≥0則原LP模型可以化為規(guī)范形：二、對(duì)偶問(wèn)題和原問(wèn)題的轉(zhuǎn)換Max(-z)=-3x1-4x2
5、-6x3’+6x3’’s.t：x1+3x2-2x3’+2x3’’+x4≤25-x1-3x2+2x3’-2x3’’-x4≤-25-2x1-7x3’+7x3’’-2x4≤-602x1+2x2-4x3’+4x3’’≤30x1,x2,x3’,x3’’,x4≥0二、對(duì)偶問(wèn)題和原問(wèn)題的轉(zhuǎn)換故DLP可寫(xiě)出：Minf＝25y1-25y2-60y3+30y4s.t：y1-y2-2y3+2y4≥-33y1-3y2+2y4≥-4-2y1+2y2-7y3-4y4≥-62y1-2y2+7y3+4y4≥6y1-y2-2y3≥0y1，y2，y3，y
6、4，y5≥0二、對(duì)偶問(wèn)題和原問(wèn)題的轉(zhuǎn)換將DLP模型整理可得：Minf＝25y5+60y3+30y4s.t：y5+2y3+2y4≥-33y5+2y4≥-4-2y5+7y3-4y4＝-6y5+2y3≥0y5無(wú)非負(fù)約束，y3≤0，y4≥0LP與DLP的一般對(duì)應(yīng)關(guān)系原問(wèn)題LP對(duì)偶問(wèn)題DLP目標(biāo)函數(shù)maxzminf目標(biāo)函數(shù)變量xj（j＝1，2……n）n個(gè)n個(gè)約束條件j（j＝1，2……n）≥0≥≤0≤無(wú)約束＝約束條件i（i＝1，2……m）m個(gè)m個(gè)變量yj（i＝1，2……m）≤≥0≥≤0＝無(wú)約束目標(biāo)函數(shù)變量的系數(shù)cj（j＝1，2……
7、n）約束條件右端項(xiàng)cjT（j＝1，2……n）約束條件右端項(xiàng)bi（i＝1，2……m）目標(biāo)函數(shù)變量的系數(shù)biT（i＝1，2……m）練習(xí)寫(xiě)出下面LP問(wèn)題的DLP模型Minz=x1+2x2+5x3s.t：2x1+3x2+x3＝103x1+x2+x3≥50x1+x3≤20x1≥0，x2≤0，x3無(wú)非負(fù)約束三、對(duì)偶規(guī)劃的性質(zhì)1、對(duì)稱(chēng)性：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。2、弱對(duì)偶性：若X是原問(wèn)題（max）的可行解，Y是對(duì)偶問(wèn)題（min）的可行解，則存在CX≤bTY三、對(duì)偶規(guī)劃的性質(zhì)推論a：原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的
8、下界；反之對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界。推論b：若原問(wèn)題解無(wú)界，則其對(duì)偶問(wèn)題無(wú)可行解；若對(duì)偶問(wèn)題解無(wú)界，則原問(wèn)題無(wú)可行解。（逆命題不成立）推論c：若原問(wèn)題有可行解而對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題無(wú)界；反之，對(duì)偶問(wèn)題有可行解而原問(wèn)題無(wú)可行解，則對(duì)偶問(wèn)題解無(wú)界。三、對(duì)偶規(guī)劃的性質(zhì)3、最優(yōu)性：若x,y分別是原問(wèn)題
