【正文】 1小時(shí)，裝配線每周計(jì)劃開動(dòng)40小時(shí)。預(yù)計(jì)市場(chǎng)每周彩色電視機(jī)的銷量是 24臺(tái)，每臺(tái)可獲利 80元；黑白電視機(jī)的銷量是 30臺(tái)，每臺(tái)可獲利 40元。該企業(yè)決策者確定的目標(biāo)為： ? 第一優(yōu)先級(jí)：充分利用裝配線每周計(jì)劃開動(dòng) 40小時(shí)； ? 第二優(yōu)先級(jí)：允許裝配線加班；但加班時(shí)間每周盡量不超過 10小時(shí)； ? 第三優(yōu)先級(jí)：裝配電視機(jī)的數(shù)量盡量滿足市場(chǎng)需要。因彩色電視機(jī)的利潤高，取其權(quán)數(shù)為 2。 ? 試建立該問題的目標(biāo)規(guī)劃模型，并求解 黑白和彩色電視機(jī)的產(chǎn)量。 例 3 23 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 ⑴ ⑵ ⑶ A 0 10 20 30 40 50 60 70 80 10 20 30 40 50 60 x2 x1 B ?1d?1d ?2d?2C ?3d?3d⑷ ?4d?4D E F H G E(24 ,26)為所求的滿意解。 ????????????????????????????????????????????)41(0,0,302450 40)2(m in21442331222111214332211?iddxxddxddxddxxddxxddPdPdPZii解：設(shè) x1， x2分別表示彩色和黑白電視機(jī)的產(chǎn)量。 24 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 ⑴ ⑵ ⑶ A x2 x1 B ?1d?1 ?2d?2C B ( , ) C (0 , ) ， B、 C 線段上的所有點(diǎn)均是該問題的解（無窮多最優(yōu)解）。 ????????????????????????????????)(0,0,8 2 102 )(min21212221112122111lddxxxxddxxddxxdPddPZll例 用圖解法求解目標(biāo)規(guī)劃問題 25 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 例 已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為 ???????????????01006014021230max21212121xxxxxxxZ)( )( )( 丙資源乙資源甲資源 其中目標(biāo)函數(shù)為總利潤， x1,x2 為產(chǎn)品 A、 B產(chǎn)量?，F(xiàn)有下列目標(biāo)： 要求總利潤必須超過 2500 元； 考慮產(chǎn)品受市場(chǎng)影響，為避免積壓， A、 B的 生產(chǎn)量不超過 60 件和 100 件； 由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量 140。 試建立目標(biāo)規(guī)劃模型，并用圖解法求解。 26 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 解：以產(chǎn)品 A、 B 的單件利潤比 ： 1 為權(quán)系數(shù)，模型 如下： ?????????????????????????????????????????????)(0,0100601402250 01230)(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll 27 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 0 x2 ⑴ x1 140 120 100 80 60 40 20 20 40 60 80 100 ⑵ ⑶ ⑷ ?2d?2?1d??3d?3?4d?4A B C D 結(jié)論： C(60 ,)為所求的滿意解。 作圖： ?????????????????????????????????????????????)(0,0100601402250 01230)(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll 28 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 檢驗(yàn)：將上述結(jié)果帶入模型，因 ＝ ＝ 0； ＝ ＝ 0； ＝ 0， 存在； ＝ 0， 存在。所以，有下式： min Z=P3 ?2d ?2d ?1d?1d?3d?3d ?4?4 將 x1＝ 60， x2 ＝ 帶入約束條件，得 30 60＋ 12 ＝ ≈2500； 2 60+= 140； 1 60＝ 60 1 ＝ 100 由上可知：若 A、 B的計(jì)劃產(chǎn)量為 60件和 ，所需甲資源數(shù)量將超過現(xiàn)有庫存。在現(xiàn)有條件下，此解為非可行解。為此，企業(yè)必須采取措施降低 A、 B產(chǎn)品對(duì)甲資源的消耗量，由原來的 100％降至 ％（ 140247。 ＝ ），才能使生產(chǎn)方案（ 60， ）成為可行方案。 29 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 cj c1 … cm cm+1 … x1 … xm xm+1 … xn 1 … 0 a1m+1 … a1n 0 … 0 a2m+1 … a2n … 0 … 1 amm+1 … amn b b1 b2 bm XB x1 x2 xm CB c1 c2 cm σ =cjzj 0 … 0 … ??? mi ininac1 ?? ??? mi imimac1 11θi θ1 θ2 θm z ??? mi iibc13 目標(biāo)規(guī)劃的單純形法 （一）、一般形式： 線性規(guī)劃的初始單純形表 30 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 σj ? 目標(biāo)規(guī)劃的單純形表的一般形式 CB XB b x1 x2 xn+2m Cj c1 c2 +2m a11 a12 a1n+2m a21 a22 a2n+2m am1 am2 amn+2m b1 b2 bm ?xj1 xj2 xjm Pj1 Pj2 Pjm P1 P2 PK σ11 σ12 σ1n+2m σ21 σ22 σ2n+2m σm1 σm2 σmn+2m α1 α2 αK ?? ??? ? ??? ?? ??k P ? d kkjijBjjjj PapBCczc ?????? ? 1? d 31 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 建立初始單純形表。 一般假定初始解在原點(diǎn)，即以約束條件中的所有負(fù)偏差變量或松弛變量為初始基變量，按目標(biāo)優(yōu)先等級(jí)從左至右分別計(jì)算出各列的檢驗(yàn)數(shù)，填入表的下半部 。 檢驗(yàn)是否為滿意解。判別準(zhǔn)則如下： ⑴ .首先檢查 αk (k=… K)是否全部為零？如果全部為零，則表示目標(biāo)均已全部達(dá)到，獲得滿意解，停止計(jì)算轉(zhuǎn)到第 6步；否則轉(zhuǎn)入⑵。 （二）、單純形法的計(jì)算步驟 32 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 ⑵ .如果某一個(gè) αk 0。說明第 k個(gè)優(yōu)先等級(jí)的目標(biāo)尚未達(dá)到 ,必須檢查 Pk這一的檢驗(yàn)數(shù) σkj(j=?n+2m). 若Pk這一行某些負(fù)檢驗(yàn)數(shù)的同列上面（較高優(yōu)先等級(jí)）沒有正檢驗(yàn)數(shù)，說明未得到滿意解，應(yīng)繼續(xù)改進(jìn)，轉(zhuǎn)到第 3步；若 Pk這一行全部負(fù)檢驗(yàn)數(shù)的同列上面（較高優(yōu)先等級(jí)）都有正檢驗(yàn)數(shù)，說明目標(biāo)雖沒達(dá)到，但已不能改進(jìn)，故得滿意解，轉(zhuǎn)到第 6步。 確定進(jìn)基變量。 在 Pk行，從那些上面沒有正檢驗(yàn)數(shù)的負(fù)檢驗(yàn)數(shù)中，選絕對(duì)值最大者，對(duì)應(yīng)的變量 xs就是進(jìn)基變量。若 Pk行中有幾個(gè)相同的絕對(duì)值最大者，則依次比較它們各列下部的檢驗(yàn)數(shù)，取其絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)的所在列的 xs為進(jìn)基變量。假如仍無法確定，則選最左邊的變量（變量下標(biāo)小者）為進(jìn)基變量。 33 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 確定出基變量 其方法同線性規(guī)劃，即依據(jù)最小比值法則 故確定 xr為出基變量， ars為主元素。若有幾個(gè)相同的行可供選擇時(shí)，選最上面那一行所對(duì)應(yīng)得變量為 xr 。 rsorisissiabaab ????????? 0/min? 旋轉(zhuǎn)變換（變量迭代）。 以為主元素進(jìn)行變換，得到新的單純形表，獲得一組新解，返回到第 2步。 對(duì)求得的解進(jìn)行分析 若計(jì)算結(jié)果滿意，停止運(yùn)算；若不滿意，需修改模型，即調(diào)整目標(biāo)優(yōu)先等級(jí)和權(quán)系數(shù)，或者改變目標(biāo)值，重新進(jìn)行第 1步。 34 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 ?????????????????????????????????????????????)( 0,0100 60 140 2 250 01230214423312221112123423211lddxddxddxddxxddxxdPdPdPdPZll例 用單純形法求解下列目標(biāo)規(guī)劃問題 35 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 Cj CB XB b x1 x2 σ ?1d?1 ?2d?2?3d?3d?4?4dθ= min｛ 2500/30,140/2,60/1｝ =60 ,故 為換出變量。 ?3dθi 0 0 P1 0 0 P3 0 2 0 P2 30 12 1 1 0 0 0 0 0 0 2 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 1 ?????????????????????????????????????????????)( 0,0100 60 140 2 250 01230214423312221112123423211lddxddxddxddxxddxxdPdPdPdPZll2500 140 60 100 ?1d?23d?4dP1 0 0 0 P1 P2 P3 32111111003030)1000102030(0PPPPPacciB????????????????? ??30 0 0 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 2500 0 0 2500/30 140/2 60/1 / 36 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 Cj 0 0 P1 0 0 P3 0 2 0 P2 CB XB b x1 x2 P1 700 0 12 1 － 1 0 0 － 30 30 0 0 0 20 0 1 0 0 1 － 1 － 2 2 0 0 0 x1 60 1 0 0 0 0 0 1 － 1 0 0 0 100 0 1 0 0 0 0 0 0 1 － 1 σkj P1 － 700 0 － 12 0 1 0 0