【文章內(nèi)容簡介】 d n j x m i b x a K k g d d x c d d P z k k j i j n j ij k k k j n j kj k lk k K k lk L l l L L L 滿足約束條件： 目標函數(shù) ： w w 其中 Pl為優(yōu)先因子， wlk， w?lk為優(yōu)先系數(shù) 七、建模的步驟 ? 根據(jù)要研究的問題所提出的各目標與條件 ， 確定目標值 ， 列出目標約束與絕對約束； ? 可根據(jù)決策者的需要 ， 將某些或全部絕對約束轉(zhuǎn)化為目標約束 。 這時只需要給絕對約束加上負偏差變量和減去正偏差變量即可 。 ? 給各目標賦予相應(yīng)的優(yōu)先因子 Pk ? 對同一優(yōu)先等級中的各偏差變量 ， 若需要可按其重要程度的不同 ， 賦予相應(yīng)的權(quán)系數(shù) ωkl+和 ωkl 。 ? 根據(jù)決策者的要求 ， 構(gòu)造一個由優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的 ， 要求實現(xiàn)極小化的目標函數(shù) ，即達成函數(shù) 。 46 47 48 線性規(guī)劃與目標規(guī)劃 線性規(guī)劃 LP 目標規(guī)劃 GP 目標函數(shù) min, max 系數(shù)可正負 min , 偏差變量 系數(shù) ≥0 變量 xi , xs , xa xi , xs , xa , d 約束條件 系統(tǒng)約束 (絕對約束 ) 目標約束 系統(tǒng)約束 解 最優(yōu) 滿意 第三節(jié) 目標規(guī)劃的圖解法 73 1 1 2 2 31 2 1 12 2 21 3 3121212m in ( 2 )3 5 30 ( 1 )4 ( 2)( 3 )6( 4)2 16 .( 5 )2 10( 6)3 4 32( 7 ),0, 0( 1 , 2 , 3 )llG P d P d dx x d dx d dx d dxxxxxxd d l ????? ? ?? ? ? ??? ???? ??? ????????????????F 2x1 =16 2x2 =10 B C x1 4 A 10 3x1 +4 x2 =32 6 x2 0 D 2 6 4 2 E G H 1d1d?2d?3d3?滿意解： x1=5, x2=4 74 第三節(jié) 目標規(guī)劃的圖解法 目標規(guī)劃的圖解法 ?首先，按照絕對約束畫出可行域， ?其次，不考慮正負偏差變量，畫出目標約束的邊界線， ?最后。按優(yōu)先級別和權(quán)重依次分析各級目標。 1 1 2 2 31 2 1 12 2 21 3 3121212m in ( 2 )3 5 30 ( 1 )4 ( 2)( 3 )6( 4)2 16 .( 5 )2 10( 6)3 4 32( 7 ),0, 0( 1 , 2 , 3 )llG P d P d dx x d dx d dx d dxxxxxxd d l ????? ? ?? ? ? ??? ???? ??? ????????????????F 2x1 =16 2x2 =10 B C x1 4 A 10 3x1 +4 x2 =32 6 x2 0 D 2 6 4 2 E G H 1d1d?2d?3d3?滿意解： x1=5, x2=4 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ) 2 . 1 ( 0 , 0 8 2 10 2 5 . 62 12 10 ) ( min 2 1 2 1 2 2 2 1 1 1 2 1 2 2 1 1 1 l d d x x x d d x x d d x x d P d d P Z l l 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 ⑴ ⑵ ⑶ A x2 x1 B 1d?1 2d2C B ( , ) C (0 , ) ， B、 C 線段上的所有點均是該問題的解 (無窮多最優(yōu)解 )。 第三節(jié) 目標規(guī)劃的圖解法 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ) 4 . 3 . 2 . 1 ( 0 , , 0 100 60 140 2 2500 12 30 ) 5 . 2 ( min 2 1 4 4 2 3 3 1 2 2 2 1 1 1 2 1 2 3 4 3 2 1 1 l d d x d d x d d x d d x x d d x x d P d d P d P Z l l 0 x2 (1) x1 140 120 100 80 60 40 20 20 40 60 80 100 (2) (3) (4) 2d?21d?3d?34d?4A B C D 結(jié)論： C(60 ,)為所求的滿意解 。 目標規(guī)劃的圖解法 目標規(guī)劃的圖解法 圖解法解題步驟如下： ， 即將所有約束條件 (包括目標約束和絕對約束 ， 暫不考慮正負偏差變量 )在坐標平面上表示出來； ， 用箭頭標出正 、 負偏差變量值增大的方向； ； ， 在不破壞所有較高優(yōu)先等級目標的前提下 ， 求出該優(yōu)先等級目標的解； 4， 直到所有優(yōu)先等級目標都已審查完畢為止； 。 78 第四節(jié) 目標規(guī)劃的單純形法 ? 目標規(guī)劃與線性規(guī)劃的數(shù)學(xué)模型的結(jié)構(gòu)相似 ? 可用前述單純形算法求解目標規(guī)劃模型： ? 將優(yōu)先等級 Pk視為正常數(shù) (大 Ｍ 法 ) ? 正負偏差變量 dk+、 dk視為松弛變量 ? 以負偏差變量 dk為初始基變量，建立初始單純形表 ? 檢驗數(shù)的計算與 LP單純形法相同，即 ?j= cj CBi Pj ? 最優(yōu)性判別準則類似于 LP的單純形算法： ? 檢驗數(shù)一般是各優(yōu)先等級因子的代數(shù)和 ? 判斷檢驗數(shù)的正負和大小 目標規(guī)劃的單純形法 目標規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)形式上沒有本質(zhì)的區(qū)別 ， 所以可用單純形法求解 。 但要考慮目標規(guī)劃的數(shù)學(xué)模型一些特點 ， 作以下規(guī)定： (1) 因目標規(guī)劃問題的目標函數(shù)都是求最小化 ， 所以以 cjzj≥0， j=1,2,… ， n為最優(yōu)準則 。 (2)因非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子 ， 即 K k n j P a z c k kj j j , , 2 , 1 。 , , 2 , 1 L L ? ? ? ? 因 P1P2… PK；從每個檢驗數(shù)的整體來看：檢驗數(shù)的正 、 負首先決定于 P1的系數(shù) α1j的正 、 負 。 若 α1j=0， 這時此檢驗數(shù)的正 、 負就決定于 P2的系數(shù) α2j的正 、 負 。 例 見表 413. 目標規(guī)劃的單純形法 例 ：用單純形法求解下列目標規(guī)劃問題 MinZ=P1 d1 + P2(d2+d2+)+P3(3d3+5d4) 5x1+4x2 +d1 d1+ = 20 4x1+3x2 +d2 d2+= 24 x1 +d3 d3+ = 3 x1 + x2 +d4 d4+ = 2 x1 , x2 ,dk , dk+ ≥0 目標規(guī)劃的單純形法 cj ? 值 CB XB b x1 x2 d1 d1+ d2 d2+ d3 d3+ d4 d4+ 檢驗數(shù) λj P1 P2 P3 0 0 P1 0 P2 P2 3P3 0 5P3 0 20 5 4 1 1 0 0 0 0 0 0 24 4 3 0 0 1 1 0 0 0 0 3 1 0 0 0 0 0 1 1 0 0 2 1 1 0 0 0 0 0 0 1 1 d1 d2 d3 d4 5 4 0 1 0 0 0 4 3 2 2 5 3 5 4 6 3 檢驗數(shù) λj P1 P2 P3 d1 d2 x1 d4 P1 P2 0 5P3 3 1 0 0 0 0 0 1 1 0 0 5 0 4 1 1 0 0 5 5 0 0 12 0 3 0 0 1 1 4 4 0 0 5 0 1 0 0 0 0 1 1 1 1 0 4 0 1 0 5 5 0 3 2 4 4 5 2 5 5 1 3 P1 P2 3P3 5P3 目標規(guī)劃的單純形法 cj 0 0 P1 0 P2 P2 3P3 0 5P3 0 ? 值 CB XB b x1 x2 d1 d1+ d2 d