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

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

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

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

解：這是一個(gè)單目標(biāo)規(guī)劃問(wèn)題，可用線(xiàn)性規(guī)劃模型表述為：試求獲利最大的方案。第13頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月目標(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頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月在實(shí)際決策時(shí)，還應(yīng)考慮市場(chǎng)等一系列其他條件，如：（1）市場(chǎng)調(diào)查發(fā)現(xiàn)：Ⅰ的銷(xiāo)量有下降趨勢(shì)，故應(yīng)考慮適當(dāng)減少Ⅰ的產(chǎn)量增加Ⅱ的產(chǎn)量，使Ⅰ＜Ⅱ

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

d-

：決策值未達(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時(shí)，目標(biāo)約束與目標(biāo)等價(jià)絕對(duì)約束2x1+x2≤11可以變換為目標(biāo)約束：

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

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

)三種基本形式：目標(biāo)類(lèi)型目標(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+:決策值超過(guò)目標(biāo)值的部分d-

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

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

x2極小化即x1－x2≤

0第20頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月3.充分利用設(shè)備有效臺(tái)時(shí)，不加班x1＋2x2

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

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

P1——不超過(guò)年工資總額60000元；

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

P3——二、三級(jí)的升級(jí)面盡可能達(dá)到現(xiàn)有人 數(shù)的20%接下來(lái)確定模型第26頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月首先給出基本模型：年工資總額不超過(guò)60000元：

2000(10-10*0.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)≤60000即 500x1+500x2+1000x3≤900每級(jí)的人數(shù)不超過(guò)定編規(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頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月一、三級(jí)的升級(jí)面不大于現(xiàn)有人數(shù)的20%，但盡可能多提： 二級(jí)提升、x1

≤12*0.2 即x1

≤2.4

三級(jí)提升、x2

≤15*0.2 即x2

≤3第28頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月

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頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月x1≤2.4x2≤3x1+d5–-d5+＝2.4x2+d6–-d6+＝3D5++d6+極小化目標(biāo)函數(shù)：

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