多目標(biāo)最優(yōu)化

多目標(biāo)最優(yōu)化第1頁，共35頁，2023年，2月20日，星期一本章內(nèi)容主要介紹：如何建立目標(biāo)規(guī)劃模型如何求解單目標(biāo)模型只需簡單確定一個目標(biāo)，而將其余的列為約束；在構(gòu)建多目標(biāo)模型時，則需要對問題有較深的理解，必須考慮更全面——雖然費時較多，卻非常有益，更切合實際。第2頁，共35頁，2023年，2月20日，星期一【例1】某工廠在計劃期內(nèi)要安排生產(chǎn)甲、乙兩種產(chǎn)品。已知制造甲產(chǎn)品需要A型配件5個，B型配件3個；制造乙產(chǎn)品需要A型配件2個，B型配件4個。而在計劃期內(nèi)該工廠只能提供A型配件180個，B型配件135個。又知道該工廠每生產(chǎn)一件甲產(chǎn)品可獲利潤20元，一件乙產(chǎn)品可獲利潤15元。問在計劃期內(nèi)甲、乙產(chǎn)品應(yīng)該各安排生產(chǎn)多少件，才能使總利潤最大?甲乙現(xiàn)有配件A52180B34135利潤（元）2015將該例所述情況列成表格:第3頁，共35頁，2023年，2月20日，星期一設(shè)x1、x2分別表示生產(chǎn)甲、乙產(chǎn)品的件數(shù)，Z表示總利潤，當(dāng)用線性規(guī)劃來描述和解決這個問題時，其數(shù)學(xué)模型為最優(yōu)值：775x1:32 x2:9第4頁，共35頁，2023年，2月20日，星期一但是，如果站在工廠計劃人員的立場上對此進行評價的話，問題就不是這么簡單了。第一，這是一個單目標(biāo)最優(yōu)化問題。但是，一般來說，一個計劃問題要滿足多方面的要求。例如財務(wù)部門利潤目標(biāo)：利潤盡可能大物資部門節(jié)約資金：消耗盡可能小銷售部門適銷對路：產(chǎn)品品種多樣計劃部門安排生產(chǎn)：產(chǎn)品批量盡可能大第5頁，共35頁，2023年，2月20日，星期一一個計劃問題實際上是一個多目標(biāo)決策問題。只是由于需要用線性規(guī)劃來處理，計劃人員才不得不從眾多目標(biāo)要求中硬性選擇其一，作為線性規(guī)劃的目標(biāo)函數(shù)。但這樣做的結(jié)果可能嚴(yán)重違背了某些部門的愿望，因而使生產(chǎn)計劃的實施受到影響；或者在一開始就由于多方面的矛盾而無法從多個目標(biāo)中選出一個目標(biāo)來。第6頁，共35頁，2023年，2月20日，星期一第二，線性規(guī)劃有最優(yōu)解的必要條件是其可行解集非空，即各約束條件彼此相容。但是，實際問題有時不能滿足這樣的要求。例如，由于設(shè)備維修、能源供應(yīng)、其它產(chǎn)品生產(chǎn)需要等原因，計劃期內(nèi)可以提供的設(shè)備工時不能滿足計劃產(chǎn)量工時需要?；蛴捎趦滟Y金的限制，原材料的最大供應(yīng)量不能滿足計劃產(chǎn)量的需要。第7頁，共35頁，2023年，2月20日，星期一第三，線性規(guī)劃解的可行性和最優(yōu)性具有十分明確的意義，但那都是針對特定數(shù)學(xué)模型而言的。 在實際問題中，決策者在作決策時，往往還會對它作某種調(diào)整和修改，其原因可能是由于數(shù)學(xué)模型相對于實際問題的近似性近似性建模時對實際問題的抽象建模時未考慮到的新情況決策者需要計劃人員提供的不是嚴(yán)格的數(shù)學(xué)上的最優(yōu)解，而是可以幫助做出最優(yōu)決策的參考性的計劃，或是提供多種計劃方案。第8頁，共35頁，2023年，2月20日，星期一

1961年，查恩斯(A.Charnes)和庫柏(W.w.CooPer)提出目標(biāo)規(guī)劃(goalprogramming)，得到廣泛重視和較快發(fā)展。目標(biāo)規(guī)劃在處理實際決策問題時，承認各項決策要求(即使是沖突的)的存在有其合理性；在作最終決策時，不強調(diào)其絕對意義上的最優(yōu)性。

因此，目標(biāo)規(guī)劃被認為是一種較之線性規(guī)劃更接近于實際決策過程的決策工具。第9頁，共35頁，2023年，2月20日，星期一求解多目標(biāo)決策常用的三種方法（或思想）：加權(quán)或效用系數(shù)法序列或優(yōu)先級法有效解（非劣解）法加權(quán)法：加權(quán)法把問題中的所有目標(biāo)用統(tǒng)一的單位來度量（例如用錢或效用系數(shù)）這種方法的核心是把多目標(biāo)模型化成單目標(biāo)模型。優(yōu)點：適于計算機求解（例如模型是線性的時候可用一般的單純形法求解）第10頁，共35頁，2023年，2月20日，星期一缺點：難處在于如何尋到合理的權(quán)系數(shù)。序列或優(yōu)先級法：序列或優(yōu)先級法不是對每個目標(biāo)加權(quán)，而是按照目標(biāo)的輕重緩急，將其分為不同等級再求解。優(yōu)點：避免了權(quán)系數(shù)的困擾，絕大多數(shù)決策者都能采用，事實上他們在許多決策中也正是這樣做的。例如建設(shè)高速公路時，既希望減少開支又希望降低交通傷亡事故，此時能否用金錢來衡量一個人的生命價值呢？例如決定人員的提升時，許多單位是按其工作態(tài)度、工作能力及對單位的有效價值等這樣一個先后順序來進行評定的。第11頁，共35頁，2023年，2月20日，星期一即沒有任何其他方案能在各個方面完全勝出這個解缺點：難處在于如何確切地定出各個目標(biāo)的優(yōu)先順序以獲得滿意的求解結(jié)果。有效解（或非劣解）法：有效解（或非劣解）法“不會產(chǎn)生”象加權(quán)法或優(yōu)先級法所具有的局限性，它將找出全部有效解集（即非劣解）以供決策者從中挑選。缺點：難處在于實際問題中非劣解太多，難于一一推薦給決策者。第12頁，共35頁，2023年，2月20日，星期一目標(biāo)規(guī)劃引例：利潤最大化問題某工廠在計劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)如下表所示：ⅠⅡ擁有量原材料kg2111設(shè)備臺時hr1210利潤元/件810

解：這是一個單目標(biāo)規(guī)劃問題，可用線性規(guī)劃模型表述為：試求獲利最大的方案。第13頁，共35頁，2023年，2月20日，星期一目標(biāo)函數(shù) maxz=8x1+10x2

約束條件 2x1+x2≤11

x1+2x2≤10

x1,x2≥0可用圖解法求得最優(yōu)決策方案為：

x1*=4,x2*=3,z*=62 x1+2x2≤108x1+10x2=c6123452468102x1+x2≤11第14頁，共35頁，2023年，2月20日，星期一在實際決策時，還應(yīng)考慮市場等一系列其他條件，如：（1）市場調(diào)查發(fā)現(xiàn)：Ⅰ的銷量有下降趨勢，故應(yīng)考慮適當(dāng)減少Ⅰ的產(chǎn)量增加Ⅱ的產(chǎn)量，使Ⅰ＜Ⅱ

（2）原材料的價格不斷上漲，增加供應(yīng)會使成本提高。故不考慮再購買原材料。（3）為提高效率，應(yīng)充分利用設(shè)備，但不希望加班。（4）市場雖發(fā)生變化，但利潤應(yīng)盡可能達到或超過56元。此時的決策是多目標(biāo)決策問題——目標(biāo)規(guī)劃方法是解決這類決策問題的方法之一。第15頁，共35頁，2023年，2月20日，星期一1.正、負偏差變量d+,d- d+:決策值超過目標(biāo)值的部分

d-

：決策值未達到目標(biāo)值的部分恒有d+×d-=0與建立目標(biāo)規(guī)劃模型有關(guān)的概念例如目標(biāo)z=8x1+10x2≥56

可以變化為目標(biāo)約束：

8x1+10x2+d1--d1+＝56

當(dāng)d1-＝0時，目標(biāo)約束與目標(biāo)等價絕對約束2x1+x2≤11可以變換為目標(biāo)約束：

2x1+x2+d2--d2+＝11

當(dāng)d2+＝0時，目標(biāo)約束與絕對約束等價第16頁，共35頁，2023年，2月20日，星期一硬約束軟約束2.絕對約束、目標(biāo)約束絕對約束：必須嚴(yán)格滿足的等式或不等式約束目標(biāo)約束：目標(biāo)規(guī)劃所特有的約束，約束右端項看作要追求的目標(biāo)值，在達到目標(biāo)值時，允許發(fā)生正或負的偏差例如，原材料的價格不斷上漲，增加供應(yīng)會使成本提高。故不考慮再購買原材料從而2x1+x2≤11是硬約束第17頁，共35頁，2023年，2月20日，星期一3.優(yōu)先因子與權(quán)系數(shù)目標(biāo)規(guī)劃問題常常有多個目標(biāo)，但這些目標(biāo)的主次或輕重緩急是不同的。最重要的目標(biāo)賦予優(yōu)先因子P1，次一級的目標(biāo)賦予優(yōu)先因子P2，…，并規(guī)定Pk>>Pk+1——即表示Pk比Pk+1有更大的優(yōu)先權(quán)。如果要區(qū)別具有相同優(yōu)先因子的兩個目標(biāo)的差別，則分別賦予它們不同的權(quán)系數(shù)wj。第18頁，共35頁，2023年，2月20日，星期一4.目標(biāo)規(guī)劃的目標(biāo)函數(shù)minz=g(d＋,d－

)三種基本形式：目標(biāo)類型目標(biāo)規(guī)劃格式需要極小化的偏差變量fi(x)≤bifi(x)＋d－－d＋＝bid＋fi(x)≥bifi(x)＋d－－d＋＝bid－fi(x)＝bifi(x)＋d－－d＋＝bid－＋d＋d+:決策值超過目標(biāo)值的部分d-

：決策值未達到目標(biāo)值的部分第19頁，共35頁，2023年，2月20日，星期一例2引例的目標(biāo)規(guī)劃模型：2.產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量1.原材料供應(yīng)受嚴(yán)格限制2x1+x2≤11硬約束x1－x2

＋d1－－d1＋＝0d1＋x1≤

x2極小化即x1－x2≤

0第20頁，共35頁，2023年，2月20日，星期一3.充分利用設(shè)備有效臺時，不加班x1＋2x2

＋d2－－d2＋＝10d2－＋d2＋x1＋2x2

＝10極小化4.利潤額不小于56元8x1＋10x2＋d3－－d3＋＝56d3－8x1＋10x2≥56極小化第21頁，共35頁，2023年，2月20日，星期一第22頁，共35頁，2023年，2月20日，星期一建模步驟小結(jié)：建立基礎(chǔ)模型為每一個理想目標(biāo)確定期望值對每一個現(xiàn)實目標(biāo)和約束都加上正負偏差變量將目標(biāo)按其重要性劃分優(yōu)先級，第一優(yōu)先級為硬約束建立目標(biāo)規(guī)劃函數(shù)反映決策者欲望，如“利潤最大”配上期望值的理想目標(biāo)第23頁，共35頁，2023年，2月20日，星期一例3： 某單位領(lǐng)導(dǎo)在考慮本單位職工的升級調(diào)資方案時，依次遵守以下規(guī)定：不超過年工資總額60000元每級的人數(shù)不超過定編規(guī)定的人數(shù)二、三級升級面盡可能達到但不超過現(xiàn)有人數(shù)的20%三級不足編制的人數(shù)可錄用新職工，又一級的職工中又10%要退休試據(jù)下表數(shù)據(jù)建立模型第24頁，共35頁，2023年，2月20日，星期一等級工資額(元/年)現(xiàn)有人數(shù)編制人數(shù)一20001012二15001215三10001515合計3742第25頁，共35頁，2023年，2月20日，星期一參考模型如下：設(shè)x1、x2、x3分別表示提升到一、二級和錄用到三級的新職工人數(shù)。各目標(biāo)確定的優(yōu)先因子為：

P1——不超過年工資總額60000元；

P2——每級的人數(shù)不超過定編制規(guī)定的人數(shù)

P3——二、三級的升級面盡可能達到現(xiàn)有人 數(shù)的20%接下來確定模型第26頁，共35頁，2023年，2月20日，星期一首先給出基本模型：年工資總額不超過60000元：

2000(10-10*0.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)≤60000即 500x1+500x2+1000x3≤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頁，2023年，2月20日，星期一一、三級的升級面不大于現(xiàn)有人數(shù)的20%，但盡可能多提： 二級提升、x1

≤12*0.2 即x1

≤2.4

三級提升、x2

≤15*0.2 即x2

≤3第28頁，共35頁，2023年，2月20日，星期一

x1

≤3

x2-x1

≤3

x3-x2

≤0

x1+d2–-d2+＝3

x2-x1+d3–-d3+＝3

x3-x2+d4–-d4+＝0轉(zhuǎn)化為目標(biāo)規(guī)劃模型500x1+500x2+1000x3≤900500x1+500x2+1000x3

+d1–-d1+＝900d1+極小化d2++d3++d4+極小化第29頁，共35頁，2023年，2月20日，星期一x1≤2.4x2

≤3x1+d5–-d5+＝2.4x2+d6–-d6+＝3D5++d6+極小化目標(biāo)函數(shù)：

minz=P1d1++P2(d2++d3++d4+)+P3(d5++d6+