運籌學目標規(guī)劃

1、運籌學運籌學 第四章第四章 目標規(guī)劃目標規(guī)劃 第四章第四章 目標規(guī)劃目標規(guī)劃 目標規(guī)劃的求解方法目標規(guī)劃的求解方法 本章內容本章內容 目標規(guī)劃的數(shù)學模型目標規(guī)劃的數(shù)學模型 目標規(guī)劃的靈敏度分析及應用舉例目標規(guī)劃的靈敏度分析及應用舉例 目的：目的：掌握掌握目標規(guī)劃的數(shù)學模型及求解目標規(guī)劃的數(shù)學模型及求解 理解理解目標規(guī)劃的靈敏度分析目標規(guī)劃的靈敏度分析 例例1、某廠計劃在下一個生產周期內生產甲、乙兩種產品，、某廠計劃在下一個生產周期內生產甲、乙兩種產品， 已知資料如表所示。試制定生產計劃，使獲得的利潤最大，已知資料如表所示。試制定生產計劃，使獲得的利潤最大， 試建立數(shù)學模型。試建立數(shù)學模型。 引

2、言：引言： 12070單件利潤單件利潤 3000103設備臺時設備臺時 200054煤炭煤炭 360049鋼材鋼材 資源限制資源限制乙乙甲甲 單位單位 產品產品 資源資源 消耗消耗 例例2、某廠計劃在下一個生產周期內生產甲、乙兩種產品，、某廠計劃在下一個生產周期內生產甲、乙兩種產品， 已知資料如表所示。試制定生產計劃，使獲得的利潤最大。已知資料如表所示。試制定生產計劃，使獲得的利潤最大。 試建立數(shù)學模型。試建立數(shù)學模型。 12070單件利潤單件利潤 3000103設備臺時設備臺時 200054煤炭煤炭 360049鋼材鋼材 資源限制資源限制乙乙甲甲 單位單位 產品產品 資源資源 消耗消耗 要求

3、：要求： 1、完成或超額完成利潤指標、完成或超額完成利潤指標 50000元；元； 2、產品甲不超過、產品甲不超過 200件，產品乙不低于件，產品乙不低于 250件；件； 3、現(xiàn)有鋼材、現(xiàn)有鋼材 3600噸用完。噸用完。 第一節(jié)第一節(jié) 目標規(guī)劃的數(shù)學模型目標規(guī)劃的數(shù)學模型 目標規(guī)劃是在線性規(guī)劃的基礎上，為適應實際問題中目標規(guī)劃是在線性規(guī)劃的基礎上，為適應實際問題中多多 目標決策目標決策的需要而逐步發(fā)展起來的一個分支。的需要而逐步發(fā)展起來的一個分支。 2 2、線性規(guī)劃要求問題的解必須嚴格滿足全部約束條件，、線性規(guī)劃要求問題的解必須嚴格滿足全部約束條件， 但實際問題中并非所有約束都需嚴格滿足；目標規(guī)

4、劃無此要但實際問題中并非所有約束都需嚴格滿足；目標規(guī)劃無此要 求。求。 1 1、線性規(guī)劃只討論一個線性目標函數(shù)在一組線性約束條、線性規(guī)劃只討論一個線性目標函數(shù)在一組線性約束條 件下的極值問題；而目標規(guī)劃是多個目標決策，可求得更切件下的極值問題；而目標規(guī)劃是多個目標決策，可求得更切 合實際的解。合實際的解。 一、目標規(guī)劃概述一、目標規(guī)劃概述 （一）目標規(guī)劃與線性規(guī)劃的比較（一）目標規(guī)劃與線性規(guī)劃的比較 5 5、線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花去大、線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花去大 量的人力、物力、財力才能得到；實際過程中，只要求得量的人力、物力、財力才能得到；實際過程中，

5、只要求得 滿意解，就能滿足需要（或更能滿足需要）。滿意解，就能滿足需要（或更能滿足需要）。 4 4、線性規(guī)劃中的約束條件是同等重要的，是、線性規(guī)劃中的約束條件是同等重要的，是硬約束硬約束；而；而 目標規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權。目標規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權。 目前，已經(jīng)在經(jīng)濟計劃、生產管理、經(jīng)營管理、市場分析、目前，已經(jīng)在經(jīng)濟計劃、生產管理、經(jīng)營管理、市場分析、 財務管理等方面得到了廣泛的應用。財務管理等方面得到了廣泛的應用。 3 3、線性規(guī)劃求最優(yōu)解；目標規(guī)劃是找到一個滿意解。、線性規(guī)劃求最優(yōu)解；目標規(guī)劃是找到一個滿意解。 目標值目標值：是指預先給定的某個目標的一個

6、期望值。：是指預先給定的某個目標的一個期望值。 1 1、目標值和偏差變量、目標值和偏差變量 （二）目標規(guī)劃的基本概念（二）目標規(guī)劃的基本概念 偏差變量偏差變量（事先無法確定的未知數(shù)）：是指實現(xiàn)值和（事先無法確定的未知數(shù)）：是指實現(xiàn)值和 目標值之間的差異目標值之間的差異, ,記為記為 d d 。 正偏差變量正偏差變量：表示實現(xiàn)值超過目標值的部分，記為：表示實現(xiàn)值超過目標值的部分，記為 d d 。 。 負偏差變量負偏差變量：表示實現(xiàn)值未達到目標值的部分，記為：表示實現(xiàn)值未達到目標值的部分，記為 d d 。 。 當完成或超額完成規(guī)定的指標則表示：當完成或超額完成規(guī)定的指標則表示： 當未完成規(guī)定的指標

7、則表示：當未完成規(guī)定的指標則表示： 當恰好完成指標時則表示：當恰好完成指標時則表示： 在一次決策中，實現(xiàn)值不可能既超過目標值又未達到目在一次決策中，實現(xiàn)值不可能既超過目標值又未達到目 標值，故有標值，故有 d d d d 0,0,并規(guī)定并規(guī)定d d 0, d d0 注意注意：目標規(guī)劃中，一般有多個目標值，每個目標值都：目標規(guī)劃中，一般有多個目標值，每個目標值都 相應有一對偏差變量相應有一對偏差變量 。 d d 0, d d 0 d d 0, d d 0 d d 0, d d 0 2 2、絕對約束和目標約束、絕對約束和目標約束 絕對約束：絕對約束：是指必須嚴格滿足的等式約束或不等式約束；是指必須

8、嚴格滿足的等式約束或不等式約束； 如線性規(guī)劃問題的所有約束條件，不能滿足這些條件的解如線性規(guī)劃問題的所有約束條件，不能滿足這些條件的解 稱為非可行解，所以絕對約束是稱為非可行解，所以絕對約束是硬約束硬約束。 目標約束：目標約束：是目標規(guī)劃所特有的一種約束，它把要追求的是目標規(guī)劃所特有的一種約束，它把要追求的 目標值作為右端常數(shù)項，在追求此目標值時允許發(fā)生正偏目標值作為右端常數(shù)項，在追求此目標值時允許發(fā)生正偏 差和負偏差。因此，目標約束是由決策變量，正、負偏差差和負偏差。因此，目標約束是由決策變量，正、負偏差 變量和要追求的目標值組成的變量和要追求的目標值組成的軟約束軟約束。 優(yōu)先因子優(yōu)先因子P

9、k 是將決策目標按其重要程度排序并表示出是將決策目標按其重要程度排序并表示出 來。來。P1P2PkPk+1，k=1.2N。 3 3、優(yōu)先因子（優(yōu)先等級）與優(yōu)先權系數(shù)、優(yōu)先因子（優(yōu)先等級）與優(yōu)先權系數(shù) 權系數(shù)權系數(shù)k 區(qū)別具有相同優(yōu)先因子的兩個目標的差別，區(qū)別具有相同優(yōu)先因子的兩個目標的差別， 決策者可視具體情況而定。決策者可視具體情況而定。 解釋：解釋： 表示表示Pk比比Pk+1有更大的優(yōu)先級。有更大的優(yōu)先級。 目標函數(shù)是按各目標約束的正、負偏差變量和賦予相應目標函數(shù)是按各目標約束的正、負偏差變量和賦予相應 的優(yōu)先因子及權系數(shù)而構造的。的優(yōu)先因子及權系數(shù)而構造的。 4 4、目標函數(shù)、目標函數(shù)

10、要求恰好達到規(guī)定的目標值：要求恰好達到規(guī)定的目標值： 要求不超過目標值：要求不超過目標值： 彈性約束基本形式：彈性約束基本形式： 要求超過目標值：要求超過目標值： 則則min(d d ) 則則min(d ) 則則min(d ) 對于這種解來說，前面的目標可以保證實現(xiàn)或部分對于這種解來說，前面的目標可以保證實現(xiàn)或部分 實現(xiàn)，而后面的目標就不一定能保證實現(xiàn)或部分實現(xiàn)，實現(xiàn)，而后面的目標就不一定能保證實現(xiàn)或部分實現(xiàn)， 有些可能就不能實現(xiàn)。有些可能就不能實現(xiàn)。 5 5、滿意解（具有層次意義的解）、滿意解（具有層次意義的解） （三）目標規(guī)劃的數(shù)學模型（三）目標規(guī)劃的數(shù)學模型 )2.1( 0 . n)1.

11、2(j 0 )2.1( ).( )2.1( )(min 1 1 11 Lldd x mibxa Llqddxc ddPZ ll j n j ijij n j llljkj K k L l lkllklk 例例2、某廠計劃在下一個生產周期內生產甲、乙兩種產品，、某廠計劃在下一個生產周期內生產甲、乙兩種產品， 已知資料如表所示。試制定生產計劃，使獲得的利潤最大？已知資料如表所示。試制定生產計劃，使獲得的利潤最大？ 試建立數(shù)學模型。試建立數(shù)學模型。 12070單件利潤單件利潤 3000103設備臺時設備臺時 200054煤炭煤炭 360049鋼材鋼材 資源限制資源限制乙乙甲甲 單位單位 產品產品 資

12、源資源 消耗消耗 要求：要求： 1、完成或超額完成利潤指標、完成或超額完成利潤指標 50000元；元； 2、產品甲不超過、產品甲不超過 200件，產品乙不低于件，產品乙不低于 250件；件； 3、現(xiàn)有鋼材、現(xiàn)有鋼材 3600噸用完。噸用完。 11223344 1211 122 233 1244 12 12 min()() 7012050000 200 250 9 43600 4 5 2000 3 10 ZPdP ddP dd xxdd xdd xdd xxdd xx xx 1 2 3000 0,. 0 (1.2.3.4) jj xddj 目標規(guī)劃模型為：目標規(guī)劃模型為： 分析：分析： 例一分析

13、：例一分析： 題目有三個目標層次，包含四個目標值。題目有三個目標層次，包含四個目標值。 第一目標：第一目標： 第二目標：有兩個要求即甲第二目標：有兩個要求即甲 ，乙，乙 ，但兩個具，但兩個具 有相同的優(yōu)先因子。有相同的優(yōu)先因子。 本題可用單件利潤比作為權系數(shù)即本題可用單件利潤比作為權系數(shù)即 70 :120，化簡為，化簡為7:12。 11d P 32 dd )127( 322 ddP 第三目標：第三目標：)( 443 ddP )4 .3 .2 .1( 0 .,0 3000 10 3 2000 5 4 36004 9 250 200 5000012070 )()127(min 21 21 21 4

14、421 332 221 1121 44332211 jddx xx xx ddxx ddx ddx ddxx ddPddPdPZ jj 目標規(guī)劃模型為：目標規(guī)劃模型為： 例例3：某廠生產：某廠生產、兩兩 種產品，有關數(shù)據(jù)如表所種產品，有關數(shù)據(jù)如表所 示。試求獲利最大的生產示。試求獲利最大的生產 方案？方案？ 擁有量擁有量 原材料原材料2111 設備設備(臺時臺時)1210 單件利潤單件利潤810 在此基礎上考慮：在此基礎上考慮： 1、產品、產品的產量不低于產品的產量不低于產品的產量；的產量； 2、充分利用設備有效臺時，不加班；、充分利用設備有效臺時，不加班； 3、利潤不小于、利潤不小于 56

15、元。元。 2111 1222 1233 12 1 2 0 210 81056 2 11 0,. 0 (1.2.3) jj xxdd xxdd xxdd xx xddj 目標：目標： 1、產品、產品的產量不低于產品的產量不低于產品的產量；的產量； 2、充分利用設備有效臺時，不加班；、充分利用設備有效臺時，不加班； 3、利潤不小于、利潤不小于 56 元。元。 第一目標：第一目標： 即產品即產品的產量不大于的產量不大于的產量。的產量。 第二目標：第二目標： 11 P d 222 ()P dd 第三目標：第三目標： 33 dP 目標：目標： 1、產品、產品的產量不低于產品的產量不低于產品的產量；的產量

16、； 2、充分利用設備有效臺時，不加班；、充分利用設備有效臺時，不加班； 3、利潤不小于、利潤不小于 56 元。元。 目標函數(shù)：目標函數(shù)： )(min 3322211 dPddPdPZ 1122233 2111 1222 1233 12 1 2 min() 0 210 81056 2 11 0,. 0 (1.2.3) jj ZPdP ddP d xxdd xxdd xxdd xx xddj 目標規(guī)劃模型為：目標規(guī)劃模型為： 課堂練習課堂練習 某廠生產某廠生產A、B、C三種產品，裝配工作在同一生產線三種產品，裝配工作在同一生產線 上完成，三種產品的工時消耗分別為上完成，三種產品的工時消耗分別為6

17、6、8 8、1010小時，生產小時，生產 線每月正常工作時間為線每月正常工作時間為200200小時；三種產品銷售后，每臺可小時；三種產品銷售后，每臺可 獲利分別為獲利分別為500500、650650和和800800元；每月銷售量預計為元；每月銷售量預計為1212、1010和和 6 6臺。臺。 該廠經(jīng)營目標如下：該廠經(jīng)營目標如下： 1 1、利潤指標為每月、利潤指標為每月1600016000元，爭取超額完成；元，爭取超額完成； 2 2、充分利用現(xiàn)有生產能力；、充分利用現(xiàn)有生產能力； 3 3、可以適當加班，但加班時間不超過、可以適當加班，但加班時間不超過2424小時；小時； 4 4、產量以預計銷售量

18、為準。、產量以預計銷售量為準。 試建立目標規(guī)劃模型。試建立目標規(guī)劃模型。 答案：答案： )6 ,2, 1(0,0, 6 10 12 24 2001086 16000800650500 )( min , .1 321 663 552 441 332 22321 11321 6655444 332211 321 iddxxx ddx ddx ddx ddd ddxxx ddxxx ddddddp dpdpdpZ xxx ii 型型為為則則該該問問題題的的目目標標規(guī)規(guī)劃劃模模 量量，分分別別表表示示三三種種產產品品的的產產設設 （四（四）小結小結 線性規(guī)劃線性規(guī)劃LPLP目標規(guī)劃目標規(guī)劃GPGP 目

19、標函數(shù)目標函數(shù) min , max 系數(shù)可正負系數(shù)可正負 min , 偏差變量偏差變量 系數(shù)系數(shù)00 變量變量決策變量決策變量 決策變量決策變量 d d 約束條件約束條件絕對約束絕對約束 目標約束目標約束 絕對約束絕對約束 解解最優(yōu)最優(yōu)最滿意最滿意 第二節(jié)第二節(jié) 解目標規(guī)劃的圖解法解目標規(guī)劃的圖解法 引例：某廠生產引例：某廠生產、兩兩 種產品，有關數(shù)據(jù)如表所種產品，有關數(shù)據(jù)如表所 示。試求獲利最大的生產示。試求獲利最大的生產 方案？方案？ 擁有量擁有量 原材料原材料2111 設備設備(臺時臺時)1210 單件利潤單件利潤810 在此基礎上考慮：在此基礎上考慮： 1、產品、產品的產量不低于產品的

20、產量不低于產品的產量；的產量； 2、充分利用設備有效臺時，不加班；、充分利用設備有效臺時，不加班； 3、利潤不小于、利潤不小于 56 元。元。 1122233 12 1211 1222 1233 12 m in() 2 1 1 0 21 0 81 05 6 0,. 0 (1,2,3 ) jj ZP dPddP d xx xxdd xxdd xxdd xddj 目標規(guī)劃模型為：目標規(guī)劃模型為： 圖解法解題步驟如下：圖解法解題步驟如下： 步驟步驟1 1 建立直角坐標系，令各偏差變量為建立直角坐標系，令各偏差變量為0 0，作出所有的約，作出所有的約 束直線束直線 。滿足所有。滿足所有絕對約束條件絕對

21、約束條件的區(qū)域，用陰影標出。的區(qū)域，用陰影標出。 3322211 mindpddpdpz 。 ， ， ， ， 3,2,1,0, 56108 102 0 112 s.t. 21 3321 2221 1121 21 iddxx ddxx ddxx ddxx xx ii 步驟步驟2 2 作圖表示偏差變量增減對約束直線的影響作圖表示偏差變量增減對約束直線的影響 在所有目標約束直線旁在所有目標約束直線旁標上標上 d d + +， d d - - ， 3322211 mindpddpdpz 。 ， ， ， ， 3,2,1,0, 56108 102 0 112 s.t. 21 3321 2221 1121

22、21 iddxx ddxx ddxx ddxx xx ii 步驟步驟3 3 根據(jù)目標函數(shù)中的優(yōu)先因子次序，逐步分析求解。根據(jù)目標函數(shù)中的優(yōu)先因子次序，逐步分析求解。 3322211 mindpddpdpz 。 ， ， ， ， 3,2,1,0, 56108 102 0 112 s.t. 21 3321 2221 1121 21 iddxx ddxx ddxx ddxx xx ii 步驟步驟3 3 根據(jù)目標函數(shù)中的優(yōu)先因子次序，逐步分析求解。根據(jù)目標函數(shù)中的優(yōu)先因子次序，逐步分析求解。 根據(jù)目標函數(shù)中的優(yōu)先因子次序，首先考慮具有優(yōu)先根據(jù)目標函數(shù)中的優(yōu)先因子次序，首先考慮具有優(yōu)先 因子因子 p p1

23、 1 的目標的實現(xiàn)。目標函數(shù)要求實現(xiàn) 的目標的實現(xiàn)。目標函數(shù)要求實現(xiàn) min min d d1 1+ +，從圖從圖 中可見，可以滿足中可見，可以滿足d d1 1+ +=0 =0 ，這時，只能在三角形這時，只能在三角形 OBCOBC的區(qū)的區(qū) 域上取值；域上取值； 考察具有優(yōu)先因子考察具有優(yōu)先因子 p p2 2的目的目 標，此時可在線段標，此時可在線段ED ED 上取值；上取值； 考察優(yōu)先因子考察優(yōu)先因子 p p3 3 的目標， 的目標， 這就使取值范圍縮小到線段這就使取值范圍縮小到線段 GD GD 上，該線段上所有點的坐上，該線段上所有點的坐 標，都是問題的解，標，都是問題的解，G(2,4)G(

24、2,4) D(10/3,10/3)D(10/3,10/3)。 例例1、用圖解法求解目標規(guī)劃問題、用圖解法求解目標規(guī)劃問題 )2 . 1(0, 0 8 2 102 5 .621210 )(min 21 21 2221 1121 22111 lddx xx ddxx ddxx dPddPZ ll 01 2 3 4 5 6 7 8 1 2 3 4 5 6 x2 x1 1 d 1 d 2 d 2 d B C B (0.6250 , 4.6875) C (0 , 5.2083) ， B、C 線段上的所線段上的所 有點均是該問題的解（無窮多最優(yōu)解）。有點均是該問題的解（無窮多最優(yōu)解）。 )2 .1(0,0

25、 8 2 102 5 .621210 )(min 21 21 2221 1121 22111 lddx xx ddxx ddxx dPddPZ ll 例例2、已知一個生產計劃的線性規(guī)劃模型為、已知一個生產計劃的線性規(guī)劃模型為 12 12 1 2 12 ma x3 01 2 21 4 0 () 6 0 1 0 0 0 Zxx xx x x x 甲 資 源 其中目標函數(shù)為總利潤，其中目標函數(shù)為總利潤，x1， ，x2 為產品 為產品A、B產量?，F(xiàn)有下產量?，F(xiàn)有下 列目標：列目標： 1、要求總利潤必須超過、要求總利潤必須超過 2500 元；元； 2、考慮產品受市場影響，為避免積壓，、考慮產品受市場影響

26、，為避免積壓，A、B的生產量不生產量不 超過超過 60 件和件和 100 件；件； 3、由于甲資源供應比較緊張，不要超過現(xiàn)有量、由于甲資源供應比較緊張，不要超過現(xiàn)有量140。 試建立目標規(guī)劃模型，并用圖解法求解。試建立目標規(guī)劃模型，并用圖解法求解。 解：以產品解：以產品 A A、B B 的單件利潤比的單件利潤比 2.5 2.5 ：1 1 為權系數(shù)，模為權系數(shù)，模 型如下：型如下： )4 .3 .2 .1(0,0 100 60 1402 25001230 )5 .2(min 21 442 331 2221 1121 2343211 lddx ddx ddx ddxx ddxx dPddPdPZ

27、ll 0 x2 0 x1 140 120 100 80 60 40 20 20 40 60 80 100 3 作圖：作圖： )4 .3 .2 .1(0,0 100 60 1402 25001230 )5 .2(min 21 442 331 2221 1121 2343211 lddx ddx ddx ddxx ddxx dPddPdPZ ll x2 x1 140 120 100 80 60 40 20 20 40 60 80 100 0 0 2 d 2 d 1 d 1 d 3 d 3 d 4 d 4 dAB C 結論：結論：C(60 ,58.3)C(60 ,58.3)為所求的滿意解。為所求的滿

28、意解。 作圖：作圖： )4 .3 .2 .1(0,0 100 60 1402 25001230 )5 .2(min 21 442 331 2221 1121 2343211 lddx ddx ddx ddxx ddxx dPddPdPZ ll 第三節(jié)第三節(jié) 解目標規(guī)劃的單純形法解目標規(guī)劃的單純形法 目標規(guī)劃的數(shù)學模型與線性規(guī)劃的數(shù)學模型基本相目標規(guī)劃的數(shù)學模型與線性規(guī)劃的數(shù)學模型基本相 同，因此利用單純形法求解步驟也基本相同，但是需要同，因此利用單純形法求解步驟也基本相同，但是需要 尤其注意它們之間的區(qū)別。尤其注意它們之間的區(qū)別。 線性規(guī)劃的單純形法求解過程線性規(guī)劃的單純形法求解過程( (目標

29、函數(shù)極大化情況下目標函數(shù)極大化情況下) )： 1.1.建立初始單純形表，計算出所有變量的檢驗數(shù)；建立初始單純形表，計算出所有變量的檢驗數(shù)； 2.2.在非基變量檢驗數(shù)中找到最大的正數(shù)在非基變量檢驗數(shù)中找到最大的正數(shù)j j，它所對應的它所對應的 變量變量x xj j 作為換入基的變量； 作為換入基的變量； 3.3.對于所有對于所有a aij ij0 0 計算計算b bi i / /a aij ij 其中最小的元素 其中最小的元素所對應所對應 的基變量的基變量x xi i 作為換出基的變量；作為換出基的變量； 4.4.建立新單純形表，重復上述步驟建立新單純形表，重復上述步驟2 2、3 3，直到所有檢

30、驗，直到所有檢驗 數(shù)都小于等于零。數(shù)都小于等于零。 由于目標規(guī)劃的目標函數(shù)都是求由于目標規(guī)劃的目標函數(shù)都是求極小化極小化問題，而線性問題，而線性 規(guī)劃問題的標準型中目標函數(shù)是求規(guī)劃問題的標準型中目標函數(shù)是求極大化極大化問題，因此在用問題，因此在用 單純形法求解時要注意一些重要的的差別。單純形法求解時要注意一些重要的的差別。 11223 111 1222 1233 12 min 10 240 32100 ,0 (1,2,3) ii zP ddPd xdd xxdd xxdd x x ddi 例例1 1 用單純形法求解下述目標規(guī)劃問題：用單純形法求解下述目標規(guī)劃問題： 第一步：第一步：列出初始單純

31、形表，并計算檢驗數(shù)。列出初始單純形表，并計算檢驗數(shù)。 將表格中最后一行檢驗數(shù)按優(yōu)先級改寫為：將表格中最后一行檢驗數(shù)按優(yōu)先級改寫為： （這是與線性規(guī)劃單純形法的（這是與線性規(guī)劃單純形法的第一個差別第一個差別） 第二步：第二步：確定換入基的變量。確定換入基的變量。 在負檢驗數(shù)中，選擇最小的一個在負檢驗數(shù)中，選擇最小的一個j j 所對應的變量 所對應的變量x xj j作為作為 換入基的變量換入基的變量( (第二個差別第二個差別) )。 第三步：第三步：確定換出基的變量（這與線性規(guī)劃相同）。確定換出基的變量（這與線性規(guī)劃相同）。 第四步：第四步：用換入變量替換換出變量，進行單純形法迭代運算，用換入變量

32、替換換出變量，進行單純形法迭代運算， 直至優(yōu)先級直至優(yōu)先級 P P1 1 所對應的檢驗數(shù)全為非負。 所對應的檢驗數(shù)全為非負。 本例中，第本例中，第 一優(yōu)先級計一優(yōu)先級計 算后得：算后得： 由于優(yōu)先級由于優(yōu)先級 P P2 2 的檢驗數(shù)仍然的檢驗數(shù)仍然 有負值，因此有負值，因此 可以繼續(xù)優(yōu)化，可以繼續(xù)優(yōu)化， 重復上述步驟重復上述步驟 2-4 2-4 。 確定換入、換出變量：確定換入、換出變量： 第一點說明：第一點說明： 目標函數(shù)按優(yōu)先級順序進行優(yōu)化，當目標函數(shù)按優(yōu)先級順序進行優(yōu)化，當P P1 1 行所有檢驗數(shù)非負 行所有檢驗數(shù)非負 時，說明第一級已經(jīng)優(yōu)化，可以轉入下一級，考察時，說明第一級已經(jīng)優(yōu)化

33、，可以轉入下一級，考察 P P2 2 行檢驗 行檢驗 數(shù)，依此類推。數(shù)，依此類推。 第二點說明：第二點說明： 從考察從考察P P2 2行檢驗數(shù)開始，注意應把更高級別的優(yōu)先因子行檢驗數(shù)開始，注意應把更高級別的優(yōu)先因子 考慮在內。如上述問題的進一步單純形表如下：考慮在內。如上述問題的進一步單純形表如下： 對應的檢驗數(shù)為對應的檢驗數(shù)為 P P1 1+(+(3/2)3/2)P P2 200 對應的檢驗數(shù)為對應的檢驗數(shù)為 P P1 1 P P2 2 0 0 對應的檢驗數(shù)為對應的檢驗數(shù)為 P P1 12 2P P2 200 因此上述三種情況都不能因此上述三種情況都不能 選為換入基的變量，這其實選為換入基的

34、變量，這其實 與線性規(guī)劃相同。與線性規(guī)劃相同。 判別迭代計算停止的準則：判別迭代計算停止的準則： (1)(1)檢驗數(shù)檢驗數(shù)P P1 1, ,P P2 2 , , ,P Pk k行的所有值均為非負； 行的所有值均為非負； (2)(2)若若P P1 1, ,P P2 2 , , ,P Pi i行的所有檢驗數(shù)為非負而 行的所有檢驗數(shù)為非負而 P Pi i+1 +1 行存在負檢驗數(shù)，但在負檢驗數(shù)所在列的上面行行存在負檢驗數(shù)，但在負檢驗數(shù)所在列的上面行 中有正檢驗數(shù)（不一定是相鄰行，只要在其上方中有正檢驗數(shù)（不一定是相鄰行，只要在其上方 即可）。即可）。 例例2 2：用單純形法求解下列目標規(guī)劃問題：用單

35、純形法求解下列目標規(guī)劃問題： 112233 123 1211 1222 1233 123 Min 51060 2 0 s.t. 4 4 36 68 48 ,0,0,(1,2,3) ii ZPdPdPd xxx xxdd xxdd xxdd x x xddi cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 5 10 1 0 0 0 0 0 0 P1 0 1 -2 0 1 -1 0 0 0 0 0 36 4 4 0 0 0 1 -1 0 0 P3 48 6 8 0 0 0 0 0 1 -1 P1 -1 2 0 0 1 0 0 0 0 P2 0 0

36、0 0 0 0 1 0 0 P3 -6 -8 0 0 0 0 0 0 1 1 d 1 d 2 d 3 d 2 d 3 d 1 d 2 d 3 d jjj zc cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 5 10 1 0 0 0 0 0 0 P1 0 1 -2 0 1 -1 0 0 0 0 0 36 4 4 0 0 0 1 -1 0 0 P3 48 6 8 0 0 0 0 0 1 -1 P1 -1 2 0 0 1 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 -6 -8 0 0 0 0 0 0 1 1 d 1 d 2 d

37、3 d 2 d 3 d 1 d 2 d 3 d jjj zc cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 5 10 1 0 0 0 0 0 0 P1 0 1 -2 0 1 -1 0 0 0 0 0 36 4 4 0 0 0 1 -1 0 0 P3 48 6 8 0 0 0 0 0 1 -1 P1 -1 2 0 0 1 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 -6 -8 0 0 0 0 0 0 1 0 x3 60 0 20 1 -5 5 0 0 0 0 0 x1 0 1 -2 0 1 -1 0 0 0 0 0 36 0

38、 12 0 -4 4 1 -1 0 0 P3 48 020 0 -6 6 0 0 1 -1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6 -6 0 0 0 1 1 d 1 d 2 d 3 d 2 d 3 d 1 d 2 d 3 d jjj zc 2 d 3 d jjj zc cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 0 20 1 -5 5 0 0 0 0 0 x1 0 1 -2 0 1 -1 0 0 0 0 0 36 0 12 0 -4 4 1 -1 0 0 P3 48 020

39、 0 -6 6 0 0 1 -1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6 -6 0 0 0 1 0 x312 0 0 1 1 -1 0 0 -1 1 0 x124/5 1 0 0 2/5 -2/5 0 01/10-1/10 036/5 0 0 0 -2/5 2/5 1 -1-3/5 3/5 0 x212/5 0 1 0-3/10 3/10 0 01/20-1/20 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 0 0 0 0 0 0 1 0 1 d 1 d 2 d 3 d 2 d

40、 3 d 2 d 3 d jjj zc 2 d jjj zc )4 .3 .2 .1( 0,0 100 60 140 2 25001230 5 .2min 21 442 331 2221 1121 23423211 lddx ddx ddx ddxx ddxx dPdPdPdPZ ll 例例3 3：用單純形法求解下列目標規(guī)劃問題：用單純形法求解下列目標規(guī)劃問題 Cj 00P10000 2.5P20P2 CBXBb x1x2 P1 2500301211000000 0 1402100110000 0 601000001100 0 1000100000011 kj P1 301201000000

41、P2 00000002.501 P3 0000010000 1 d 1 d 2 d 2 d 3 d 3 d 4 d 4 d 1 d 2 d 3 d 4 d = min2500/30,140/2,60/1=60 ,故故 為換出變量。為換出變量。 3 d Cj 00P100P30 2.5P20P2 CBXBb x1x2 P1 7000121100303000 0 200100112200 0 x1 601000001100 0 1000100000011 kj P1 0120100303000 P2 00000002.501 P3 0000010000 1 d 1 d 2 d 2 d 3 d 3

42、d 4 d 4 d 1 d 2 d 4 d = min700/30,20/2, =10 ,故故 為換出變量。為換出變量。 2 d Cj 00P100P30 2.5P2 0P2 CBXBb x1x2 P1 4000-31-1-15150000 2.5P21001/2001/2-1/2-1100 0 x1 7011/2001/2-1/20000 0 100010000001-1 kj P1 030115-150000 P2 0-5/400-5/45/45/2001 P3 0000010000 1 d 1 d 2 d 2 d 3 d 3 d 4 d 4 d 1 d 4 d = min400/15,

43、=10 ,故故 為換出變量。為換出變量。 3 d 1 d Cj 00P100P30 2.5P20P2 CBXBb x1x2 P3 80/30-1/51/15-1/15-110000 2.5P270/302/51/30-1/3000-1100 0 x1 250/312/51/30-1/30000000 0 1000100000011 kj P1 0010000000 P2 0-1-1/121/12002/5001 P3 01/5-1/151/15100000 1 d 1 d 2 d 2 d 3 d 3 d 4 d 4 d 4 d = min,350/6,1250/6,100/1=75 ,故故 為

44、換出變量。為換出變量。 2 d 3 d 3 d Cj 00P100P30 2.5P20P2 CBXBb x1x2 P3 115/3001/12-1/12-11-1/21/200 0 x2 175/3011/12-1/1200-5/25/200 0 x1 60100000-1100 0 125/300-1/121/12005/2-5/211 kj P1 0010000000 P2 00000005/201 P3 00-1/121/12101/2-1/200 1 d 1 d 2 d 2 d 3 d 3 d 4 d 4 d 4 d 2 d 滿意解滿意解x x1 1* *=60=60，x x2 2*

45、*=175/3 =175/3 。 目標規(guī)劃的靈敏度分析所討論內容包括：目標規(guī)劃的靈敏度分析所討論內容包括： 1 1、約束條件（目標約束和硬約束）右端常數(shù)的變化；、約束條件（目標約束和硬約束）右端常數(shù)的變化； 2 2、約束條件中各變量系數(shù)的變化；、約束條件中各變量系數(shù)的變化； 3 3、加入新的變量（決策變量和偏差變量）；、加入新的變量（決策變量和偏差變量）； 4 4、加入新的約束條件；、加入新的約束條件； 5 5、目標函數(shù)中偏差變量的優(yōu)先等級及權系數(shù)的變化；、目標函數(shù)中偏差變量的優(yōu)先等級及權系數(shù)的變化； 第四節(jié)第四節(jié) 靈敏度分析靈敏度分析 已知目標規(guī)劃問題：已知目標規(guī)劃問題： 4 , 3 , 2

46、 , 1, 0, 12 5635 4 10 )32(min 21 4421 3321 221 1121 4332211 iddxx ddxx ddxx ddx ddxx dPdPddPz ii 滿足約束條件： 目標函數(shù)： XB CjP3 1 P3 1-22-33 P2 32 P1 kj -1 111-11 2 P2-1 12-23-318 -1114 1-1-1116 x1 x2x1 b x2 CB P23P12P1 1 d 1 d 2 d 2 d 3 d 3 d 3 d 4 d 4 d 4 d 表表1:1: 目標函數(shù)的優(yōu)先等級變化為：目標函數(shù)的優(yōu)先等級變化為： (1) (1) min z=P

47、min z=P1 1 (2d (2d1 1+ +3d+3d2 2+ +) +P) +P2 2d d4 4+ +P+P3 3d d3 3- - (2) min z= P(2) min z= P1 1d d3 3- -+P+P2 2(2d(2d1 1+ +3d+3d2 2+ +)+P)+P3 3d d4 4+ + 試分析原解有什么變化。試分析原解有什么變化。 XB CjP3 1 P3 1-22-33 P2 32 P1 kj -1 111-11 2 P2-1 12-23-318 -1114 1-1-1116 x1 x2x1 b x2 CB P23P12P1 1 d 1 d 2 d 2 d 3 d 3

48、 d 3 d 4 d 4 d 4 d 原：min z = P1(2d1+3d2+)+P2d3-+P3d4+ 分析分析(1):(1): XB CjP2 1-22-33 P3 1 P2 32 P1 kj -1 111-11 2 P3-1 12-23-318 -1114 1-1-1116 x1 x2x1 b x2 CB P33P12P1 1 d 1 d 2 d 2 d 3 d 3 d 3 d 4 d 4 d 4 d 新1: min z = P1(2d1+3d2+)+P2d4+P3 d3- 將原目標函數(shù)中將原目標函數(shù)中d d4 4+ +，d d3 3- -的優(yōu)先因子對換了一下。只的優(yōu)先因子對換了一下。

49、只 需對表需對表1 1的檢驗數(shù)中的的檢驗數(shù)中的P P2 2、P P3 3行和行和c cj j行的行的P P2 2、P P3 3對換即可。對換即可。 表表1 1: : XB CjP3 1 P3 32 P2 1-22-33 P1 kj -1 111-1 2 P1-1 12-23-318 -1114 1-1-1116 x1 x2x1 b x2 CB P13P22P2 1 d 1 d 2 d 2 d 3 d 3 d 3 d 4 d 4 d 4 d 表表2:2: 然后繼續(xù)進行迭代然后繼續(xù)進行迭代 新2: min z = P1 d3- +P2 (2d1+3d2+) +P3 d4+ 分析分析(2):(2):

50、 XB CjP3 1/3-1/3-2/32/3 P3 32 P2 1 P1 kj -1/31/32/3-2/31-1 6 P31-1-1/3 1/32/3-2/34 -1114 -1/31/35/3-5/3112 x1 x2x1 b x2 CB P13P22P2 1 d 1 d 2 d 2 d 3 d 3 d 4 d 4 d 表表3:3: 1 d 4 d 從表從表3 3中得到新的滿意解中得到新的滿意解x x1 1* *=4=4，x x2 2* *=12=12。 P111 4.2 (2)P111 4.2 (2) P112 4.4 (1)P112 4.4 (1)、(2)(2) 某公司生產某公司生產

51、A A、B B兩種藥品，這兩種藥品每小時的產量均為兩種藥品，這兩種藥品每小時的產量均為 10001000盒，該公司每天采用兩班制生產，每周最大工作時間為盒，該公司每天采用兩班制生產，每周最大工作時間為8080 小時，按預測每周市場最大銷量分別為小時，按預測每周市場最大銷量分別為7000070000盒和盒和4500045000盒盒A A 種藥每盒的利潤為種藥每盒的利潤為2.52.5元，元，B B種為種為1.51.5元試確定公司每周元試確定公司每周A A、B B 兩種藥品生產量兩種藥品生產量x x1 1和和x x2 2（單位：千盒），使公司的下列目標得單位：千盒），使公司的下列目標得 以實現(xiàn)：以實現(xiàn)： 避免每周避免每周8080小時生產能力的過少使用小時生產能力的過少使用 加班的時間盡量限制在加班的時間盡量限制在1010小時以內小時以內 A A、B B兩種藥品的每周產量盡量分別達到兩種藥品的每周產量盡量分別達到7000070000盒和盒和4500045000盒，盒， 但不得超出，其權系數(shù)依它們每盒的利潤為準但不得超出，其權系數(shù)依它們每盒的利潤為準 盡量減少加班時間盡量減少加班時間 應用舉例應用舉例 先建立這個問題的線性規(guī)劃模型，依題意分別建立各先建立這個問題的線性規(guī)劃模型，依題意分別建立各 項目標約束項目標約束 ),( , idd