管理運(yùn)籌學(xué)第3章線性規(guī)劃的對(duì)偶問(wèn)題

1、管理運(yùn)籌學(xué)管理運(yùn)籌學(xué) 第第3 3章章 管理、組織行為、運(yùn)營(yíng)管理管理、組織行為、運(yùn)營(yíng)管理 管理運(yùn)籌學(xué)、管理系統(tǒng)工程、運(yùn)營(yíng)管理管理運(yùn)籌學(xué)、管理系統(tǒng)工程、運(yùn)營(yíng)管理 經(jīng)濟(jì)學(xué)經(jīng)濟(jì)學(xué) 江蘇師范大學(xué)商學(xué)院江蘇師范大學(xué)商學(xué)院 物流管理系物流管理系 OR:SM 整理整理ppt 2 第一節(jié)第一節(jié) 線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論 第二節(jié)第二節(jié) 對(duì)偶單純形法對(duì)偶單純形法 OR:SM 整理整理ppt 3 每一個(gè)線性規(guī)劃問(wèn)題都有一個(gè)與之相伴隨的另一個(gè)問(wèn)題。每一個(gè)線性規(guī)劃問(wèn)題都有一個(gè)與之相伴隨的另一個(gè)問(wèn)題。 這兩個(gè)問(wèn)題：一是，在數(shù)學(xué)模型上有著對(duì)應(yīng)關(guān)系；二是，從這兩個(gè)問(wèn)題：一是，在數(shù)學(xué)模型上有著對(duì)應(yīng)關(guān)系；二是，從 一個(gè)

2、問(wèn)題的最優(yōu)解完全可以得出另一個(gè)問(wèn)題最優(yōu)解的全部信一個(gè)問(wèn)題的最優(yōu)解完全可以得出另一個(gè)問(wèn)題最優(yōu)解的全部信 息。息。 3.1.1 3.1.1 問(wèn)題的提出問(wèn)題的提出 例例1 引入一個(gè)資源價(jià)格問(wèn)題。引入一個(gè)資源價(jià)格問(wèn)題。 OR:SM 整理整理ppt 4 某企業(yè)生產(chǎn)甲、乙兩種某企業(yè)生產(chǎn)甲、乙兩種 產(chǎn)品，需消耗產(chǎn)品，需消耗A A、B B、C C三種材料。據(jù)市場(chǎng)分析，單位甲、乙三種材料。據(jù)市場(chǎng)分析，單位甲、乙 產(chǎn)品的銷售收益分別為產(chǎn)品的銷售收益分別為4 4萬(wàn)元和萬(wàn)元和5 5萬(wàn)元。單位甲、乙產(chǎn)品對(duì)萬(wàn)元。單位甲、乙產(chǎn)品對(duì) 材料的消耗量及材料的供應(yīng)量如表材料的消耗量及材料的供應(yīng)量如表3.13.1所示。所示。 原問(wèn)題

3、：原問(wèn)題：應(yīng)如何制定生產(chǎn)計(jì)劃，使總收益為最大。應(yīng)如何制定生產(chǎn)計(jì)劃，使總收益為最大。 表表3.13.1 產(chǎn)品材料 甲乙供應(yīng)量供應(yīng)量 A1145 B2180 C1390 收益收益4萬(wàn)元萬(wàn)元/單甲單甲5萬(wàn)元萬(wàn)元/單乙單乙 OR:SM 整理整理ppt 5 12 12 12 12 12 max( )45 45 280 s.t.(31) 390 ,0 Z xxx xx xx xx xx 設(shè)計(jì)劃安排：設(shè)計(jì)劃安排：x x1 1為甲產(chǎn)品的產(chǎn)量，為甲產(chǎn)品的產(chǎn)量， x x2 2為乙產(chǎn)品的產(chǎn)量。（決策變量）為乙產(chǎn)品的產(chǎn)量。（決策變量） 則，該問(wèn)題的數(shù)學(xué)模型為：則，該問(wèn)題的數(shù)學(xué)模型為： 12 45/ 2,45/ 2 (

4、 )405/ 2 xx Z x OR:SM 整理整理ppt 6 新問(wèn)題：新問(wèn)題：現(xiàn)在從另一角度來(lái)討論這個(gè)問(wèn)題?，F(xiàn)在從另一角度來(lái)討論這個(gè)問(wèn)題。 假設(shè)該企業(yè)經(jīng)過(guò)市場(chǎng)預(yù)測(cè)，準(zhǔn)備進(jìn)行轉(zhuǎn)產(chǎn)，且把現(xiàn)有三假設(shè)該企業(yè)經(jīng)過(guò)市場(chǎng)預(yù)測(cè)，準(zhǔn)備進(jìn)行轉(zhuǎn)產(chǎn)，且把現(xiàn)有三 種材料進(jìn)行轉(zhuǎn)讓，也恰好有一個(gè)制造商急需這批材料。于是種材料進(jìn)行轉(zhuǎn)讓，也恰好有一個(gè)制造商急需這批材料。于是 買賣雙方開始對(duì)資源的出讓價(jià)格問(wèn)題進(jìn)行磋商，希望尋找一買賣雙方開始對(duì)資源的出讓價(jià)格問(wèn)題進(jìn)行磋商，希望尋找一 個(gè)雙方都認(rèn)為比較滿意的合理價(jià)格。個(gè)雙方都認(rèn)為比較滿意的合理價(jià)格。 分析：分析：設(shè)設(shè)A、B、C三種材料的單價(jià)分別為三種材料的單價(jià)分別為y1、y2、y3

5、. 對(duì)于賣方來(lái)說(shuō)，對(duì)于賣方來(lái)說(shuō)，生產(chǎn)單位甲產(chǎn)品所獲收益為生產(chǎn)單位甲產(chǎn)品所獲收益為4萬(wàn)元，為萬(wàn)元，為 保證其總收入不少于保證其總收入不少于405/2萬(wàn)元，則將生產(chǎn)單位甲產(chǎn)品所需資萬(wàn)元，則將生產(chǎn)單位甲產(chǎn)品所需資 源轉(zhuǎn)讓出去，該企業(yè)的收入不能少于源轉(zhuǎn)讓出去，該企業(yè)的收入不能少于4萬(wàn)元。故萬(wàn)元。故y1、y2、y3必必 須滿足約束條件：須滿足約束條件： y1+2y2+y34 同樣，將生產(chǎn)單位乙產(chǎn)品所需的資源轉(zhuǎn)讓出去，其收入同樣，將生產(chǎn)單位乙產(chǎn)品所需的資源轉(zhuǎn)讓出去，其收入 不能少于生產(chǎn)單位乙產(chǎn)品的收益不能少于生產(chǎn)單位乙產(chǎn)品的收益5萬(wàn)元，所以萬(wàn)元，所以y1、y2、y3還必還必 須滿足約束條件：須滿足約束條件

6、： y1+y2+3y35 OR:SM 整理整理ppt 7 對(duì)于買方來(lái)說(shuō)，對(duì)于買方來(lái)說(shuō)，他希望在滿足上述約束條件下使總的他希望在滿足上述約束條件下使總的 支出支出 W（y） =45y1+80y2+90y3 達(dá)到最小。達(dá)到最小。 綜上所述，資源價(jià)格問(wèn)題的數(shù)學(xué)模型可描述為：綜上所述，資源價(jià)格問(wèn)題的數(shù)學(xué)模型可描述為： 123 123 123 123 min( )458090 24 s.t.35(32) ,0 W yyyy yyy yyy yyy 上述兩個(gè)模型（上述兩個(gè)模型（3-1）和（）和（3-2）是對(duì)同一問(wèn)題的兩種不）是對(duì)同一問(wèn)題的兩種不 同考慮的數(shù)學(xué)描述，其間有著一定的內(nèi)在聯(lián)系，將逐一剖同考慮的數(shù)

7、學(xué)描述，其間有著一定的內(nèi)在聯(lián)系，將逐一剖 析。析。 OR:SM 整理整理ppt 8 首先，分析這兩個(gè)模型之間的對(duì)應(yīng)關(guān)系：首先，分析這兩個(gè)模型之間的對(duì)應(yīng)關(guān)系： （1 1）一個(gè)問(wèn)題的目標(biāo)函數(shù)為極大化，約束條件為）一個(gè)問(wèn)題的目標(biāo)函數(shù)為極大化，約束條件為“”類類 型，另一個(gè)問(wèn)題的目標(biāo)為極小化，約束條件為型，另一個(gè)問(wèn)題的目標(biāo)為極小化，約束條件為“”類型；類型； （2 2）一個(gè)問(wèn)題的變量個(gè)數(shù)等于另一個(gè)問(wèn)題的約束條件個(gè)）一個(gè)問(wèn)題的變量個(gè)數(shù)等于另一個(gè)問(wèn)題的約束條件個(gè) 數(shù)；數(shù)； （3 3）一個(gè)問(wèn)題的右端常數(shù)（約束系數(shù)）是另一個(gè)問(wèn)題的）一個(gè)問(wèn)題的右端常數(shù)（約束系數(shù)）是另一個(gè)問(wèn)題的 目標(biāo)函數(shù)的系數(shù)（成本系數(shù)）；目標(biāo)

8、函數(shù)的系數(shù)（成本系數(shù)）； （4 4）兩個(gè)問(wèn)題的系數(shù)矩陣互為轉(zhuǎn)置。）兩個(gè)問(wèn)題的系數(shù)矩陣互為轉(zhuǎn)置。 我們把這種對(duì)應(yīng)關(guān)系稱為我們把這種對(duì)應(yīng)關(guān)系稱為對(duì)偶關(guān)系對(duì)偶關(guān)系。如果把（。如果把（3-13-1）稱為）稱為 原始問(wèn)題，則（原始問(wèn)題，則（3-23-2）稱為對(duì)偶問(wèn)題。）稱為對(duì)偶問(wèn)題。 OR:SM 整理整理ppt 9 3.1.2 3.1.2 對(duì)稱型線性規(guī)劃問(wèn)題對(duì)稱型線性規(guī)劃問(wèn)題對(duì)稱型對(duì)偶問(wèn)題對(duì)稱型對(duì)偶問(wèn)題 每一個(gè)線性規(guī)劃問(wèn)題都必然有與之相伴隨的對(duì)偶問(wèn)每一個(gè)線性規(guī)劃問(wèn)題都必然有與之相伴隨的對(duì)偶問(wèn) 題存在。先討論對(duì)稱型對(duì)偶問(wèn)題；對(duì)于非對(duì)稱型對(duì)偶問(wèn)題存在。先討論對(duì)稱型對(duì)偶問(wèn)題；對(duì)于非對(duì)稱型對(duì)偶問(wèn) 題，可以先轉(zhuǎn)化

9、為對(duì)稱型，然后再進(jìn)行分析，也可以直題，可以先轉(zhuǎn)化為對(duì)稱型，然后再進(jìn)行分析，也可以直 接從非對(duì)稱型進(jìn)行分析。接從非對(duì)稱型進(jìn)行分析。 對(duì)稱型線性規(guī)劃問(wèn)題對(duì)稱型線性規(guī)劃問(wèn)題數(shù)學(xué)模型的一般形式為數(shù)學(xué)模型的一般形式為 1122 11112211 21122222 1122 12 max( ) s.t.(33) ,0 nn nn nn mmmnnm n Z xc xc xc x a xa xa xb a xa xaxb axaxaxb x xx Y1 Y2 ym OR:SM 整理整理ppt 10 這種模型的特點(diǎn)是：這種模型的特點(diǎn)是： （1 1）目標(biāo)函數(shù)是最大化類型）目標(biāo)函數(shù)是最大化類型( (或是最小化類型

10、或是最小化類型) )； （2 2）所有約束條件都是）所有約束條件都是“”型（或都是型（或都是“”型）；型）； （3 3）所有決策變量都是非負(fù)的。）所有決策變量都是非負(fù)的。 如果把（如果把（3-33-3）作為原始問(wèn)題，根據(jù)原始與對(duì)偶問(wèn)題）作為原始問(wèn)題，根據(jù)原始與對(duì)偶問(wèn)題 的對(duì)應(yīng)關(guān)系可得（的對(duì)應(yīng)關(guān)系可得（3-33-3）的對(duì)偶問(wèn)題為）的對(duì)偶問(wèn)題為 1122 11121211 12122222 1122 12 min( ) s.t.(34) ,0 mm mm mm nnmnmn m W yb yb yb y a ya ya yc a ya yayc a ya yayc y yy OR:SM 整理整理p

11、pt 11 用矩陣表示的原始問(wèn)題（用矩陣表示的原始問(wèn)題（3-33-3）和對(duì)偶問(wèn)題（）和對(duì)偶問(wèn)題（3-43-4）為）為 其中其中Y=Y=（y y1 1,y,y2 2, ,y,ym m）, ,其它同前其它同前。 3.1.3 3.1.3 一般問(wèn)題的對(duì)偶問(wèn)題一般問(wèn)題的對(duì)偶問(wèn)題非對(duì)稱型對(duì)偶問(wèn)題非對(duì)稱型對(duì)偶問(wèn)題 線性規(guī)劃有時(shí)以非對(duì)稱型出現(xiàn)，那么如何從原始問(wèn)題寫線性規(guī)劃有時(shí)以非對(duì)稱型出現(xiàn)，那么如何從原始問(wèn)題寫 出它的對(duì)偶問(wèn)題呢？出它的對(duì)偶問(wèn)題呢？ max( ) s.t. 0 Z xCX AXb X min( ) s.t. 0 WyYb YAC Y OR:SM 整理整理ppt 12 例例1 寫出下列線性規(guī)劃的

12、對(duì)偶問(wèn)題寫出下列線性規(guī)劃的對(duì)偶問(wèn)題 23 13 123 123 123 m ax()25 2 266 s.t. 30 ,0 Zxxx xx xxx xxx xxx OR:SM 整理整理ppt 13 轉(zhuǎn)換成轉(zhuǎn)換成對(duì)稱型對(duì)稱型 123 123 123 123 123 123 m ax()025 02 266 s.t.30 30 ,0 Zxxxx xxx xxx xxx xxx xxx Y1 Y2 Y/3 y/3 3 3 / 1233 / 1233 / 123 / 1233 / 123 min( )2600 20 02 s.t. 6335 ,0 Wyyyyy yyyy yyyy yyyy yyyy

13、OR:SM 整理整理ppt 14 再設(shè)再設(shè)y y/ /3 3-y-y/ /3 3=y =y3 3，代入上述模型得，代入上述模型得： 123 123 123 123 123 min( )260 20 02 s.t. 635 ,0;? Wyyyy yyy yyy yyy yyy OR:SM 整理整理ppt 15 例例2 2 將例將例1 1模型中的模型中的x x2 2改為無(wú)非負(fù)約束變量，即模型為改為無(wú)非負(fù)約束變量，即模型為 寫出其對(duì)偶問(wèn)題寫出其對(duì)偶問(wèn)題 23 13 123 123 132 m ax( )25 2 266 s.t. 30 ,0;? Zxxx xx xxx xxx xxx OR:SM 整

14、理整理ppt 16 令令x2=x 2-x2. .其中 其中x 2,x20 轉(zhuǎn)換成轉(zhuǎn)換成對(duì)稱型對(duì)稱型 2 2 2 / / 123 / / 123 / / 1223 / / 1223 / / 1223 / / 123 m ax()0225 002 266 s.t.30 30 ,0 Zxxxxx xxxx xxxx xxxx xxxx xxxx Y1 Y2 Y/3 y/3 OR:SM 整理整理ppt 17 3 3 / 1233 / 1233 / 123 / 1233 / 1233 / 123 min( )2600 20 02 s.t. 02 6335 ,0 W yyyyy yyyy yyyy yyy

15、y yyyy yyyy 123 123 123 123 123 min( )260 20 02 s.t. 635 ,0,? Wyyyy yyy yyy yyy yyy OR:SM 整理整理ppt 18 綜合上述兩個(gè)例子，可以看出，線性規(guī)劃與其對(duì)偶模型綜合上述兩個(gè)例子，可以看出，線性規(guī)劃與其對(duì)偶模型 的關(guān)系有了新的拓展：的關(guān)系有了新的拓展： （1 1）一個(gè)問(wèn)題的目標(biāo)函數(shù)為極大化，約束條件為）一個(gè)問(wèn)題的目標(biāo)函數(shù)為極大化，約束條件為“”或或 “= =”類型，另一個(gè)問(wèn)題的目標(biāo)為極小化，約束條件為類型，另一個(gè)問(wèn)題的目標(biāo)為極小化，約束條件為“”或或 “= =”類型；類型； （2 2）一個(gè)問(wèn)題的變量個(gè)數(shù)等于

16、另一個(gè)問(wèn)題的約束條件個(gè)）一個(gè)問(wèn)題的變量個(gè)數(shù)等于另一個(gè)問(wèn)題的約束條件個(gè) 數(shù)；數(shù)； （3 3）一個(gè)問(wèn)題的右端常數(shù)（約束系數(shù)）是另一個(gè)問(wèn)題的）一個(gè)問(wèn)題的右端常數(shù)（約束系數(shù)）是另一個(gè)問(wèn)題的 目標(biāo)函數(shù)的系數(shù)（成本系數(shù)）；目標(biāo)函數(shù)的系數(shù)（成本系數(shù)）； （4 4）兩個(gè)問(wèn)題的系數(shù)矩陣互為轉(zhuǎn)置）兩個(gè)問(wèn)題的系數(shù)矩陣互為轉(zhuǎn)置; ; （5 5）一個(gè)問(wèn)題的第）一個(gè)問(wèn)題的第i i個(gè)約束為個(gè)約束為“= =”，則另一個(gè)問(wèn)題的第，則另一個(gè)問(wèn)題的第i i 個(gè)變量為個(gè)變量為“無(wú)非負(fù)約束變量無(wú)非負(fù)約束變量”（自由變量）。反之，一個(gè)問(wèn)（自由變量）。反之，一個(gè)問(wèn) 題的第題的第i i個(gè)變量為個(gè)變量為“無(wú)非負(fù)約束變量無(wú)非負(fù)約束變量”，則另一

17、個(gè)問(wèn)題的第，則另一個(gè)問(wèn)題的第i i 個(gè)約束為個(gè)約束為“= =”（方程）。（方程）。 OR:SM 整理整理ppt 19 原始問(wèn)題原始問(wèn)題(或?qū)ε紗?wèn)題或?qū)ε紗?wèn)題)對(duì)偶問(wèn)題對(duì)偶問(wèn)題(或原問(wèn)題或原問(wèn)題) 目標(biāo)目標(biāo) max 目標(biāo)目標(biāo) min 變量變量 n個(gè)個(gè) 約束約束 n個(gè)個(gè) 變量變量 0 0 無(wú)非負(fù)約束無(wú)非負(fù)約束 約束約束 =（方程）（方程） 約束約束 m個(gè)個(gè) 變量變量 m個(gè)個(gè) 約束約束 = （方程）（方程） 變量變量 0 0 無(wú)非負(fù)約束無(wú)非負(fù)約束 系數(shù)矩陣系數(shù)矩陣 b c 轉(zhuǎn)置轉(zhuǎn)置 c b OR:SM 整理整理ppt 20 這樣對(duì)于任意給定的一個(gè)線性規(guī)劃問(wèn)題，均可依據(jù)上述這樣對(duì)于任意給定的一個(gè)線性規(guī)

18、劃問(wèn)題，均可依據(jù)上述 對(duì)應(yīng)關(guān)系對(duì)應(yīng)關(guān)系直接寫出其對(duì)偶問(wèn)題模型直接寫出其對(duì)偶問(wèn)題模型，而無(wú)須先化成對(duì)稱型。，而無(wú)須先化成對(duì)稱型。 例例3 3 寫出下列線性規(guī)劃的對(duì)偶問(wèn)題寫出下列線性規(guī)劃的對(duì)偶問(wèn)題 123 123 123 123 123 m ax()2 2 1 s.t. 22 0;,? Zxxxx xxx xxx xxx xxx 解：解：因目標(biāo)函數(shù)為因目標(biāo)函數(shù)為“maxmax”類型，則約束條件應(yīng)為類型，則約束條件應(yīng)為“”和和 “= =”類型，故只需改變第三個(gè)約束條件的不等號(hào)方向，類型，故只需改變第三個(gè)約束條件的不等號(hào)方向， 即有：即有： 123 22xxx OR:SM 整理整理ppt 21 這樣所

19、有的約束條件均為這樣所有的約束條件均為“”和和“=”類型，按前述對(duì)類型，按前述對(duì) 應(yīng)關(guān)系原則，可寫出其對(duì)偶問(wèn)題為：應(yīng)關(guān)系原則，可寫出其對(duì)偶問(wèn)題為： 123 123 123 123 132 min( )22 21 2 s.t. 1 ,0,? W yyyy yyy yyy yyy yyy 123 123 123 123 123 m ax()2 2 1 s.t. 22 0;,? Zxxxx xxx xxx xxx xxx Y1 Y2 Y3 OR:SM 整理整理ppt 22 3.1.4 對(duì)偶問(wèn)題的基本性質(zhì)對(duì)偶問(wèn)題的基本性質(zhì) 設(shè)原始問(wèn)題為：設(shè)原始問(wèn)題為： 則其對(duì)偶問(wèn)題為：則其對(duì)偶問(wèn)題為： 1 1、對(duì)稱性

20、定理、對(duì)稱性定理 對(duì)偶問(wèn)題的對(duì)偶是原始問(wèn)題。對(duì)偶問(wèn)題的對(duì)偶是原始問(wèn)題。 根據(jù)對(duì)偶規(guī)劃，很容易寫出對(duì)偶問(wèn)題的對(duì)偶模型。根據(jù)對(duì)偶規(guī)劃，很容易寫出對(duì)偶問(wèn)題的對(duì)偶模型。 max( ),0(35)Z xCX AXb X min( ),0(36)W yYb YAC Y 2、對(duì)偶性定理、對(duì)偶性定理 若原問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解，而且兩者的若原問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解，而且兩者的 目標(biāo)函數(shù)值相等。目標(biāo)函數(shù)值相等。 OR:SM 整理整理ppt 23 3.1.5 對(duì)偶問(wèn)題的最優(yōu)解對(duì)偶問(wèn)題的最優(yōu)解 重要推論：重要推論： 1.1.原始問(wèn)題單純形表中松馳變量的檢驗(yàn)數(shù)恰好對(duì)應(yīng)著對(duì)原始問(wèn)題單純形表中

21、松馳變量的檢驗(yàn)數(shù)恰好對(duì)應(yīng)著對(duì) 偶問(wèn)題的一個(gè)解。偶問(wèn)題的一個(gè)解。 2.2.原始問(wèn)題單純形表中原始問(wèn)題單純形表中, ,原始問(wèn)題的松弛變量的檢驗(yàn)數(shù)對(duì)原始問(wèn)題的松弛變量的檢驗(yàn)數(shù)對(duì) 應(yīng)于對(duì)偶問(wèn)題的決策變量應(yīng)于對(duì)偶問(wèn)題的決策變量; ;而原始問(wèn)題的決策變量的檢驗(yàn)數(shù)對(duì)而原始問(wèn)題的決策變量的檢驗(yàn)數(shù)對(duì) 應(yīng)于對(duì)偶問(wèn)題的松弛變量應(yīng)于對(duì)偶問(wèn)題的松弛變量, ,只是只是符號(hào)相反符號(hào)相反。 注意：注意：在兩個(gè)互為對(duì)偶的線性規(guī)劃問(wèn)題中，可任選一個(gè)進(jìn)行在兩個(gè)互為對(duì)偶的線性規(guī)劃問(wèn)題中，可任選一個(gè)進(jìn)行 求解，通常是選擇約束條件少的，因求解的工作量主要受到求解，通常是選擇約束條件少的，因求解的工作量主要受到 約束條件個(gè)數(shù)的影響。約束條

22、件個(gè)數(shù)的影響。 OR:SM 整理整理ppt 24 例例4 求解下列線性規(guī)劃問(wèn)題求解下列線性規(guī)劃問(wèn)題 解：解：該問(wèn)題僅有兩個(gè)變量，但約束較多，其對(duì)偶問(wèn)題為該問(wèn)題僅有兩個(gè)變量，但約束較多，其對(duì)偶問(wèn)題為 12 1 2 12 12 2 12 m a x()43 6 8 7 s .t .( 37 ) 31 5 1 ,0 Zxxx x x xx xx x xx 12345 134 2345 125 min( )68715 34 s.t.3(3 8) ,0 W yyyyyy yyy yyyy y yy Y1 Y2 Y3 Y4 Y5 OR:SM 整理整理ppt 25 把上述問(wèn)題（把上述問(wèn)題（3-83-8）作為

23、原始問(wèn)題求解，其最終單純形表見下）作為原始問(wèn)題求解，其最終單純形表見下 表（表（3.33.3） 由表（由表（3.33.3）得其最優(yōu)解為：）得其最優(yōu)解為： 例例4 4的最優(yōu)解可直接從表（的最優(yōu)解可直接從表（3.33.3）的松弛變量）的松弛變量y y6、y y7的檢驗(yàn)數(shù)中的檢驗(yàn)數(shù)中 讀出，即有：讀出，即有： -6 -8 -7 -15 -1 0 0 Y1 y2 y3 y4 y5 Y6 y7 -15y41/2 1/2 -1/2 0 1 1/2-1/2 1/2 -7y35/2-1/2 3/2 1 0 -3/2 1/2 -3/2 j -2 -5 0 0 -4 -4 -3 51 (0,0,0,0,0) 22

24、 51 ()71525 22 T Y W Y (4,3,2,5,0,0,4) ()443325 T X Z X OR:SM 整理整理ppt 26 第一章中的單純形法，是從線性規(guī)劃標(biāo)準(zhǔn)型的一個(gè)基本第一章中的單純形法，是從線性規(guī)劃標(biāo)準(zhǔn)型的一個(gè)基本 可行解出發(fā)，逐步迭代，使目標(biāo)函數(shù)值不斷改進(jìn)，直到取得可行解出發(fā)，逐步迭代，使目標(biāo)函數(shù)值不斷改進(jìn)，直到取得 最優(yōu)解為止。在運(yùn)算過(guò)程中，必須保證解的可行性，即在單最優(yōu)解為止。在運(yùn)算過(guò)程中，必須保證解的可行性，即在單 純形表中，始終有常數(shù)項(xiàng)純形表中，始終有常數(shù)項(xiàng)b b/ /00。當(dāng)最優(yōu)性條件。當(dāng)最優(yōu)性條件j j0 0得到滿得到滿 足時(shí)，迭代終止，這時(shí)原始問(wèn)題和

25、對(duì)偶問(wèn)題同時(shí)達(dá)到最優(yōu)。足時(shí)，迭代終止，這時(shí)原始問(wèn)題和對(duì)偶問(wèn)題同時(shí)達(dá)到最優(yōu)。 單純形法的實(shí)質(zhì)單純形法的實(shí)質(zhì)保證解的可行性（常數(shù)項(xiàng)保證解的可行性（常數(shù)項(xiàng)b b/ /00）, , 通過(guò)逐步迭代，達(dá)到最優(yōu)性條件（通過(guò)逐步迭代，達(dá)到最優(yōu)性條件（j j0 0 ）。）。 考慮到原始和對(duì)偶問(wèn)題的對(duì)稱性，在求解方法上換一角考慮到原始和對(duì)偶問(wèn)題的對(duì)稱性，在求解方法上換一角 度，即在運(yùn)算過(guò)程中，始終保持其對(duì)偶問(wèn)題解的可行性。也度，即在運(yùn)算過(guò)程中，始終保持其對(duì)偶問(wèn)題解的可行性。也 即在單純形表中，始終保證最優(yōu)性條件（即在單純形表中，始終保證最優(yōu)性條件（j j0 0 ），而原始），而原始 問(wèn)題的解未必可行（常數(shù)項(xiàng)問(wèn)題的

26、解未必可行（常數(shù)項(xiàng) ）。）。 / b 0 OR:SM 整理整理ppt 27 通過(guò)逐步迭代，當(dāng)通過(guò)逐步迭代，當(dāng)b b/ /0 0 時(shí)，終止迭代，這時(shí)原始時(shí)，終止迭代，這時(shí)原始 問(wèn)題和對(duì)偶問(wèn)題同時(shí)達(dá)到最優(yōu)。這種方法稱之為對(duì)偶單問(wèn)題和對(duì)偶問(wèn)題同時(shí)達(dá)到最優(yōu)。這種方法稱之為對(duì)偶單 純形法。純形法。 對(duì)偶單純形法的實(shí)質(zhì)對(duì)偶單純形法的實(shí)質(zhì)保證最優(yōu)性條件（保證最優(yōu)性條件（j j0 0），）， 通過(guò)逐步迭代，達(dá)到解的可行性（常數(shù)項(xiàng)通過(guò)逐步迭代，達(dá)到解的可行性（常數(shù)項(xiàng)b b/ /0 0 ）。）。 OR:SM 整理整理ppt 28 3.2.1 3.2.1 對(duì)偶單純形法的運(yùn)算步驟對(duì)偶單純形法的運(yùn)算步驟 單純形法的運(yùn)算

27、思路單純形法的運(yùn)算思路: :先從非基變量中確定進(jìn)基變量先從非基變量中確定進(jìn)基變量, ,再再 從基變量中選擇出基變量從基變量中選擇出基變量( (大進(jìn)大進(jìn)-小出小出);); 對(duì)偶單純形法的運(yùn)算思路對(duì)偶單純形法的運(yùn)算思路: :先從基變量中確定出基變量先從基變量中確定出基變量, , 再?gòu)姆腔兞恐羞x擇進(jìn)基變量再?gòu)姆腔兞恐羞x擇進(jìn)基變量( (小出小出-小進(jìn)小進(jìn)).). 具體計(jì)算步驟如下具體計(jì)算步驟如下: : (1) (1)根據(jù)線性規(guī)劃模型根據(jù)線性規(guī)劃模型, ,列出初始單純形表列出初始單純形表, ,但需保證所有但需保證所有 檢驗(yàn)數(shù)檢驗(yàn)數(shù)j j0 .0 . (2) (2)檢驗(yàn)檢驗(yàn). .若常數(shù)項(xiàng)若常數(shù)項(xiàng)b b

28、/ /0 ,0 ,則得到最優(yōu)解則得到最優(yōu)解, ,停止運(yùn)算停止運(yùn)算; ;否則否則 轉(zhuǎn)下步轉(zhuǎn)下步. . OR:SM 整理整理ppt 29 (3) (3)基變換基變換: : 確定出基變量。在確定出基變量。在b b/ /列中，將所有負(fù)值進(jìn)行比較，其列中，將所有負(fù)值進(jìn)行比較，其 中最小的一個(gè)分量所對(duì)應(yīng)的變量為出基變量（中最小的一個(gè)分量所對(duì)應(yīng)的變量為出基變量（小出小出）；）； 確定進(jìn)基變量。根據(jù)確定進(jìn)基變量。根據(jù) ， 對(duì)應(yīng)列的非基變量對(duì)應(yīng)列的非基變量x xk k為進(jìn)基變量為進(jìn)基變量( (小進(jìn)小進(jìn)) )。 迭代運(yùn)算與檢驗(yàn)。以迭代運(yùn)算與檢驗(yàn)。以 為主元素，按單純形法進(jìn)為主元素，按單純形法進(jìn) 行迭代計(jì)算，得到新

29、的單純形表，再返回到（行迭代計(jì)算，得到新的單純形表，再返回到（2 2）檢驗(yàn)。）檢驗(yàn)。 / / min0 j k sj sjsk a aa / s k a OR:SM 整理整理ppt 30 例例7 用對(duì)偶單純形法求線性規(guī)劃問(wèn)題用對(duì)偶單純形法求線性規(guī)劃問(wèn)題 解：首先將問(wèn)題化成標(biāo)準(zhǔn)型，得解：首先將問(wèn)題化成標(biāo)準(zhǔn)型，得 123 123 123 123 min( )458090 24 s.t.35 ,0 W yyyy yyy yyy yyy 123 1234 1235 12345 max( )458090 24 s.t.35 ,0 W yyyy yyyy yyyy y yyyy OR:SM 整理整理ppt 31 將約束條件兩端（將約束條件兩端（-1-1