【文章內(nèi)容簡介】 規(guī)劃的圖解法 ? 目標(biāo)規(guī)劃的圖解法 ? 作業(yè) 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃的圖解法 Step2. 根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子來分析求解： P1優(yōu)先因子的目標(biāo)的實現(xiàn) 。 P2優(yōu)先因子的目標(biāo)的實現(xiàn) 。 P3優(yōu)先因子的目標(biāo)的實現(xiàn) 。 ? 圖解法的主要步驟： Step1． 在平面直角坐標(biāo)系內(nèi)，作各約束條件： （畫法同線性規(guī)劃圖解法）； ： ① 先令 di = di+ =0，作相應(yīng)直線； ② 在直線旁標(biāo)上 di 、 di+ ，表明目標(biāo)約束可沿 di 、 di+所示方向平移（平移方向是使 di 或 di+ 增加的方向）。 對只具有二個決策變量的目標(biāo)規(guī)劃的數(shù)學(xué)模型，可以用圖解法來分析求解。我們用例 53來說明具體求解過程。 山東理工大學(xué)管理學(xué)院 ③ 有效解為 GD線段： G=(2,4) 利潤 =56 D=(10/3,10/3)利潤 =60 目標(biāo)規(guī)劃的圖解法 例 54 用圖解法求解例 53。 3,2,1,0,561081020112)()()(m i n21332122211121213322211????????????????????????????????iddxxddxxddxxddxxxxdPddPdPfiid3+ 5 x2 11 10 10 5 7 x1 A B C D E G d2+ d1 x1+2x2 = 10 x1 x2=0 8x1+10x2=56 2x1+x2 =11 O d1+ d2 d3 解： 1．在平面直角坐標(biāo)系內(nèi)，做約束條件。 2．根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子來分析求解： ① 可行域 ? OAB ② 目標(biāo) 1： ? OBC 目標(biāo) 2： ED線段 目標(biāo) 3： GD線段 ④ min f =0 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃的圖解法 例 5 5 某電視機廠裝配黑白和彩色電視機，每裝配一臺電視機需占用裝配線 1 h ，裝配線每周計劃開動 40 h 。預(yù)計市場每周彩色電視機的銷量是 24 臺，每臺可獲利 80 元，黑白電視機的銷量是 30 臺，每臺可獲利 40 元，該廠確定的目標(biāo)是： 1P：充分利用裝配線每周計劃開動的 40 h ； 2P：允許裝配線加班，但加班時間每周盡量不超過 10 h ； 3P：裝配電視機的數(shù)量盡量滿足市場需求。因彩電的利潤高，取其權(quán)系數(shù)為 2 。 試建立這一問題的目標(biāo)規(guī)劃模型，并求解黑白電視機和彩色電視機的產(chǎn)量。 解 設(shè)21, xx 分別表示彩色電視機和黑白電視機的產(chǎn)量。根據(jù)問題的要求，可建立相應(yīng)的目標(biāo)規(guī)劃模型為 1 1 2 2 3 3 41 2 1 11 2 2 21 3 32 4 412m in ( ) ( ) ( 2 )40502430, , , 0 , 1 , 2 , 3 , 4iif P d P d P d dx x d dx x d dx d dx d dx x d d i? ? ? ???????????? ? ? ?? ? ? ?? ? ? ?? ? ?? ? ??? 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃的圖解法 用圖解法求解，見下圖： 2x 241 ?x ?1d ?3d ?3d ?1d ?4d 302 ?x ?4d ?2d ?2d 1x 4021 ?? xx 5021 ?? xx 圖 5 3 目標(biāo)約束條件示意圖 H E D C G A B F 1. 滿足目標(biāo)① 、 ②的滿意域為 ABCD 2. 先考慮③的滿意域為 ABEF 3. 在滿足目標(biāo)① 、 ② 、③ 的基礎(chǔ)上，使得 d4 最小的是 E點 (24,26)，獲利 2960。 4. min f =d4 = 4 再考慮④，無公共滿意域。 min f=P1d1+P2d2++P3(2d3+d4)(目標(biāo)函數(shù) ) 因此，該廠每周應(yīng)裝配彩色電視機 24臺，黑白電視機 26臺。 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃的圖解法 ? 作業(yè) ? 用圖解法找出以下目標(biāo)規(guī)劃問題的有效解。 )()()()(m i n 4332312431 ?????? ?????? ddPdPdPddPf 1 2 1 11 2 2 21 3 32 4 412401003015, , , 0 , 1 , 2 , 3 , 4iix x d dx x d dx d dx d dx x d d i??????????? ? ? ?? ? ? ?? ? ?? ? ??? 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃的分層單純形法 ? 目標(biāo)規(guī)劃的分層單純形法 ? 作業(yè) 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃的分層單純形法 伊杰尼（ Y． Ijiri） 1965年在提出目標(biāo)的優(yōu)先等級和優(yōu)先權(quán)因子的概念的基礎(chǔ)上，給出了改進的“目標(biāo)規(guī)劃”的分層單純形算法。 目標(biāo)規(guī)劃模型的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)沒有本質(zhì)的區(qū)別，所以其計算方法與單純形法類似。但要考慮目標(biāo)規(guī)劃數(shù)學(xué)模型的一些特點，作以下規(guī)定： 1 ）因目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求極小值，所以以 njj ,2,1,0 ???? 為最優(yōu)準(zhǔn)則。 2 ）因非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子，即 njPKkkkjj ,2,1,1??? ???? 因KPPP ?????? ?21；從每個檢驗數(shù)的整體來看：檢驗數(shù)的正 、 負首先決定于1P的系數(shù)j1?的正 、 負。若01 ?j?，這時，檢驗數(shù)的正 、 負就決定于2P的系數(shù)j2?的正 、 負。下面可依此類推。 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃的分層單純形法 解目標(biāo)規(guī)劃問題的分層單純形法的計算步驟： 1 ）建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成 K 行，令 1?k 。 2 ）檢查該行中是否存在負數(shù)，且對應(yīng)的前 1?k 行的系數(shù)是零。若有，取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn) 3 ）。若無負數(shù)，則轉(zhuǎn) 5 ）。 3 ）按最小比值規(guī)則確定換出變量，當(dāng)存在兩個或兩個以上相同的最小比值時，選取具有較高優(yōu)先層次的變量為換出變量。 4 ）按單純形法進行基變換運算，建立新的計算表，返回 2 ）。 5 ）當(dāng) Kk ? 時，計算結(jié)束。表中的解即為有效解。否則 令 1?? kk ，返回到 2 ）。 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃的分層單純形法 例 56 試用分層單純形法求解例 53。 解 1 ） 取 ???? 4321 , dddd 為初始基變量，列初始單純形表，見表 5 2 。 表 5 2 分層單純形表 BC BX b 1x 2x ?1d ?1d ?2d ?2d ?3d ?3d ?4d ?4d jc 1P 2P 3P 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 1 0 0 0 1P 3P 3P ?1d ?2d ?3d ?4d 40 50 24 30 1 1 1 0 1 1 0 1 1 0 0 0 1? 0 0 0 0 1 0 0 0 1? 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1? j? 1P 2P 3P 1 0 2 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 1 2 ）取 1?k ，檢查檢驗數(shù)的 1P 行，有 1? ， 1? ，取變量 1x 為換入變量，轉(zhuǎn) 3 ）。 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃的分層單純形法 3 ）在表 5 2 上計算24124124,150,140m i n0m i n 11??????????????? ?iii aab ，將該最小比值對應(yīng)的變量 ?3d作為換出變量，轉(zhuǎn) 4 ）。 4 ）進行基變換運算，得表 5 3 ，返回到 2 ）。 表 5 3 分層單純形迭代表 BC BX b 1x 2x ?1d ?1d ?2d ?2d ?3d ?3d ?4d ?4d 1P 3P ?1d ?2d 1x ?4d 16 26 24 30 0 0 1 0 1 1 0 1 1 0 0 0 1? 0 0 0 0 1 0 0 0 1? 0 0 0 1? 1 0 1? 1 1? 0 1 0 0 1 0 0 0 1? j? 1P 2P 3P 0 0 0 1? 0 1? 0 0 0 1 0 0 0 0 0 0 1 0 1 0 2 1? 0 0 0 0 0 0 0 1 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃的分層單純形法 依此類推，直至得到最終單純形表為止（見表 55）。 表 5 4 分層單純形迭代表 BC BX b 1x 2x ?1d ?1d ?2d ?2d ?3d ?3d ?4d ?4d 3P 2x ?2d 1x ?4d 16 10 24 14 0 0 1 0 1 0 0 0 1 1? 0 1? 1? 1 0 1 0 1 0 0 0 1? 0 0 1? 0 1 1 1 0 1? 1? 0 0 0 1 0 0