運籌學(xué) 第4章目標規(guī)劃

1、1Chapter4 目標規(guī)劃( Goal programming )目標規(guī)劃問題的數(shù)學(xué)模型目標規(guī)劃問題的數(shù)學(xué)模型目標規(guī)劃的圖解分析法目標規(guī)劃的圖解分析法目標規(guī)劃的單純形法目標規(guī)劃的單純形法靈敏度分析靈敏度分析2第第1節(jié)節(jié) 目標規(guī)劃的數(shù)學(xué)模型目標規(guī)劃的數(shù)學(xué)模型3線性規(guī)劃線性規(guī)劃只討論只討論一個一個線性目標函數(shù)在一組線性約束條件線性目標函數(shù)在一組線性約束條件下的極值問題；而下的極值問題；而目標規(guī)劃目標規(guī)劃是是多個多個目標決策，可求得更目標決策，可求得更切合實際的解。切合實際的解。線性規(guī)劃求線性規(guī)劃求最優(yōu)解最優(yōu)解；目標規(guī)劃是找到一個；目標規(guī)劃是找到一個滿意解滿意解線性規(guī)劃線性規(guī)劃中的約束條件是中的約

2、束條件是同等重要同等重要的，是硬約束；而的，是硬約束；而目目標規(guī)劃標規(guī)劃中有輕重緩急和主次之分，即有中有輕重緩急和主次之分，即有優(yōu)先權(quán)。優(yōu)先權(quán)。線性規(guī)劃線性規(guī)劃的最優(yōu)解是絕對意義下的的最優(yōu)解是絕對意義下的最優(yōu)最優(yōu)，但需花去大量，但需花去大量的人力、物力、財力才能得到；實際過程中，只要求得的人力、物力、財力才能得到；實際過程中，只要求得滿意解滿意解，就能滿足需要（或更能滿足需要）。，就能滿足需要（或更能滿足需要）。一、目標規(guī)劃與線性規(guī)劃的比較一、目標規(guī)劃與線性規(guī)劃的比較4例1：某工廠生產(chǎn)I、 II兩種產(chǎn)品，數(shù)據(jù)如下表，試求獲利最大的生產(chǎn)方案？III擁有量原材料（kg）設(shè)備（hr）21121110

3、利潤(元/件)81012121212max810211s.t.210 x ,0zxxxxxxx從數(shù)據(jù)到模型 為了具體形象地闡述目標規(guī)劃與線性規(guī)劃在處理問題的方法上的一些差異，我們這里通過一個例子來簡介多目標規(guī)劃的相關(guān)概念及數(shù)學(xué)模型。5但企業(yè)的經(jīng)營目標不僅僅是利潤，而且要考慮但企業(yè)的經(jīng)營目標不僅僅是利潤，而且要考慮多個方面多個方面，如：，如：產(chǎn)品產(chǎn)品產(chǎn)量不大于產(chǎn)品產(chǎn)量不大于產(chǎn)品；考超過計劃供應(yīng)原材料時，需高價采購，這使成本增加考超過計劃供應(yīng)原材料時，需高價采購，這使成本增加；應(yīng)盡可能充分利用設(shè)備工時，但不希望加班；應(yīng)盡可能充分利用設(shè)備工時，但不希望加班；(1)(1)利潤不少于利潤不少于5656元

4、。元。6 目標規(guī)劃通過引入目標值和偏差變量，可以將目標函數(shù)目標規(guī)劃通過引入目標值和偏差變量，可以將目標函數(shù)轉(zhuǎn)化為目標約束。轉(zhuǎn)化為目標約束。 目標值：目標值：是指預(yù)先給定的某個目標的一個期望值。是指預(yù)先給定的某個目標的一個期望值。 實現(xiàn)值或決策值：實現(xiàn)值或決策值：是指當(dāng)決策變量是指當(dāng)決策變量x xj j 選定以后，目標函選定以后，目標函數(shù)的對應(yīng)值。數(shù)的對應(yīng)值。 偏差變量（事先無法確定的未知數(shù)）：偏差變量（事先無法確定的未知數(shù)）：是指實現(xiàn)值和目是指實現(xiàn)值和目標值之間的差異標值之間的差異, ,記為記為 d d 。 正偏差變量：正偏差變量：表示實現(xiàn)值超過目標值的部分，記為表示實現(xiàn)值超過目標值的部分，記

5、為 d d。 負偏差變量：負偏差變量：表示實現(xiàn)值未達到目標值的部分，記為表示實現(xiàn)值未達到目標值的部分，記為 d d。1 1、目標值和偏差變量、目標值和偏差變量二、目標規(guī)劃的基本概念二、目標規(guī)劃的基本概念7 當(dāng)當(dāng)完成或超額完成完成或超額完成規(guī)定的指標則表示：規(guī)定的指標則表示：d d0, d0, d0 0 當(dāng)當(dāng)未完成未完成規(guī)定的指標則表示：規(guī)定的指標則表示： d d0, d0, d00 當(dāng)當(dāng)恰好完成恰好完成指標時則表示：指標時則表示： d d0, d0, d0 0 d d d d 0 0 成立。成立。 在一次決策中，實現(xiàn)值不可能既超過目標值又未達到目標在一次決策中，實現(xiàn)值不可能既超過目標值又未達到

6、目標值，故有值，故有 d d d d 0,0,并規(guī)定并規(guī)定d d0, d0, d00 絕對約束絕對約束（系統(tǒng)約束）：是指必須（系統(tǒng)約束）：是指必須嚴格滿足的等式或不等嚴格滿足的等式或不等式約束式約束。如線性規(guī)劃中的。如線性規(guī)劃中的所有約束條件所有約束條件都是絕對約束，否則都是絕對約束，否則無可行解。所以，絕對約束是硬約束。無可行解。所以，絕對約束是硬約束。 目標約束目標約束: :是指希望達到的目標。是指希望達到的目標。目標約束是目標規(guī)劃中特目標約束是目標規(guī)劃中特有的，是軟約束。有的，是軟約束。2 2、絕對約束和目標約束、絕對約束和目標約束8例如要求例如要求I I、IIII兩種產(chǎn)品保持兩種產(chǎn)品保

7、持1:11:1的比例，即的比例，即x x1 1=x=x2 2。由于這個比例允許有偏差，由于這個比例允許有偏差，當(dāng)當(dāng)x x1 1xxx2 2時，出現(xiàn)時，出現(xiàn)正偏差正偏差d d+ +，即：，即： x x1 1-d-d+ + =x=x2 2或或x x1 1x x2 2-d-d+ + =0=0正負偏差不可能同時出現(xiàn)，故目標約束為：正負偏差不可能同時出現(xiàn)，故目標約束為：0ddxx21 9 0min21ddxxd 若希望若希望I I的產(chǎn)量不低于的產(chǎn)量不低于IIII的產(chǎn)量，即不希望的產(chǎn)量，即不希望d d- -0,0,用目標約束用目標約束可表為可表為: : 若希望若希望I I的產(chǎn)量低于的產(chǎn)量低于IIII的產(chǎn)量

8、，即不希望的產(chǎn)量，即不希望d d0,0,用目標約束用目標約束可表為可表為: : 0min21ddxxd 若希望若希望I I的產(chǎn)量恰好等于的產(chǎn)量恰好等于IIII的產(chǎn)量，即不希望的產(chǎn)量，即不希望d d0,0,也不希望也不希望d d- -00用目標約束可表為用目標約束可表為: : 0min21ddxxdd10 10ddx2xdmin21 56ddx10 x8dmin21 10ddx2xddmin21 力求使利潤指標不低于力求使利潤指標不低于5656元，目標約束表示為：元，目標約束表示為： 設(shè)備必要時可加班及加班時間要控制，目標約束表示為：設(shè)備必要時可加班及加班時間要控制，目標約束表示為： 設(shè)備既要求

9、充分利用，又盡可能不加班，目標約束表示為設(shè)備既要求充分利用，又盡可能不加班，目標約束表示為：11優(yōu)先因子優(yōu)先因子P Pk k 是將決策目標按其重要程度排序并表示出來是將決策目標按其重要程度排序并表示出來P P1 1PP2 2PPl lPPl+1l+1PPL L ，l=1.2Ll=1.2L。必須必須“滿足滿足”第一級才能第一級才能“滿足滿足”第二級，依次類推。第二級，依次類推。 權(quán)系數(shù)權(quán)系數(shù)l lk k ：區(qū)別具有相同優(yōu)先因子的兩個目標的重要性區(qū)別具有相同優(yōu)先因子的兩個目標的重要性差別，決策者可視具體情況而定。差別，決策者可視具體情況而定。（優(yōu)先因子和權(quán)系數(shù)的大小具有主觀性和模糊性，它不是運籌（

10、優(yōu)先因子和權(quán)系數(shù)的大小具有主觀性和模糊性，它不是運籌學(xué)本身的問題，主要是決策人自身的經(jīng)驗，可用專家評定法給學(xué)本身的問題，主要是決策人自身的經(jīng)驗，可用專家評定法給以量化。）以量化。） 對于這種解來說，前面的目標可以保證實現(xiàn)或部分實現(xiàn)，對于這種解來說，前面的目標可以保證實現(xiàn)或部分實現(xiàn)，而后面的目標就不一定能保證實現(xiàn)或部分實現(xiàn)，有些可能就不而后面的目標就不一定能保證實現(xiàn)或部分實現(xiàn)，有些可能就不能實現(xiàn)。能實現(xiàn)。3 3、優(yōu)先因子（優(yōu)先等級）與優(yōu)先權(quán)系數(shù)、優(yōu)先因子（優(yōu)先等級）與優(yōu)先權(quán)系數(shù) 4、滿意解（具有層次意義的解）12 目標函數(shù)：由各目標約束的正、負偏差變量及相應(yīng)的優(yōu)先因目標函數(shù)：由各目標約束的正、負

11、偏差變量及相應(yīng)的優(yōu)先因子和權(quán)系數(shù)構(gòu)成子和權(quán)系數(shù)構(gòu)成。從決策者的要求來分析，總希望得到的結(jié)果與。從決策者的要求來分析，總希望得到的結(jié)果與規(guī)定的指標值之間的偏差量愈小愈好。由此可構(gòu)造一個規(guī)定的指標值之間的偏差量愈小愈好。由此可構(gòu)造一個使總偏差使總偏差量為最小化的目標函數(shù)，量為最小化的目標函數(shù)， minminZ Z = = f f（d d、d d）。）。 一般說來，有以下三種情況，但只能出現(xiàn)其中之一：一般說來，有以下三種情況，但只能出現(xiàn)其中之一： 要求要求恰好達到恰好達到規(guī)定的目標值，即正、負偏差變量要盡可能規(guī)定的目標值，即正、負偏差變量要盡可能小，則小，則minZ = minZ = f f（d d

12、 d d）。）。 要求要求不超過不超過目標值，即允許達不到目標值，也就是正偏差目標值，即允許達不到目標值，也就是正偏差變量盡可能小，則變量盡可能小，則minZ = minZ = f f（d d）。）。 要求要求超過超過目標值，即超過量不限，但不低于目標值，也就目標值，即超過量不限，但不低于目標值，也就是負偏差變量盡可能小，則是負偏差變量盡可能小，則minZ = minZ = f f（d d）。）。 5 5、目標規(guī)劃中的目標函數(shù)、目標規(guī)劃中的目標函數(shù)13目標規(guī)劃建模的步驟 1 1、根據(jù)要研究的問題所提出的各目標與條件，確定目標值，列、根據(jù)要研究的問題所提出的各目標與條件，確定目標值，列出目標約束

13、與絕對約束出目標約束與絕對約束； 3 3、給各目標、給各目標賦予賦予相應(yīng)的相應(yīng)的優(yōu)先因子優(yōu)先因子 P Pl l（l=1.2Ll=1.2L）。）。 2 2、根據(jù)決策者的需要，將某些或全部、根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目標約束絕對約束轉(zhuǎn)化為目標約束。這時只需要給這時只需要給絕對約束加上負偏差變量和減去正偏差變量即可。絕對約束加上負偏差變量和減去正偏差變量即可。 4 4、對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度、對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度的不同，的不同，賦予相應(yīng)的權(quán)系數(shù)賦予相應(yīng)的權(quán)系數(shù) 。lklk和 5 5、根據(jù)決策者的要求，按下列情況之一構(gòu)造一個由

14、優(yōu)先因子、根據(jù)決策者的要求，按下列情況之一構(gòu)造一個由優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的，要求實現(xiàn)極小化的和權(quán)系數(shù)相對應(yīng)的偏差變量組成的，要求實現(xiàn)極小化的目標函數(shù)目標函數(shù)。 恰好恰好達到目標值，取達到目標值，取lldd 允許允許超過超過目標值，取目標值，取 ld(3) (3) 不不允許允許超過超過目標值，取目標值，取 ld14解：確定優(yōu)先因子后得數(shù)學(xué)模型：解：確定優(yōu)先因子后得數(shù)學(xué)模型： min Z =Pmin Z =P1 1 d d1 1+ + +P +P2 2 (d (d2 2- - +d +d2 2+ + )+P )+P3 3 d d3 3- - 2x 2x1 1 +x +x2 2 11

15、 11 （在絕對約束基礎(chǔ)上進行目標規(guī)劃）（在絕對約束基礎(chǔ)上進行目標規(guī)劃） x x1 1 - x - x2 2 + d + d1 1- - - d - d1 1+ + = 0 = 0 ( (要求：要求： d d1 1+ + 盡可能小，最好是盡可能小，最好是0 0才能滿足才能滿足 ) ) x x1 1 +2x +2x2 2 + d + d2 2- - - d - d2 2+ + =10 =10 （要求：（要求：d d2 2- - 和和 d d2 2+ + 都盡可能小，最好等于都盡可能小，最好等于0 0） 8x8x1 1 +10 x +10 x2 2 + d + d3 3- - - d - d3 3

16、+ + =56 =56 （要求：（要求：d d3 3- - 盡可能小，最好是盡可能小，最好是0 0才能滿足才能滿足） x x1 1 , x , x2 2 , d , di i- - ,d ,di i+ + 00 例1：要求：1 1）超過計劃供應(yīng)原材料時，需高價采購，這使成本增）超過計劃供應(yīng)原材料時，需高價采購，這使成本增加。加。2 2）產(chǎn)品）產(chǎn)品產(chǎn)量不大于產(chǎn)品產(chǎn)量不大于產(chǎn)品。3 3）應(yīng)盡可能充分利用設(shè)備工時，但不希望加班。）應(yīng)盡可能充分利用設(shè)備工時，但不希望加班。 4 4）利潤不少于）利潤不少于5656元。元。 2x1 +x2 11 x1 - x2 0 x1 +2x2 = 10 8x1 +10

17、 x2 5615)3 . 2 . 1( 0 ., 011 256108102 0 )(min21213321222111213322211jddxxxddxxddxxddxxdPddPdPZjj規(guī)劃模型：16 練習(xí)練習(xí)1 1：某電視機廠裝配黑白、彩色兩種電視機，每裝配一臺某電視機廠裝配黑白、彩色兩種電視機，每裝配一臺電視機需占用裝配線電視機需占用裝配線1 1小時，裝配線每周計劃開動小時，裝配線每周計劃開動4040小時。預(yù)小時。預(yù)計市場每周彩色電視機的銷量是計市場每周彩色電視機的銷量是2424臺，每臺可獲利臺，每臺可獲利8080元；黑白元；黑白電視機的銷量是電視機的銷量是3030臺，每臺可獲利臺

18、，每臺可獲利4040元。該廠確定的目標為：元。該廠確定的目標為： 第一優(yōu)先級：充分利用裝配線；第一優(yōu)先級：充分利用裝配線； 第二優(yōu)先級：加班時間不超過第二優(yōu)先級：加班時間不超過1010小時；小時； 第三優(yōu)先級：滿足市場需求，因彩色電視機的利潤高，第三優(yōu)先級：滿足市場需求，因彩色電視機的利潤高，取其權(quán)系數(shù)為取其權(quán)系數(shù)為2 2。)dd2(pdpdpzmin4332211 401121ddxx502221ddxx24331ddx30442ddx4 , 3 , 2 , 1, 0,21iddxxii解：設(shè)x1和x2分別為彩色電視機和黑百電視機的產(chǎn)量，于是有：17目標規(guī)劃模型的一般形式1111min()

19、(1.2)(.) (1.2)0 (j1.2n). 0 (1.2)LKllkklkklknkjjkkkjnijjijjkkZPddc xddgkKa xbimxddkK 優(yōu)先因子優(yōu)先因子負偏差權(quán)系數(shù)負偏差權(quán)系數(shù)正偏差權(quán)系數(shù)正偏差權(quán)系數(shù)目標約束目標約束系統(tǒng)約束系統(tǒng)約束變量非負變量非負18 求解目標規(guī)劃問題常用的兩種方法：求解目標規(guī)劃問題常用的兩種方法： 圖解法圖解法 特點：形象直觀，但只適用于只有兩個決策變特點：形象直觀，但只適用于只有兩個決策變量。量。 單純形法單純形法 目標規(guī)劃的數(shù)學(xué)模型與線性規(guī)劃的數(shù)學(xué)模型本目標規(guī)劃的數(shù)學(xué)模型與線性規(guī)劃的數(shù)學(xué)模型本質(zhì)上是一致的，故可以利用單純形方法求解目標質(zhì)上

20、是一致的，故可以利用單純形方法求解目標規(guī)劃問題規(guī)劃問題第二節(jié)第二節(jié) 解目標規(guī)劃的圖解法解目標規(guī)劃的圖解法191.1.將所有將所有約束條件約束條件（包括絕對約束和目標約束，此（包括絕對約束和目標約束，此時令目標約束的正負偏差變量均為零）的時令目標約束的正負偏差變量均為零）的直線方直線方程程分別標示于坐標平面上。然后在目標約束所代分別標示于坐標平面上。然后在目標約束所代表的邊界線上，用箭頭標出表的邊界線上，用箭頭標出正、負偏差變量值增正、負偏差變量值增大的方向大的方向2.2.確定確定系統(tǒng)約束系統(tǒng)約束的可行域。的可行域。3.3.從第一個目標（最重要目標）起，分析半個平面從第一個目標（最重要目標）起，

21、分析半個平面的取舍并的取舍并結(jié)合系統(tǒng)約束結(jié)合系統(tǒng)約束，確定滿足第一目標的，確定滿足第一目標的可可行區(qū)域行區(qū)域并確定達成目標的函數(shù)并確定達成目標的函數(shù) （1 1）要求不低于目標值：）要求不低于目標值：min min f f (d (d- -) （2 2）要求不超過目標值：）要求不超過目標值： min min f f (d(d+ +) （3 3）要求恰好達到目標值：）要求恰好達到目標值： min min f f (d(d- -+d+d+ +)4. 4. 第二目標在第一目標確定區(qū)域內(nèi)選擇第二目標在第一目標確定區(qū)域內(nèi)選擇, ,依此類推依此類推圖解法的步驟：圖解法的步驟：20 )3 , 2 , 1( 0

22、,)4(56108)3(102)2(0) 1 (112)min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii（x1x2(1)(2)d1+d1-(3)d2-d2+(4)d3-d3+GD滿意解是線段滿意解是線段GD上任意點上任意點其中其中G點點X(2,4),D點點X(10/3,10/3)05.51055.6112,410/3,10/35107例例5.321 )4 , 1(0,)(30)(24)(50)(40)2(min21442331222111214332211iddxxdddxcddxbddxxaddxxddPdPdPziiOx1x22

23、040605020406050abd1-d1+d2-d2+cdd3-d3+d4-d4+(24,26)滿意解滿意解X=(24，26)例例322(a)(b)(c)(d )x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+滿意解滿意解(3,3) )4 , 1(0,)1 . 4(82)1 . 4(1222)1 . 4(0)1 . 4(1232)1 . 4(124)1 . 4(16421442133212221112121iddxxfddxxeddxxdddxxcddxxbxaxii 4433322211)()mindPddPddPdPz（04683462 2例例423一、目標規(guī)劃的特

24、點：1目標函數(shù)： minmin2最優(yōu)性判斷：j j 0 0 時時為最優(yōu)3非基變量檢驗數(shù)的特殊性： 非基變量檢驗數(shù)中含有不同等級的優(yōu)先因子，即 因 P1 P2 P3 Pk ，所以檢驗數(shù)的正負首先取決于取決于P P1 1 的系數(shù)的正負的系數(shù)的正負，若P1 的系數(shù)為0，再由P2 的系數(shù)的正負決定檢驗數(shù)的正負，然后依次類推。第三節(jié)目標規(guī)劃的單純形法pakkjj 24列出初始單純形表。按照傳統(tǒng)單純形法列出初始單純形表。按照傳統(tǒng)單純形法求解檢驗數(shù)求解檢驗數(shù)，此時由于檢驗數(shù)，此時由于檢驗數(shù)中必然會含有優(yōu)先因子，按照優(yōu)先因子的優(yōu)先程度，將中必然會含有優(yōu)先因子，按照優(yōu)先因子的優(yōu)先程度，將檢驗數(shù)分成多檢驗數(shù)分成多

25、行行，每行每行輸入檢驗數(shù)中對應(yīng)的輸入檢驗數(shù)中對應(yīng)的優(yōu)先因子的系數(shù)優(yōu)先因子的系數(shù)，則每個變量對應(yīng)的總，則每個變量對應(yīng)的總檢驗數(shù)即為檢驗數(shù)即為（行系數(shù)（行系數(shù)* *優(yōu)先因子）；優(yōu)先因子）；從從最優(yōu)先因子最優(yōu)先因子開始，檢查其系數(shù)，觀察其系數(shù)是否為開始，檢查其系數(shù)，觀察其系數(shù)是否為，如非負，如非負，則完成。如含有負系數(shù)，則需要進行變量的替代；則完成。如含有負系數(shù)，則需要進行變量的替代；確定換入變量確定換入變量：從：從最優(yōu)先因子最優(yōu)先因子開始，選擇其負開始，選擇其負檢驗數(shù)檢驗數(shù)中中最小值最小值所對應(yīng)所對應(yīng)的變量為的變量為換入變量換入變量；（；（選擇絕對值最大的負檢驗數(shù)選擇絕對值最大的負檢驗數(shù)）確定換出

26、變量確定換出變量：按單純形法中的最小比值規(guī)則確定，當(dāng)存在兩個和兩：按單純形法中的最小比值規(guī)則確定，當(dāng)存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。按單純形法進行基變換運算，建立按單純形法進行基變換運算，建立新的單純形表新的單純形表，（注意：要對所有，（注意：要對所有的行進行轉(zhuǎn)軸運算）返回的行進行轉(zhuǎn)軸運算）返回(1)(1)；迭代運算停止的準則迭代運算停止的準則：（：（1 1）檢驗數(shù)）檢驗數(shù)p p1 1，p p2 2.，p pk k行的所有值均為非負；行的所有值均為非負；（2 2）p p1 1，p p2 2.

27、，p pi i行所有檢驗數(shù)均為非負，第行所有檢驗數(shù)均為非負，第p pi+1i+1行存在負檢驗數(shù)，行存在負檢驗數(shù)，但在負檢驗數(shù)所在的列的上面行中都有正檢驗數(shù)（原因是但在負檢驗數(shù)所在的列的上面行中都有正檢驗數(shù)（原因是p p1 1pp2 2.p.pi+1i+1）單純形法的計算步驟單純形法的計算步驟25例例：某車間計劃生產(chǎn)：某車間計劃生產(chǎn)A A、B B兩種產(chǎn)品。決策者首先考慮要充分利用供電部門兩種產(chǎn)品。決策者首先考慮要充分利用供電部門分配的電量限額指標分配的電量限額指標62.5kw/62.5kw/日，然后考慮完成與超額完成利潤指標日，然后考慮完成與超額完成利潤指標1010元元/ /日。每日可給車間供應(yīng)

28、所需原料日。每日可給車間供應(yīng)所需原料8t8t。其他有關(guān)數(shù)據(jù)匯總于下表。應(yīng)。其他有關(guān)數(shù)據(jù)匯總于下表。應(yīng)當(dāng)如何確定產(chǎn)品當(dāng)如何確定產(chǎn)品A A、B B的產(chǎn)量。的產(chǎn)量。產(chǎn)品產(chǎn)品耗電量耗電量（kw/kw/單位產(chǎn)品）單位產(chǎn)品）材料消耗材料消耗（t/t/單位產(chǎn)品）單位產(chǎn)品）利潤利潤（元（元/ /單位產(chǎn)品）單位產(chǎn)品）A AB B101012122 21 11 12 2試用單純形法求解試用單純形法求解。 解：目標規(guī)劃問題的數(shù)學(xué)模型解：目標規(guī)劃問題的數(shù)學(xué)模型 min min Z = Z = P P1 1 ( (d d1 1- -+ + d d1 1+ +) +P) +P2 2 d d2 2- - 10 x10 x1

29、 1 + 12x+ 12x2 2 + + d d1 1- - - - d d1 1+ += 62.5 = 62.5 x x1 1 + 2x+ 2x2 2 + + d d2 2- - - - d d2 2+ += 10= 10 2x 2x1 1 + + x x2 2 8 8 x x1 1 ,x,x2 2 , 0 , 0 ,d d1 1- -, ,d d1 1+ +, , d d2 2- -, ,d d2 2+ + 0 026 c cj j0 00 00 0P P1 1P P1 1P P2 20 0C CB Bx xB Bb bx x1 1x x2 2x x3 3d d1 1- -d d1 1+

30、+d d2 2- -d d2 2+ +P P1 1P P2 20d d1 1- -d d2 2- -x x3 362.562.510108 810101 12 212122 21 10 00 01 11 10 00 0-1-10 00 00 01 10 00 0-1-10 0c cj j- -z zj jP P1 1P P2 2檢驗數(shù)檢驗數(shù)j j= = c cj j z zj j 1 1= 0= 0 10 10P P1 1 1 1P P2 2 0 02= 102= 10P P1 1 P P2 2-10-1-12-221 (1) 確定初始解，建立初始計算表確定初始解，建立初始計算表27 cj00

31、0P1P1P20CBxBbx1x2x3d1-d1+d2-d2+P1P20d1-d2-x362.510810121221001100-1000100-10cj-zjP1P2-10-1-12-221(2) 先從檢驗數(shù)先從檢驗數(shù)P P1 1行中，選擇行中，選擇 min(min(j j0 0）=min(-10,-12)= -12=min(-10,-12)= -12 換入變量：換入變量：x x2 262.5/1210/28/1換出變量換出變量：d2- 再按再按=min(8/1, 10/2, 62.5/12)=528 cj000P1P1P20CBxBbx1x2x3d1-d1+d2-d2+P100d1-x2

32、x32.55341/2-3/2010001100100-61/2-1/26-1/21/2cj-zjP1P2-4 261-62.5/63/0.5 檢查檢查P P1 1行所有系數(shù)，行所有系數(shù)，P1行還有負數(shù)，選行還有負數(shù)，選d d2 2+ +換入變量換入變量，計算計算得得d d1 1- -換出變量換出變量(3) (3) 用用x x2 2替換基變量替換基變量d d2 2- -，進行迭代運算，得到下表，進行迭代運算，得到下表：29用用d d2 2+ +替換基變量替換基變量d d1 1- -，進行迭代運算，得到下表，進行迭代運算，得到下表cj000P1P1P20CBxBbx1x2x3d1-d1+d2-d

33、2+000d2+x2x35/12125/2467/242/35/67/6010 0011/61/12-1/12-1/6-1/121/12-100100cj-zjP1P2 111檢驗數(shù)都為正，得滿意解檢驗數(shù)都為正，得滿意解： x1=0， x2=5.208，x3=2.79，d2+=0.41730 cj000P1P1P20CBxBbx1x2x3d1-d1+d2-d2+000d2+x2x35/12125/2467/242/35/67/6010 0011/61/12-1/12-1/6-1/121/12-100100cj-zjP1P2 1115/8125/2067/28 非基變量非基變量x x1 1 的的

34、檢驗數(shù)是零檢驗數(shù)是零, ,用用x x1 1替換基變量替換基變量d d2 2+ +，進行迭代運算，得下表，進行迭代運算，得下表表示有表示有多重解多重解。31 cj000P1P1P20CBxBbx1x2x3d1-d1+d2-d2+000 x1x2x35/8225/4833/16100010 0011/4-1/8-3/8-1/41/83/8-3/25/47/43/2-5/4-7/4cj-zjP1P2 111另一個滿意解另一個滿意解： x1=0.625， x2=4.6375，x3=2.062532)3 . 2 . 1( 0 ., 011 256108102 0 )(min212133212221112

35、13322211jddxxxddxxddxxddxxdPddPdPZjj例：例：用單純形法求解下列目標規(guī)劃問題用單純形法求解下列目標規(guī)劃問題解：對第四個約束條件引入松弛變量，列初始單純性表解：對第四個約束條件引入松弛變量，列初始單純性表33Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 00111100000P210120011000 P3 5681000001100 x3 11210000001jP1 000100000P2 120002000P3 81000000101d1d2d2d3d3d1d2d3d= min，10/2，56/10，11/1= 52d換出變量換出變量換入

36、變量換入變量2x34Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 053/20111/2-1/20000 x251/21001/2-1/2000 P3 63000-551100 x3 63/2000-1/21/2001jP1 000100000P2 000011000P3 30005-50101d1d2d2d3d3d1d3d= min10/3,10,6/3,12/3= 2,3d換入變量換入變量1x換出變量換出變量35Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 0200113-3-1/21/200 x2401004/3-4/3-1/61/600 x121000-5/35/31/3-1/300 x3 300002-2-1/21/21jP1 000100000P2 000011000P3 0000001001d1d2d2d3d3d1d 最優(yōu)解為最優(yōu)解為x12 2， x2 4 4。1d但非基變量但非基變量 的檢驗數(shù)為零，故此題有無窮多最優(yōu)解。的檢驗數(shù)為零，故此題有無窮多最優(yōu)解。= min4 , 24