第6章的最終目的標(biāo)規(guī)劃

1、第6章的最終目的標(biāo)規(guī)劃目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型v問題的提出：v目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理多目標(biāo)決策的需要而由線性規(guī)劃逐步發(fā)展起來的一個分支。v由于現(xiàn)代化企業(yè)內(nèi)專業(yè)分工越來越細(xì)，組織機(jī)構(gòu)日益復(fù)雜，為了統(tǒng)一協(xié)調(diào)企業(yè)各部門圍繞一個整體的目標(biāo)工作，產(chǎn)生了目標(biāo)管理這種先進(jìn)的管理技術(shù)。目標(biāo)規(guī)劃是實行目標(biāo)管理的有效工具，它根據(jù)企業(yè)制定的經(jīng)營目標(biāo)以及這些目標(biāo)的輕重緩急次序，考慮現(xiàn)有資源情況，分析如何達(dá)到規(guī)定目標(biāo)或從總體上離規(guī)定目標(biāo)的差距為最小。目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型v例6.1 某企業(yè)計劃生產(chǎn)甲，乙兩種產(chǎn)品，這些產(chǎn)品分別要在A,B,C,D四種不同設(shè)備上加工。按工藝文件規(guī)定，如表所示。ABCD

2、單件利潤單件利潤甲甲21402乙乙22043最大負(fù)荷最大負(fù)荷1281612問該企業(yè)應(yīng)如何安排計劃，使得計劃期內(nèi)的總利潤收入為最問該企業(yè)應(yīng)如何安排計劃，使得計劃期內(nèi)的總利潤收入為最大？大？目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型v解：設(shè)甲、乙產(chǎn)品的產(chǎn)量分別為x1，x2，建立線性規(guī)劃模型： 0,124164821222.32max2121212121xxxxxxxxtsxxz其最優(yōu)解為其最優(yōu)解為x14，x22，z14元元目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型但企業(yè)的經(jīng)營目標(biāo)不僅僅是利潤，而且要考慮多個方面，如：但企業(yè)的經(jīng)營目標(biāo)不僅僅是利潤，而且要考慮多個方面，如：力求使利潤指標(biāo)不低于力求使利潤指標(biāo)不低于12元；元；考慮到市場需

3、求，甲、乙兩種產(chǎn)品的生產(chǎn)量需保持考慮到市場需求，甲、乙兩種產(chǎn)品的生產(chǎn)量需保持1:1的比的比例；例；C和和D為貴重設(shè)備，嚴(yán)格禁止超時使用；為貴重設(shè)備，嚴(yán)格禁止超時使用；(1)設(shè)備設(shè)備B必要時可以加班，但加班時間要控制；設(shè)備必要時可以加班，但加班時間要控制；設(shè)備A即要求即要求充分利用，又盡可能不加班。充分利用，又盡可能不加班。目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型v1）要求問題的解必須滿足全部約束條件，實際問題中并非所有約束都需要嚴(yán)格滿足。v2）只能處理單目標(biāo)的優(yōu)化問題。實際問題中，目標(biāo)和約束可以相互轉(zhuǎn)化。v3）線性規(guī)劃中各個約束條件都處于同等重要地位，但現(xiàn)實問題中，各目標(biāo)的重要性即有層次上的差別，同一層次中又

4、可以有權(quán)重上的區(qū)分。v4）線性規(guī)劃尋求最優(yōu)解，但很多實際問題中只需找出滿意解就可以。目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型1. 設(shè)置偏差變量，用來表明實際值同目標(biāo)值之間的差異。設(shè)置偏差變量，用來表明實際值同目標(biāo)值之間的差異。偏差變量用下列符號表示：偏差變量用下列符號表示：d+超出目標(biāo)的偏差，稱正偏差變量超出目標(biāo)的偏差，稱正偏差變量d-未達(dá)到目標(biāo)的偏差，稱負(fù)偏差變量未達(dá)到目標(biāo)的偏差，稱負(fù)偏差變量正負(fù)偏差變量兩者必有一個為正負(fù)偏差變量兩者必有一個為0。 當(dāng)實際值超出目標(biāo)值時：當(dāng)實際值超出目標(biāo)值時： d+0, d-=0; 當(dāng)實際值未達(dá)到目標(biāo)值時：當(dāng)實際值未達(dá)到目標(biāo)值時： d+=0, d-0; 當(dāng)實際值同目標(biāo)值恰好

5、一致時：當(dāng)實際值同目標(biāo)值恰好一致時： d+=0, d-=0;故恒有故恒有d+d-=0目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型2. 統(tǒng)一處理目標(biāo)和約束。統(tǒng)一處理目標(biāo)和約束。 對有嚴(yán)格限制的資源使用建立系統(tǒng)約束，數(shù)學(xué)形式同線性規(guī)劃對有嚴(yán)格限制的資源使用建立系統(tǒng)約束，數(shù)學(xué)形式同線性規(guī)劃中的約束條件。如中的約束條件。如C和和D設(shè)備的使用限制。（硬約束）設(shè)備的使用限制。（硬約束）12416421 xx 對不嚴(yán)格限制的約束，連同原線性規(guī)劃建模時的目標(biāo)，均通過對不嚴(yán)格限制的約束，連同原線性規(guī)劃建模時的目標(biāo)，均通過目標(biāo)約束目標(biāo)約束(軟約束軟約束)來表達(dá)。來表達(dá)。1）例如要求甲、乙兩種產(chǎn)品保持）例如要求甲、乙兩種產(chǎn)品保持1:1

6、的比例，系統(tǒng)約束表達(dá)為：的比例，系統(tǒng)約束表達(dá)為：x1=x2。由于這個比例允許有偏差，。由于這個比例允許有偏差，當(dāng)當(dāng)x1x2時，出現(xiàn)正偏差時，出現(xiàn)正偏差d+，即：，即： x1-d+ =x2或或x1x2-d+ =0目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型v正負(fù)偏差不可能同時出現(xiàn)，故總有：vx1x2+d-d+ =0 0min21ddxxd 若希望甲的產(chǎn)量不低于乙的產(chǎn)量，即不希望若希望甲的產(chǎn)量不低于乙的產(chǎn)量，即不希望d-0,用目標(biāo)約束可用目標(biāo)約束可表為表為: 若希望甲的產(chǎn)量低于乙的產(chǎn)量，即不希望若希望甲的產(chǎn)量低于乙的產(chǎn)量，即不希望d0,用目標(biāo)約束可表用目標(biāo)約束可表為為: 0min21ddxxd 若希望甲的產(chǎn)量恰好等于

7、乙的產(chǎn)量，即不希望若希望甲的產(chǎn)量恰好等于乙的產(chǎn)量，即不希望d0,也不希望也不希望d-0用目標(biāo)約束可表為用目標(biāo)約束可表為: 0min21ddxxdd目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型v3）設(shè)備B必要時可加班及加班時間要控制，目標(biāo)約束表示為： 82min21ddxxd2）力求使利潤指標(biāo)不低于）力求使利潤指標(biāo)不低于12元，目標(biāo)約束表示為：元，目標(biāo)約束表示為： 1232min21ddxxd4）設(shè)備）設(shè)備A既要求充分利用，又盡可能不加班，目標(biāo)約束表示為：既要求充分利用，又盡可能不加班，目標(biāo)約束表示為： 1222min21ddxxdd目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型3. 目標(biāo)的優(yōu)先級與權(quán)系數(shù)目標(biāo)的優(yōu)先級與權(quán)系數(shù)在一個目標(biāo)規(guī)

8、劃的模型中，為達(dá)到某一目標(biāo)可犧牲其他一些在一個目標(biāo)規(guī)劃的模型中，為達(dá)到某一目標(biāo)可犧牲其他一些目標(biāo)，稱這些目標(biāo)是屬于不同層次的優(yōu)先級。優(yōu)先級層次的高低目標(biāo)，稱這些目標(biāo)是屬于不同層次的優(yōu)先級。優(yōu)先級層次的高低可分別通過優(yōu)先因子可分別通過優(yōu)先因子P1,P2,表示。對于同一層次優(yōu)先級的不同表示。對于同一層次優(yōu)先級的不同目標(biāo)，按其重要程度可分別乘上不同的權(quán)系數(shù)（懲罰因子）。權(quán)目標(biāo)，按其重要程度可分別乘上不同的權(quán)系數(shù)（懲罰因子）。權(quán)系數(shù)是一個個具體數(shù)字，乘上的權(quán)系數(shù)越大，表明該目標(biāo)越重要系數(shù)是一個個具體數(shù)字，乘上的權(quán)系數(shù)越大，表明該目標(biāo)越重要?，F(xiàn)假定：現(xiàn)假定： 第第1優(yōu)先級優(yōu)先級P1企業(yè)利潤；企業(yè)利潤；

9、第第2優(yōu)先級優(yōu)先級P2甲乙產(chǎn)品的產(chǎn)量保持甲乙產(chǎn)品的產(chǎn)量保持1:1的比例的比例 第第3優(yōu)先級優(yōu)先級P3設(shè)備設(shè)備A,B盡量不超負(fù)荷工作。其中設(shè)備盡量不超負(fù)荷工作。其中設(shè)備A的重要性的重要性比設(shè)備比設(shè)備B大三倍。大三倍。目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型v上述目標(biāo)規(guī)劃模型可以表示為：)4,.,1(0,82122201232124164. .)(3)(min214213212211121214333322211432iddxxddxxddxxddxxddxxxxtsdPddPddPdPzii目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式 )2 .1( 0 .n)1.2(j 0)2

10、.1( ).()2 .1( )(min1111KkddxmibxaKkgddxcddPZkkjnjijijnjkkkjkjLlKkklkklkl達(dá)成函數(shù)達(dá)成函數(shù)目標(biāo)約束目標(biāo)約束其中：其中：g gk k為第為第k k個目標(biāo)約束的預(yù)期目標(biāo)值，個目標(biāo)約束的預(yù)期目標(biāo)值， 和和 為為p pl l 優(yōu)先因子優(yōu)先因子對應(yīng)各目標(biāo)的權(quán)系數(shù)。對應(yīng)各目標(biāo)的權(quán)系數(shù)。 lk lk目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型明確問題，列出明確問題，列出目標(biāo)的優(yōu)先級和目標(biāo)的優(yōu)先級和權(quán)系數(shù)權(quán)系數(shù)構(gòu)造目標(biāo)規(guī)構(gòu)造目標(biāo)規(guī)劃模型劃模型求出滿意解求出滿意解滿意否？滿意否？分析各項目標(biāo)分析各項目標(biāo)完成情況完成情況據(jù)此制定出決策方案據(jù)此制定出決策方案NY目標(biāo)

11、規(guī)劃的圖解分析法適用兩個變量的目標(biāo)規(guī)劃問題，但其操作簡單，適用兩個變量的目標(biāo)規(guī)劃問題，但其操作簡單，原理一目了然。同時，也有助于理解一般目標(biāo)規(guī)劃原理一目了然。同時，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。的求解原理和過程。1. 將所有約束條件（包括目標(biāo)約束和絕對約束，暫不考慮正負(fù)偏將所有約束條件（包括目標(biāo)約束和絕對約束，暫不考慮正負(fù)偏差變量）的直線方程分別標(biāo)示于坐標(biāo)平面上。差變量）的直線方程分別標(biāo)示于坐標(biāo)平面上。2. 確定系統(tǒng)約束的可行域。確定系統(tǒng)約束的可行域。3. 在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向增大的方

12、向目標(biāo)規(guī)劃的圖解分析法v4. 求滿足最高優(yōu)先等級目標(biāo)的解v5. 轉(zhuǎn)到下一個優(yōu)先等級的目標(biāo)，在不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解v6. 重復(fù)5，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止v7. 確定最優(yōu)解和滿意解。目標(biāo)規(guī)劃的圖解分析法v例6.2 用圖解法求解下列目標(biāo)規(guī)劃問題 )4 , 1(0,)1 . 4(82)1 . 4(1222)1 . 4(0)1 . 4(1232)1 . 4(124)1 . 4(164)(3)min214421332122211121214433322211iddxxfddxxeddxxdddxxcddxxbxaxdPddPddPdPzii（目標(biāo)規(guī)劃的

13、圖解分析法(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目標(biāo)規(guī)劃的圖解分析法 )3 , 2 , 1( 0,)4(56108)3(102)2(0) 1 (112)min21332122211121213322211

14、iddxxddxxddxxddxxxxdPddPdPzii（x1x2(1)(2)d1+d1-(3)d2-d2+(4)d3-d3+CD滿意解是線段滿意解是線段CD上任意點上任意點其中其中C點點X(2,4),D點點X(10/3,10/3)0105112,410/3,10/35107例例第3節(jié) v目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)形式上沒有本質(zhì)的區(qū)別，所以可用單純形法求解。但要根據(jù)目標(biāo)規(guī)劃的特點，作以下規(guī)定：(1) 因目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，所以以j0，j=1,2,，n作為最優(yōu)性判別準(zhǔn)則。(2) 因非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子，即 因為 P1P2PK 故從每個檢驗

15、數(shù)的整體來看，檢驗數(shù)的正、負(fù)首先決定于P1的系數(shù)1j的正、負(fù)；若1j=0，則此檢驗數(shù)的正、負(fù)就決定于P2的系數(shù)2j的正、負(fù)；下面依此類推。1,2, ;1,2,jkjka Pjn kKv解目標(biāo)規(guī)劃問題的單純形法的計算步驟：(1) 建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行，置k=1。(2) 檢查該行中是否存在負(fù)數(shù)，且對應(yīng)的前k1行的系數(shù)是零。若有負(fù)數(shù)取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)到(3)；若無負(fù)數(shù)，則轉(zhuǎn)到(5)。(3) 按最小比值規(guī)則確定換出變量。當(dāng)存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。(4) 按單純形法進(jìn)行基變換運算，建立新的計算表，返回(2)。(5) 當(dāng)k=K時，計算結(jié)束，表中的解即為滿意解。否則，置k=k+1，返回到(2)。v例例4 4 試用單純形法來求解例2。解：解：將例2的數(shù)學(xué)模型化為標(biāo)準(zhǔn)型：3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxxddxxddxxddxxxxxdPddPdPziiss滿足約束條件：目標(biāo)函數(shù)：v 取xs，d1，d2 ，d