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