【文章內(nèi)容簡介】 一個區(qū)域 Rk ( ? Rk1 ?…? R1 )， 滿足 Pk 級的各目標(biāo) ， 這個 Rk 即為所求的解域 ， 如果 某一個 Ri ( 1≤ i ≤ k )已退化為一點 ，則計算終止 ， 這一點即為滿意解 ， 它只能滿足 P1 ,… ， Pi 級目標(biāo) ， 而無法進一步改進 ， 當(dāng)然 ， 此時或許有低于 Pi 級目標(biāo)被滿足 ， 這純屬巧合 。 第四章 目標(biāo)規(guī)劃 目標(biāo)規(guī)劃圖解法的具體演算過程 第 1步： 由決策變量繪畫所有約束條件的直線圖形 ， 偏差 變量以平移直線的方法加以考慮 。 第 5步： 重復(fù)第 4步過程 ， 直到解區(qū)域 Ri 減少到一點或 滿足了所有 k個級別的目標(biāo)為止 ， 此時 Rk 即為最 優(yōu)解區(qū)域 ， 其中的任何一點均為目標(biāo)規(guī)劃滿意解 。 第 2步： 對 P1級的各目標(biāo)，確定解區(qū)域 R1。 第 3步： 對下一個優(yōu)先級別 Pi 級各目標(biāo)，確定它的最優(yōu)解 空間 Ri ，但必須是 Ri ? Ri1 ( i = 2, 3, …)。 第 4步： 在這個過程中，如果某解區(qū)域 Ri 減小到一點，則 結(jié)束，因為此時沒有進一步改進的可能。 第四章 目標(biāo)規(guī)劃 ? 目標(biāo)規(guī)劃問題的標(biāo)準(zhǔn)型，實質(zhì)上是最小化的線性規(guī)劃，因而也可用單純形法求解。但要注意把目標(biāo)優(yōu)先等級系數(shù) Pi（ i=1,2,…,k）理解為一種特殊的正常數(shù)，且注意到各等級系數(shù)之間的關(guān)系： P1 187。P2187?！?87。Pk。檢驗數(shù)就是各優(yōu)先因子P1,P2,…,Pk的線性組合，如 : , 當(dāng)所有檢驗數(shù)都滿足最優(yōu)性條件（ ）時，從最終表上即可得出目標(biāo)規(guī)劃的解。 第三節(jié) 目標(biāo)規(guī)劃的單純形解法 0j jjC c z? ? ?3211 32 PPPC ??? ?比如用單純形法求前面例 43的解： 第四章 目標(biāo)規(guī)劃 1 1 2 2 3 31 2 11 2 1 1 21 2 2 2 31 2 3 3 412Mi n 5 10 60 ( )2 0 ( )s. t 4 4 36 ( )6 8 48 ( ), 0 , , 0 , ( 1 , 2 , 3 )iiZ P d P d P dx x lx x d d lx x d d lx x d d lx x d d i? ? ?????????? ? ?????? ? ? ???? ? ? ???? ? ? ??? ? ? ??解 引入松馳變量 x3 , 將它們化為標(biāo)準(zhǔn)型： 1 1 2 2 3 31 2 31 2 1 11 2 2 21 2 3 31 2 3Mi n 5 10 602 0. 4 4 366 8 48, , 0 , , 0 , ( 1 , 2 , 3 )iiZ P d P d P dx x xx x d dx x d dx x d dx x x d d i? ? ?????????? ? ?? ? ???? ? ? ???? ? ? ???? ? ? ??? ? ? ??建立單純形表，見表 42。 例 45 用單純形法求例 43的解 第四章 目標(biāo)規(guī)劃 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 5 10 1 0 0 0 0 0 0 P1 0 1 2 0 1 1 0 0 0 0 0 36 4 4 0 0 0 1 1 0 0 P3 48 6 8 0 0 0 0 0 1 1 P1 1 2 0 0 1 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 6 8 0 0 0 0 0 0 1 0 x3 60 0 20 1 5 5 0 0 0 0 0 x1 0 1 2 0 1 1 0 0 0 0 0 36 0 12 0 4 4 1 1 0 0 P3 48 0 20 0 6 6 0 0 1 1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 20 0 6 6 0 0 0 1 ?1d ?1d ?2d ?3d?2d ?3d?1d?2d?3djjj zc ????2d?3djjj zc ???表 42 單純形表 ? ?11 1 313123510 0 0466106PPPPPPP???????????????? ? ??? ? ? ?? ? ? ???? ? ? ?? ? ? ??? ? ? ?其中“ ?”是一種運算符號，表示向量的數(shù)量積運算 第四章 目標(biāo)規(guī)劃 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 0 20 1 5 5 0 0 0 0 0 x1 0 1 2 0 1 1 0 0 0 0 0 36 0 12 0 4 4 1 1 0 0 P3 48 0 [20] 0 6 6 0 0 1 1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 20 0 6 6 0 0 0 1 0 x3 12 0 0 1 1 1 0 0 1 1 0 x1 24/5 1 0 0 2/5 2/5 0 0 1/10 1/10 0 36/5 0 0 0 2/5 2/5 1 1 3/5 3/5 0 x2 12/5 0 1 0 3/10 3/10 0 0 1/20 1/20 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 0 0 0 0 0 0 1 0 ?1d ?1d ?2d ?3d?2d ?3d?2d?3djjj zc ????2djjj zc ???表 42 單純形表 全部檢驗數(shù)非負，計算結(jié)束。 第四章 目標(biāo)規(guī)劃 計算步驟說明： 2． 最優(yōu)性檢驗 目標(biāo)規(guī)劃的最優(yōu)性檢驗是分優(yōu)先級進行 的 ， 從 P1級開始依次到 Pk 級為止 ， 具體檢驗 Pi 級目標(biāo) 時 ， 可能有下述三種情況 。 （ 1） 若檢驗數(shù)矩陣的 Pi 行系數(shù)均 ≥0， 則 Pi 級目標(biāo)已達最 優(yōu) ， 轉(zhuǎn)入對 Pi+1 級目標(biāo)尋優(yōu) ， 直到 i = k， 計算結(jié)束 。 如本題中第二段檢驗數(shù)部分 ， P1行各系數(shù)均 ≥0， 故 P1目標(biāo)已達最優(yōu)： 011 ?? ?? dd1．確定初始“基”（同線性規(guī)劃單純形法），計算檢驗 矩陣。 第四章 目標(biāo)規(guī)劃 （ 2）若檢驗數(shù)矩陣的 Pi 中有負系數(shù)，且負系數(shù)所在列的前 i1行優(yōu)先因子的系數(shù)全為 0 ( 例如 P2 +223 P3 0 ) ， 可判定該檢驗數(shù)為負 ，則選該系數(shù)（若此類負系數(shù)有多個，則可選絕對值最大者）所在列對應(yīng)的非基變量為入基變量，繼續(xù)進行基變換。 如本題中初始基確定后，從檢驗數(shù)可確定出 x1為入基變量，經(jīng)變換后，再從檢驗數(shù)行看出， P3行的系數(shù)有兩個負數(shù) 20和 6，它們所對應(yīng)列的前兩行元素全為 0，故選 20對應(yīng)的變量 x2為入基變量，繼續(xù)進行迭代變換。 第四章 目標(biāo)規(guī)劃 （ 3） 若檢驗數(shù)矩陣的 Pi行中有負系數(shù) ， 但負系數(shù)所在列的前 i1行優(yōu)先因子的系數(shù)有 0， 也有正數(shù) （ 例如 P2 3 P3 0） ， 即整個檢驗數(shù)的值可判為正 （ 因 Pi1187。Pi ） ， 故也應(yīng)轉(zhuǎn)入對 Pi+1級目標(biāo)的尋優(yōu) ， 否則會使高優(yōu)先級別的目標(biāo)函數(shù)值劣化 。 3． 基變換 ① 入基變量的確定：依步驟 2可確定入基變量 。 ② 出基變量的確定：按最小非負比值規(guī)則確定出基變量 ， 同線性規(guī)劃的單純形法 。 ③ 主元素的確定：出基變量與入基變量在系數(shù)矩陣中對應(yīng)的交叉點上的元素即為主元素 。 ④ 迭代變換：同線性規(guī)劃的單純形法 。 第四章 目標(biāo)規(guī)劃 4． 從表中找到基本可行解和相應(yīng)于各優(yōu)先級的目標(biāo)函數(shù)值 ， 每個單純形表中常數(shù)列 b， 即為各基變量的相應(yīng)取值 。 本題最后一個單純形表已為最優(yōu) ， 它對應(yīng)的基本可行解： x1=24/5, x2=12/5, x3=12， d2=36/5， 即為最優(yōu)解 。 這與圖解法得到結(jié)果一致 。 注意： 在最優(yōu)單純形表中非基變量 的檢驗數(shù)都是零 ， 故知本題有多個最優(yōu)解 。 如以 為入基變量繼續(xù)迭代 ， 可得單純形表 43， 如以 為入基變量繼續(xù)迭代 ， 可得單純形表 44。 13dd??和??d??d第四章 目標(biāo)規(guī)劃 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 0 20 1 5 5 0 0 0 0 0 x1 0 1 2 0 1 1 0 0 0 0 0 36 0 12 0 4 4 1 1 0 0 P3 48 0 [20] 0 6 6 0 0 1 1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 20 0 6 6 0 0 0 1 0 x3 12 0 0 1 1 1 0 0 1 1 0 x1 24/5 1 0 0 2/5 2/5 0 0 1/10 1/10 0 36/5 0 0 0 2/5 2/5 1 1 3/5 3/5 0 x2 12/5 0 1 0 3/10 3/10 0 0 1/20 1/20 P1 0 0 0 1 0 0 0 0 0