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

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

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

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

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

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

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

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

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

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

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

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

12、向目標規(guī)劃的圖解分析法v4. 求滿足最高優(yōu)先等級目標的解v5. 轉到下一個優(yōu)先等級的目標，在不破壞所有較高優(yōu)先等級目標的前提下，求出該優(yōu)先等級目標的解v6. 重復5，直到所有優(yōu)先等級的目標都已審查完畢為止v7. 確定最優(yōu)解和滿意解。目標規(guī)劃的圖解分析法v例6.2 用圖解法求解下列目標規(guī)劃問題 )4 , 1(0,)1 . 4(82)1 . 4(1222)1 . 4(0)1 . 4(1232)1 . 4(124)1 . 4(164)(3)min214421332122211121214433322211iddxxfddxxeddxxdddxxcddxxbxaxdPddPddPdPzii（目標規(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目標規(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目標規(guī)劃的數學模型結構與線性規(guī)劃的數學模型結構形式上沒有本質的區(qū)別，所以可用單純形法求解。但要根據目標規(guī)劃的特點，作以下規(guī)定：(1) 因目標規(guī)劃問題的目標函數都是求最小化，所以以j0，j=1,2,，n作為最優(yōu)性判別準則。(2) 因非基變量的檢驗數中含有不同等級的優(yōu)先因子，即 因為 P1P2PK 故從每個檢驗

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