數(shù)據(jù)模型與決策 多目標(biāo)規(guī)劃PPT課件

1、1線性目標(biāo)規(guī)劃與線性規(guī)劃比較 線性規(guī)劃只討論單一線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題；而目標(biāo)規(guī)劃是多個(gè)目標(biāo)決策，能統(tǒng)籌兼顧處理實(shí)際問題中經(jīng)常出現(xiàn)的多種目標(biāo)關(guān)系，求得更切合實(shí)際的最優(yōu)解。 線性規(guī)劃求在滿足所有約束條件的可行解中的最優(yōu)解；目標(biāo)規(guī)劃通常是在相互矛盾的約束條件的制約下找到一個(gè)滿意解。 線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。 線性規(guī)劃的最優(yōu)解是絕對(duì)意義下的最優(yōu)，但需花去大量的人力、物力、財(cái)力才能得到；實(shí)際過程中，只要求得滿意解，就能滿足需要（或更能滿足需要）。 目標(biāo)規(guī)劃能有效地描述和解決經(jīng)濟(jì)管理中的許多問題，其理論與方法在經(jīng)濟(jì)計(jì)劃

2、、生產(chǎn)管理、經(jīng)營管理、市場分析等方面有著廣泛的應(yīng)用。第1頁/共24頁 例例: :某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤最大？同時(shí)，根據(jù)市場預(yù)測(cè)，甲的銷路不是太試制定生產(chǎn)計(jì)劃，使獲得的利潤最大？同時(shí)，根據(jù)市場預(yù)測(cè)，甲的銷路不是太好，應(yīng)盡可能少生產(chǎn)；乙的銷路較好，可以擴(kuò)大生產(chǎn)。試建立此問題的數(shù)學(xué)模好，應(yīng)盡可能少生產(chǎn)；乙的銷路較好，可以擴(kuò)大生產(chǎn)。試建立此問題的數(shù)學(xué)模型。型。12070單件利潤3000103設(shè)備臺(tái)時(shí)200054煤炭360049鋼材資源限制乙甲 單位 產(chǎn)品資源 消耗目標(biāo)規(guī)

3、劃的基本概念第2頁/共24頁3設(shè)：甲產(chǎn)品設(shè)：甲產(chǎn)品 x1 ，乙產(chǎn)品，乙產(chǎn)品 x2 一般有：一般有：maxZ=70 x1 + 120 x2 9 x1 +4 x2 3600 4 x1 +5 x2 2000 3 x1 +10 x2 3000 x1 ， x2 0同時(shí)：同時(shí)：maxZ1=70 x1 + 120 x2 minZ2= x1 maxZ3= x2 9 x1 +4 x2 3600 4 x1 +5 x2 2000 3 x1 +10 x2 3000 x1 ， x2 0 顯然，這是一個(gè)多目標(biāo)規(guī)劃問題，用線性規(guī)劃方法顯然，這是一個(gè)多目標(biāo)規(guī)劃問題，用線性規(guī)劃方法很難找到最優(yōu)解。很難找到最優(yōu)解。第3頁/共24

4、頁 目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量，可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量，可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約束目標(biāo)約束。 目標(biāo)值目標(biāo)值是指預(yù)先給定的某個(gè)目標(biāo)的一個(gè)期望值。是指預(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)值。 偏差變量偏差變量（事先無法確定的未知數(shù)）是指實(shí)現(xiàn)值和目標(biāo)值之間的差異（事先無法確定的未知數(shù)）是指實(shí)現(xiàn)值和目標(biāo)值之間的差異, ,記為記為 d d 。 正正偏差變量表示實(shí)現(xiàn)值超過目標(biāo)值的部分，記為偏差變量表示實(shí)現(xiàn)值超過目標(biāo)值的部分，記為 d d。 負(fù)負(fù)偏差變

5、量表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記為偏差變量表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記為 d d。1 1、目標(biāo)值和偏差變量、目標(biāo)值和偏差變量第4頁/共24頁在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有到目標(biāo)值，故有 d d d d0 0，且，且d d0, d0, d0 0完成或超額完成規(guī)定的指標(biāo)則表示：d0, d0未完成規(guī)定的指標(biāo)則表示： d0, d0恰好完成指標(biāo)時(shí)則表示： d0, d0 d d 0 成立。第5頁/共24頁6 引入了目標(biāo)值和正、負(fù)偏差變量后，就對(duì)某一問題有了新的限制，即目標(biāo)約引入了目標(biāo)值和正、負(fù)偏差變量后，就對(duì)某一問題有了新的限制

6、，即目標(biāo)約束。束。 目標(biāo)約束目標(biāo)約束即可對(duì)原目標(biāo)函數(shù)起作用，也可對(duì)原約束起作用。目標(biāo)約束是目即可對(duì)原目標(biāo)函數(shù)起作用，也可對(duì)原約束起作用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。標(biāo)規(guī)劃中特有的，是軟約束。絕對(duì)約束絕對(duì)約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對(duì)約束，否則無可行解。所以，絕對(duì)約束是硬約束。劃中的所有約束條件都是絕對(duì)約束，否則無可行解。所以，絕對(duì)約束是硬約束。2 2、目標(biāo)約束和絕對(duì)約束第6頁/共24頁7 例如：在例中，規(guī)定例如：在例中，規(guī)定Z1 的目標(biāo)值為的目標(biāo)值為 50000,正、負(fù)正、

7、負(fù)偏差為偏差為d、d ,則目標(biāo)函數(shù)可以轉(zhuǎn)換為目標(biāo)約束，則目標(biāo)函數(shù)可以轉(zhuǎn)換為目標(biāo)約束，即即 70 x1 + 120 x2 50000 同樣，若規(guī)定同樣，若規(guī)定 Z2200， Z3250 則有則有 11dd200221ddx250332ddx)3 . 2 . 1( 0,jddjj 若規(guī)定若規(guī)定36003600的鋼材必須用完，原式的鋼材必須用完，原式9 x1 +4 x2 3600則變?yōu)閯t變?yōu)?, 360049444421ddddxx第7頁/共24頁 達(dá)成函數(shù)達(dá)成函數(shù)是一個(gè)使總偏差量為最小的目標(biāo)函數(shù)，記是一個(gè)使總偏差量為最小的目標(biāo)函數(shù)，記為為 minZ = f（d、d），又稱為準(zhǔn)則函數(shù)。），又稱為準(zhǔn)則

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

9、達(dá)成函數(shù)（即目標(biāo)規(guī)劃中的目標(biāo)函數(shù)）第8頁/共24頁 優(yōu)先因子優(yōu)先因子Pk 是將決策目標(biāo)按其重要程度排序并表示出來。是將決策目標(biāo)按其重要程度排序并表示出來。P1P2PkPk+1PK ，k=1.2K。 權(quán)系數(shù)權(quán)系數(shù)k 區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，決策者可視具體情況區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，決策者可視具體情況而定。而定。 前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)。分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)。4 4、優(yōu)先因子（優(yōu)先等級(jí)）與優(yōu)先權(quán)系數(shù)、優(yōu)先因子（優(yōu)先等級(jí)）與優(yōu)先

10、權(quán)系數(shù) 5、滿意解（具有層次意義的解）第9頁/共24頁 若在例一中提出下列要求：若在例一中提出下列要求： 1、完成或超額完成利潤指標(biāo)、完成或超額完成利潤指標(biāo) 50000元；元； 2、產(chǎn)品甲不超過、產(chǎn)品甲不超過 200件，產(chǎn)品乙不低于件，產(chǎn)品乙不低于 250件；件； 3、現(xiàn)有鋼材、現(xiàn)有鋼材 3600噸必須用完。噸必須用完。試建立目標(biāo)規(guī)劃模型。試建立目標(biāo)規(guī)劃模型。 分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目標(biāo)值。分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目標(biāo)值。 第一目標(biāo)：第一目標(biāo)： 第二目標(biāo)：有兩個(gè)要求即甲第二目標(biāo)：有兩個(gè)要求即甲 ，乙，乙 ，但兩，但兩個(gè)具有相同的優(yōu)先因子，因此需要確定權(quán)系數(shù)。本題個(gè)具有相同

11、的優(yōu)先因子，因此需要確定權(quán)系數(shù)。本題可用單件利潤比作為權(quán)系數(shù)即可用單件利潤比作為權(quán)系數(shù)即 70 :120，化簡為，化簡為7:12。11dP32 dd)127( 322ddP第10頁/共24頁11第三目標(biāo)：第三目標(biāo)：)(443 ddP)4 . 3 . 2 . 1( 0 ., 03000 10 3 2000 5 4 36004 9 250 200 5000012070)()127(min2121214421332221112144332211jddxxxxxddxxddxddxddxxddPddPdPZjj目標(biāo)規(guī)劃模型為：目標(biāo)規(guī)劃模型為：第11頁/共24頁 某廠生產(chǎn)某廠生產(chǎn)、兩兩種產(chǎn)品，有關(guān)數(shù)據(jù)如

12、種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最表所示。試求獲利最大的生產(chǎn)方案？大的生產(chǎn)方案？擁有量原材料2111設(shè)備(臺(tái)時(shí))1210單件利潤810 在此基礎(chǔ)上考慮：在此基礎(chǔ)上考慮： 1、產(chǎn)品、產(chǎn)品的產(chǎn)量不低于產(chǎn)品的產(chǎn)量不低于產(chǎn)品的產(chǎn)量；的產(chǎn)量； 2、充分利用設(shè)備有效臺(tái)時(shí)，不加班；、充分利用設(shè)備有效臺(tái)時(shí)，不加班； 3、利潤不小于、利潤不小于 56 元。元。解解: : 分析分析 第一目標(biāo)：第一目標(biāo)： 即產(chǎn)品即產(chǎn)品的產(chǎn)量不大于的產(chǎn)量不大于的產(chǎn)量。的產(chǎn)量。 第二目標(biāo)：第二目標(biāo)：11dP)(222ddP第12頁/共24頁13第三目標(biāo)：第三目標(biāo)：33dP規(guī)劃模型：規(guī)劃模型：)3 . 2 . 1( 0 ., 011

13、256108102 0 )(min21213321222111213322211jddxxxddxxddxxddxxdPddPdPZjj第13頁/共24頁)2 .1( 0 .n)1.2(j 0)2 .1( ).()2 .1( )(min1111LlddxmibxaLlqddxcddPZlljnjijijnjllljkjKkLllkllklk目標(biāo)規(guī)劃的數(shù)學(xué)模型第14頁/共24頁15建模的步驟建模的步驟 根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對(duì)約束； 可根據(jù)決策者的需要，將某些或全部絕對(duì)約束轉(zhuǎn)化為目標(biāo)約束, ,只需要給絕對(duì)約束加上負(fù)偏差變量和減去正偏差變量即可; ; 給

14、各目標(biāo)賦予相應(yīng)的優(yōu)先因子 P Pk k（k=1.2Kk=1.2K）; ; 對(duì)同一優(yōu)先等級(jí)中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù) 。klkl和和第15頁/共24頁16 根據(jù)決策者要求，按下列情況之一構(gòu)造一個(gè)由根據(jù)決策者要求，按下列情況之一構(gòu)造一個(gè)由 優(yōu)先因子和權(quán)系數(shù)相對(duì)應(yīng)的偏差變量組成的，優(yōu)先因子和權(quán)系數(shù)相對(duì)應(yīng)的偏差變量組成的，要求實(shí)現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)。要求實(shí)現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)。llddldld. .恰好達(dá)到目標(biāo)值，取恰好達(dá)到目標(biāo)值，取 。. .允許超過目標(biāo)值，取允許超過目標(biāo)值，取 。. .不允許超過目標(biāo)值，取不允許超過目標(biāo)值，取 。第16頁/共24

15、頁目標(biāo)規(guī)劃的圖解法1、確定各約束條件的可行域，即將所有約束條件（包括目標(biāo)約束和絕對(duì)約束，暫不考慮正負(fù)偏差變量）在坐標(biāo)平面上表示出來；2、在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向；3、求滿足最高優(yōu)先等級(jí)目標(biāo)的解；4、轉(zhuǎn)到下一個(gè)優(yōu)先等級(jí)的目標(biāo)，在不破壞所有較高優(yōu)先等級(jí)目標(biāo)的前提下，求出該優(yōu)先等級(jí)目標(biāo)的解；5、重復(fù)4，直到所有優(yōu)先等級(jí)目標(biāo)都已審查完畢為止；6、確定最優(yōu)解和滿意解。第17頁/共24頁18例一、用圖解法求解目標(biāo)規(guī)劃問題例一、用圖解法求解目標(biāo)規(guī)劃問題)2 . 1(0, 08 2 102 5 .621210)(min21212221112122111lddxxxddx

16、xddxxdPddPZll第18頁/共24頁1901 2 3 4 5 6 7 8 1 2 3 4 5 6 Ax2 x1B1d1d2d2dC B (0.6250 , 4.6875) C (0 , 5.2083) ， B、C 線段線段上的所有點(diǎn)均是該問題的解（無窮多最優(yōu)解）。上的所有點(diǎn)均是該問題的解（無窮多最優(yōu)解）。)2 . 1(0, 08 2 102 5 .621210)(min21212221112122111lddxxxddxxddxxdPddPZll第19頁/共24頁20 例二、已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為例二、已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為 01006014021230max212

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

18、型，并用圖解法求解。第20頁/共24頁21 解：以產(chǎn)品解：以產(chǎn)品 A A、B B 的單件利潤比的單件利潤比 2.5 2.5 ：1 1 為權(quán)系數(shù)，為權(quán)系數(shù)，模型如下：模型如下： )4 . 3 . 2 . 1(0, 010060140225001230)5 . 2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll 第21頁/共24頁220 x2 0 x11401201008060402020 40 60 80 1002d2d1d1d3d3d4d4dABCD 結(jié)論：結(jié)論：C(60 ,58.3)C(60 ,58.3)為所求的滿意解。為所求的滿意解。作圖