運(yùn)籌學(xué)：第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析

1、 基可行解的概念和幾何意義基可行解的概念和幾何意義 單純形法的原理步驟單純形法的原理步驟 單純形表的原理和結(jié)構(gòu)單純形表的原理和結(jié)構(gòu) 大大M法的原理和步驟法的原理和步驟 Min型單純形表計(jì)算方法型單純形表計(jì)算方法對(duì)偶理論是對(duì)偶理論是LP的重要基礎(chǔ)理論，它揭示了：每一個(gè)的重要基礎(chǔ)理論，它揭示了：每一個(gè)LP都存在與它對(duì)偶的一個(gè)都存在與它對(duì)偶的一個(gè)LP，二者之間有密切的聯(lián)系，以，二者之間有密切的聯(lián)系，以至于把二者放在一起研究往往比單獨(dú)研究一個(gè)問(wèn)題更有至于把二者放在一起研究往往比單獨(dú)研究一個(gè)問(wèn)題更有意義意義 線性規(guī)劃的對(duì)偶模型線性規(guī)劃的對(duì)偶模型 對(duì)偶性質(zhì)對(duì)偶性質(zhì) 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格對(duì)偶問(wèn)題的經(jīng)濟(jì)

2、解釋影子價(jià)格 對(duì)偶單純形法對(duì)偶單純形法 靈敏度分析靈敏度分析設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備按種設(shè)備按A，B，C，D順序加工，每件產(chǎn)品加工所需的機(jī)時(shí)數(shù)、每件產(chǎn)品的利潤(rùn)順序加工，每件產(chǎn)品加工所需的機(jī)時(shí)數(shù)、每件產(chǎn)品的利潤(rùn)值及每種設(shè)備的可利用機(jī)時(shí)數(shù)列于下表值及每種設(shè)備的可利用機(jī)時(shí)數(shù)列于下表 ：產(chǎn)品數(shù)據(jù)表產(chǎn)品數(shù)據(jù)表 設(shè)備設(shè)備產(chǎn)品產(chǎn)品ABCD產(chǎn)品利潤(rùn)產(chǎn)品利潤(rùn)（元件）（元件） 甲甲 21402乙乙 22043設(shè)備可利用設(shè)備可利用機(jī)時(shí)數(shù)（時(shí)）機(jī)時(shí)數(shù)（時(shí)） 1281612問(wèn)：充分利用設(shè)備機(jī)時(shí)，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能問(wèn)：充分利用設(shè)備機(jī)時(shí)，工廠應(yīng)生產(chǎn)甲和

3、乙型產(chǎn)品各多少件才能獲得最大利潤(rùn)？獲得最大利潤(rùn)？1. 解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及及x2件，則數(shù)學(xué)模型為：件，則數(shù)學(xué)模型為： 0,124164821222.32max2121212121xxxxxxxxtsxxz若廠長(zhǎng)決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機(jī)器用于接受外若廠長(zhǎng)決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機(jī)器用于接受外加工，只收加工費(fèi)，那么種機(jī)器的機(jī)時(shí)如何定價(jià)才是最佳加工，只收加工費(fèi)，那么種機(jī)器的機(jī)時(shí)如何定價(jià)才是最佳決策？決策？在市場(chǎng)競(jìng)爭(zhēng)的時(shí)代，廠長(zhǎng)的最佳決策顯然應(yīng)符合兩條：在市場(chǎng)競(jìng)爭(zhēng)的時(shí)代，廠長(zhǎng)的最佳決策顯然應(yīng)符合兩條：（1）不吃虧原則。即機(jī)時(shí)定價(jià)所賺利潤(rùn)不能低于加工甲

4、、乙型）不吃虧原則。即機(jī)時(shí)定價(jià)所賺利潤(rùn)不能低于加工甲、乙型產(chǎn)品所獲利潤(rùn)。由此原則，便構(gòu)成了新規(guī)劃的不等式約束條件。產(chǎn)品所獲利潤(rùn)。由此原則，便構(gòu)成了新規(guī)劃的不等式約束條件。 （2）競(jìng)爭(zhēng)性原則。即在上述不吃虧原則下，盡量降低機(jī)時(shí)總收）競(jìng)爭(zhēng)性原則。即在上述不吃虧原則下，盡量降低機(jī)時(shí)總收費(fèi)，以便爭(zhēng)取更多用戶。費(fèi)，以便爭(zhēng)取更多用戶。設(shè)設(shè)A、B、C、D設(shè)備的機(jī)時(shí)價(jià)分別為設(shè)備的機(jī)時(shí)價(jià)分別為y1、y2、y3、y4，則新的線性，則新的線性規(guī)劃數(shù)學(xué)模型為：規(guī)劃數(shù)學(xué)模型為： 0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy把同種問(wèn)題的兩種提法所獲得的數(shù)

5、學(xué)模型用表把同種問(wèn)題的兩種提法所獲得的數(shù)學(xué)模型用表2表示，將會(huì)發(fā)表示，將會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象。現(xiàn)一個(gè)有趣的現(xiàn)象。原問(wèn)題與對(duì)偶問(wèn)題對(duì)比表原問(wèn)題與對(duì)偶問(wèn)題對(duì)比表A（y1） B（y2）C（y3） D（y4） 甲（甲（x1） 21402乙（乙（x2） 220431281612 min max z 對(duì)偶性是線性規(guī)劃問(wèn)題的最重要的內(nèi)容之一。每一個(gè)線性規(guī)劃（對(duì)偶性是線性規(guī)劃問(wèn)題的最重要的內(nèi)容之一。每一個(gè)線性規(guī)劃（ LP ）必然有與之相伴而生的另一個(gè)線性規(guī)劃問(wèn)題，即任何一個(gè)求必然有與之相伴而生的另一個(gè)線性規(guī)劃問(wèn)題，即任何一個(gè)求 maxZ 的的LP都都有一個(gè)求有一個(gè)求 minZ 的的LP。其中的一個(gè)問(wèn)題叫。其中

6、的一個(gè)問(wèn)題叫“原問(wèn)題原問(wèn)題”，記為，記為“P”，另一個(gè)，另一個(gè)稱為稱為“對(duì)偶問(wèn)題對(duì)偶問(wèn)題”，記為，記為“D”。2. 0,124164821222.32max2121212121xxxxxxxxtsxxz 0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy原問(wèn)題原問(wèn)題-P對(duì)偶問(wèn)題對(duì)偶問(wèn)題-D（4）目標(biāo)的系數(shù)）目標(biāo)的系數(shù)C 約束的常數(shù)項(xiàng)約束的常數(shù)項(xiàng) 約束的約束的A （4）約束條件的常數(shù)項(xiàng)）約束條件的常數(shù)項(xiàng) 目標(biāo)的系數(shù)目標(biāo)的系數(shù) 約束的約束的A2. 0,124164821222.32max2121212121xxxxxxxxtsxxz 0

7、,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy原問(wèn)題原問(wèn)題-P對(duì)偶問(wèn)題對(duì)偶問(wèn)題-D（1）max（2）2個(gè)變量，對(duì)應(yīng)兩個(gè)產(chǎn)品個(gè)變量，對(duì)應(yīng)兩個(gè)產(chǎn)品（3）4個(gè)約束，對(duì)應(yīng)四種資源個(gè)約束，對(duì)應(yīng)四種資源 （1）min（2）2個(gè)約束，基于兩個(gè)產(chǎn)品列出的個(gè)約束，基于兩個(gè)產(chǎn)品列出的 （3）4個(gè)變量，對(duì)應(yīng)每個(gè)資源的出讓個(gè)變量，對(duì)應(yīng)每個(gè)資源的出讓價(jià)格價(jià)格（1）對(duì)稱形式）對(duì)稱形式特點(diǎn)：目標(biāo)函數(shù)求極大值時(shí)，所有約束條件為特點(diǎn)：目標(biāo)函數(shù)求極大值時(shí)，所有約束條件為號(hào)，變號(hào)，變量非負(fù)量非負(fù);目標(biāo)函數(shù)求極小值時(shí)，所有約束條件為目標(biāo)函數(shù)求極小值時(shí)，所有約束條件為號(hào)，

8、變量非號(hào)，變量非負(fù)負(fù). 0XbAX CXmaxZ ：PTT : minA YC Y0TDWY b原問(wèn)題原問(wèn)題對(duì)偶問(wèn)題對(duì)偶問(wèn)題目標(biāo)函數(shù)目標(biāo)函數(shù)maxmin約束條件約束條件變量數(shù)量變量數(shù)量約束條件個(gè)數(shù)約束條件個(gè)數(shù)約束條件個(gè)數(shù)約束條件個(gè)數(shù)變量數(shù)量變量數(shù)量對(duì)稱形式下對(duì)偶問(wèn)題的一般形式對(duì)稱形式下對(duì)偶問(wèn)題的一般形式0.XbAXtsCXzmax（P）min. .0TTTw Y bA YCstY（D）這是最常見(jiàn)的對(duì)偶模型形式，稱為對(duì)稱式對(duì)偶模型。二者間具有十分對(duì)稱的對(duì)這是最常見(jiàn)的對(duì)偶模型形式，稱為對(duì)稱式對(duì)偶模型。二者間具有十分對(duì)稱的對(duì)應(yīng)關(guān)系：應(yīng)關(guān)系： 原問(wèn)題（原問(wèn)題（P P） 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （D D） 目

9、標(biāo)目標(biāo)max型型 目標(biāo)目標(biāo)min型型 有有n個(gè)變量（非負(fù)）個(gè)變量（非負(fù)） 有有n個(gè)約束（大于等于）個(gè)約束（大于等于） 有有m個(gè)約束個(gè)約束 （小于等于）（小于等于） 有有m個(gè)變量（非負(fù)）個(gè)變量（非負(fù)） 價(jià)格系數(shù)價(jià)格系數(shù) 資源向量資源向量 資源向量資源向量 價(jià)格系數(shù)價(jià)格系數(shù) 技術(shù)系數(shù)矩陣技術(shù)系數(shù)矩陣 技術(shù)系數(shù)矩陣的轉(zhuǎn)置技術(shù)系數(shù)矩陣的轉(zhuǎn)置例例 寫出線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題寫出線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 0,5643 7 32 532432max321321321321321xxxxxxxxxxxxxxxZ解：首先將原問(wèn)題變形為對(duì)稱形式解：首先將原問(wèn)題變形為對(duì)稱形式 0,5 64 3 7 32532432m

10、ax32132132132321xxxxxxxxxxxxxxxZ 注意：以后不強(qiáng)調(diào)等注意：以后不強(qiáng)調(diào)等式右段項(xiàng)式右段項(xiàng) b b00，原因在對(duì)，原因在對(duì)偶單純型表中只保證偶單純型表中只保證 而不保證而不保證 ，故，故 b b可以是負(fù)數(shù)?？梢允秦?fù)數(shù)。0 j 01 bB123123123123123 min235232343 s.t.5764,0Wyyyyyyyyyyyyyyy 對(duì)對(duì)偶偶問(wèn)問(wèn)題題：(2) 非對(duì)稱型對(duì)偶問(wèn)題非對(duì)稱型對(duì)偶問(wèn)題若給出的線性規(guī)劃不是對(duì)稱形式，可以先化成對(duì)稱形式若給出的線性規(guī)劃不是對(duì)稱形式，可以先化成對(duì)稱形式再寫對(duì)偶問(wèn)題。再寫對(duì)偶問(wèn)題。例例 寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題寫出下

11、列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題.112233111122133121122223323113223333123max. .0,0,Zc xc xc xa xa xa xba xa xa xbs ta xa xa xbxxx無(wú)無(wú)約約束束例例 寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題.112233111122133121122223323113223333123max. .0,0,Zc xc xc xa xa xa xba xa xa xbs ta xa xa xbxxx無(wú)無(wú)約約束束解：先將原問(wèn)題化為對(duì)稱形式解：先將原問(wèn)題化為對(duì)稱形式2112222332211222233221122

12、223322112222332211222233231132233333113223333222333333=00,0,0a xa xa xba xa xa xba xa xa xba xa xa xba xa xa xba xa xa xba xa xa xbxxxxxxxxx 無(wú)無(wú)約約束束1122333311112213313312112222332332211222233233231132233333331233max. .0,0,0,0Zc xc xc xc xa xa xa xa xba xa xa xa xbs ta xa xa xa xba xa xa xa xbxxxx 例例

13、寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題.112233111122133121122223323113223333123max. .0,0,Zc xc xc xa xa xa xba xa xa xbs ta xa xa xbxxx無(wú)無(wú)約約束束1122333311112213313312112222332332211222233233231132233333331233max. .0,0,0,0Zc xc xc xc xa xa xa xa xba xa xa xa xbs ta xa xa xa xba xa xa xa xbxxxx 112222331112122123

14、1311212222223232131232232333313123223233331223min. .0,0,0,0 b yb yb yb ya ya ya ya yca ya ya ya ycs ta ya ya ya yca ya ya ya ycyyyy對(duì)偶問(wèn)題對(duì)偶問(wèn)題.1122223311121221231311212222223232131232232333313123223233331223min. .0,0,0,0 b yb yb yb ya ya ya ya yca ya ya ya ycs ta ya ya ya yca ya ya ya ycyyyy22233,yyyyy

15、 令令1122331112123131121222323213123233331312323333123min. .0,0 b yb yb ya ya ya yca ya ya ycs ta ya ya yca ya ya ycyyy無(wú)無(wú)約約束束112233111212313112122232321312323333123min. .0,0 b yb yb ya ya ya yca ya ya ycs ta ya ya ycyyy無(wú)無(wú)約約束束112233111212313112122232321312323333123min. .0,0 b yb yb ya ya ya yca ya ya y

16、cs ta ya ya ycyyy無(wú)無(wú)約約束束112233111122133121122223323113223333123max. .0,0,Zc xc xc xa xa xa xba xa xa xbs ta xa xa xbxxx無(wú)無(wú)約約束束原問(wèn)題原問(wèn)題.對(duì)偶問(wèn)題對(duì)偶問(wèn)題 原問(wèn)題（原問(wèn)題（P P） 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （D D） 目標(biāo)目標(biāo)max型型 目標(biāo)目標(biāo)min型型 有有n個(gè)變量個(gè)變量 有有n個(gè)約束個(gè)約束 有有m個(gè)約束個(gè)約束 有有m個(gè)變量個(gè)變量 價(jià)格系數(shù)價(jià)格系數(shù) 資源向量資源向量 資源向量資源向量 價(jià)格系數(shù)價(jià)格系數(shù) 技術(shù)系數(shù)矩陣技術(shù)系數(shù)矩陣 技術(shù)系數(shù)矩陣的轉(zhuǎn)置技術(shù)系數(shù)矩陣的轉(zhuǎn)置原問(wèn)題原問(wèn)

17、題（或?qū)ε紗?wèn)題）（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題對(duì)偶問(wèn)題（或原問(wèn)題）（或原問(wèn)題）目標(biāo)函數(shù)目標(biāo)函數(shù) max目標(biāo)函數(shù)目標(biāo)函數(shù) min約約束束條條件件m個(gè)個(gè)m個(gè)個(gè)變變量量0000= =無(wú)約束無(wú)約束變變量量n個(gè)個(gè)n個(gè)個(gè)約約束束條條件件0000無(wú)約束無(wú)約束= =b b約束條件右端項(xiàng)約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)C C目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)約束條件右端項(xiàng)例例 寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題.123123123123123max23423523 73. .465,0Zxxxxxxxxxs txxxx xx解：原問(wèn)題的對(duì)偶問(wèn)題為解：原問(wèn)題的對(duì)

18、偶問(wèn)題為123123123123123m in235 23 2 3 43. .5764, Wyyyyyyyyys tyyyyyy無(wú)約束無(wú)約束例例 寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題.1234123412412341234max235 4 325 32 74. .2 34 60,0,Zxxxxxxxxxxxs txxxxxxxx無(wú)無(wú)約約束束解：原問(wèn)題的對(duì)偶問(wèn)題為解：原問(wèn)題的對(duì)偶問(wèn)題為12312312313123123m in546 4322 233. .3 45 27 10,0,Wyyyyyyyyys tyyyyyyyy 無(wú)無(wú) 約約 束束例例12312312312312

19、312341234234123412341.min22423523 73 s.t. 465,02 min3234 2340 345 s.t.2374200, Zxxxxxxxxxxxxx xx.Zxxxxxxxxxxxxxxxxxxx ，、無(wú)無(wú)約約束束123123123123123123131231231.max2352y3y y23y y4y2 s.t.5y7y6y4y0,y .y0 2.max352 y 2y32y y3y2 s.t. 3y3y7y3WyyyWyyy 答答案案：123123 4y4y4y4y0,y0,y無(wú)無(wú)約約束束性質(zhì)性質(zhì)1 1 對(duì)稱性定理對(duì)稱性定理：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題

20、：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題min Z= - CXs.t. - AX - b X 0 min W= Y Tbs.t. ATY CT Y 0max Z=C Xs.t. AX b X 0對(duì)偶的定義對(duì)偶的定義對(duì)偶的定義對(duì)偶的定義max W = -YTbs.t. -ATY - CT Y 0性質(zhì)性質(zhì)2 2 弱對(duì)偶原理弱對(duì)偶原理( (弱對(duì)偶性弱對(duì)偶性) )：設(shè)設(shè) 和和 分別是問(wèn)題分別是問(wèn)題(P)(P)和和(D)(D)的可行解，則必有的可行解，則必有XY11nmTjjiijiCXY bc xb y即即：()(),(),TTTTTTXYPDAXb A YCYACYAXY b YAXCX證證：和和分分別別是是和和的

21、的可可行行解解，有有 從從而而有有：TCXY b 即即：圖示：圖示：CXTY b0.XbAXtsCXzmax（P）m in. .0TTTwYbAYCs tY（D）推論推論1: 原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；反之，對(duì)偶問(wèn)題任意可行解的目標(biāo)函數(shù)值是其原問(wèn)題目的下界；反之，對(duì)偶問(wèn)題任意可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界。標(biāo)函數(shù)值的上界。推論推論2: 在一對(duì)對(duì)偶問(wèn)題（在一對(duì)對(duì)偶問(wèn)題（P）和（）和（D）中，若其中一個(gè)問(wèn)題可行）中，若其中一個(gè)問(wèn)題可行但目標(biāo)函數(shù)無(wú)界，則另一個(gè)問(wèn)題無(wú)可行解；但目標(biāo)函數(shù)無(wú)界，則另一個(gè)問(wèn)題無(wú)可

22、行解；反之不成立反之不成立。這也是這也是對(duì)偶問(wèn)題的無(wú)界性。對(duì)偶問(wèn)題的無(wú)界性。圖示：圖示：CXTY b推論推論3 3：在一對(duì)對(duì)偶問(wèn)題（在一對(duì)對(duì)偶問(wèn)題（P）和（）和（D）中，若一個(gè)可行（如）中，若一個(gè)可行（如P），而另一個(gè)不可行（如），而另一個(gè)不可行（如D），則該可行的問(wèn)題目標(biāo)函數(shù)），則該可行的問(wèn)題目標(biāo)函數(shù)值無(wú)界。值無(wú)界。 02023220322 432max41432143214321xxxxxxxxxxxxxZ試估計(jì)它們目標(biāo)函數(shù)的界，并驗(yàn)證弱對(duì)偶性原理。試估計(jì)它們目標(biāo)函數(shù)的界，并驗(yàn)證弱對(duì)偶性原理。（P）例例解：解： 0,04233322 212 2020min212121212121yyyyy

23、yyyyyyyW（D） 由觀察可知：由觀察可知： =(1 1 1 1)T， =(1 1) T ，分別是（，分別是（P）和（和（D）的可行解。）的可行解。Z=10 ，W=40，故有，故有 ,弱對(duì)弱對(duì)偶定理成立。由推論可知，偶定理成立。由推論可知，W 的最小值不能小于的最小值不能小于10，Z 的最大值不能超過(guò)的最大值不能超過(guò)40。TCX Y b_X_Y0.XbAXtsCXzmax（P）min. .0TTTzY bA YCs tY（D） , ,3.TXYPDCXY bXX YY若若 與與 分分別別是是（ ）與與（ ）的的可可行行解解，性性質(zhì)質(zhì)解解的的最最優(yōu)優(yōu)且且性性則則( ).TPXCXY bCX證

24、證：對(duì)對(duì)的的任任一一可可行行解解 ，由由弱弱對(duì)對(duì)偶偶性性，.XXYY故故同同理理，圖示：圖示：*TCXYb性質(zhì)性質(zhì)4 強(qiáng)對(duì)偶性強(qiáng)對(duì)偶性：若原問(wèn)題及其對(duì)偶問(wèn)題均具有可行解，則若原問(wèn)題及其對(duì)偶問(wèn)題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。還可推出另一結(jié)論：若（還可推出另一結(jié)論：若（P）與（）與（D）都有可行解，則兩者都）都有可行解，則兩者都有最優(yōu)解，若一個(gè)問(wèn)題無(wú)最優(yōu)解，則另一問(wèn)題也無(wú)最優(yōu)解。有最優(yōu)解，若一個(gè)問(wèn)題無(wú)最優(yōu)解，則另一問(wèn)題也無(wú)最優(yōu)解。0.XbAXtsCXzmax（P）min. .0TTTzY bA YCs tY（D）證：

25、對(duì)（證：對(duì)（P）增加松弛變量）增加松弛變量 ， 化為：化為：0,. .SSXXbIXAXtsCXMaxz設(shè)其最優(yōu)基為設(shè)其最優(yōu)基為B，終表為，終表為SXXC 0 IBAB11 1bBCB11 0bBC B ICC B A00011IBCABCCBsB其檢驗(yàn)數(shù)為其檢驗(yàn)數(shù)為1,TBYC BY取取則則 滿滿足足0TA YCY1DTBYY bC B bz即即 是是（ ）的的可可行行解解，且且3.YY由由性性質(zhì)質(zhì) ，SX性質(zhì)性質(zhì)4 強(qiáng)對(duì)偶性強(qiáng)對(duì)偶性：若原問(wèn)題及其對(duì)偶問(wèn)題均具有可行解，則若原問(wèn)題及其對(duì)偶問(wèn)題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函

26、數(shù)值相等。初始單純形表和初始單純形表和B為基的單純形表為基的單純形表(2) 求求Y*是否有必要重新求解（是否有必要重新求解（ D）？）？ CBB-1 不必。由對(duì)偶定理的證明過(guò)程可知，原問(wèn)題（不必。由對(duì)偶定理的證明過(guò)程可知，原問(wèn)題（P）的的單純形終表單純形終表可同時(shí)得到（可同時(shí)得到（P）和對(duì)偶問(wèn)題（）和對(duì)偶問(wèn)題（D）的）的最優(yōu)解最優(yōu)解。SXXC 0 IBAB11 1 BB bC11 bBCC B AC B（P）的最優(yōu)解）的最優(yōu)解中基變量的解中基變量的解（D）的最優(yōu)解）的最優(yōu)解 BCx（P）和（）和（D）的）的最優(yōu)值相等最優(yōu)值相等0,25.2121 21xxxxxxts105153212.5xxM

27、axz例如，已知例如，已知 的終表為的終表為51 0 52 153- 1 519 02913xx2.50 0.5- 0 0 0TX)09,0,2,(5z請(qǐng)指出其對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)值。請(qǐng)指出其對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)值。5)5 . 0 , 0(wY(P) (D)() ()0TTssXYXYPDYXYX 若若與與分分 別別 是是、的的 可可 行行 解解 ，則則和和是是、最最性性 質(zhì)質(zhì) 互互 補(bǔ)補(bǔ) 松松 弛弛優(yōu)優(yōu) 解解 的的 充充 要要 條條 件件 是是定定 理理 (P) (D), ()()=0,0,0TTssTTTTssTTssTTssTTssAXIXbA YIYCXYCXYbYAYI XYAX

28、IXYXYXYXYXYXYX證證 ： 將將、的的 約約 束束 化化 為為 等等 式式 ： 、是是 最最 優(yōu)優(yōu) 解解 ， 所所 以以從從 而而即即 而而 故故 只只 有有 。（ 自自 證證 ） 。 (P) (D)() ()0TTssXYXYPDYXYX 若若與與分分 別別 是是、的的 可可 行行 解解 ，則則和和是是、最最性性 質(zhì)質(zhì) 互互 補(bǔ)補(bǔ) 松松 弛弛優(yōu)優(yōu) 解解 的的 充充 要要 條條 件件 是是定定 理理 11110000imimmijiiijiiiiininniminijjiijjijjxyia yca ycyxia xba xyxb或或 者者 寫寫 為為 ：若若， 則則。 即即 對(duì)對(duì)

29、偶偶 問(wèn)問(wèn) 題題 的的 第第 個(gè)個(gè) 約約 束束 取取 等等 號(hào)號(hào) ： 若若， 則則。 即即 原原 問(wèn)問(wèn) 題題 的的 第第 個(gè)個(gè) 約約 束束 取取 等等 號(hào)號(hào) ： y1 yi ym ym+1 ym+j ym+n x1 xj xn xn+1xn+ixn+m 對(duì)偶問(wèn)題的變量對(duì)偶問(wèn)題的變量 對(duì)偶問(wèn)題的松弛變量對(duì)偶問(wèn)題的松弛變量 原始問(wèn)題的變量原始問(wèn)題的變量 原始問(wèn)題的松弛變量原始問(wèn)題的松弛變量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一對(duì)變量中，其中一個(gè)大于在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于，另一個(gè)一定等于0直觀上直觀上性質(zhì)性質(zhì)5的應(yīng)用：的應(yīng)用：該性質(zhì)給出了已知一

30、個(gè)問(wèn)題最優(yōu)解求另一個(gè)問(wèn)題最優(yōu)解該性質(zhì)給出了已知一個(gè)問(wèn)題最優(yōu)解求另一個(gè)問(wèn)題最優(yōu)解的方法，即已知的方法，即已知Y求求X 或已知或已知X 求求Y 00TsTsYXYX互補(bǔ)松弛條件互補(bǔ)松弛條件由于松弛變量都非負(fù)，要使求和式等于零，則必定每一分量為由于松弛變量都非負(fù)，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系：零，因而有下列關(guān)系：若若Y 0，則，則Xs必為必為0；若；若X 0，則，則Ys必為必為0利用上述關(guān)系，建立對(duì)偶問(wèn)題（或原問(wèn)題）的約束線性方程組，利用上述關(guān)系，建立對(duì)偶問(wèn)題（或原問(wèn)題）的約束線性方程組，方程組的解即為最優(yōu)解。方程組的解即為最優(yōu)解。例例 已知線性規(guī)劃已知線性規(guī)劃 3 , 2

31、, 1, 0162210243max321321321jxxxxxxxxxxzj的最優(yōu)解是的最優(yōu)解是X=(6,2,0)T,求其對(duì)偶問(wèn)題的最優(yōu)解求其對(duì)偶問(wèn)題的最優(yōu)解Y。解：寫出原問(wèn)題的對(duì)偶問(wèn)題，即解：寫出原問(wèn)題的對(duì)偶問(wèn)題，即 0,1422321610min2121212121yyyyyyyyyywwyy y +y -y y +y -y y +y -yyyyyy1212312412512345min1016232241,0 設(shè)對(duì)偶問(wèn)題最優(yōu)解為設(shè)對(duì)偶問(wèn)題最優(yōu)解為Y(y1，y2),由互補(bǔ)松弛性定理可知，由互補(bǔ)松弛性定理可知，X和和 Y滿足：滿足：00TsTsY XYX即：即：0),)(,(0),)(,

32、(5421321543 TTxxyyxxxyyy因?yàn)橐驗(yàn)閄1=60，X2=20，所以對(duì)偶問(wèn)題的第一、二個(gè)約束的，所以對(duì)偶問(wèn)題的第一、二個(gè)約束的松弛變量等于零，即松弛變量等于零，即y30，y40，帶入方程中：，帶入方程中： 422322121yyyy解此線性方程組得解此線性方程組得y1=1,y2=1,從而對(duì)偶問(wèn)題的最優(yōu)解為：從而對(duì)偶問(wèn)題的最優(yōu)解為：Y=(1,1)，最優(yōu)值，最優(yōu)值w=26。例例 已知線性規(guī)劃已知線性規(guī)劃 123451234512345iminz2x3x5x2x3xxx2xx3x4s.t. 2xx3xxx3x0的對(duì)偶問(wèn)題的最優(yōu)解為的對(duì)偶問(wèn)題的最優(yōu)解為Y=(4/5,3/5)，求原問(wèn)題的

33、最優(yōu)解。，求原問(wèn)題的最優(yōu)解。解解: 對(duì)偶問(wèn)題是對(duì)偶問(wèn)題是12121212121212maxw4y3yy2y2yy32y3y5s.t.yy23yy3y ,y01212312412126127imaxw4y3yy2yy2yyy32y3yy5s.t.yyy23yyy3y0,i1,7設(shè)對(duì)偶問(wèn)題最優(yōu)解為設(shè)對(duì)偶問(wèn)題最優(yōu)解為X(x1，x2 ，x3，x4，x5)T ,由互補(bǔ)松由互補(bǔ)松弛性定理可知，弛性定理可知，X和和 Y滿足：滿足：T3456712345T1267(y ,y ,y ,y ,y )(x ,x ,x ,x ,x )0(y ,y )(x ,x )0將將Y =(4/5,3/5)帶入由方程可知第二帶入由

34、方程可知第二-四約束為等式，從而四約束為等式，從而x2x3=x40。 y1=4/50, y2=3/50 x6 x7= 01515x3x42xx3從而解方程組得：解方程組得：x1=5,x5=1, 所以原問(wèn)題的最優(yōu)解為所以原問(wèn)題的最優(yōu)解為X=(1,0,0,0,1)T，最優(yōu)值，最優(yōu)值z(mì)=5定義：在一對(duì)定義：在一對(duì) P 和和 D 中，若中，若 P 的某個(gè)約束條件的右端項(xiàng)常數(shù)的某個(gè)約束條件的右端項(xiàng)常數(shù)bi 增加增加一個(gè)單位時(shí)，所引起的目標(biāo)函數(shù)最優(yōu)值一個(gè)單位時(shí)，所引起的目標(biāo)函數(shù)最優(yōu)值Z* 的改變量的改變量y*i稱為稱為第第i個(gè)約束條件的影子價(jià)格，又稱為邊際價(jià)格。個(gè)約束條件的影子價(jià)格，又稱為邊際價(jià)格。 設(shè)：

35、設(shè)：B是問(wèn)題是問(wèn)題 （ P ）的最優(yōu)基，則）的最優(yōu)基，則 Z*=CB B-1b = Y*Tb =y*1b1+ y*2b2+y*ibi+y*mbm 當(dāng)當(dāng)bi 變?yōu)樽優(yōu)閎i+1 時(shí)（其余右端項(xiàng)不變，也不影響時(shí)（其余右端項(xiàng)不變，也不影響B(tài)） 目標(biāo)函數(shù)最優(yōu)值變?yōu)椋耗繕?biāo)函數(shù)最優(yōu)值變?yōu)椋?Z*= y*1b1+ y*2b2+y*i （ bi+1 ）+y*mbm Z*= Z* Z* = y*i 也可以寫成：也可以寫成： 即即y*i 表示表示Z*對(duì)對(duì) bi的變化率。的變化率。*(1,2)iiZyimb其經(jīng)濟(jì)意義是：在其它條件不變的情況下，單位資源變其經(jīng)濟(jì)意義是：在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函

36、數(shù)的最優(yōu)值的變化。即對(duì)偶變量化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。即對(duì)偶變量yi 就是第就是第 i 個(gè)約束條件的影子價(jià)格。個(gè)約束條件的影子價(jià)格。也可以理解為目標(biāo)函數(shù)最優(yōu)值對(duì)資源的一階偏導(dǎo)數(shù)（但也可以理解為目標(biāo)函數(shù)最優(yōu)值對(duì)資源的一階偏導(dǎo)數(shù)（但問(wèn)題中所有其它數(shù)據(jù)都保持不變）。問(wèn)題中所有其它數(shù)據(jù)都保持不變）。若第若第 i 種資源的單位市場(chǎng)價(jià)格為種資源的單位市場(chǎng)價(jià)格為mi ，當(dāng)，當(dāng)yi mi 時(shí)，企業(yè)時(shí)，企業(yè)愿意購(gòu)進(jìn)這種資源，單位純利為愿意購(gòu)進(jìn)這種資源，單位純利為yimi ，則有利可圖；如果，則有利可圖；如果yi mi ，則企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利為，則企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利為miy

37、i ，否則企業(yè)無(wú)利可圖，甚至虧損。否則企業(yè)無(wú)利可圖，甚至虧損。例（原問(wèn)題）例（原問(wèn)題） 某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源，有關(guān)單某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源，有關(guān)單耗耗 數(shù)據(jù)如表，試擬定使總收入最大的生產(chǎn)計(jì)劃。數(shù)據(jù)如表，試擬定使總收入最大的生產(chǎn)計(jì)劃。127單價(jià)單價(jià)300103油油20054電電36049煤煤資源限制資源限制乙乙甲甲產(chǎn)品產(chǎn)品資源資源例（對(duì)偶問(wèn)題）例（對(duì)偶問(wèn)題）這時(shí)有另一家廠商提出要購(gòu)買其煤、電、油全部資源，并希望花費(fèi)盡這時(shí)有另一家廠商提出要購(gòu)買其煤、電、油全部資源，并希望花費(fèi)盡量少。試建立購(gòu)買者的線性規(guī)劃模型。量少。試建立購(gòu)買者的線性規(guī)

38、劃模型。12121212127129436045200. .310300,0MaxZxxxxxxs txxx x乙甲油電煤 123123123123W360200300943 7. . 451012,0Minyyyyyys tyyyy yy油電煤 乙甲 對(duì)偶問(wèn)題的最優(yōu)解對(duì)偶問(wèn)題的最優(yōu)解 買主的最低出價(jià)；買主的最低出價(jià)； 原問(wèn)題原問(wèn)題資源的影子價(jià)格資源的影子價(jià)格 當(dāng)該資源增加當(dāng)該資源增加1單單 位時(shí)引起的總收入的增量位時(shí)引起的總收入的增量賣主的內(nèi)控價(jià)格。賣主的內(nèi)控價(jià)格。 *1TBYC B 對(duì)偶問(wèn)題的最優(yōu)解對(duì)偶問(wèn)題的最優(yōu)解 買主的最低出價(jià)；買主的最低出價(jià)； 原問(wèn)題原問(wèn)題資源的影子價(jià)格資源的影子價(jià)格

39、 當(dāng)該資源增加當(dāng)該資源增加1單單 位時(shí)引起的總收入的增量位時(shí)引起的總收入的增量賣主的內(nèi)控價(jià)格。賣主的內(nèi)控價(jià)格。 *1TBYC B設(shè)：設(shè)：B是問(wèn)題是問(wèn)題 （ P ）的最優(yōu)基，則）的最優(yōu)基，則 Z*=CB B-1b = Y*Tb =y*1b1+ y*2b2+y*ibi+y*mbm 當(dāng)當(dāng)bi 變?yōu)樽優(yōu)閎i+1 時(shí)（其余右端項(xiàng)不變，也不影響時(shí)（其余右端項(xiàng)不變，也不影響B(tài)） 目標(biāo)函數(shù)最優(yōu)值變?yōu)椋耗繕?biāo)函數(shù)最優(yōu)值變?yōu)椋?Z*= y*1b1+ y*2b2+y*i （ bi+1 ）+y*mbm Z*= Z* Z* = y*i 也可以寫成：也可以寫成： 即即y*i 表示表示Z*對(duì)對(duì) bi的變化率。的變化率。*(1

40、,2)iiZyimb例（煤電油例）的單純形終表如下：例（煤電油例）的單純形終表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z（1）請(qǐng)指出資源煤電油的影子價(jià)格，并解釋其經(jīng)濟(jì)意義。）請(qǐng)指出資源煤電油的影子價(jià)格，并解釋其經(jīng)濟(jì)意義。（2）由單純形終表還可得到哪些有用的信息？）由單純形終表還可得到哪些有用的信息？例例（煤電油例）的單純形終表如下：（煤電油例）的單純形終表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx127

41、0 0.52- 1.36- 0 0 0242084100j（1）請(qǐng)指出資源煤、電、油的影子價(jià)格，并解釋其經(jīng)濟(jì)意義。）請(qǐng)指出資源煤、電、油的影子價(jià)格，并解釋其經(jīng)濟(jì)意義。（2）由單純形終表還可得到哪些有用的信息？）由單純形終表還可得到哪些有用的信息？解：（解：（1）煤、電、油的影子價(jià)格分別是）煤、電、油的影子價(jià)格分別是0、1.36、0.52； 其經(jīng)濟(jì)意義是當(dāng)煤、電、油分別增加其經(jīng)濟(jì)意義是當(dāng)煤、電、油分別增加1單位時(shí)可使總單位時(shí)可使總 收入分別增加收入分別增加0 、1.36、0.52。（2）由單純形終表還可得到：原問(wèn)題的最優(yōu)生產(chǎn)計(jì)劃、）由單純形終表還可得到：原問(wèn)題的最優(yōu)生產(chǎn)計(jì)劃、資源剩余，對(duì)偶問(wèn)題的

42、最低購(gòu)買價(jià)格等。資源剩余，對(duì)偶問(wèn)題的最低購(gòu)買價(jià)格等。 y1y2ym（2）對(duì)偶對(duì)偶約束的約束的經(jīng)濟(jì)解釋經(jīng)濟(jì)解釋產(chǎn)品的機(jī)會(huì)成本產(chǎn)品的機(jī)會(huì)成本 (Opportunity Cost)機(jī)會(huì)成本機(jī)會(huì)成本表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤(rùn)表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤(rùn)mmjiijjjyayayaya2211增加單位資源可以增加的利潤(rùn)增加單位資源可以增加的利潤(rùn)減少一件產(chǎn)品可以節(jié)省的資源減少一件產(chǎn)品可以節(jié)省的資源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j21211

43、1nnjj2211機(jī)會(huì)成本機(jī)會(huì)成本利潤(rùn)利潤(rùn)差額成本差額成本0. .min212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayayatsybybybw（3）對(duì)偶對(duì)偶松弛變量的松弛變量的經(jīng)濟(jì)解釋經(jīng)濟(jì)解釋產(chǎn)品的差額成本（產(chǎn)品的差額成本（Reduced Cost）差額成本差額成本=機(jī)會(huì)成本機(jī)會(huì)成本 利潤(rùn)利潤(rùn)jjTjmjmjjjmcaYcayayayy)(22110000000000jjmjmjjmjiininiinixyyxyxyxxyxy 在利潤(rùn)最大化的生產(chǎn)計(jì)劃中在利潤(rùn)最大化的生產(chǎn)計(jì)劃中 （1）影

44、子價(jià)格大于）影子價(jià)格大于0的資源沒(méi)有剩余；的資源沒(méi)有剩余； （2）有剩余的資源影子價(jià)格等于）有剩余的資源影子價(jià)格等于0； （3）安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本等于利潤(rùn)；）安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本等于利潤(rùn)； （4）機(jī)會(huì)成本大于利潤(rùn)的產(chǎn)品不安排生產(chǎn)。）機(jī)會(huì)成本大于利潤(rùn)的產(chǎn)品不安排生產(chǎn)。（4）互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋）互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋練習(xí)：填空練習(xí)：填空1 .根據(jù)根據(jù)LP的互補(bǔ)松弛定理，影子價(jià)格大于的互補(bǔ)松弛定理，影子價(jià)格大于0的資源一定的資源一定 剩余；安剩余；安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本一定排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本一定 利潤(rùn)。利潤(rùn)。 A.沒(méi)有，小于沒(méi)有，小于 B .沒(méi)有，大于沒(méi)有，大于 C .沒(méi)有，等于沒(méi)有，等

45、于 D .有，等于有，等于2.若若LP的原始問(wèn)題增加一個(gè)變量，則其對(duì)偶問(wèn)題就增加一個(gè)的原始問(wèn)題增加一個(gè)變量，則其對(duì)偶問(wèn)題就增加一個(gè) ；因而對(duì)偶的最優(yōu)目標(biāo)值可能變因而對(duì)偶的最優(yōu)目標(biāo)值可能變 。 A.約束，好約束，好 B .約束，壞約束，壞 C .變量，好變量，好 D .變量，壞變量，壞 對(duì)偶單純形法是求解線性規(guī)劃的另一個(gè)基本方法。它對(duì)偶單純形法是求解線性規(guī)劃的另一個(gè)基本方法。它是根據(jù)對(duì)偶原理和單純形法原理而設(shè)計(jì)出來(lái)的，因此稱為是根據(jù)對(duì)偶原理和單純形法原理而設(shè)計(jì)出來(lái)的，因此稱為對(duì)偶單純形法對(duì)偶單純形法。不要簡(jiǎn)單理解為是求解對(duì)偶問(wèn)題的單純形。不要簡(jiǎn)單理解為是求解對(duì)偶問(wèn)題的單純形法。法。 能否嘗試對(duì)稱

46、的思路，在保持能否嘗試對(duì)稱的思路，在保持0（對(duì)偶問(wèn)題有可行解）（對(duì)偶問(wèn)題有可行解）下改善可行性下改善可行性B-1b0？SXXC 0 IBAB11 1bBCB11 0bBCC B AC B 單純形法是在保持可行性單純形法是在保持可行性B-1b0下改善最優(yōu)性下改善最優(yōu)性0?；舅枷牖舅枷?若保持對(duì)偶問(wèn)題的解是基可行解，而原問(wèn)題在非若保持對(duì)偶問(wèn)題的解是基可行解，而原問(wèn)題在非可行解的基礎(chǔ)上，通過(guò)逐步迭代達(dá)到基可行解，這樣可行解的基礎(chǔ)上，通過(guò)逐步迭代達(dá)到基可行解，這樣也就得到了最優(yōu)解。這種方法的優(yōu)點(diǎn)是原問(wèn)題的初始也就得到了最優(yōu)解。這種方法的優(yōu)點(diǎn)是原問(wèn)題的初始解不一定是基可行解，可從非基可行解開(kāi)始迭代。

47、解不一定是基可行解，可從非基可行解開(kāi)始迭代。 基本原理基本原理 對(duì)于原問(wèn)題對(duì)于原問(wèn)題 max. .0ZCXAXbs tX設(shè)設(shè)B是一個(gè)基，不失一般性是一個(gè)基，不失一般性,令令 ，它對(duì)應(yīng)的基變量為，它對(duì)應(yīng)的基變量為 。當(dāng)非基變量都為零時(shí)，可以得到。當(dāng)非基變量都為零時(shí)，可以得到 。若在。若在 中至少有一個(gè)負(fù)分量，設(shè)中至少有一個(gè)負(fù)分量，設(shè) ，并且在單純形表的檢驗(yàn)，并且在單純形表的檢驗(yàn)數(shù)行中的檢驗(yàn)數(shù)都非正，即對(duì)偶問(wèn)題保持可行解，它的各分量是數(shù)行中的檢驗(yàn)數(shù)都非正，即對(duì)偶問(wèn)題保持可行解，它的各分量是: 對(duì)應(yīng)基變量的檢驗(yàn)數(shù)是對(duì)應(yīng)基變量的檢驗(yàn)數(shù)是 對(duì)應(yīng)非基變量的檢驗(yàn)數(shù)是對(duì)應(yīng)非基變量的檢驗(yàn)數(shù)是,21mPPPB,2

48、1mBxxxXbBXB1bB10)(1ibB), 2 , 1(01miPBCczciBiiii), 2, 1(01nmmjPBCczcjBjjjj 每次迭代是將基變量中的負(fù)分量取出，去替換非基變量中的每次迭代是將基變量中的負(fù)分量取出，去替換非基變量中的，經(jīng)過(guò)基變換，所有檢驗(yàn)數(shù)仍保持非正。從原問(wèn)題來(lái)看，經(jīng)過(guò)每次，經(jīng)過(guò)基變換，所有檢驗(yàn)數(shù)仍保持非正。從原問(wèn)題來(lái)看，經(jīng)過(guò)每次迭代，原問(wèn)題由非可行解往可行解靠近，當(dāng)原問(wèn)題得到可行解時(shí)，迭代，原問(wèn)題由非可行解往可行解靠近，當(dāng)原問(wèn)題得到可行解時(shí)，便得到了最優(yōu)解。便得到了最優(yōu)解。 找出一個(gè)對(duì)偶問(wèn)題的可行基，保持對(duì)偶問(wèn)題為可行解的找出一個(gè)對(duì)偶問(wèn)題的可行基，保持對(duì)偶

49、問(wèn)題為可行解的條件下，判斷條件下，判斷XB是否可行（是否可行（XB=b為非負(fù)），有最優(yōu)解。否則，為非負(fù)），有最優(yōu)解。否則，通過(guò)變換基解，直到找到原問(wèn)題基可行解（即通過(guò)變換基解，直到找到原問(wèn)題基可行解（即XB為非負(fù)），為非負(fù)），這時(shí)原問(wèn)題與對(duì)偶問(wèn)題同時(shí)達(dá)到可行解，由定理這時(shí)原問(wèn)題與對(duì)偶問(wèn)題同時(shí)達(dá)到可行解，由定理4可得?？傻谩Ｕ页鲆粋€(gè)找出一個(gè)D的可行基的可行基P是否可行是否可行（XB 0）保持保持D為可行解情況下轉(zhuǎn)移到為可行解情況下轉(zhuǎn)移到P的的另一個(gè)基本解另一個(gè)基本解最優(yōu)解最優(yōu)解是是否否循循環(huán)環(huán)結(jié)束結(jié)束列出初始單純形表，檢查b列中的各分量，若都為非負(fù)，且檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解。若b列中至少

50、有一個(gè)負(fù)分量，檢驗(yàn)數(shù)保持非正，進(jìn)行以下計(jì)算。確定換出變量。按照法則確定對(duì)應(yīng)的基變量為換出變量。 liibBbBbB)(0)()min(111 確定換入變量。 若xj所在行有負(fù)系數(shù)，計(jì)算 所對(duì)應(yīng)的非基變量xk為換入變量。 以 為主元素，按原單純形法迭代運(yùn)算，得新單純形表。 重復(fù) 的步驟，直至求得最優(yōu)解。 lkkkljljjjjazcaazc0minlka例例 用對(duì)偶單純形法求解：用對(duì)偶單純形法求解：123123123123m in91 21 5221 0231 2. . 51 40 (1 .2 .3)jZxxxxxxxxxs txxxxj解解:（1）將模型轉(zhuǎn)化為求最大化問(wèn)題，約束方程化為等式求將

51、模型轉(zhuǎn)化為求最大化問(wèn)題，約束方程化為等式求出一組基本解，因?yàn)閷?duì)偶問(wèn)題可行（求出一組基本解，因?yàn)閷?duì)偶問(wèn)題可行（求max問(wèn)題）。問(wèn)題）。1231234123512361 6max9121522 1023 12. . 5 140Zxxxxxxxxxxxs txxxxx cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-10-2-2-11000 x5-12-2-3-10100 x6-14-1-1-5001j-9-12-15000icj-9-12-15000cBxBbx1x2x3x4x5x60 x4-36/5-9/5-9/5010-1/50 x5-46/5-9/5-14/5001-1

52、/5-15x314/51/51/5100-1/5(-30/-9,-45/-14,-15/-1)-6-9000-3icj-9-12-15000cBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14(-3/-9,-45/-9,-33/-1)-15x315/71/140101/14-3/14-3/14000-45/14-33/14ij j cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9000-1/3-3-7/3j

53、 原問(wèn)題的最優(yōu)解為：原問(wèn)題的最優(yōu)解為：X*=（2 , 2 , 2 , 0 , 0 , 0），），Z* =72 由定理由定理4，其對(duì)偶問(wèn)題的最優(yōu)解為：，其對(duì)偶問(wèn)題的最優(yōu)解為：Y*= （1/3 , 3 , 7/3），），W*= 72 對(duì)偶單純形法應(yīng)注意的問(wèn)題：對(duì)偶單純形法應(yīng)注意的問(wèn)題： 用對(duì)偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對(duì)用對(duì)偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對(duì)偶問(wèn)題的最優(yōu)解偶問(wèn)題的最優(yōu)解 初始表中一定要滿足對(duì)偶問(wèn)題可行，也就是說(shuō)檢驗(yàn)數(shù)滿足最優(yōu)初始表中一定要滿足對(duì)偶問(wèn)題可行，也就是說(shuō)檢驗(yàn)數(shù)滿足最優(yōu)判別準(zhǔn)則判別準(zhǔn)則 對(duì)偶單純形法與普通單純形法的換基順序不一樣，普通單純

54、形法對(duì)偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進(jìn)基變量后確定出基變量，對(duì)偶單純形法是先確定出基變是先確定進(jìn)基變量后確定出基變量，對(duì)偶單純形法是先確定出基變量后確定進(jìn)基變量；量后確定進(jìn)基變量； 普通單純形法的最小比值是普通單純形法的最小比值是 其目的是保證下一其目的是保證下一個(gè)原問(wèn)題的基本解可行，對(duì)偶單純形法的最小比值是個(gè)原問(wèn)題的基本解可行，對(duì)偶單純形法的最小比值是 0minikikiiaab其目的是保證下一個(gè)對(duì)偶問(wèn)題的基本解可行。其目的是保證下一個(gè)對(duì)偶問(wèn)題的基本解可行。 jjljjljczmin|a0a 對(duì)偶單純形法在確定出基變量時(shí)，若不遵循對(duì)偶單純形法在確定出基變量時(shí)，

55、若不遵循 規(guī)則，任選一個(gè)小于零的規(guī)則，任選一個(gè)小于零的b bii對(duì)應(yīng)的基變量出基，不影響計(jì)算結(jié)果，對(duì)應(yīng)的基變量出基，不影響計(jì)算結(jié)果，只是迭代次數(shù)可能不一樣。只是迭代次數(shù)可能不一樣。 0|min iilbbb靈敏度分析又稱靈敏度分析又稱“后驗(yàn)分析后驗(yàn)分析”，它是對(duì)已經(jīng)得到的最優(yōu)方案改，它是對(duì)已經(jīng)得到的最優(yōu)方案改變某些條件來(lái)檢驗(yàn)最優(yōu)解的變某些條件來(lái)檢驗(yàn)最優(yōu)解的“穩(wěn)定性穩(wěn)定性”以及目標(biāo)函數(shù)最優(yōu)值以及目標(biāo)函數(shù)最優(yōu)值隨各種條件變化的隨各種條件變化的“敏感性敏感性”。討論模型的系數(shù)或變量發(fā)生小的變化時(shí)對(duì)解的影響討論模型的系數(shù)或變量發(fā)生小的變化時(shí)對(duì)解的影響（如，當(dāng)模型的一個(gè)參數(shù)或多個(gè)參數(shù)發(fā)生變化時(shí)，問(wèn)題的最

56、（如，當(dāng)模型的一個(gè)參數(shù)或多個(gè)參數(shù)發(fā)生變化時(shí)，問(wèn)題的最優(yōu)解會(huì)有什么變化？或，它們?cè)诤畏秶鷥?nèi)變化時(shí)可使原最優(yōu)優(yōu)解會(huì)有什么變化？或，它們?cè)诤畏秶鷥?nèi)變化時(shí)可使原最優(yōu)解或最優(yōu)基不變？）解或最優(yōu)基不變？）換言之，假定對(duì)于已知線性規(guī)劃問(wèn)題已求得的最優(yōu)解是獲得換言之，假定對(duì)于已知線性規(guī)劃問(wèn)題已求得的最優(yōu)解是獲得的最大利潤(rùn)的生產(chǎn)計(jì)劃安排，現(xiàn)在如果在生產(chǎn)過(guò)程中成本系的最大利潤(rùn)的生產(chǎn)計(jì)劃安排，現(xiàn)在如果在生產(chǎn)過(guò)程中成本系數(shù)向量數(shù)向量C，約束常數(shù)向量，約束常數(shù)向量b，約束系數(shù)，約束系數(shù)A以及其他條件發(fā)生變以及其他條件發(fā)生變化或波動(dòng)，這些變化限制在什么范圍內(nèi)，在原來(lái)得到的最優(yōu)化或波動(dòng)，這些變化限制在什么范圍內(nèi)，在原來(lái)得到

57、的最優(yōu)安排仍為最優(yōu)，而不需要改變工作計(jì)劃？安排仍為最優(yōu)，而不需要改變工作計(jì)劃？靈敏度越小，解的穩(wěn)定性越好靈敏度越小，解的穩(wěn)定性越好67分析成本系數(shù)向量分析成本系數(shù)向量C C的變化對(duì)解和目標(biāo)函數(shù)值的影響的變化對(duì)解和目標(biāo)函數(shù)值的影響分析約束常數(shù)向量分析約束常數(shù)向量b b的變化對(duì)解的影響，以及通過(guò)對(duì)偶最的變化對(duì)解的影響，以及通過(guò)對(duì)偶最優(yōu)解研究?jī)?yōu)解研究b b的變化對(duì)目標(biāo)函數(shù)值的影響的變化對(duì)目標(biāo)函數(shù)值的影響分析系數(shù)矩陣分析系數(shù)矩陣A A中元素變化對(duì)解和目標(biāo)值的影響中元素變化對(duì)解和目標(biāo)值的影響增加新變化量時(shí)最優(yōu)解和最優(yōu)值的變化增加新變化量時(shí)最優(yōu)解和最優(yōu)值的變化增加新的約束條件后對(duì)最優(yōu)解和最優(yōu)值的影響增加新

58、的約束條件后對(duì)最優(yōu)解和最優(yōu)值的影響主要討論主要討論C、b和變量結(jié)構(gòu)和變量結(jié)構(gòu)變化時(shí)對(duì)解的影響。變化時(shí)對(duì)解的影響。對(duì)解怎樣影響？對(duì)解怎樣影響？ 影響解的影響解的 - 最優(yōu)性最優(yōu)性 - 可行性可行性1100jjBjcC B PB b 10jBjjjjjjccccBCP 價(jià)價(jià)格格變變?yōu)闉闀r(shí)時(shí)，因因?yàn)闉樗恢挥坝绊戫懽钭顑?yōu)優(yōu)性性，即即對(duì)對(duì)檢檢驗(yàn)驗(yàn)數(shù)數(shù) 產(chǎn)產(chǎn)生生影影響響，故故只只要要其其使使變變化化后后的的即即可可。jc變變動(dòng)動(dòng)可可能能由由于于市市場(chǎng)場(chǎng)價(jià)價(jià)格格的的波波動(dòng)動(dòng)，或或生生產(chǎn)產(chǎn)成成 價(jià)價(jià)格格本本的的變變動(dòng)動(dòng)jjjccc的的靈靈敏敏度度分分析析是是在在保保證證最最優(yōu)優(yōu)解解的的基基變變量量不不變變

59、的的情情況況下下，分分析析允允許許的的 ；或或這這些些參參數(shù)數(shù)中中的的一一個(gè)個(gè)或或多多個(gè)個(gè)發(fā)發(fā)生生變變化化時(shí)時(shí)，最最優(yōu)優(yōu)解解如如變變動(dòng)動(dòng)范范圍圍何何變變化化？1100jjBjcC B PB b 1 = 0kkBkkkkkkcccC BPxcc 的的變變化化分分兩兩種種情情況況，只只影影響響自自己己的的檢檢驗(yàn)驗(yàn)當(dāng)當(dāng)是是非非 ，一一數(shù)數(shù)， 個(gè)個(gè)不不等等式式解解出出 由由基基變變量量的的價(jià)價(jià)值值系系數(shù)數(shù)范范圍圍時(shí)時(shí)的的kkcc1mkkiikkkikccc ac0kkkc kc設(shè)設(shè)變化為變化為只要只要即即 則最優(yōu)解不變（則最優(yōu)解不變（此表仍為最優(yōu)，此時(shí)最優(yōu)解不變但最優(yōu)值改此表仍為最優(yōu)，此時(shí)最優(yōu)解不變但

60、最優(yōu)值改變變）；否則（）；否則（此表不是最優(yōu)單純形表此表不是最優(yōu)單純形表），將最優(yōu)單純形表），將最優(yōu)單純形表的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) k k 用用 取代，繼續(xù)單純形法的表格計(jì)算取代，繼續(xù)單純形法的表格計(jì)算。 k111110 =0= jjnjjnjnjjjccccBPccccBPxc當(dāng)當(dāng) 的的變變化化分分兩兩種種是是基基變變量量的的價(jià)價(jià)值值系系情情況況，要要影影響響所所有有的的檢檢驗(yàn)驗(yàn)數(shù)數(shù)， 由由，一一組組不不等等式式解解出出 數(shù)數(shù)時(shí)時(shí) 的的范范圍圍例：某企業(yè)利用三種資源生產(chǎn)兩種產(chǎn)品的最優(yōu)計(jì)劃問(wèn)題歸結(jié)例：某企業(yè)利用三種資源生產(chǎn)兩種產(chǎn)品的最優(yōu)計(jì)劃問(wèn)題歸結(jié)為下列線性規(guī)劃為下列線性規(guī)劃 0,45 802903