【正文】 山東理工大學(xué)管理學(xué)院 第五章 目標(biāo)規(guī)劃 ? 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 ? 目標(biāo)規(guī)劃的圖解法 ? 目標(biāo)規(guī)劃的分層單純形法 ? 目標(biāo)規(guī)劃應(yīng)用案例 目標(biāo)規(guī)劃應(yīng)用案例 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 ? 多目標(biāo)規(guī)劃簡介 ? 以多目標(biāo)規(guī)劃模型建立目標(biāo)規(guī)劃模型 ? 以單目標(biāo)規(guī)劃模型建立目標(biāo)規(guī)劃數(shù)學(xué)模型 ? 小結(jié) ? 作業(yè) 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 多目標(biāo)規(guī)劃簡介 多目標(biāo)問題最早是由 Franklin在 1772年提出來的，最早的多目標(biāo)問題的經(jīng)濟模型是 Cournot于 1838年提出的。 1896年，Pareto首次從數(shù)學(xué)的角度提出多目標(biāo)最優(yōu)化問題，后來， Von Neumann， Koopmans及 Kohn－ tucker， Charnes， Karlin， Polak等人又做了許多較有影響的工作。今天，多目標(biāo)規(guī)劃受到了人們的普遍重視。 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 多目標(biāo)規(guī)劃簡介 （ 1）問題的提出及數(shù)學(xué)模型的建立 在實際問題中，常常需要研究在某些限制條件下，同時考慮多個目標(biāo)的最優(yōu)化問題。例如，人們購買一件物品，既要求價廉又要求物美，這就包含了兩個目標(biāo)。再把購買物品具體到購買一件衣服，可能要考慮質(zhì)量、顏色、式樣、大小、價格這五個目標(biāo)。又如選擇一個新廠址，除了考慮運費、造價、燃料供應(yīng)費等經(jīng)濟指標(biāo)外，還要考慮對環(huán)境的影響等社會因素。 我們可以通過下面幾個實例來具體了解多目標(biāo)規(guī)劃問題的提出及數(shù)學(xué)模型的建立： 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 多目標(biāo)規(guī)劃簡介 （ 1）問題的提出及數(shù)學(xué)模型的建立 例 5 1 生產(chǎn)計劃問題。某工廠生產(chǎn))2( ?nn種產(chǎn)品： 1 號品，2 號品，?， n 號品。已知：該廠生產(chǎn) i （ni ,3,2,1 ??）號品的生產(chǎn)能力是ia 噸 / 小時 ；生產(chǎn) 1 噸 i 號品可獲利潤i?元；據(jù)市場預(yù)測，下月 i 號品的最大銷售量為ib（ni ,3,2 ??） 噸 ；工廠下月的開工工時能力為 T 小時；下月市場需要盡可能多的 1 號品。問：應(yīng)如何安排下月的生產(chǎn)計劃，在避免開工不足的條件下，使 1 ）工人加班時間盡量地少； 2 ）工廠獲得最大利潤； 3 ）滿足市場對 1 號品的盡可能多的需求。 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 解 : 為制定下月的生產(chǎn)計劃，設(shè)該廠下月生產(chǎn) i 號品的時間為ix （ ni ,3,2,1 ?? ） 小時 。根據(jù)所給的已知條件，可以把問題中希望追求的三個目標(biāo)用數(shù)量關(guān)系描述如下 1 ）因為下月用 ix 小時 生產(chǎn) i 號品 （ ni ,3,2,1 ?? ），故工廠的生產(chǎn)總工時為 ??niix1小時 ，工人的加班時間為 Txnii ??? 1小時 ，為使工人的加班時間盡量地少，應(yīng)要求 m in1????Txni i2 ）下月該廠 i 號品的產(chǎn)量為 ii xa 噸 ，可獲得 iii xa? 元利潤（ ni ,3,2,1 ?? ），因而工廠總利潤為 ??niiii xa1? 元。為使該廠獲得最大利潤，應(yīng)使 max1???ni iiixa?山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 3 ）下月 1 號品的產(chǎn)量為 11 xa 噸 ，故應(yīng)盡可能多地生產(chǎn) 1 號品，以供市場需求，即 m a x11 ?xa此 外 ， 由 預(yù) 測 得 知 下 月 i 號 品 的 最 大 銷 售 量 為 ib 噸（ ni ,3,2 ?? ），所以 i 號品的產(chǎn)量 ii xa 要不超過 ib ， 即 nibxa iii ,3,2, ???為避免工廠開工不足，生產(chǎn)總工時 ??ni ix1應(yīng)不低于開工能力 T ，即 Txnii ???1山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 當(dāng)然，生產(chǎn)時間應(yīng)為非負，故還有 nix i ,2,1,0 ??? 綜合上面的討論，所考慮的生產(chǎn)計劃問題可歸納為下面具有三個目標(biāo)的最優(yōu)化問題： 1131211m a xm a xm inxafxafTxfniiiinii?????????nixTxnixabiniiiii,2,1,00,3,2,01???????????)(39。max11 Txfnii ??? ??山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 若令Tnxxxx ),(21?? ),)(()(1111xaxaTxxfniiiinii ??????? ? }0,0。,2,0{1?????????xTxnixabxRniiiii? 則上面的最優(yōu)化問題又可化為 )(m ax xfVRx ?? （ VP ） 的形式。這里， x ， )( xf 皆為向量。 1131211m a xm a xm inxafxafTxfniiiinii?????????nixTxnixabiniiiii,2,1,00,3,2,01???????????Vector Optimization 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 例 5 2 投資決策問題。某投資開發(fā)公司擁有總資金 A 萬元，今有 )2( ?n 個項目可供選擇投資。設(shè)投資第 i （ ni ,3,2,1 ?? ）個項目要用資金 ia 萬元，預(yù)計可獲得收益 ib 萬元，問應(yīng)如何決策投資方案。 分析： 一個好的投資方案應(yīng)該是投資 少、收益大的方案。 設(shè) ?ix???個項目決定不投資第個項目決定投資第ii,0,1，（ ni ,3,2,1 ?? ），并稱它們?yōu)橥顿Y決策變量。按問題所給的條件，投資第 i 個項目的金額應(yīng)為ii xa萬元（ ni ,3,2,1 ?? ），因而總投資金額為 ??niii xa1萬元。 為使投資所用的資金盡可能地少，應(yīng)使 m i n1???niii xa山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 為使獲得的收益最大，又應(yīng)要求 m a x1???niii xb由于該公司的總資金為 A萬元，故要有限制條件 Axaniii ???1又因為 ix （ ni ,2,1 ?? ）只能是取 1 或 0 值，所以還要滿足 nixx ii ,1,0)1( ???? 與前面的假設(shè)： xi=0或 1的關(guān)系？ 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 綜上所述，所考慮的投資決策問題可歸為對兩個目標(biāo)中的一個極小化，對另一個極大化的如下問題： nixxxaAxbfxafiiniiiniiiniii,1,0)1(0m a xm i n11211??????????????山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 類似上述要考慮的多目標(biāo)最優(yōu)化問題的例子還可以舉出很多。例如 : 為制定國家的經(jīng)濟發(fā)展規(guī)劃，在一定條件下就需要考慮以生產(chǎn)、消費、就業(yè)、投資回收率等項目的多個目標(biāo)的最優(yōu)化問題； 設(shè)計貨船，人們通常要考慮選取使船舶的試航速率最大，年貨運量最多和運輸成本最低等多個目標(biāo)都盡可能好的方案； 為了編制人才培養(yǎng)計劃，在某些限制條件下亦需同時考慮以各級人員數(shù)額、升調(diào)面比率和工資總額等多個目標(biāo)的最優(yōu)化問題； 為合理地使用醫(yī)院的血庫，也會遇到以血液庫存量、血液平均壽命以及血液收集費用等為目標(biāo)的多個目標(biāo)的最優(yōu)化問題；等等。 這些例子說明，在實際應(yīng)用中，具有多個目標(biāo)的最優(yōu)化問題是廣泛的和大量存在的。 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 在把實際問題建立成多目標(biāo)規(guī)劃模型時，我們應(yīng)注意以下三點： （ 1）決策變量。選擇并確定所考慮的問題的供選方案，并把它們用一組變量表示出來。這些變量取不同的一組值對應(yīng)著問題的一個不同方案。 （ 2）目標(biāo)函數(shù)。按照決策者的意圖，對問題提出期望要極小化或極大化若干個目標(biāo)（指標(biāo)），它們是決策變量的函數(shù)，并且一起組成一個向量目標(biāo)函數(shù)。 （ 3）約束條件。尋找并建立決策變量必需滿足的所有限制條件，并用含有決策變量的不等式或等式表示之。 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 （ 2）基本概念 21)( xxf ?? 22)1()( ??? xxf 圖 5 1 函數(shù)曲線圖 0 1 x 考慮如下的向量函數(shù)： 122 ,))1(,()( Rxxxxf ?????山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 （ 2）基本概念 定義 5 1 設(shè)Tmaaa ),(1?? ，Tmbbb ),(1?? 是 m 維歐氏空間mR 中的兩 個向量。 1 ）若iiba ? （ mi ,2,1 ?? ），則稱向量 a 等于向量 b ，記作 ba ? 。 2 ） 若ia ≤ib （ mi ,2,1 ?? ），則稱向量 a 小于等于向量 b ，記作 a ≦ b 或 b ≧ a 。 3 ）若ia ≤ib （ mi ,2,1 ?? ）并且其中至少有一個是嚴(yán)格不等式，則稱 向量 a 小于向量 b ，記作 a ≤ b 或 b ≥ a 。 4 ）若 ),1( mibaii??? ，則稱向量 a 嚴(yán)格小于向量 b ，記作 ba ? 或 ab ? 。 定義 5 2 設(shè) nRX ? 是模型（ VP ）的約束集合， mRxf ?)( 是（ VP ）的向 量目標(biāo)函數(shù)。若 Xx ?* ，并且不存在 Xx ? 使得 )()( *xfxf ? ，則 稱 *x 是多目標(biāo)規(guī)劃（ VP ）的有效解，也稱做 P ar e t o 解 、 非劣解 或滿意解等。 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 單目標(biāo)規(guī)劃與多目標(biāo)規(guī)劃的區(qū)別 VP：多個目標(biāo)函數(shù) 完成額定的總產(chǎn)值 滿意解 LP：單一目標(biāo)函數(shù) 追求目標(biāo)的極端值 優(yōu)點 缺陷 最優(yōu)解 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 以多目標(biāo)規(guī)劃模型建立目標(biāo)規(guī)劃模型 設(shè)有 m 個目標(biāo)函數(shù)： )2()(,),(),(21?mxfxfxfm? ，對應(yīng)的目標(biāo)值為ooff21, ，omf,? 。為了使各個目標(biāo)函數(shù)都盡可能地達到或接近于它們對應(yīng)的目標(biāo)值，我們考慮 mifxfoii,1,)( ??? 記 ))(,),(()(1xfxfxfm?? ， 則 上 述 在 約 束 條 件 Xx ? 下 考 慮 各),1()( mixfi?? 逼近其對應(yīng)目標(biāo)值oif 的問題可記作 oXxfxfapprV ???)( （ AGP ） 模型（ AG P ）（ App r oxim a te G oal P r og r a mm in g ）稱為逼近目標(biāo)規(guī)劃模型（式中的記號 apprV ? 代表向量逼近的意思）。 山東理工大學(xué)管理學(xué)院 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立 如何來描述向量目標(biāo)函數(shù) )( xf 逼近其對應(yīng)的目標(biāo)值的程度呢？ 需要引入空間 mR 中點 )( xf 和 of 之間的某種距離： ]),([ ofxfD 。由于 )( xf 逼近于 of , 可用它們之間的距離 ]),([ ofxfD 盡可能小來刻劃，因而問題（ A G P ）可歸結(jié)為數(shù)值極小化問題 ]),([m i