1、2022-5-61運(yùn)籌學(xué)運(yùn)籌學(xué)OPERATIONS RESEARCH2022-5-62第二章第二章 線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論 ( Dual Linear Programming, DLP)n原問題與對(duì)偶問題原問題與對(duì)偶問題n對(duì)偶問題的基本性質(zhì)對(duì)偶問題的基本性質(zhì)n影子價(jià)格影子價(jià)格n對(duì)偶單純形法對(duì)偶單純形法n靈敏度分析靈敏度分析n參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃2022-5-631 1 對(duì)偶問題的提出對(duì)偶問題的提出1 1.1 .1 線性規(guī)劃單純形法的矩陣描述線性規(guī)劃單純形法的矩陣描述設(shè)有線性規(guī)劃問題的標(biāo)準(zhǔn)形式設(shè)有線性規(guī)劃問題的標(biāo)準(zhǔn)形式0.maxXbAXtsCXz),(INBA將系數(shù)矩陣表示成：

2、將系數(shù)矩陣表示成：2022-5-64初始單純形表初始單純形表bBNIjN初等行變換后初等行變換后b1BNIjNmyy., 1ICBC初始表中是初始表中是 I 的位置，經(jīng)變換后成為的位置，經(jīng)變換后成為 .1B2022-5-65其中其中),.,(21myyyY 10BCYB1BCYB則則 YNCNBCCNBNN1例：書例：書 P36 P36 例例1010，驗(yàn)證上述公式。，驗(yàn)證上述公式。 jjPBPNBN11,或;1bBb上述公式對(duì)于靈敏度分析很有幫助上述公式對(duì)于靈敏度分析很有幫助 。 記記2022-5-66例例 甲方生產(chǎn)計(jì)劃問題：甲方生產(chǎn)計(jì)劃問題： 能力能力 設(shè)備設(shè)備A 2 2 12 設(shè)備設(shè)備B

3、4 0 16 設(shè)備設(shè)備C 0 5 15 利潤利潤 2 3，各生產(chǎn)多少各生產(chǎn)多少, , 可獲最大利潤可獲最大利潤? ?1 1.2 .2 對(duì)偶問題的提出對(duì)偶問題的提出 設(shè)有原問題設(shè)有原問題 2022-5-67現(xiàn)在現(xiàn)在乙方乙方租借設(shè)備租借設(shè)備, ,甲方以何種價(jià)格將設(shè)備甲方以何種價(jià)格將設(shè)備A A、B B、C C租借給乙方比較合理？租借給乙方比較合理？ 請(qǐng)為其定價(jià)。請(qǐng)為其定價(jià)。思路思路： 就甲方而言就甲方而言， 租金收入應(yīng)不低于將設(shè)備用租金收入應(yīng)不低于將設(shè)備用于自己生產(chǎn)時(shí)的利潤。于自己生產(chǎn)時(shí)的利潤。而就乙方而言而就乙方而言，希望甲方的租金收入在滿足約束的，希望甲方的租金收入在滿足約束的條件下越小越好，這

4、樣雙方才可能達(dá)成協(xié)議。條件下越小越好，這樣雙方才可能達(dá)成協(xié)議。解：解： 假設(shè)假設(shè)A A、B B、C C的單位租金分別為的單位租金分別為 。321,yyy2022-5-68于是得到下述于是得到下述 的線性規(guī)劃模型：的線性規(guī)劃模型：生產(chǎn)產(chǎn)品生產(chǎn)產(chǎn)品的資源用于出租時(shí)，租金收入應(yīng)滿足：的資源用于出租時(shí)，租金收入應(yīng)滿足：24221yy類似的，生產(chǎn)產(chǎn)品類似的，生產(chǎn)產(chǎn)品的資源用于出租時(shí)，租金收入的資源用于出租時(shí)，租金收入應(yīng)滿足：應(yīng)滿足：35231 yy總的租金收入：總的租金收入：321151612yyy321151612minyyyW242.21 yyts0,35232131yyyyy2022-5-690,

5、15 5 16 41222212121xxxxxx2132maxxxZ321151612minyyyW0,352242213121yyyyyy原問題原問題 對(duì)偶問題對(duì)偶問題 2022-5-610原問題原問題 對(duì)偶問題對(duì)偶問題 用矩陣將上述原問題對(duì)偶問題寫出用矩陣將上述原問題對(duì)偶問題寫出0151612500422) 3 , 2(max2121XbxxAXxxCXZ032502042)15,16,12(min321321YcyyyYAyyyYbWTTT2022-5-611即：即：原原問問題題 0maxXbAXCXZ0minYCYAYbWTTT對(duì)對(duì)偶偶問問題題 2022-5-6120,2122112

6、22222121111212111nmmnmnmmnnnnxxxybxaxaxaybxaxaxaybxaxaxannxcxcxcz2211max2 2 原問題與對(duì)偶問題原問題與對(duì)偶問題對(duì)于一般的線性規(guī)劃問題對(duì)于一般的線性規(guī)劃問題2022-5-613類似于前面的資源定價(jià)問題，每一個(gè)約束條件對(duì)類似于前面的資源定價(jià)問題，每一個(gè)約束條件對(duì)應(yīng)一個(gè)應(yīng)一個(gè)“ 對(duì)偶變量對(duì)偶變量”，它就相當(dāng)于給各資源的單，它就相當(dāng)于給各資源的單位定價(jià)。于是我們有如下的位定價(jià)。于是我們有如下的對(duì)偶規(guī)劃對(duì)偶規(guī)劃：0,212211222222112111221111mnnmmnnnmmmmyyyxcyayayaxcyayayaxcy

7、ayayammybybybW2211min2022-5-614對(duì)偶問題與原問題的關(guān)系：對(duì)偶問題與原問題的關(guān)系：原原問問題題 對(duì)對(duì)偶偶問問題題 目標(biāo)函數(shù)：目標(biāo)函數(shù)：MAXMAX約束條件：約束條件：m m個(gè)個(gè)變量變量 ： n個(gè)個(gè)目標(biāo)函數(shù)：目標(biāo)函數(shù)：MINbAX 0X約束條件：約束條件：n個(gè)個(gè)變量變量 ： m個(gè)個(gè)CXZ maxYbWTminTTCYA0Y2022-5-615這是規(guī)范形式這是規(guī)范形式 的原問題，由此寫出其對(duì)偶問題如的原問題，由此寫出其對(duì)偶問題如右方所示，那么，當(dāng)原問題不是規(guī)范形式時(shí)，應(yīng)右方所示，那么，當(dāng)原問題不是規(guī)范形式時(shí)，應(yīng)如何寫出其對(duì)偶問題？如何寫出其對(duì)偶問題？可以先將原問題化成規(guī)

8、范的原問題，再寫出對(duì)偶可以先將原問題化成規(guī)范的原問題，再寫出對(duì)偶問題。問題。2022-5-616例例 寫出下述規(guī)劃的對(duì)偶問題寫出下述規(guī)劃的對(duì)偶問題321151612minyyyW242.21 yyts0,35232131yyyyy于是對(duì)偶問題即為：于是對(duì)偶問題即為：321151612)max(yyyW2-4-2-.21yyt s0,35232131yyyyy0,15- 5- 16- 4-12-2-2-212121xxxxxx2132)(inxxZm解解 先將該問題化為規(guī)范形式先將該問題化為規(guī)范形式也即為：也即為：0,15 5 16 41222212121xxxxxx2132maxxxZ互為對(duì)偶

9、互為對(duì)偶2022-5-617如何寫出非規(guī)范的原問題相應(yīng)的對(duì)偶問題：如何寫出非規(guī)范的原問題相應(yīng)的對(duì)偶問題：目標(biāo)函數(shù)目標(biāo)函數(shù)MIN MAX 約束條件約束條件約束條件約束條件 = ? 4. 變量變量 ? 無約束或 0例：例：P55 例例2，寫出下，寫出下面規(guī)劃的對(duì)偶規(guī)劃面規(guī)劃的對(duì)偶規(guī)劃0, 030351546324624347min32132321321321xxxxxxxxxxxxxxz無約束，2022-5-618解：解：將原問題模型變形將原問題模型變形,0, 030351546324624347min32132321321321xxxxxxxxxxxxxxz無約束，321yyy11xx令則對(duì)偶問

10、題是則對(duì)偶問題是無約束32132132121321, 0,33464562734301524maxxyyxyyyyyyyyyyw321xxx2022-5-619小結(jié)：小結(jié)：對(duì)偶問題與原問題的關(guān)系：對(duì)偶問題與原問題的關(guān)系：原原問問題題 對(duì)對(duì)偶偶問問題題 目標(biāo)函數(shù)：目標(biāo)函數(shù)：MAX約束條件：約束條件：m個(gè)約束個(gè)約束變量變量 ： n個(gè)變量個(gè)變量目標(biāo)函數(shù)：目標(biāo)函數(shù)：MIN)(無約束0)(0約束條件：約束條件：n個(gè)約束個(gè)約束變量變量 ： m個(gè)變量個(gè)變量無約束0)(0)(約束條件右端項(xiàng)約束條件右端項(xiàng)價(jià)值系數(shù)價(jià)值系數(shù)價(jià)值系數(shù)價(jià)值系數(shù)約束條件右端項(xiàng)約束條件右端項(xiàng)2022-5-6203 對(duì)偶問題的基本性質(zhì)對(duì)偶問

11、題的基本性質(zhì)2、無界性、無界性 如果原問題（對(duì)偶問題）有無界解，則如果原問題（對(duì)偶問題）有無界解，則其對(duì)偶問題其對(duì)偶問題(原問題）無可行解。原問題）無可行解。就上節(jié)所討論的一般的線性規(guī)劃問題及其對(duì)偶問題，就上節(jié)所討論的一般的線性規(guī)劃問題及其對(duì)偶問題，有如下的性質(zhì)：有如下的性質(zhì)：1、弱對(duì)偶性、弱對(duì)偶性 如果如果 分別是原問題和對(duì)偶問題的可行解，則恒有分別是原問題和對(duì)偶問題的可行解，則恒有考慮利用考慮利用 及及 代入。代入。miiinjjjybxc11,jxnjmiyi,.1,.,1,miiijjyac1injjijbxa12022-5-6213、最優(yōu)性、最優(yōu)性如果如果 分別是原問題和對(duì)分別是原問

12、題和對(duì)偶問題的可行解，且有偶問題的可行解，且有則則 分別是原問題和對(duì)分別是原問題和對(duì)偶問題的偶問題的最優(yōu)解。最優(yōu)解。,jxnjmiyi,.1,.,1,miiinjjjybxc11,jxnjmiyi,.1,.,1,2022-5-622證明證明 設(shè)設(shè) 分別是原分別是原問題和對(duì)偶問題的最優(yōu)解，則由弱對(duì)偶性，問題和對(duì)偶問題的最優(yōu)解，則由弱對(duì)偶性，又又 ，所以，所以,jxnjmiyi,.1,.,1,miiimiiinjjjnjjjybybxcxc1111miiinjjjybxc11miiimiiinjjjnjjjybybxcxc11112022-5-6234、強(qiáng)對(duì)偶性、強(qiáng)對(duì)偶性 如果原問題有最優(yōu)解，則其

13、對(duì)如果原問題有最優(yōu)解，則其對(duì)偶問題也必有最優(yōu)解，且兩者最優(yōu)目標(biāo)函數(shù)值相偶問題也必有最優(yōu)解，且兩者最優(yōu)目標(biāo)函數(shù)值相等，即等，即 。wzminmax證明證明 設(shè)有線性規(guī)劃問題設(shè)有線性規(guī)劃問題經(jīng)單純形法計(jì)算后，令經(jīng)單純形法計(jì)算后，令 ,最終表中最終表中0,;maxssXXbXAXCXZ01BCYB2022-5-624b1BNIjNBCCBNN11BCYBBBCCBB10所以所以 ,即：即：由此可知由此可知 是對(duì)偶問題的是對(duì)偶問題的可行解可行解 ,又又 由最優(yōu)性知由最優(yōu)性知 就是最優(yōu)解。就是最優(yōu)解。0YACCYAYYbbBCCXB1Y2022-5-6255、互補(bǔ)松弛性：、互補(bǔ)松弛性：在線性規(guī)劃的最優(yōu)解

14、中，如果對(duì)在線性規(guī)劃的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值非零，則該約束條應(yīng)某一約束條件的對(duì)偶變量值非零，則該約束條件取嚴(yán)格等式；反之，如果約束條件取嚴(yán)格不等件取嚴(yán)格等式；反之，如果約束條件取嚴(yán)格不等式，則其對(duì)偶變量一定為零。即式，則其對(duì)偶變量一定為零。即若若 若若;,01injjijibxay則.0,1iinjjijybxa則2022-5-626證明證明 由弱對(duì)偶性知：由弱對(duì)偶性知：又因在最優(yōu)解中又因在最優(yōu)解中 ，于是上式，于是上式應(yīng)為等式，即有應(yīng)為等式，即有而而 故要使得上式成立，必有故要使得上式成立，必有miiimiijnjijnjjjybyxaxc1111miiinjjjybxc

15、110)(11111 imiijnjijmiiimiijnjijybxaybyxa; 01ijnjijbxa0 iy2022-5-627; 01ijnjijbxa.1ijnjijbxa后半部分是前一命體的逆否命題，自然成立。后半部分是前一命體的逆否命題，自然成立。互補(bǔ)松弛性還可寫為互補(bǔ)松弛性還可寫為對(duì)偶問題的相應(yīng)的互補(bǔ)松弛性見書對(duì)偶問題的相應(yīng)的互補(bǔ)松弛性見書 P58。例例 書書P76 ，習(xí)題，習(xí)題2-4;0SXY0SYX 即即2022-5-6286、設(shè)原問題與對(duì)偶問題分別是：設(shè)原問題與對(duì)偶問題分別是：則原問題的檢驗(yàn)數(shù)行對(duì)應(yīng)對(duì)偶問題的一個(gè)基解則原問題的檢驗(yàn)數(shù)行對(duì)應(yīng)對(duì)偶問題的一個(gè)基解（不一定是可行

16、解）（不一定是可行解），對(duì)應(yīng)關(guān)系如下表，對(duì)應(yīng)關(guān)系如下表 。0,maxssXXbXAXCXZ0,minSTSTTYYCYYAYbWbNBN11 BIjNBCCBN1BXNXSX1BCB1SY2SYYIB 2022-5-629說明：說明：原問題與對(duì)偶問題存在一對(duì)互補(bǔ)基解，原原問題與對(duì)偶問題存在一對(duì)互補(bǔ)基解，原問題的松弛變量與對(duì)偶問題的變量對(duì)應(yīng)；原問題問題的松弛變量與對(duì)偶問題的變量對(duì)應(yīng)；原問題的變量與對(duì)偶問題的剩余變量對(duì)應(yīng)。互補(bǔ)的基解的變量與對(duì)偶問題的剩余變量對(duì)應(yīng)?；パa(bǔ)的基解對(duì)應(yīng)的目標(biāo)函數(shù)值相等。對(duì)應(yīng)的目標(biāo)函數(shù)值相等。2022-5-630例例 書書P59 例例3 0,.,15x 5 16x 4122

17、2515241321xxxxxxx2132maxxxZ321yyy1y2y3y5y4y1x2x3x4x5xBCbBX1x4x2xj2022-5-631321151612minyyyW242.421yyyts0,.,35251531yyyyy1x2x1y2y3y4y5y1y3yb1x2x3x4x5xj2022-5-6321、 對(duì)偶變量對(duì)偶變量 可理解為對(duì)一個(gè)單位第可理解為對(duì)一個(gè)單位第 種資源種資源的估價(jià)，稱為的估價(jià)，稱為影子價(jià)格影子價(jià)格，但并非市場(chǎng)價(jià)格。，但并非市場(chǎng)價(jià)格。2、 對(duì)偶變量對(duì)偶變量 的值（即影子價(jià)格）表示第的值（即影子價(jià)格）表示第 種資種資源數(shù)量變化一個(gè)單位時(shí)，目標(biāo)函數(shù)的增量。源數(shù)量

18、變化一個(gè)單位時(shí)，目標(biāo)函數(shù)的增量。因?yàn)橐驗(yàn)? 4 影子價(jià)格影子價(jià)格0maxXbAXCXZ0minYCYAYbWTTT假設(shè)有假設(shè)有原問題原問題和和對(duì)偶問題對(duì)偶問題如下：如下：iyiiibzyiiy2022-5-6332132maxxxz資源增加一個(gè)單位時(shí)，最優(yōu)解及目標(biāo)函數(shù)值的變化資源增加一個(gè)單位時(shí)，最優(yōu)解及目標(biāo)函數(shù)值的變化1,132221zxx0,1741zx2 . 0,1652zx2x1xO1Q2Q3Q4Q342132xxZ目標(biāo)函數(shù)等值線2022-5-6343、 影子價(jià)格可用于指導(dǎo)資源的購入與賣出。影子價(jià)格可用于指導(dǎo)資源的購入與賣出。當(dāng)當(dāng) 影子價(jià)格影子價(jià)格 市場(chǎng)價(jià)格時(shí)市場(chǎng)價(jià)格時(shí)，買入；，買入；

19、影子價(jià)格影子價(jià)格 市場(chǎng)價(jià)格市場(chǎng)價(jià)格 時(shí)，賣出時(shí)，賣出.4、 由互補(bǔ)松弛性可知，由互補(bǔ)松弛性可知， 即影子價(jià)格為零。即影子價(jià)格為零。經(jīng)濟(jì)解釋：資源未用完，再增加對(duì)目標(biāo)函數(shù)也無貢經(jīng)濟(jì)解釋：資源未用完，再增加對(duì)目標(biāo)函數(shù)也無貢獻(xiàn)。獻(xiàn)。反之，反之， 表明該種資源用表明該種資源用盡，再購進(jìn)用于擴(kuò)大生產(chǎn)可增加總利潤。盡，再購進(jìn)用于擴(kuò)大生產(chǎn)可增加總利潤。 .0,1iinjjijybxa則;,01injjijibxay則2022-5-6355 5 對(duì)偶單純形法對(duì)偶單純形法在單純形表中，在單純形表中， 列對(duì)應(yīng)原問題的基可行解，列對(duì)應(yīng)原問題的基可行解， 行行對(duì)應(yīng)對(duì)偶問題的一個(gè)對(duì)應(yīng)對(duì)偶問題的一個(gè)基解基解（不一定可行）

20、，當(dāng)（不一定可行），當(dāng) 時(shí)，在檢驗(yàn)數(shù)行就得到對(duì)偶問題的時(shí)，在檢驗(yàn)數(shù)行就得到對(duì)偶問題的基可行解基可行解，此時(shí)，此時(shí)兩個(gè)問題的目標(biāo)函數(shù)值相等兩個(gè)問題的目標(biāo)函數(shù)值相等 ，由由最優(yōu)性條件最優(yōu)性條件知，兩個(gè)問題都達(dá)到了最優(yōu)解。知，兩個(gè)問題都達(dá)到了最優(yōu)解。j0b0jYbbBCCXB1單純形法：?jiǎn)渭冃畏ǎ赫乙粋€(gè)初始基可行解，保持找一個(gè)初始基可行解，保持b列為正，通列為正，通過迭代找到下一個(gè)基可行解，使目標(biāo)函數(shù)值不斷增大，過迭代找到下一個(gè)基可行解，使目標(biāo)函數(shù)值不斷增大，當(dāng)當(dāng)檢驗(yàn)數(shù)行全部小于等于零檢驗(yàn)數(shù)行全部小于等于零時(shí)，達(dá)到最優(yōu)解。時(shí)，達(dá)到最優(yōu)解。2022-5-636對(duì)偶單純形法思想：對(duì)偶單純形法思想：找一個(gè)

21、對(duì)偶問題的基可行解（保持找一個(gè)對(duì)偶問題的基可行解（保持 行非正），原行非正），原問題的解為基解（問題的解為基解（ b列可以為負(fù)），通過迭代，當(dāng)列可以為負(fù)），通過迭代，當(dāng)b列全部為正（原問題也達(dá)到了基可行解）列全部為正（原問題也達(dá)到了基可行解），即找到最，即找到最優(yōu)解。優(yōu)解。j2022-5-6373、檢查是否達(dá)最優(yōu)、檢查是否達(dá)最優(yōu) ：b列列 非負(fù)非負(fù)時(shí)達(dá)最優(yōu)，否則繼時(shí)達(dá)最優(yōu)，否則繼續(xù)續(xù)1、2。對(duì)偶單純形法計(jì)算步驟：對(duì)偶單純形法計(jì)算步驟：1、確定出基變量、確定出基變量 ：選擇選擇b列中負(fù)值最小者對(duì)應(yīng)變列中負(fù)值最小者對(duì)應(yīng)變量出基，即量出基，即 對(duì)應(yīng)的對(duì)應(yīng)的 為出為出基變量?；兞俊?、確定進(jìn)基變量、

22、確定進(jìn)基變量 ：最小比值規(guī)則，即以最小比值規(guī)則，即以 對(duì)應(yīng)的對(duì)應(yīng)的 為進(jìn)基變量，為進(jìn)基變量， 為主元素進(jìn)行迭代為主元素進(jìn)行迭代。0miniirbbbrxsjsrjrjjaaa0minsxrsa2022-5-6381、 為何只考慮為何只考慮 行中行中 的元素對(duì)應(yīng)的變量的元素對(duì)應(yīng)的變量進(jìn)基？進(jìn)基？為使迭代后的基變量取正值。為使迭代后的基變量取正值。rx0rja2、為何采用最小比值規(guī)則選擇進(jìn)基變量？、為何采用最小比值規(guī)則選擇進(jìn)基變量？為了使得為了使得迭代后的多偶問題解仍為可行解（檢驗(yàn)數(shù)行仍為非迭代后的多偶問題解仍為可行解（檢驗(yàn)數(shù)行仍為非正）正）2022-5-6393、 原問題無可行解的判別準(zhǔn)則：原問

23、題無可行解的判別準(zhǔn)則：當(dāng)對(duì)偶問題存在可當(dāng)對(duì)偶問題存在可行解時(shí)，若有某個(gè)行解時(shí)，若有某個(gè) ，而所有，而所有 ，則原問，則原問題無可行解，對(duì)偶問題目標(biāo)值無界。題無可行解，對(duì)偶問題目標(biāo)值無界。因?yàn)榈谝驗(yàn)榈趓 r行的約束方程即為：行的約束方程即為： 其中其中 ， ，因此不可能存在，因此不可能存在 使上使上式成立。也即原問題無可行解。式成立。也即原問題無可行解。0rb0rjarnnrmmrrbxaxax,11,.0rja0rb0X2022-5-640例例、用對(duì)偶單純形法求解下述問題、用對(duì)偶單純形法求解下述問題321151612minyyyW242.21yyts0,35232131yyyyy解解 將問題改

24、寫為目標(biāo)最大化，并化為標(biāo)準(zhǔn)型將問題改寫為目標(biāo)最大化，并化為標(biāo)準(zhǔn)型321151612)max(yyyW242.421yyyts0,.,35251531yyyyy2022-5-641列單純形表列單純形表 1y2y3y4y5yBCbBX4y5y4y3y1y3y達(dá)到最優(yōu)達(dá)到最優(yōu) 2022-5-642注意：注意：1、 使用對(duì)偶單純形法時(shí)，使用對(duì)偶單純形法時(shí)，當(dāng)約束條件是當(dāng)約束條件是 時(shí)，可時(shí)，可以不必添加人工變量。以不必添加人工變量。 2、使用對(duì)偶單純形法時(shí)，、使用對(duì)偶單純形法時(shí)，初始單純形表中要保證對(duì)初始單純形表中要保證對(duì)偶解為可行解常難以做到，偶解為可行解常難以做到， 所以一般不單獨(dú)使用，所以一般不

25、單獨(dú)使用，常與靈敏度分析結(jié)合使用。常與靈敏度分析結(jié)合使用。 2022-5-6436 6 靈敏度分析靈敏度分析靈敏度分析：靈敏度分析：線性規(guī)劃問題中的某些參數(shù)發(fā)生變線性規(guī)劃問題中的某些參數(shù)發(fā)生變化，對(duì)解的影響。（化，對(duì)解的影響。（C C，A A，b b）靈敏度分析的一般步驟：靈敏度分析的一般步驟：1 1、 將參數(shù)的改變經(jīng)計(jì)算后反映到最終單純形表中；將參數(shù)的改變經(jīng)計(jì)算后反映到最終單純形表中；2 2、 檢查原問題和對(duì)偶問題是否仍為可行解；檢查原問題和對(duì)偶問題是否仍為可行解； 3 3、 按照下表對(duì)應(yīng)情況，決定下一步驟。按照下表對(duì)應(yīng)情況，決定下一步驟。2022-5-6446.6.1 C 1 C 的變化分

26、析的變化分析 C C 的變化只影響檢驗(yàn)數(shù)。的變化只影響檢驗(yàn)數(shù)。例例1 1 設(shè)有如下的線性規(guī)劃模型設(shè)有如下的線性規(guī)劃模型試分析試分析 分別在什么范圍變化時(shí)，最優(yōu)解不變？分別在什么范圍變化時(shí)，最優(yōu)解不變？ 0,15 5 16 41222212121xxxxxx2132maxxxZ21,cc2022-5-6451x2x3x4x5xBCbBX1x4x2xj解：解：?jiǎn)栴}的最終單純形表如下：?jiǎn)栴}的最終單純形表如下：1x2x3x4x5xBCbBX1x4x2xj1c1c121c53511 c2022-5-6461 1、當(dāng)、當(dāng) 變化時(shí)，假設(shè)變化時(shí)，假設(shè) ，則要使得問題的，則要使得問題的 最優(yōu)解保持不變，則檢驗(yàn)數(shù)

27、行最優(yōu)解保持不變，則檢驗(yàn)數(shù)行 即可，即要求即可，即要求1c11cc00535115c02113c01 c31 c301 c02 2、當(dāng)、當(dāng) 變化時(shí)，假設(shè)變化時(shí)，假設(shè) ，則要使得問題的，則要使得問題的 最優(yōu)解保持不變，則檢驗(yàn)數(shù)行最優(yōu)解保持不變，則檢驗(yàn)數(shù)行 即可，即要求即可，即要求2c22cc0515225c01322 c2022-5-6476.6.2 b 2 b 的變化分析的變化分析b b的變化將只影響原問題的基可行解，即最終表的變化將只影響原問題的基可行解，即最終表中的中的b b列數(shù)值。列數(shù)值。例例2 設(shè)有如下的線性規(guī)劃模型設(shè)有如下的線性規(guī)劃模型試分析試分析 分別在什么范圍變化時(shí)，最優(yōu)基分別在

28、什么范圍變化時(shí)，最優(yōu)基不變？不變？ 0,15 5 16 41222212121xxxxxx2132maxxxZ321,bbb2022-5-648解：解：將將 重新計(jì)算后填入問題的最終單純形表：重新計(jì)算后填入問題的最終單純形表：1 1、當(dāng)、當(dāng) 變化時(shí)，假設(shè)變化時(shí)，假設(shè) ，則問題的解變?yōu)?，則問題的解變?yōu)樘钊胂卤?，得填入下表，?bbB111bb328b23b211516b5/1005/4125/102/1bBX11111x2x3x4x5xBCbBX1x4x2xj328b23b21112022-5-6490要使得最優(yōu)基保持不變，則要使得最優(yōu)基保持不變，則b b列數(shù)值列數(shù)值 即可，即即可，即要求要求0

29、1bB同理可得同理可得 的變化范圍是：的變化范圍是： 的變化范圍是：的變化范圍是：2b3b212b30103 b028b203b211114b6b1114b616.6.3 3 增加一個(gè)變量的變化分析增加一個(gè)變量的變化分析 增加一個(gè)變量，在方程組（矩陣增加一個(gè)變量，在方程組（矩陣A A）中就要增）中就要增加一個(gè)系數(shù)列，在原來的最終表中也要添加一加一個(gè)系數(shù)列，在原來的最終表中也要添加一列列 ，檢驗(yàn)數(shù)也要計(jì)算，其余部分不受影響。，檢驗(yàn)數(shù)也要計(jì)算，其余部分不受影響。如果檢驗(yàn)數(shù)行仍如果檢驗(yàn)數(shù)行仍 ，則最優(yōu)解不變，否則繼，則最優(yōu)解不變，否則繼續(xù)迭代尋找最優(yōu)。續(xù)迭代尋找最優(yōu)。一般分析步驟：一般分析步驟： 1

30、 1、計(jì)算增加的新變量系數(shù)列、計(jì)算增加的新變量系數(shù)列 在原最終表中的在原最終表中的結(jié)果結(jié)果 ； 2 2、計(jì)算新變量對(duì)應(yīng)的檢驗(yàn)數(shù)、計(jì)算新變量對(duì)應(yīng)的檢驗(yàn)數(shù) ； 3 3、根據(jù)、根據(jù) 的符號(hào)判斷是否仍是最優(yōu)解，若是，的符號(hào)判斷是否仍是最優(yōu)解，若是，最優(yōu)解不變；若不是，繼續(xù)求解。最優(yōu)解不變；若不是，繼續(xù)求解。2022-5-650jP0jjPjPjj2022-5-6510,15 5 16 41222212121xxxxxx2132maxxxZ例例3 3 設(shè)有如下的線性規(guī)劃模型設(shè)有如下的線性規(guī)劃模型, ,現(xiàn)增加變量現(xiàn)增加變量 ，其，其對(duì)應(yīng)系數(shù)列為對(duì)應(yīng)系數(shù)列為 ，價(jià)值系數(shù)，價(jià)值系數(shù) ，請(qǐng)，請(qǐng)問最優(yōu)解是否改變？

31、問最優(yōu)解是否改變？ TP)5 , 4 , 2(66x46C2022-5-652解：解：最終表最終表1x2x3x4x5xBCbBX1x4x2xj2022-5-6531405425/1005/4125/102/1616PBP1140)3 , 0 , 2(466jBPCc新變量的檢驗(yàn)數(shù)及系數(shù)列分別為：新變量的檢驗(yàn)數(shù)及系數(shù)列分別為：填入表中，易知未達(dá)最優(yōu)，繼續(xù)迭代求解。填入表中，易知未達(dá)最優(yōu)，繼續(xù)迭代求解。2022-5-6541x2x3x4x5xBCbBX1x4x2xj6x1x2x6x已達(dá)最優(yōu)。最優(yōu)解為已達(dá)最優(yōu)。最優(yōu)解為 最優(yōu)目標(biāo)值最優(yōu)目標(biāo)值1, 2, 3621xxx16z2022-5-6556.6.

32、4 4 增加一個(gè)約束條件的變化分析增加一個(gè)約束條件的變化分析 增加一個(gè)約束條件，相當(dāng)于增加一道工序。增加一個(gè)約束條件，相當(dāng)于增加一道工序。一般分析步驟：一般分析步驟： 1 1、先將原最優(yōu)解帶入此新約束，若滿足條件，、先將原最優(yōu)解帶入此新約束，若滿足條件，說明此約束未起作用，原最優(yōu)解不變；說明此約束未起作用，原最優(yōu)解不變； 2 2、否則，將新約束加入到最終表中，繼續(xù)分析。、否則，將新約束加入到最終表中，繼續(xù)分析。例例4 4 在上例中添加新約束在上例中添加新約束 ，分析，分析最優(yōu)解的變化情況。最優(yōu)解的變化情況。 解：解：因?yàn)閷⒃顑?yōu)解因?yàn)閷⒃顑?yōu)解 帶入此約束，帶入此約束，不滿足約束，原解已不是最

33、優(yōu)，繼續(xù)分析。不滿足約束，原解已不是最優(yōu)，繼續(xù)分析。142321 xx141532333, 321xx2022-5-6561423621xxx1x2x3x4x5xBCbBX1x4x2xj6x6x1x4x2x6x2022-5-6571x4x2x3x已達(dá)最優(yōu)。最優(yōu)解為已達(dá)最優(yōu)。最優(yōu)解為 最優(yōu)目標(biāo)值最優(yōu)目標(biāo)值316,32, 3,384321xxxx343z2022-5-6587 7 參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃：參數(shù)線性規(guī)劃：研究參數(shù)連續(xù)變化時(shí)最優(yōu)解的變化研究參數(shù)連續(xù)變化時(shí)最優(yōu)解的變化以及目標(biāo)函數(shù)值隨參數(shù)變化的情況。以及目標(biāo)函數(shù)值隨參數(shù)變化的情況。注：注：當(dāng)多個(gè)參數(shù)同時(shí)變化時(shí)，可以引入一個(gè)參

34、數(shù)當(dāng)多個(gè)參數(shù)同時(shí)變化時(shí)，可以引入一個(gè)參數(shù) 來表示這種變化。來表示這種變化。如：如：b b列多個(gè)值發(fā)生變化時(shí)，可表示成列多個(gè)值發(fā)生變化時(shí)，可表示成miabbiii,.,2 , 1,2022-5-659求解參數(shù)線性規(guī)劃的步驟：求解參數(shù)線性規(guī)劃的步驟：1 1、 令令 求解得最終單純形表；求解得最終單純形表；2 2、 將參數(shù)的變化反映到最終單純形表中；將參數(shù)的變化反映到最終單純形表中；3 3、 找到使得最優(yōu)解不變的參數(shù)變化范圍，在臨界找到使得最優(yōu)解不變的參數(shù)變化范圍，在臨界點(diǎn)處令參數(shù)增加或減少，分析最優(yōu)解的變化，并分點(diǎn)處令參數(shù)增加或減少，分析最優(yōu)解的變化，并分析目標(biāo)函數(shù)值隨參數(shù)變化的情況。析目標(biāo)函數(shù)值

35、隨參數(shù)變化的情況。02022-5-660例例5 5 求解下述參數(shù)線性規(guī)劃問題求解下述參數(shù)線性規(guī)劃問題: :0,15 5 16 41222212121xxxxxx21)3()22()(maxxxZ2022-5-661解：解：求得求得 時(shí)最終單純形表并將參數(shù)的變化填時(shí)最終單純形表并將參數(shù)的變化填入表中入表中 ： 0j1x2x3x4x5xBCbBX1x4x2x22322315512022-5-6621 1、由表可知，當(dāng)、由表可知，當(dāng) 時(shí)，即時(shí)，即 最優(yōu)解不變最優(yōu)解不變 目標(biāo)函數(shù)值是：目標(biāo)函數(shù)值是： 0551, 01111593)3(3)22()(z)3, 3(21xx2022-5-6632 2、 是

36、臨界點(diǎn)，當(dāng)是臨界點(diǎn)，當(dāng) 時(shí)，時(shí)， 所以選擇所以選擇 作為進(jìn)基變量，迭代一步得到：作為進(jìn)基變量，迭代一步得到：110551, 013x31x2x3x4x5xBCbBX3x4x2x223553222022-5-6640553, 0223 3、由上表可知，當(dāng)、由上表可知，當(dāng) 時(shí)，即時(shí)，即 最優(yōu)解不變最優(yōu)解不變 目標(biāo)函數(shù)值是目標(biāo)函數(shù)值是 13933)3(0)22()(z)3, 0(21xx2022-5-6654 4、 是臨界點(diǎn)，當(dāng)是臨界點(diǎn)，當(dāng) 時(shí)，時(shí)， 所以選擇所以選擇 作為進(jìn)基變量，迭代一步得到：作為進(jìn)基變量，迭代一步得到：335x0553, 0222231x2x3x4x5xBCbBX3x4x5x2

37、232022-5-6665 5、由上表可知，當(dāng)、由上表可知，當(dāng) 時(shí)，最優(yōu)解不再變化。時(shí)，最優(yōu)解不再變化。目標(biāo)函數(shù)值是目標(biāo)函數(shù)值是 315,16,12, 0, 055421xxxxx00)3(0)22()(z6 6、 是臨界點(diǎn)，當(dāng)是臨界點(diǎn)，當(dāng) 時(shí)，時(shí)， 所以選擇所以選擇 作為進(jìn)基變量，迭代一步得到：作為進(jìn)基變量，迭代一步得到：110551, 015x2022-5-6671x2x3x4x5xBCbBX1x5x2x223223223441此時(shí)無論此時(shí)無論 如何增加，檢驗(yàn)數(shù)始終為負(fù)，最優(yōu)解不如何增加，檢驗(yàn)數(shù)始終為負(fù)，最優(yōu)解不再變化。目標(biāo)函數(shù)值是再變化。目標(biāo)函數(shù)值是 14102)3(4)22()(z2022-5-66893)(z159)(z1524341410)(z)(z1-12-2-3341410)(z)(z2022-5-669例例6 6某文教用品廠利用原材料白坯紙生產(chǎn)原稿紙、日某文教用品廠利用原材料白坯紙生