運(yùn)籌學(xué)目標(biāo)規(guī)劃PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多目標(biāo)決策的需要而逐步發(fā)展起來(lái)的一個(gè)分支。理中多目標(biāo)決策的需要而逐步發(fā)展起來(lái)的一個(gè)分支。 2 2、線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個(gè)滿意解、線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個(gè)滿意解。 1 1、線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在一組線性約、線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在一組線性約束條件下的極值問(wèn)題；而目標(biāo)規(guī)劃是多個(gè)目標(biāo)決策，可束條件下的極值問(wèn)題；而目標(biāo)規(guī)劃是多個(gè)目標(biāo)決策，可求得更切合實(shí)際的解。求得更切合實(shí)際的解。第1頁(yè)/共54頁(yè) 4 4、線性規(guī)劃的最優(yōu)解是絕對(duì)意義下的最優(yōu)，但需花、線性規(guī)劃的最優(yōu)

2、解是絕對(duì)意義下的最優(yōu)，但需花去大量的人力、物力、財(cái)力才能得到；實(shí)際過(guò)程中，去大量的人力、物力、財(cái)力才能得到；實(shí)際過(guò)程中，只要求得滿意解，就能滿足需要（或更能滿足需要）只要求得滿意解，就能滿足需要（或更能滿足需要）。 3 3、線性規(guī)劃中的約束條件是同等重要的，是硬約束、線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。；而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。目前，已經(jīng)在經(jīng)濟(jì)計(jì)劃、生產(chǎn)管理、經(jīng)營(yíng)管理、市場(chǎng)目前，已經(jīng)在經(jīng)濟(jì)計(jì)劃、生產(chǎn)管理、經(jīng)營(yíng)管理、市場(chǎng)分析、財(cái)務(wù)管理等方面得到了廣泛的應(yīng)用。分析、財(cái)務(wù)管理等方面得到了廣泛的應(yīng)用。第2頁(yè)/共54頁(yè)第3頁(yè)/共

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

4、標(biāo)值的部分，記為 d d。 負(fù)偏差變量：表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記負(fù)偏差變量：表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記為為 d d。第5頁(yè)/共54頁(yè)當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：d d0, d d0 當(dāng)未完成規(guī)定的指標(biāo)則表示：當(dāng)未完成規(guī)定的指標(biāo)則表示： d d0, d d0 當(dāng)恰好完成指標(biāo)時(shí)則表示：當(dāng)恰好完成指標(biāo)時(shí)則表示： d d0, d d0 d d d d 0 0 成立。成立。 引入了目標(biāo)值和正、負(fù)偏差變量后，就對(duì)某一問(wèn)引入了目標(biāo)值和正、負(fù)偏差變量后，就對(duì)某一問(wèn)題有了新的限制，即目標(biāo)約束。題有了新的限制，即目標(biāo)約束。 目標(biāo)約束既可對(duì)原目標(biāo)函數(shù)起作用，也可

5、對(duì)原約目標(biāo)約束既可對(duì)原目標(biāo)函數(shù)起作用，也可對(duì)原約束起作用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束束起作用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。絕對(duì)約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式絕對(duì)約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對(duì)約束，否則無(wú)可行解。所以，絕對(duì)約束是硬約束。對(duì)約束，否則無(wú)可行解。所以，絕對(duì)約束是硬約束。在一次決策中，實(shí)現(xiàn)值不可能既超過(guò)目標(biāo)值又未達(dá)在一次決策中，實(shí)現(xiàn)值不可能既超過(guò)目標(biāo)值又未達(dá)到目標(biāo)值，故有到目標(biāo)值，故有 d d d d 0,0,并規(guī)定并規(guī)定d d0, d d0第6頁(yè)/共54頁(yè)

6、 達(dá)成函數(shù)是一個(gè)使總偏差量為最小的目標(biāo)函數(shù)，記為達(dá)成函數(shù)是一個(gè)使總偏差量為最小的目標(biāo)函數(shù)，記為 minZ = f（d、d）。）。 一般說(shuō)來(lái)，有以下三種情況，但只能出現(xiàn)其中之一：一般說(shuō)來(lái)，有以下三種情況，但只能出現(xiàn)其中之一： .要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要盡可能小，則盡可能小，則minZ = f（d d）。）。 .要求不超過(guò)目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是要求不超過(guò)目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是正偏差變量盡可能小，則正偏差變量盡可能小，則minZ = f（d）。）。 .要求超過(guò)目標(biāo)值，即超過(guò)量不限，但不低于目標(biāo)值要求超過(guò)目標(biāo)值，即

7、超過(guò)量不限，但不低于目標(biāo)值，也就是負(fù)偏差變量盡可能小，則，也就是負(fù)偏差變量盡可能小，則minZ = f（d）。）。 對(duì)于由絕對(duì)約束轉(zhuǎn)化而來(lái)的目標(biāo)函數(shù)，也照上述處理對(duì)于由絕對(duì)約束轉(zhuǎn)化而來(lái)的目標(biāo)函數(shù)，也照上述處理即可。即可。第7頁(yè)/共54頁(yè) 優(yōu)先因子優(yōu)先因子Pk 是將決策目標(biāo)按其重要程度排序并表是將決策目標(biāo)按其重要程度排序并表示出來(lái)。示出來(lái)。P1P2PlPl+1PL ，l=1.2L。后面乘任意大的數(shù)還是小。必須后面乘任意大的數(shù)還是小。必須“滿足滿足”第一級(jí)才第一級(jí)才能能“滿足滿足”第二級(jí)，依次類推。第二級(jí)，依次類推。 權(quán)系數(shù)權(quán)系數(shù)lk ：區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)：區(qū)別具有相同優(yōu)先因子的兩個(gè)目

8、標(biāo)的重要性差別，決策者可視具體情況而定。的重要性差別，決策者可視具體情況而定。（優(yōu)先因子和權(quán)系數(shù)的大小具有主觀性和模糊性，（優(yōu)先因子和權(quán)系數(shù)的大小具有主觀性和模糊性，它不是運(yùn)籌學(xué)本身的問(wèn)題，主要是決策人自身的經(jīng)它不是運(yùn)籌學(xué)本身的問(wèn)題，主要是決策人自身的經(jīng)驗(yàn)，可用專家評(píng)定法給以量化。）驗(yàn)，可用專家評(píng)定法給以量化。） 對(duì)于這種解來(lái)說(shuō)，前面的目標(biāo)可以保證實(shí)現(xiàn)或部分對(duì)于這種解來(lái)說(shuō)，前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)。，有些可能就不能實(shí)現(xiàn)。第8頁(yè)/共54頁(yè)第9頁(yè)/共54頁(yè))3 . 2 . 1( 0

9、., 011 256108102 0 )(min21213321222111213322211jddxxxddxxddxxddxxdPddPdPZjj第10頁(yè)/共54頁(yè)（一）、模型的一般形式（一）、模型的一般形式1111min() (1.2)(.) (1.2)0 (j1.2n). 0 (1.2)LKllkklkklknkjjkkkjnijjijjkkZPddc xddgkKa xbimxddkK 第11頁(yè)/共54頁(yè)（二）、建模的步驟（二）、建模的步驟 1 1、根據(jù)要研究的問(wèn)題所提出的各目標(biāo)與條件，確定、根據(jù)要研究的問(wèn)題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對(duì)約束；目標(biāo)值，列出目標(biāo)約

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

11、一個(gè)由、根據(jù)決策者的要求，按下列情況之一構(gòu)造一個(gè)由 優(yōu)先因子和權(quán)系數(shù)相對(duì)應(yīng)的偏差變量組成的，要求實(shí)優(yōu)先因子和權(quán)系數(shù)相對(duì)應(yīng)的偏差變量組成的，要求實(shí)現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)?，F(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)。llddldld. .恰好達(dá)到目標(biāo)值，取恰好達(dá)到目標(biāo)值，取 。. .允許超過(guò)目標(biāo)值，取允許超過(guò)目標(biāo)值，取 。. .不允許超過(guò)目標(biāo)值，取不允許超過(guò)目標(biāo)值，取 。第13頁(yè)/共54頁(yè)（三）、小結(jié)（三）、小結(jié)線性規(guī)劃線性規(guī)劃LPLP目標(biāo)規(guī)劃目標(biāo)規(guī)劃GPGP目標(biāo)函數(shù)目標(biāo)函數(shù)min , max系數(shù)可正負(fù)系數(shù)可正負(fù)min , 偏差變量偏差變量系數(shù)系數(shù)00變量變量x xi,i, x xs s x xa a

12、 x xi i x xs s x xa a d d約束條件約束條件系統(tǒng)約束系統(tǒng)約束（絕對(duì)約束）（絕對(duì)約束）目標(biāo)約束目標(biāo)約束系統(tǒng)約束系統(tǒng)約束解解最優(yōu)最優(yōu)最滿意最滿意第14頁(yè)/共54頁(yè) 圖解法同樣適用兩個(gè)變量的目標(biāo)規(guī)劃問(wèn)題，但其操圖解法同樣適用兩個(gè)變量的目標(biāo)規(guī)劃問(wèn)題，但其操作簡(jiǎn)單，原理一目了然。同時(shí)，也有助于理解一般目作簡(jiǎn)單，原理一目了然。同時(shí)，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過(guò)程。標(biāo)規(guī)劃的求解原理和過(guò)程。 圖解法解題步驟如下：圖解法解題步驟如下： 1、確定各約束條件的可行域，即將所有約束條件、確定各約束條件的可行域，即將所有約束條件（包括目標(biāo)約束和絕對(duì)約束，暫不考慮正負(fù)偏差變量（包括目標(biāo)約束

13、和絕對(duì)約束，暫不考慮正負(fù)偏差變量）在坐標(biāo)平面上表示出來(lái)；）在坐標(biāo)平面上表示出來(lái)； 2、在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向；、負(fù)偏差變量值增大的方向；第15頁(yè)/共54頁(yè) 3、求滿足最高優(yōu)先等級(jí)目標(biāo)的解；、求滿足最高優(yōu)先等級(jí)目標(biāo)的解； 4、轉(zhuǎn)到下一個(gè)優(yōu)先等級(jí)的目標(biāo)，在不破壞所有較高、轉(zhuǎn)到下一個(gè)優(yōu)先等級(jí)的目標(biāo)，在不破壞所有較高優(yōu)先等級(jí)目標(biāo)的前提下，求出該優(yōu)先等級(jí)目標(biāo)的解；優(yōu)先等級(jí)目標(biāo)的前提下，求出該優(yōu)先等級(jí)目標(biāo)的解； 5、重復(fù)、重復(fù)4，直到所有優(yōu)先等級(jí)的目標(biāo)都已審查完畢，直到所有優(yōu)先等級(jí)的目標(biāo)都已審查完畢為止；為止； 6、確定最

14、優(yōu)解和滿意解。、確定最優(yōu)解和滿意解。例一、用圖解法求解目標(biāo)規(guī)劃問(wèn)題例一、用圖解法求解目標(biāo)規(guī)劃問(wèn)題min Z =P1 d1+ +P2 (d2- +d2+ )+P3 d3- 2x1 +x2 11 x1 - x2 + d1- - d1+ = 0 x1 +2x2 + d2- - d2+ =10 8x1 +10 x2 + d3- - d3+ =56 x1 , x2 , di- ,di+ 0 第16頁(yè)/共54頁(yè)第17頁(yè)/共54頁(yè) 例二、已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為例二、已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為 01006014021230max21212121xxxxxxxZ)( )( )( 丙丙資資源源乙乙

15、資資源源甲甲資資源源 其中目標(biāo)函數(shù)為總利潤(rùn)，其中目標(biāo)函數(shù)為總利潤(rùn)，x1,x2 為產(chǎn)品為產(chǎn)品A、B產(chǎn)量?，F(xiàn)產(chǎn)量?，F(xiàn)有下列目標(biāo)：有下列目標(biāo)： 1、要求總利潤(rùn)必須超過(guò)、要求總利潤(rùn)必須超過(guò) 2500 元；元； 2、考慮產(chǎn)品受市場(chǎng)影響，為避免積壓，、考慮產(chǎn)品受市場(chǎng)影響，為避免積壓，A、B的生產(chǎn)生產(chǎn)量不超過(guò)量不超過(guò) 60 件和件和 100 件；件； 3、由于甲資源供應(yīng)比較緊張，不要超過(guò)現(xiàn)有量、由于甲資源供應(yīng)比較緊張，不要超過(guò)現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。第18頁(yè)/共54頁(yè) 解：以產(chǎn)品解：以產(chǎn)品 A A、B B 的單件利潤(rùn)比的單件利潤(rùn)比 2.5 2.5

16、 ：1 1 為權(quán)系數(shù)為權(quán)系數(shù)，模型如下：，模型如下： )4 . 3 . 2 . 1(0, 010060140225001230)5 . 2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll 第19頁(yè)/共54頁(yè)0 x2 0 x11401201008060402020 40 60 80 1002d2d1d1d3d3d4d4dABCD 結(jié)論：結(jié)論：C(60 ,58.3)C(60 ,58.3)為所求的滿意解。為所求的滿意解。作圖：作圖： )4 . 3 . 2 . 1(0, 010060140225001230)5 . 2(min2144233

17、1222111212343211lddxddxddxddxxddxxdPddPdPZll 第20頁(yè)/共54頁(yè) 檢驗(yàn)：將上述結(jié)果帶入模型，因檢驗(yàn)：將上述結(jié)果帶入模型，因 0； 0； 0， 存在；存在； 0， 存在。所存在。所以，有下式：以，有下式： minZ=P3 2d2d1d1d3d3d4d4d2d 將將 x160， x2 58.3 帶入約束條件，得帶入約束條件，得30601258.32499.62500；260+58.3=178.3 140；16060158.358.3 0。說(shuō)明第。說(shuō)明第k k個(gè)優(yōu)先等級(jí)的目標(biāo)尚個(gè)優(yōu)先等級(jí)的目標(biāo)尚未達(dá)到未達(dá)到, ,必須檢查必須檢查Pk這一行的檢驗(yàn)數(shù)這一行的檢

18、驗(yàn)數(shù)kj(j=1.2n+2m).(j=1.2n+2m).若若Pk這一行某些負(fù)檢驗(yàn)數(shù)的同列上這一行某些負(fù)檢驗(yàn)數(shù)的同列上面（較高優(yōu)先等級(jí)）沒(méi)有正檢驗(yàn)數(shù)，說(shuō)明未得到滿意面（較高優(yōu)先等級(jí)）沒(méi)有正檢驗(yàn)數(shù)，說(shuō)明未得到滿意解，應(yīng)繼續(xù)改進(jìn)，轉(zhuǎn)到第解，應(yīng)繼續(xù)改進(jìn)，轉(zhuǎn)到第3 3步；若步；若Pk這一行全部負(fù)檢驗(yàn)這一行全部負(fù)檢驗(yàn)數(shù)的同列上面（較高優(yōu)先等級(jí)）都有正檢驗(yàn)數(shù)，說(shuō)明數(shù)的同列上面（較高優(yōu)先等級(jí)）都有正檢驗(yàn)數(shù)，說(shuō)明目標(biāo)雖沒(méi)達(dá)到，但已不能改進(jìn)，故得滿意解，轉(zhuǎn)到第目標(biāo)雖沒(méi)達(dá)到，但已不能改進(jìn)，故得滿意解，轉(zhuǎn)到第6 6步。步。 3 3、確定進(jìn)基變量。、確定進(jìn)基變量。 在在Pk行，從那些上面沒(méi)有正檢驗(yàn)數(shù)的負(fù)檢驗(yàn)數(shù)中，行，從

19、那些上面沒(méi)有正檢驗(yàn)數(shù)的負(fù)檢驗(yàn)數(shù)中，選絕對(duì)值最大者，對(duì)應(yīng)的變量選絕對(duì)值最大者，對(duì)應(yīng)的變量xs就是進(jìn)基變量。若就是進(jìn)基變量。若Pk行中有幾個(gè)相同的絕對(duì)值最大者，則依次比較它們各行中有幾個(gè)相同的絕對(duì)值最大者，則依次比較它們各列下部的檢驗(yàn)數(shù)，取其絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)的所在列下部的檢驗(yàn)數(shù)，取其絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)的所在列的列的xs為進(jìn)基變量。假如仍無(wú)法確定，則選最左邊的為進(jìn)基變量。假如仍無(wú)法確定，則選最左邊的變量（變量下標(biāo)小者）為進(jìn)基變量。變量（變量下標(biāo)小者）為進(jìn)基變量。第27頁(yè)/共54頁(yè) 4 4、確定出基變量、確定出基變量 其方法同線性規(guī)劃，即依據(jù)最小比值法則其方法同線性規(guī)劃，即依據(jù)最小比值法則故確定

20、故確定xr為出基變量，為出基變量，e ersrs為主元素。若有幾個(gè)相同的為主元素。若有幾個(gè)相同的行可供選擇時(shí)，選最上面那一行所對(duì)應(yīng)得變量為行可供選擇時(shí)，選最上面那一行所對(duì)應(yīng)得變量為xr 。rsorisissiebeeb0/min 5 5、旋轉(zhuǎn)變換（變量迭代）。、旋轉(zhuǎn)變換（變量迭代）。 以為主元素進(jìn)行變換，得到新的單純形表，獲得一組以為主元素進(jìn)行變換，得到新的單純形表，獲得一組新解，返回到第新解，返回到第2 2步。步。 6 6、對(duì)求得的解進(jìn)行分析、對(duì)求得的解進(jìn)行分析 若計(jì)算結(jié)果滿意，停止運(yùn)算；若不滿意，需修改模若計(jì)算結(jié)果滿意，停止運(yùn)算；若不滿意，需修改模型，即調(diào)整目標(biāo)優(yōu)先等級(jí)和權(quán)系數(shù)，或者改變目

21、標(biāo)值型，即調(diào)整目標(biāo)優(yōu)先等級(jí)和權(quán)系數(shù)，或者改變目標(biāo)值，重新進(jìn)行第，重新進(jìn)行第1 1步。步。第28頁(yè)/共54頁(yè))4 . 3 . 2 . 1( 0, 0100 60 140 2 250012305 . 2min214423312221112123423211lddxddxddxddxxddxxdPdPdPdPZll第29頁(yè)/共54頁(yè)Cj00P1000000000000002.5P20P200000P30000CBXBbx1x2P1250030121100000001402100110000060100000110001000100000011kjP1 -2500301201000000P2 0000

22、00002.501P3 000000100001d1d2d2d3d3d4d4d1d2d3d4d= min2500/30,140/2,60/1=60 ,故故 為換出變量為換出變量。3d第30頁(yè)/共54頁(yè)Cj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x160100000110001000100000011kjP1 7000120100303000P2 000000002.501P3 000000100001d1d2d2d3d3d4d4d1d2d4d= min700/30,20/2, =10 ,故故 為換出變量。為換出變量

23、。2d第31頁(yè)/共54頁(yè)Cj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000 x17011/2001/2-1/200000100010000001-1kjP1 -400030115-150000P2 -250-5/400-5/45/45/2001P3 000000100001d1d2d2d3d3d4d4d1d4d= min400/15, =10 ,故故 為換出變量。為換出變量。3d1d第32頁(yè)/共54頁(yè)Cj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/1

24、5-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/3000000001000100000011kjP1 00010000000P2 -175/30-1-1/121/12002/5001P3 -80/301/5-1/151/151000001d1d2d2d3d3d4d4d4d= min,350/6,1250/6,100/1=75 ,故故 為換出變量為換出變量。2d3d3d第33頁(yè)/共54頁(yè)Cj 00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000 x2175/3011/1

25、2-1/1200-5/25/2000 x160100000-11000125/300-1/121/12005/2-5/211kjP1 00010000000P2 000000005/201P3 -115/300-1/121/12101/2-1/2001d1d2d2d3d3d4d4d4d2d表中表中3115/30，說(shuō)明說(shuō)明P3 優(yōu)先等級(jí)目標(biāo)沒(méi)有實(shí)現(xiàn)，但已無(wú)法改進(jìn)，得到滿意解優(yōu)先等級(jí)目標(biāo)沒(méi)有實(shí)現(xiàn)，但已無(wú)法改進(jìn)，得到滿意解 x1 60， x2 175/3， 115/3， 125/3。4d2d第34頁(yè)/共54頁(yè) 結(jié)果分析：計(jì)算結(jié)果表明，工廠應(yīng)生產(chǎn)結(jié)果分析：計(jì)算結(jié)果表明，工廠應(yīng)生產(chǎn)A產(chǎn)品產(chǎn)品60件，件，

26、B產(chǎn)品產(chǎn)品175/3件，件，2500元的利潤(rùn)目標(biāo)剛好達(dá)到。元的利潤(rùn)目標(biāo)剛好達(dá)到。 125/3，表明產(chǎn)品比最高限額少，表明產(chǎn)品比最高限額少125/3件，滿足要求。件，滿足要求。 115/3 表明甲資源超過(guò)庫(kù)存表明甲資源超過(guò)庫(kù)存115/3公斤，該目標(biāo)沒(méi)有公斤，該目標(biāo)沒(méi)有達(dá)到。達(dá)到。 從表中還可以看到，從表中還可以看到，P3 的檢驗(yàn)數(shù)還有負(fù)數(shù)，但其高等的檢驗(yàn)數(shù)還有負(fù)數(shù)，但其高等級(jí)的檢驗(yàn)數(shù)卻是正數(shù)，要保證級(jí)的檢驗(yàn)數(shù)卻是正數(shù)，要保證 P1目標(biāo)實(shí)現(xiàn)，目標(biāo)實(shí)現(xiàn)，P3等級(jí)目標(biāo)則等級(jí)目標(biāo)則無(wú)法實(shí)現(xiàn)。所以，按現(xiàn)有消耗水平和資源庫(kù)存量，無(wú)無(wú)法實(shí)現(xiàn)。所以，按現(xiàn)有消耗水平和資源庫(kù)存量，無(wú)法實(shí)現(xiàn)法實(shí)現(xiàn)25002500元的

27、利潤(rùn)目標(biāo)。元的利潤(rùn)目標(biāo)。 可考慮如下措施：降低可考慮如下措施：降低A、B產(chǎn)品對(duì)甲資源的消耗產(chǎn)品對(duì)甲資源的消耗量，以滿足現(xiàn)有甲資源庫(kù)存量的目標(biāo)；或改變量，以滿足現(xiàn)有甲資源庫(kù)存量的目標(biāo)；或改變P3等級(jí)目等級(jí)目標(biāo)的指標(biāo)值，增加甲資源標(biāo)的指標(biāo)值，增加甲資源115/3115/3公斤。公斤。 若很難實(shí)現(xiàn)上述措施，則需改變現(xiàn)有目標(biāo)的優(yōu)先等若很難實(shí)現(xiàn)上述措施，則需改變現(xiàn)有目標(biāo)的優(yōu)先等級(jí)，以取得可行的滿意結(jié)果。級(jí)，以取得可行的滿意結(jié)果。4d2d第35頁(yè)/共54頁(yè))3 . 2 . 1( 0 ., 011 256108102 0 )(min21213321222111213322211jddxxxddxxddxxd

28、dxxdPddPdPZjj第36頁(yè)/共54頁(yè)Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 00111100000P210120011000 P3 5681000001100 x3 11210000001kjP1 0000100000P2 10120002000P3 5681000000101d1d2d2d3d3d1d2d3d= min,10/2,56/10,11/1= 5,故故 為換出變量為換出變量。2d第37頁(yè)/共54頁(yè)Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 023/20111/2-1/20000 x251/21001/2-1/2000 P3 630

29、00-551100 x3 63/2000-1/21/2001kjP1 0000100000P2 0000011000P3 630005-50101d1d2d2d3d3d1d3d= min10/3,10,6/3,12/3= 2,故故 為換出變量。為換出變量。3d第38頁(yè)/共54頁(yè)Cj 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/21kjP1 0000100000P2 0000011000P3 00000001001d

30、1d2d2d3d3d1d 最優(yōu)解為最優(yōu)解為x12 2， x2 4 4。 但非基變量但非基變量 的檢的檢驗(yàn)數(shù)為零，故此題有無(wú)窮多最優(yōu)解。驗(yàn)數(shù)為零，故此題有無(wú)窮多最優(yōu)解。= min4 , 24 , 6= 4,故故 為換出變量。為換出變量。1d3d第39頁(yè)/共54頁(yè)Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 04002-26-6-1100 x210/301-1/31/31/3-1/30000 x110/3102/3-2/31/3-1/30000 x3 100-11-11001kjP1 0000100000P2 0000011000P3 00000001001d1d2d2d3d3d

31、3d 最優(yōu)解為最優(yōu)解為x110/3,，x2 =10/3。第40頁(yè)/共54頁(yè) 1 1、某廠生產(chǎn)、某廠生產(chǎn)A、B、C三種產(chǎn)品，裝配工作在同三種產(chǎn)品，裝配工作在同一生產(chǎn)線上完成，三種產(chǎn)品時(shí)的工時(shí)消耗分別為一生產(chǎn)線上完成，三種產(chǎn)品時(shí)的工時(shí)消耗分別為6 6、8 8、1010小時(shí)，生產(chǎn)線每月正常工作時(shí)間為小時(shí)，生產(chǎn)線每月正常工作時(shí)間為200200小時(shí)；三小時(shí)；三種產(chǎn)品銷售后，每臺(tái)可獲利分別為種產(chǎn)品銷售后，每臺(tái)可獲利分別為500500、650650和和800800元元；每月銷售量預(yù)計(jì)為；每月銷售量預(yù)計(jì)為1212、1010和和6 6臺(tái)。臺(tái)。 該廠經(jīng)營(yíng)目標(biāo)如下：該廠經(jīng)營(yíng)目標(biāo)如下：1 1、利潤(rùn)指標(biāo)為每月、利潤(rùn)指標(biāo)

32、為每月1600016000元元，爭(zhēng)取超額完成；，爭(zhēng)取超額完成；2 2、充分利用現(xiàn)有生產(chǎn)能力；、充分利用現(xiàn)有生產(chǎn)能力；3 3、可、可以適當(dāng)加班，但加班時(shí)間不得超過(guò)以適當(dāng)加班，但加班時(shí)間不得超過(guò)2424小時(shí)；小時(shí)；4 4、產(chǎn)量、產(chǎn)量以預(yù)計(jì)銷售量為準(zhǔn)。試建立目標(biāo)規(guī)劃模型。以預(yù)計(jì)銷售量為準(zhǔn)。試建立目標(biāo)規(guī)劃模型。 第41頁(yè)/共54頁(yè)2 2、用圖解法求解下列目標(biāo)規(guī)劃問(wèn)題：、用圖解法求解下列目標(biāo)規(guī)劃問(wèn)題： )3.2.1(0,0,15552426)(min21332222111211132231lddxxddxddxxddxxddPdPdPZll滿意解為由滿意解為由x1 =（3， 3）, x2 =（3.5，1

33、.5） 所連線段。所連線段。第42頁(yè)/共54頁(yè) 3 3、用圖解法解下列目標(biāo)規(guī)劃模型。、用圖解法解下列目標(biāo)規(guī)劃模型。 4 ,3,2, 1 0,2403 .04 .0300 5002400 . )( min 214421331222111214332211iddxxddxxddxddxxddxxtsdpdpddpfiix1=400, x2=0, Z=80p3第43頁(yè)/共54頁(yè)0 100 200 300 400 500 100 200 300 400 x2 x11d1d4第44頁(yè)/共54頁(yè)4 4、用單純形法求解下列目標(biāo)規(guī)劃問(wèn)題：、用單純形法求解下列目標(biāo)規(guī)劃問(wèn)題： )3 .2 .1(0,2010260

34、3)(min313332122321113213332211lddxddxxxddxxxddxxxddPdPdPZllx =（10，20，10）第45頁(yè)/共54頁(yè) 5、用目標(biāo)規(guī)劃的單純形方法解以下目標(biāo)規(guī)劃模型。、用目標(biāo)規(guī)劃的單純形方法解以下目標(biāo)規(guī)劃模型。 3 , 2 , 1 0,10 12 202. . )( min 213322211121214233211iddxxddxddxddxxtsddpdpdpdpfii 5、x1=12, x2=10, =14, Z=14p4 1d第46頁(yè)/共54頁(yè)答案：答案： )6 , 2 , 1(0, 0,610122420010861600080065050

35、0 )( min , . 132166355244133222321113216655444332211321iddxxxddxddxddxdddddxxxddxxxddddddpdpdpdpZxxxii型型為為則則該該問(wèn)問(wèn)題題的的目目標(biāo)標(biāo)規(guī)規(guī)劃劃模模量量，分分別別表表示示三三種種產(chǎn)產(chǎn)品品的的產(chǎn)產(chǎn)設(shè)設(shè)第47頁(yè)/共54頁(yè)習(xí)習(xí) 題題1.已知條件如表所示已知條件如表所示工序工序型號(hào)型號(hào)每周最大每周最大加工能力加工能力AB（小時(shí)（小時(shí)/臺(tái)）臺(tái)）（小時(shí)（小時(shí)/臺(tái)）臺(tái)）436215070利潤(rùn)（元利潤(rùn)（元/臺(tái)）臺(tái)）300450如果工廠經(jīng)營(yíng)目標(biāo)的期望值和優(yōu)先等級(jí)如下：如果工廠經(jīng)營(yíng)目標(biāo)的期望值和優(yōu)先等級(jí)如下：p

36、 p1 1: : 每周總利潤(rùn)不得低于每周總利潤(rùn)不得低于1000010000元；元；p p2 2: : 因合同要求，因合同要求，A A型機(jī)每周至少生產(chǎn)型機(jī)每周至少生產(chǎn)1010臺(tái)，臺(tái)，B B型機(jī)每周至少型機(jī)每周至少 生產(chǎn)生產(chǎn)1515臺(tái)；臺(tái)；p p3 3: : 希望工序希望工序的每周生產(chǎn)時(shí)間正好為的每周生產(chǎn)時(shí)間正好為150150小時(shí)，工序小時(shí)，工序的生產(chǎn)時(shí)間最好用足，甚至可適當(dāng)加班。的生產(chǎn)時(shí)間最好用足，甚至可適當(dāng)加班。試建立這個(gè)問(wèn)題的目標(biāo)規(guī)劃模型。試建立這個(gè)問(wèn)題的目標(biāo)規(guī)劃模型。 第48頁(yè)/共54頁(yè)1 1223344512111222331244125 min ()()30045010000 10 1