多目標最優(yōu)化

1、多目標最優(yōu)化 第1頁，共35頁，2022年，5月20日，14點10分，星期二本章內容主要介紹：如何建立目標規(guī)劃模型如何求解 單目標模型只需簡單確定一個目標，而將其余的列為約束； 在構建多目標模型時，則需要對問題有較深的理解，必須考慮更全面雖然費時較多，卻非常有益，更切合實際。第2頁，共35頁，2022年，5月20日，14點10分，星期二【例1】某工廠在計劃期內要安排生產甲、乙兩種產品。已知制造甲產品需要A型配件5個，B型配件3個； 制造乙產品需要A型配件2個，B型配件4個。 而在計劃期內該工廠只能提供A型配件180個，B型配件135個。 又知道該工廠每生產一件甲產品可獲利潤20元，一件乙產品可

2、獲利潤15元。問在計劃期內甲、乙產品應該各安排生產多少件，才能使總利潤最大? 甲乙現(xiàn)有配件A52180B34135利潤（元）2015 將該例所述情況列成表格:第3頁，共35頁，2022年，5月20日，14點10分，星期二 設x1、x2分別表示生產甲、乙產品的件數(shù)，Z表示總利潤，當用線性規(guī)劃來描述和解決這個問題時，其數(shù)學模型為 最優(yōu)值：775 x1: 32x2: 9第4頁，共35頁，2022年，5月20日，14點10分，星期二 但是，如果站在工廠計劃人員的立場上對此進行評價的話，問題就不是這么簡單了。 第一，這是一個單目標最優(yōu)化問題。但是，一般來說，一個計劃問題要滿足多方面的要求。例如財務部門利

3、潤目標：利潤盡可能大物資部門節(jié)約資金：消耗盡可能小銷售部門適銷對路：產品品種多樣計劃部門安排生產：產品批量盡可能大第5頁，共35頁，2022年，5月20日，14點10分，星期二 一個計劃問題實際上是一個多目標決策問題。只是由于需要用線性規(guī)劃來處理，計劃人員才不得不從眾多目標要求中硬性選擇其一，作為線性規(guī)劃的目標函數(shù) 。 但這樣做的結果可能嚴重違背了某些部門的愿望，因而使生產計劃的實施受到影響；或者在一開始就由于多方面的矛盾而無法從多個目標中選出一個目標來。第6頁，共35頁，2022年，5月20日，14點10分，星期二第二，線性規(guī)劃有最優(yōu)解的必要條件是其可行解集非空，即各約束條件彼此相容。但是，

4、實際問題有時不能滿足這樣的要求 。例如，由于設備維修、能源供應、其它產品生產需要等原因，計劃期內可以提供的設備工時不能滿足計劃產量工時需要 。 或由于儲備資金的限制，原材料的最大供應量不能滿足計劃產量的需要 。第7頁，共35頁，2022年，5月20日，14點10分，星期二第三，線性規(guī)劃解的可行性和最優(yōu)性具有十分明確的意義，但那都是針對特定數(shù)學模型而言的。在實際問題中，決策者在作決策時，往往還會對它作某種調整和修改，其原因可能是由于數(shù)學模型相對于實際問題的近似性 近似性建模時對實際問題的抽象 建模時未考慮到的新情況 決策者需要計劃人員提供的不是嚴格的數(shù)學上的最優(yōu)解，而是可以幫助做出最優(yōu)決策的參考

5、性的計劃，或是提供多種計劃方案。第8頁，共35頁，2022年，5月20日，14點10分，星期二 1961年，查恩斯(A.Charnes)和庫柏(W.w.CooPer)提出目標規(guī)劃(goal programming)，得到廣泛重視和較快發(fā)展。 目標規(guī)劃在處理實際決策問題時，承認各項決策要求(即使是沖突的)的存在有其合理性；在作最終決策時，不強調其絕對意義上的最優(yōu)性。 因此，目標規(guī)劃被認為是一種較之線性規(guī)劃更接近于實際決策過程的決策工具 。第9頁，共35頁，2022年，5月20日，14點10分，星期二求解多目標決策常用的三種方法（或思想）：加權或效用系數(shù)法序列或優(yōu)先級法有效解（非劣解）法加權法：加

6、權法把問題中的所有目標用統(tǒng)一的單位來度量（例如用錢或效用系數(shù)） 這種方法的核心是把多目標模型化成單目標模型。優(yōu)點：適于計算機求解（例如模型是線性的時候可用一般的單純形法求解）第10頁，共35頁，2022年，5月20日，14點10分，星期二 缺點：難處在于如何尋到合理的權系數(shù)。序列或優(yōu)先級法：序列或優(yōu)先級法不是對每個目標加權，而是按照目標的輕重緩急，將其分為不同等級再求解。優(yōu)點：避免了權系數(shù)的困擾，絕大多數(shù)決策者都能采用，事實上他們在許多決策中也正是這樣做的。 例如建設高速公路時，既希望減少開支又希望降低交通傷亡事故，此時能否用金錢來衡量一個人的生命價值呢？例如決定人員的提升時，許多單位是按其工

7、作態(tài)度、工作能力及對單位的有效價值等這樣一個先后順序來進行評定的。第11頁，共35頁，2022年，5月20日，14點10分，星期二即沒有任何其他方案能在各個方面完全勝出這個解 缺點：難處在于如何確切地定出各個目標的優(yōu)先順序以獲得滿意的求解結果。有效解（或非劣解）法：有效解（或非劣解）法“不會產生”象加權法或優(yōu)先級法所具有的局限性，它將找出全部有效解集（即非劣解）以供決策者從中挑選。 缺點：難處在于實際問題中非劣解太多，難于一一推薦給決策者。第12頁，共35頁，2022年，5月20日，14點10分，星期二目標規(guī)劃引例： 利潤最大化問題某工廠在計劃期內要安排生產、 兩種產品，已知有關數(shù)據(jù)如下表所示

8、：擁有量原材料 kg2111設備臺時 hr1210利潤 元/件810 解：這是一個單目標規(guī)劃問題，可用線性規(guī)劃模型表述為：試求獲利最大的方案。第13頁，共35頁，2022年，5月20日，14點10分，星期二目標函數(shù)max z = 8x1+10 x2 約束條件2x1 + x2 11 x1 + 2x2 10 x1 , x2 0可用圖解法求得最優(yōu)決策方案為： x1*=4, x2*=3, z*=62x1 + 2x2 108x1+10 x2=c6123452468102x1 + x2 11第14頁，共35頁，2022年，5月20日，14點10分，星期二 在實際決策時，還應考慮市場等一系列其他條件，如：（

9、1）市場調查發(fā)現(xiàn)：的銷量有下降趨勢，故應考慮適當減少的產量增加的產量，使 （2）原材料的價格不斷上漲，增加供應會使成本提高。故不考慮再購買原材料。 （3）為提高效率，應充分利用設備，但不希望加班。 （4）市場雖發(fā)生變化，但利潤應盡可能達到或超過56元。 此時的決策是多目標決策問題目標規(guī)劃方法是解決這類決策問題的方法之一。第15頁，共35頁，2022年，5月20日，14點10分，星期二1. 正、負偏差變量d+,d- d+ : 決策值超過目標值的部分 d- ：決策值未達到目標值的部分 恒有 d+d-=0與建立目標規(guī)劃模型有關的概念例如目標 z = 8x1+10 x2 56 可以變化為目標約束： 8

10、x1+10 x2+d1-d1+56當d1 - 0時，目標約束與目標等價絕對約束 2x1 + x2 11 可以變換為目標約束： 2x1 + x2 +d2-d2+11當d2+0時，目標約束與絕對約束等價第16頁，共35頁，2022年，5月20日，14點10分，星期二硬約束軟約束2 . 絕對約束、目標約束絕對約束：必須嚴格滿足的等式或不等式約束目標約束：目標規(guī)劃所特有的約束，約束右端項看作要追求的目標值，在達到目標值時，允許發(fā)生正或負的偏差 例如，原材料的價格不斷上漲，增加供應會使成本提高。故不考慮再購買原材料 從而 2x1 + x2 11 是硬約束第17頁，共35頁，2022年，5月20日，14點

11、10分，星期二3 . 優(yōu)先因子與權系數(shù) 目標規(guī)劃問題常常有多個目標，但這些目標的主次或輕重緩急是不同的。 最重要的目標賦予優(yōu)先因子P1，次一級的目標賦予優(yōu)先因子P2，并規(guī)定PkPk+1即表示Pk比Pk+1有更大的優(yōu)先權。 如果要區(qū)別具有相同優(yōu)先因子的兩個目標的差別，則分別賦予它們不同的權系數(shù)wj。第18頁，共35頁，2022年，5月20日，14點10分，星期二4 .目標規(guī)劃的目標函數(shù) min z = g ( d, d )三種基本形式：目標類型目標規(guī)劃格式需要極小化的偏差變量fi(x) bifi(x) dd bidfi(x) bifi(x) dd bidfi(x) bifi(x) dd bidd

12、d+ : 決策值超過目標值的部分d- ：決策值未達到目標值的部分第19頁，共35頁，2022年，5月20日，14點10分，星期二例2 引例的目標規(guī)劃模型：2.產品的產量不低于產品的產量1.原材料供應受嚴格限制2x1 + x2 11硬約束x1x2 d1d1 0d1x1 x2極小化即x1 x2 0第20頁，共35頁，2022年，5月20日，14點10分，星期二3.充分利用設備有效臺時，不加班x12x2 d2d2 10d2d2x12x2 10極小化4.利潤額不小于56元8x110 x2d3d3 56d38x110 x2 56極小化第21頁，共35頁，2022年，5月20日，14點10分，星期二第22

13、頁，共35頁，2022年，5月20日，14點10分，星期二建模步驟小結：建立基礎模型為每一個理想目標確定期望值對每一個現(xiàn)實目標和約束都加上正負偏差變量將目標按其重要性劃分優(yōu)先級，第一優(yōu)先級為硬約束建立目標規(guī)劃函數(shù)反映決策者欲望，如“利潤最大”配上期望值的理想目標第23頁，共35頁，2022年，5月20日，14點10分，星期二例3：某單位領導在考慮本單位職工的升級調資方案時，依次遵守以下規(guī)定：不超過年工資總額60000元每級的人數(shù)不超過定編規(guī)定的人數(shù)二、三級升級面盡可能達到但不超過現(xiàn)有人數(shù)的20%三級不足編制的人數(shù)可錄用新職工，又一級的職工中又10%要退休 試據(jù)下表數(shù)據(jù)建立模型第24頁，共35頁

14、，2022年，5月20日，14點10分，星期二等級工資額(元/年)現(xiàn)有人數(shù)編制人數(shù)一20001012二15001215三10001515合計3742第25頁，共35頁，2022年，5月20日，14點10分，星期二參考模型如下：設x1、x2、x3分別表示提升到一、二級和錄用到三級的新職工人數(shù)。各目標確定的優(yōu)先因子為： P1不超過年工資總額60000元； P2每級的人數(shù)不超過定編制規(guī)定的人數(shù) P3二、三級的升級面盡可能達到現(xiàn)有人數(shù)的20%接下來確定模型第26頁，共35頁，2022年，5月20日，14點10分，星期二首先給出基本模型：年工資總額不超過60000元： 2000 ( 10-10*0.1+

15、x1 ) + 1500 ( 12-x1+x2 ) + 1000 ( 15-x2+x3 ) 60000即 500 x1+500 x2+1000 x3 900每級的人數(shù)不超過定編規(guī)定的人數(shù)： 10 - 10*0.1 + x1 12即 x1 3 12 - x1 + x2 15即 x2 - x1 3 15 - x2 + x3 15即 x3 - x2 0第27頁，共35頁，2022年，5月20日，14點10分，星期二一、三級的升級面不大于現(xiàn)有人數(shù)的20%，但盡可能多提：二級提升、 x1 12*0.2即 x1 2.4三級提升、 x2 15*0.2即 x2 3第28頁，共35頁，2022年，5月20日，14

16、點10分，星期二 x1 3 x2 - x1 3 x3 - x2 0 x1 + d2 -d2+ 3 x2 - x1 + d3 -d3+ 3 x3 - x2 + d4 -d4+ 0轉化為目標規(guī)劃模型500 x1+500 x2+1000 x3 900500 x1+500 x2+1000 x3 + d1 -d1+900d1+極小化d2+ + d3+ + d4+極小化第29頁，共35頁，2022年，5月20日，14點10分，星期二x1 2.4x2 3x1 + d5 -d5+ 2.4x2 + d6 -d6+ 3D5+ + d6+極小化目標函數(shù)： min z = P1 d1+ + P2( d2+ + d3+

17、 + d4+ )+ P3( d5+ + d6+ )第30頁，共35頁，2022年，5月20日，14點10分，星期二目標規(guī)劃模型為：min z = P1 d1+ + P2( d2+ + d3+ + d4+ )+ P3( d5- + d6- )s.t.500 x1+500 x2+1000 x3 + d1 -d1+900 x1 + d2 -d2+ 3 x2 - x1 + d3 -d3+ 3 x3 - x2 + d4 -d4+ 0 x1 + d5 -d5+ 2.4x2 + d6 -d6+ 3第31頁，共35頁，2022年，5月20日，14點10分，星期二三、目標規(guī)劃的求解主要思想：化成單目標問題，多階