運籌(第二章對偶與靈敏度分析)

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

2、將系數(shù)矩陣表示成：2022-3-94初始單純形表初始單純形表初始解初始解 非基變量非基變量 基變量基變量 0bBNIjN基可行解基可行解基變量基變量 非基變量非基變量 0初等行變換后初等行變換后b1BNIjNmyy., 1ICBC初始表中是初始表中是 I 的位置，經(jīng)變換后成為的位置，經(jīng)變換后成為 .1B2022-3-95其中其中),.,(21myyyY 10BCYB1BCYB則則 YNCNBCCNBNN1例：書例：書 P36 P36 例例1010，驗證上述公式。，驗證上述公式。 jjPBPNBN11,或;1bBb上述公式對于靈敏度分析很有幫助上述公式對于靈敏度分析很有幫助 。 記記2022-3

3、-96例例 甲方生產(chǎn)計劃問題：甲方生產(chǎn)計劃問題： 能力能力 設備設備A 2 2 12 設備設備B 4 0 16 設備設備C 0 5 15 利潤利潤 2 3，各生產(chǎn)多少各生產(chǎn)多少, , 可獲最大利潤可獲最大利潤? ?1 1.2 .2 對偶問題的提出對偶問題的提出 設有原問題設有原問題 2022-3-97現(xiàn)在現(xiàn)在乙方乙方租借設備租借設備, ,甲方以何種價格將設備甲方以何種價格將設備A A、B B、C C租借給乙方比較合理？租借給乙方比較合理？ 請為其定價。請為其定價。思路思路： 就甲方而言就甲方而言， 租金收入應不低于將設備用租金收入應不低于將設備用于自己生產(chǎn)時的利潤。于自己生產(chǎn)時的利潤。而就乙方

4、而言而就乙方而言，希望甲方的租金收入在滿足約束的，希望甲方的租金收入在滿足約束的條件下越小越好，這樣雙方才可能達成協(xié)議。條件下越小越好，這樣雙方才可能達成協(xié)議。解：解： 假設假設A A、B B、C C的單位租金分別為的單位租金分別為 。321,yyy2022-3-98于是得到下述于是得到下述 的線性規(guī)劃模型：的線性規(guī)劃模型：生產(chǎn)產(chǎn)品生產(chǎn)產(chǎn)品的資源用于出租時，租金收入應滿足：的資源用于出租時，租金收入應滿足：24221 yy類似的，生產(chǎn)產(chǎn)品類似的，生產(chǎn)產(chǎn)品的資源用于出租時，租金收入的資源用于出租時，租金收入應滿足：應滿足：35231 yy總的租金收入：總的租金收入：321151612yyy321

5、151612minyyyW242.21yyts0,35232131yyyyy2022-3-990,15 5 16 41222212121xxxxxx2132maxxxZ321151612minyyyW0,352242213121yyyyyy原問題原問題 對偶問題對偶問題 2022-3-910原問題原問題 對偶問題對偶問題 用矩陣將上述原問題對偶問題寫出用矩陣將上述原問題對偶問題寫出0151612500422) 3 , 2(max2121XbxxAXxxCXZ032502042)15,16,12(min321321YcyyyYAyyyYbWTTT2022-3-911即：即：原原問問題題 0max

6、XbAXCXZ0minYCYAYbWTTT對對偶偶問問題題 2022-3-9120,212211222222121111212111nmmnmnmmnnnnxxxybxaxaxaybxaxaxaybxaxaxannxcxcxcz2211max2 2 原問題與對偶問題原問題與對偶問題對于一般的線性規(guī)劃問題對于一般的線性規(guī)劃問題2022-3-913類似于前面的資源定價問題，每一個約束條件對類似于前面的資源定價問題，每一個約束條件對應一個應一個“ 對偶變量對偶變量”，它就相當于給各資源的單，它就相當于給各資源的單位定價。于是我們有如下的位定價。于是我們有如下的對偶規(guī)劃對偶規(guī)劃：0,212211222

7、222112111221111mnnmmnnnmmmmyyyxcyayayaxcyayayaxcyayayammybybybW2211min2022-3-914對偶問題與原問題的關系：對偶問題與原問題的關系：原原問問題題 對對偶偶問問題題 目標函數(shù)：目標函數(shù)：MAXMAX約束條件：約束條件：m m個個變量變量 ： n個個目標函數(shù)：目標函數(shù)：MINbAX 0X約束條件：約束條件：n個個變量變量 ： m個個CXZ maxYbWTminTTCYA0Y2022-3-915這是規(guī)范形式這是規(guī)范形式 的原問題，由此寫出其對偶問題如的原問題，由此寫出其對偶問題如右方所示，那么，當原問題不是規(guī)范形式時，應右方

8、所示，那么，當原問題不是規(guī)范形式時，應如何寫出其對偶問題？如何寫出其對偶問題？可以先將原問題化成規(guī)范的原問題，再寫出對偶可以先將原問題化成規(guī)范的原問題，再寫出對偶問題。問題。2022-3-916例例 寫出下述規(guī)劃的對偶問題寫出下述規(guī)劃的對偶問題321151612minyyyW242.21 yyts0,35232131yyyyy于是對偶問題即為：于是對偶問題即為：321151612)max(yyyW2-4-2-.21yyt s0,35232131yyyyy0,15- 5- 16- 4-12-2-2-212121xxxxxx2132)(inxxZm解解 先將該問題化為規(guī)范形式先將該問題化為規(guī)范形式

9、也即為：也即為：0,15 5 16 41222212121xxxxxx2132maxxxZ互為對偶互為對偶2022-3-917如何寫出非規(guī)范的原問題相應的對偶問題：如何寫出非規(guī)范的原問題相應的對偶問題：1. 目標函數(shù)目標函數(shù)MIN MAX 2. 約束條件約束條件3. 約束條件約束條件 = ? 4. 變量變量 ? 無約束或 0例：例：P55 例例2，寫出下，寫出下面規(guī)劃的對偶規(guī)劃面規(guī)劃的對偶規(guī)劃0, 030351546324624347min32132321321321xxxxxxxxxxxxxxz無約束，2022-3-918解：解：將原問題模型變形將原問題模型變形,0, 03035154632

10、4624347min32132321321321xxxxxxxxxxxxxxz無約束，321yyy11xx令則對偶問題是則對偶問題是無約束32132132121321, 0,33464562734301524maxxyyxyyyyyyyyyyw321xxx2022-3-919小結(jié)：小結(jié)：對偶問題與原問題的關系：對偶問題與原問題的關系：原原問問題題 對對偶偶問問題題 目標函數(shù)：目標函數(shù)：MAX約束條件：約束條件：m個約束個約束變量變量 ： n個變量個變量目標函數(shù)：目標函數(shù)：MIN)(無約束0)(0約束條件：約束條件：n個約束個約束變量變量 ： m個變量個變量無約束0)(0)(約束條件右端項約束條

11、件右端項價值系數(shù)價值系數(shù)價值系數(shù)價值系數(shù)約束條件右端項約束條件右端項2022-3-9203 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)2、無界性、無界性 如果原問題（對偶問題）有無界解，則如果原問題（對偶問題）有無界解，則其對偶問題其對偶問題(原問題）無可行解。原問題）無可行解。就上節(jié)所討論的一般的線性規(guī)劃問題及其對偶問題，就上節(jié)所討論的一般的線性規(guī)劃問題及其對偶問題，有如下的性質(zhì)：有如下的性質(zhì)：1、弱對偶性、弱對偶性 如果如果 分別是原問題和對偶問題的可行解，則恒有分別是原問題和對偶問題的可行解，則恒有考慮利用考慮利用 及及 代入。代入。miiinjjjybxc11,jxnjmiyi,.1,.,1

12、,miiijjyac1injjijbxa12022-3-9213、最優(yōu)性、最優(yōu)性如果如果 分別是原問題和對分別是原問題和對偶問題的可行解，且有偶問題的可行解，且有則則 分別是原問題和對分別是原問題和對偶問題的偶問題的最優(yōu)解。最優(yōu)解。,jxnjmiyi,.1,.,1,miiinjjjybxc11,jxnjmiyi,.1,.,1,2022-3-922證明證明 設設 分別是原分別是原問題和對偶問題的最優(yōu)解，則由弱對偶性，問題和對偶問題的最優(yōu)解，則由弱對偶性，又又 ，所以，所以,jxnjmiyi,.1,.,1,miiimiiinjjjnjjjybybxcxc1111miiinjjjybxc11miii

13、miiinjjjnjjjybybxcxc11112022-3-9234、強對偶性、強對偶性 如果原問題有最優(yōu)解，則其對如果原問題有最優(yōu)解，則其對偶問題也必有最優(yōu)解，且兩者最優(yōu)目標函數(shù)值相偶問題也必有最優(yōu)解，且兩者最優(yōu)目標函數(shù)值相等，即等，即 。wzminmax證明證明 設有線性規(guī)劃問題設有線性規(guī)劃問題經(jīng)單純形法計算后，令經(jīng)單純形法計算后，令 ,最終表中最終表中0,;maxssXXbXAXCXZ01BCYB2022-3-924基可行解基變量 非基變量 b1BNIjNBCCBNN11BCYBBBCCBB10所以所以 ,即：即：由此可知由此可知 是對偶問題的是對偶問題的可行解可行解 ,又又 由最優(yōu)性

14、知由最優(yōu)性知 就是最優(yōu)解。就是最優(yōu)解。0YACCYAYYbbBCCXB1Y2022-3-9255、互補松弛性：、互補松弛性：在線性規(guī)劃的最優(yōu)解中，如果對在線性規(guī)劃的最優(yōu)解中，如果對應某一約束條件的對偶變量值非零，則該約束條應某一約束條件的對偶變量值非零，則該約束條件取嚴格等式；反之，如果約束條件取嚴格不等件取嚴格等式；反之，如果約束條件取嚴格不等式，則其對偶變量一定為零。即式，則其對偶變量一定為零。即若若 若若;,01injjijibxay則.0,1iinjjijybxa則2022-3-926證明證明 由弱對偶性知：由弱對偶性知：又因在最優(yōu)解中又因在最優(yōu)解中 ，于是上式，于是上式應為等式，即有

15、應為等式，即有而而 故要使得上式成立，必有故要使得上式成立，必有miiimiijnjijnjjjybyxaxc1111miiinjjjybxc110)(11111 imiijnjijmiiimiijnjijybxaybyxa; 01ijnjijbxa0 iy2022-3-927; 01ijnjijbxa.1ijnjijbxa后半部分是前一命體的逆否命題，自然成立。后半部分是前一命體的逆否命題，自然成立?；パa松弛性還可寫為互補松弛性還可寫為對偶問題的相應的互補松弛性見書對偶問題的相應的互補松弛性見書 P58。例例 書書P76 ，習題，習題2-4;0SXY0SYX 即即2022-3-9286、設原

16、問題與對偶問題分別是：設原問題與對偶問題分別是：則原問題的檢驗數(shù)行對應對偶問題的一個基解則原問題的檢驗數(shù)行對應對偶問題的一個基解（不一定是可行解）（不一定是可行解），對應關系如下表，對應關系如下表 。0,maxssXXbXAXCXZ0,minSTSTTYYCYYAYbW初始解 非基變量 基變量 0bNBN11 BIjNBCCBN1BXNXSX1BCB1SY2SYYIB 2022-3-929說明：說明：原問題與對偶問題存在一對互補基解，原原問題與對偶問題存在一對互補基解，原問題的松弛變量與對偶問題的變量對應；原問題問題的松弛變量與對偶問題的變量對應；原問題的變量與對偶問題的剩余變量對應?；パa的基

17、解的變量與對偶問題的剩余變量對應。互補的基解對應的目標函數(shù)值相等。對應的目標函數(shù)值相等。2022-3-930例例 書書P59 例例3 0,.,15x 5 16x 41222515241321xxxxxxx2132maxxxZ321yyy2300023101/20-1/50400-214/53501001/500-10-1/51y2y3y5y4y1x2x3x4x5xBCbBX1x4x2xj2022-3-931基1120-1/201/50-4/511/5-1/504033321151612minyyyW242.421yyyts0,.,35251531yyyyy1x2x1y2y3y4y5y1y3yb

18、1x2x3x4x5xj2022-3-9321、 對偶變量對偶變量 可理解為對一個單位第可理解為對一個單位第 種資源種資源的估價，稱為的估價，稱為影子價格影子價格，但并非市場價格。，但并非市場價格。2、 對偶變量對偶變量 的值（即影子價格）表示第的值（即影子價格）表示第 種資種資源數(shù)量變化一個單位時，目標函數(shù)的增量。源數(shù)量變化一個單位時，目標函數(shù)的增量。因為因為4 4 影子價格影子價格0maxXbAXCXZ0minYCYAYbWTTT假設有假設有原問題原問題和和對偶問題對偶問題如下：如下：iyiiibzyiiy2022-3-9332132maxxxz資源增加一個單位時，最優(yōu)解及目標函數(shù)值的變化資

19、源增加一個單位時，最優(yōu)解及目標函數(shù)值的變化1,132221zxx0,1741zx2 . 0,1652zx2x1xO1Q2Q3Q4Q342132xxZ目標函數(shù)等值線2022-3-9343、 影子價格可用于指導資源的購入與賣出。影子價格可用于指導資源的購入與賣出。當當 影子價格影子價格 市場價格時市場價格時，買入；，買入； 影子價格影子價格 市場價格市場價格 時，賣出時，賣出.4、 由互補松弛性可知，由互補松弛性可知， 即影子價格為零。即影子價格為零。經(jīng)濟解釋：資源未用完，再增加對目標函數(shù)也無貢經(jīng)濟解釋：資源未用完，再增加對目標函數(shù)也無貢獻。獻。反之，反之， 表明該種資源用表明該種資源用盡，再購進

20、用于擴大生產(chǎn)可增加總利潤。盡，再購進用于擴大生產(chǎn)可增加總利潤。 .0,1iinjjijybxa則;,01injjijibxay則2022-3-9355 5 對偶單純形法對偶單純形法在單純形表中，在單純形表中， 列對應原問題的基可行解，列對應原問題的基可行解， 行行對應對偶問題的一個對應對偶問題的一個基解基解（不一定可行），當（不一定可行），當 時，在檢驗數(shù)行就得到對偶問題的時，在檢驗數(shù)行就得到對偶問題的基可行解基可行解，此時，此時兩個問題的目標函數(shù)值相等兩個問題的目標函數(shù)值相等 ，由由最優(yōu)性條件最優(yōu)性條件知，兩個問題都達到了最優(yōu)解。知，兩個問題都達到了最優(yōu)解。j0b0jYbbBCCXB1單純形

21、法：單純形法：找一個初始基可行解，保持找一個初始基可行解，保持b列為正，通列為正，通過迭代找到下一個基可行解，使目標函數(shù)值不斷增大，過迭代找到下一個基可行解，使目標函數(shù)值不斷增大，當當檢驗數(shù)行全部小于等于零檢驗數(shù)行全部小于等于零時，達到最優(yōu)解。時，達到最優(yōu)解。2022-3-936對偶單純形法思想：對偶單純形法思想：找一個對偶問題的基可行解（保持找一個對偶問題的基可行解（保持 行非正），原行非正），原問題的解為基解（問題的解為基解（ b列可以為負），通過迭代，當列可以為負），通過迭代，當b列全部為正（原問題也達到了基可行解）列全部為正（原問題也達到了基可行解），即找到最，即找到最優(yōu)解。優(yōu)解。j2

22、022-3-9373、檢查是否達最優(yōu)、檢查是否達最優(yōu) ：b列列 非負非負時達最優(yōu)，否則繼時達最優(yōu)，否則繼續(xù)續(xù)1、2。對偶單純形法計算步驟：對偶單純形法計算步驟：1、確定出基變量、確定出基變量 ：選擇選擇b列中負值最小者對應變列中負值最小者對應變量出基，即量出基，即 對應的對應的 為出為出基變量?；兞俊?、確定進基變量、確定進基變量 ：最小比值規(guī)則，即以最小比值規(guī)則，即以 對應的對應的 為進基變量，為進基變量， 為主元素進行迭代為主元素進行迭代。0miniirbbbrxsjsrjrjjaaa0minsxrsa2022-3-9381、 為何只考慮為何只考慮 行中行中 的元素對應的變量的元素對應的

23、變量進基？進基？為使迭代后的基變量取正值。為使迭代后的基變量取正值。rx0rja2、為何采用最小比值規(guī)則選擇進基變量？、為何采用最小比值規(guī)則選擇進基變量？為了使得為了使得迭代后的多偶問題解仍為可行解（檢驗數(shù)行仍為非迭代后的多偶問題解仍為可行解（檢驗數(shù)行仍為非正）正）2022-3-9393、 原問題無可行解的判別準則：原問題無可行解的判別準則：當對偶問題存在可當對偶問題存在可行解時，若有某個行解時，若有某個 ，而所有，而所有 ，則原問，則原問題無可行解，對偶問題目標值無界。題無可行解，對偶問題目標值無界。因為第因為第r r行的約束方程即為：行的約束方程即為： 其中其中 ， ，因此不可能存在，因此

24、不可能存在 使上使上式成立。也即原問題無可行解。式成立。也即原問題無可行解。0rb0rjarnnrmmrrbxaxax,11,.0rja0rb0X2022-3-940例例、用對偶單純形法求解下述問題、用對偶單純形法求解下述問題321151612minyyyW242.21yyts0,35232131yyyyy解解 將問題改寫為目標最大化，并化為標準型將問題改寫為目標最大化，并化為標準型321151612)max(yyyW242.421yyyts0,.,35251531yyyyy2022-3-941列單純形表列單純形表 -12-16-15000-2-2-40100-3-20-501-12-16-1

25、5001y2y3y4y5yBCbBX4y5y0-2-2-4010-153/52/5010-1/5-6-1600-34y3y-121120-1/20-151/50-4/511/5-1/50-40-3-31y3y達到最優(yōu)達到最優(yōu) 2022-3-942注意：注意：1、 使用對偶單純形法時，使用對偶單純形法時，當約束條件是當約束條件是 時，可時，可以不必添加人工變量。以不必添加人工變量。 2、使用對偶單純形法時，、使用對偶單純形法時，初始單純形表中要保證對初始單純形表中要保證對偶解為可行解常難以做到，偶解為可行解常難以做到， 所以一般不單獨使用，所以一般不單獨使用，常與靈敏度分析結(jié)合使用。常與靈敏度分

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

27、形法繼續(xù)迭代得到新的最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代得到新的最優(yōu)解非可行解非可行解引入人工變量，重新編單純形表，重新計算2022-3-9446.6.1 C 1 C 的變化分析的變化分析 C C 的變化只影響檢驗數(shù)。的變化只影響檢驗數(shù)。例例1 1 設有如下的線性規(guī)劃模型設有如下的線性規(guī)劃模型試分析試分析 分別在什么范圍變化時，最優(yōu)解不變？分別在什么范圍變化時，最優(yōu)解不變？ 0,15 5 16 41222212121xxxxxx2132maxxxZ21,cc2022-3-9452300023101/20-1/50400-214/53301001/500-10-1/51x2x3x4x5xB

28、CbBX1x4x2xj解：解：問題的最終單純形表如下：問題的最終單純形表如下：30003101/20-1/50400-214/53301001/50001x2x3x4x5xBCbBX1x4x2xj1c1c121c53511 c2022-3-9461 1、當、當 變化時，假設變化時，假設 ，則要使得問題的，則要使得問題的 最優(yōu)解保持不變，則檢驗數(shù)行最優(yōu)解保持不變，則檢驗數(shù)行 即可，即要求即可，即要求1c11cc00535115c02113c01 c31 c301 c02 2、當、當 變化時，假設變化時，假設 ，則要使得問題的，則要使得問題的 最優(yōu)解保持不變，則檢驗數(shù)行最優(yōu)解保持不變，則檢驗數(shù)行

29、即可，即要求即可，即要求2c22cc0515225c01322 c2022-3-9476.6.2 b 2 b 的變化分析的變化分析b b的變化將只影響原問題的基可行解，即最終表的變化將只影響原問題的基可行解，即最終表中的中的b b列數(shù)值。列數(shù)值。例例2 設有如下的線性規(guī)劃模型設有如下的線性規(guī)劃模型試分析試分析 分別在什么范圍變化時，最優(yōu)基分別在什么范圍變化時，最優(yōu)基不變？不變？ 0,15 5 16 41222212121xxxxxx2132maxxxZ321,bbb2022-3-948解：解：將將 重新計算后填入問題的最終單純形表：重新計算后填入問題的最終單純形表：1 1、當、當 變化時，假設

30、變化時，假設 ，則問題的解變?yōu)?，則問題的解變?yōu)樘钊胂卤恚锰钊胂卤?，?bbB111bb328b23b211516b5/1005/4125/102/1bBX1111230002101/20-1/5000-214/5301001/500-10-1/51x2x3x4x5xBCbBX1x4x2xj328b23b21112022-3-9490要使得最優(yōu)基保持不變，則要使得最優(yōu)基保持不變，則b b列數(shù)值列數(shù)值 即可，即即可，即要求要求01bB同理可得同理可得 的變化范圍是：的變化范圍是： 的變化范圍是：的變化范圍是：2b3b212b30103 b028b203b211114b6b1114b616.6.3

31、 3 增加一個變量的變化分析增加一個變量的變化分析 增加一個變量，在方程組（矩陣增加一個變量，在方程組（矩陣A A）中就要增）中就要增加一個系數(shù)列，在原來的最終表中也要添加一加一個系數(shù)列，在原來的最終表中也要添加一列列 ，檢驗數(shù)也要計算，其余部分不受影響。，檢驗數(shù)也要計算，其余部分不受影響。如果檢驗數(shù)行仍如果檢驗數(shù)行仍 ，則最優(yōu)解不變，否則繼，則最優(yōu)解不變，否則繼續(xù)迭代尋找最優(yōu)。續(xù)迭代尋找最優(yōu)。一般分析步驟：一般分析步驟： 1 1、計算增加的新變量系數(shù)列、計算增加的新變量系數(shù)列 在原最終表中的在原最終表中的結(jié)果結(jié)果 ； 2 2、計算新變量對應的檢驗數(shù)、計算新變量對應的檢驗數(shù) ； 3 3、根據(jù)、

32、根據(jù) 的符號判斷是否仍是最優(yōu)解，若是，的符號判斷是否仍是最優(yōu)解，若是，最優(yōu)解不變；若不是，繼續(xù)求解。最優(yōu)解不變；若不是，繼續(xù)求解。2022-3-950jP0jjPjPjj2022-3-9510,15 5 16 41222212121xxxxxx2132maxxxZ例例3 3 設有如下的線性規(guī)劃模型設有如下的線性規(guī)劃模型, ,現(xiàn)增加變量現(xiàn)增加變量 ，其，其對應系數(shù)列為對應系數(shù)列為 ，價值系數(shù)，價值系數(shù) ，請，請問最優(yōu)解是否改變？問最優(yōu)解是否改變？ TP)5 , 4 , 2(66x46C2022-3-952解：解：最終表最終表2300023101/20-1/50400-214/53301001/5

33、00-10-1/51x2x3x4x5xBCbBX1x4x2xj2022-3-9531405425/1005/4125/102/1616PBP1140)3 , 0 , 2(466jBPCc新變量的檢驗數(shù)及系數(shù)列分別為：新變量的檢驗數(shù)及系數(shù)列分別為：填入表中，易知未達最優(yōu)，繼續(xù)迭代求解。填入表中，易知未達最優(yōu)，繼續(xù)迭代求解。2022-3-9542300023101/20-1/50400-214/53301001/500-10-1/51x2x3x4x5xBCbBX1x4x2xj6x23101/20-1/50100-1/21/41/532011/2-1/4000-1/2-1/4-2/501004041

34、11x2x6x已達最優(yōu)。最優(yōu)解為已達最優(yōu)。最優(yōu)解為 最優(yōu)目標值最優(yōu)目標值1, 2, 3621xxx16z2022-3-9556.6.4 4 增加一個約束條件的變化分析增加一個約束條件的變化分析 增加一個約束條件，相當于增加一道工序。增加一個約束條件，相當于增加一道工序。一般分析步驟：一般分析步驟： 1 1、先將原最優(yōu)解帶入此新約束，若滿足條件，、先將原最優(yōu)解帶入此新約束，若滿足條件，說明此約束未起作用，原最優(yōu)解不變；說明此約束未起作用，原最優(yōu)解不變； 2 2、否則，將新約束加入到最終表中，繼續(xù)分析。、否則，將新約束加入到最終表中，繼續(xù)分析。例例4 4 在上例中添加新約束在上例中添加新約束 ，分

35、析，分析最優(yōu)解的變化情況。最優(yōu)解的變化情況。 解：解：因為將原最優(yōu)解因為將原最優(yōu)解 帶入此約束，帶入此約束，不滿足約束，原解已不是最優(yōu)，繼續(xù)分析。不滿足約束，原解已不是最優(yōu)，繼續(xù)分析。142321 xx141532333, 321xx2022-3-9561423621xxx2300023101/20-1/50400-214/53301001/50143200000-10-1/50000101x2x3x4x5xBCbBX1x4x2xj6x23101/20-1/50400-214/53301001/50-100-3/201/500-10-1/5000106x1x4x2x6x2022-3-95728

36、/31000-1/10016/300018/153301001/502/30010-2/150000-2/51x4x2x3x1/3-4/30-2/3-2/3已達最優(yōu)。最優(yōu)解為已達最優(yōu)。最優(yōu)解為 最優(yōu)目標值最優(yōu)目標值316,32, 3,384321xxxx343z2022-3-9587 7 參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃：參數(shù)線性規(guī)劃：研究參數(shù)連續(xù)變化時最優(yōu)解的變化研究參數(shù)連續(xù)變化時最優(yōu)解的變化以及目標函數(shù)值隨參數(shù)變化的情況。以及目標函數(shù)值隨參數(shù)變化的情況。注：注：當多個參數(shù)同時變化時，可以引入一個參數(shù)當多個參數(shù)同時變化時，可以引入一個參數(shù) 來表示這種變化。來表示這種變化。如：如：b b列

37、多個值發(fā)生變化時，可表示成列多個值發(fā)生變化時，可表示成miabbiii,.,2 , 1,2022-3-959求解參數(shù)線性規(guī)劃的步驟：求解參數(shù)線性規(guī)劃的步驟：1 1、 令令 求解得最終單純形表；求解得最終單純形表；2 2、 將參數(shù)的變化反映到最終單純形表中；將參數(shù)的變化反映到最終單純形表中；3 3、 找到使得最優(yōu)解不變的參數(shù)變化范圍，在臨界找到使得最優(yōu)解不變的參數(shù)變化范圍，在臨界點處令參數(shù)增加或減少，分析最優(yōu)解的變化，并分點處令參數(shù)增加或減少，分析最優(yōu)解的變化，并分析目標函數(shù)值隨參數(shù)變化的情況。析目標函數(shù)值隨參數(shù)變化的情況。02022-3-960例例5 5 求解下述參數(shù)線性規(guī)劃問題求解下述參數(shù)線

38、性規(guī)劃問題: :0,15 5 16 41222212121xxxxxx21)3()22()(maxxxZ2022-3-961解：解：求得求得 時最終單純形表并將參數(shù)的變化填時最終單純形表并將參數(shù)的變化填入表中入表中 ： 00003101/20-1/50400-214/5301001/5000j1x2x3x4x5xBCbBX1x4x2x22322315512022-3-9621 1、由表可知，當、由表可知，當 時，即時，即 最優(yōu)解不變最優(yōu)解不變 目標函數(shù)值是：目標函數(shù)值是： 0551, 01111593)3(3)22()(z)3, 3(21xx2022-3-9632 2、 是臨界點，當是臨界點，

39、當 時，時， 所以選擇所以選擇 作為進基變量，迭代一步得到：作為進基變量，迭代一步得到：110551, 013x000062010-2/501640010301001/500031x2x3x4x5xBCbBX3x4x2x223553222022-3-9640553, 0223 3、由上表可知，當、由上表可知，當 時，即時，即 最優(yōu)解不變最優(yōu)解不變 目標函數(shù)值是目標函數(shù)值是 13933)3(0)22()(z)3, 0(21xx2022-3-9654 4、 是臨界點，當是臨界點，當 時，時， 所以選擇所以選擇 作為進基變量，迭代一步得到：作為進基變量，迭代一步得到：335x0553, 022000

40、0122210001640010015050010002231x2x3x4x5xBCbBX3x4x5x2232022-3-9665 5、由上表可知，當、由上表可知，當 時，最優(yōu)解不再變化。時，最優(yōu)解不再變化。目標函數(shù)值是目標函數(shù)值是 315,16,12, 0, 055421xxxxx00)3(0)22()(z6 6、 是臨界點，當是臨界點，當 時，時， 所以選擇所以選擇 作為進基變量，迭代一步得到：作為進基變量，迭代一步得到：110551, 015x2022-3-96700041001/400500-5/25/412011/2-1/400001x2x3x4x5xBCbBX1x5x2x223223223441此時無論此時無論 如何增加，檢驗數(shù)始終為負，最優(yōu)解不如何增加，檢驗數(shù)始終為負，最優(yōu)解不再變化。目標函數(shù)值是再變化。目標函數(shù)值是 14102)3(4)22()(z2022-3-96893)(z159)(z1524341410)(z)(z1-12-2-3341410)(z)(z2022-3-969例例6 6某文教用品廠利用原材料白坯紙生產(chǎn)原稿紙、日某文教用品廠利用原材料白坯紙生產(chǎn)原稿紙、日記本、練習本三種產(chǎn)品，該廠現(xiàn)有工人記本、練習本三種產(chǎn)品