1、多目標(biāo)最優(yōu)化 第1頁(yè)，共35頁(yè)，2022年，5月20日，14點(diǎn)10分，星期二本章內(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è)，2022年，5月20日，14點(diǎn)10分，星期二【例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)品可

2、獲利潤(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è)，2022年，5月20日，14點(diǎn)10分，星期二 設(shè)x1、x2分別表示生產(chǎn)甲、乙產(chǎn)品的件數(shù)，Z表示總利潤(rùn)，當(dāng)用線性規(guī)劃來(lái)描述和解決這個(gè)問(wèn)題時(shí)，其數(shù)學(xué)模型為 最優(yōu)值：775 x1: 32x2: 9第4頁(yè)，共35頁(yè)，2022年，5月20日，14點(diǎn)10分，星期二 但是，如果站在工廠計(jì)劃人員的立場(chǎng)上對(duì)此進(jìn)行評(píng)價(jià)的話，問(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)利

3、潤(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è)，2022年，5月20日，14點(diǎn)10分，星期二 一個(gè)計(jì)劃問(wèn)題實(shí)際上是一個(gè)多目標(biāo)決策問(wèn)題。只是由于需要用線性規(guī)劃來(lái)處理，計(jì)劃人員才不得不從眾多目標(biāo)要求中硬性選擇其一，作為線性規(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è)，2022年，5月20日，14點(diǎn)10分，星期二第二，線性規(guī)劃有最優(yōu)解的必要條件是其可行解集非空，即各約束條件彼此相容。但是，

4、實(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è)，2022年，5月20日，14點(diǎn)10分，星期二第三，線性規(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)決策的參考

5、性的計(jì)劃，或是提供多種計(jì)劃方案。第8頁(yè)，共35頁(yè)，2022年，5月20日，14點(diǎn)10分，星期二 1961年，查恩斯(A.Charnes)和庫(kù)柏(W.w.CooPer)提出目標(biāo)規(guī)劃(goal programming)，得到廣泛重視和較快發(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)為是一種較之線性規(guī)劃更接近于實(shí)際決策過(guò)程的決策工具 。第9頁(yè)，共35頁(yè)，2022年，5月20日，14點(diǎn)10分，星期二求解多目標(biāo)決策常用的三種方法（或思想）：加權(quán)或效用系數(shù)法序列或優(yōu)先級(jí)法有效解（非劣解）法加權(quán)法：加

6、權(quán)法把問(wèn)題中的所有目標(biāo)用統(tǒng)一的單位來(lái)度量（例如用錢(qián)或效用系數(shù)） 這種方法的核心是把多目標(biāo)模型化成單目標(biāo)模型。優(yōu)點(diǎn)：適于計(jì)算機(jī)求解（例如模型是線性的時(shí)候可用一般的單純形法求解）第10頁(yè)，共35頁(yè)，2022年，5月20日，14點(diǎn)10分，星期二 缺點(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í)，許多單位是按其工

7、作態(tài)度、工作能力及對(duì)單位的有效價(jià)值等這樣一個(gè)先后順序來(lái)進(jìn)行評(píng)定的。第11頁(yè)，共35頁(yè)，2022年，5月20日，14點(diǎn)10分，星期二即沒(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è)，2022年，5月20日，14點(diǎn)10分，星期二目標(biāo)規(guī)劃引例： 利潤(rùn)最大化問(wèn)題某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)、 兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)如下表所示

8、：擁有量原材料 kg2111設(shè)備臺(tái)時(shí) hr1210利潤(rùn) 元/件810 解：這是一個(gè)單目標(biāo)規(guī)劃問(wèn)題，可用線性規(guī)劃模型表述為：試求獲利最大的方案。第13頁(yè)，共35頁(yè)，2022年，5月20日，14點(diǎn)10分，星期二目標(biāo)函數(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頁(yè)，共35頁(yè)，2022年，5月20日，14點(diǎn)10分，星期二 在實(shí)際決策時(shí)，還應(yīng)考慮市場(chǎng)等一系列其他條件，如：（

9、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è)，2022年，5月20日，14點(diǎn)10分，星期二1. 正、負(fù)偏差變量d+,d- d+ : 決策值超過(guò)目標(biāo)值的部分 d- ：決策值未達(dá)到目標(biāo)值的部分 恒有 d+d-=0與建立目標(biāo)規(guī)劃模型有關(guān)的概念例如目標(biāo) z = 8x1+10 x2 56 可以變化為目標(biāo)約束： 8

10、x1+10 x2+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è)，2022年，5月20日，14點(diǎn)10分，星期二硬約束軟約束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è)，2022年，5月20日，14點(diǎn)

11、10分，星期二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ī)定PkPk+1即表示Pk比Pk+1有更大的優(yōu)先權(quán)。 如果要區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，則分別賦予它們不同的權(quán)系數(shù)wj。第18頁(yè)，共35頁(yè)，2022年，5月20日，14點(diǎn)10分，星期二4 .目標(biāo)規(guī)劃的目標(biāo)函數(shù) min z = g ( d, d )三種基本形式：目標(biāo)類(lèi)型目標(biāo)規(guī)劃格式需要極小化的偏差變量fi(x) bifi(x) dd bidfi(x) bifi(x) dd bidfi(x) bifi(x) dd bidd

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

13、頁(yè)，共35頁(yè)，2022年，5月20日，14點(diǎn)10分，星期二建模步驟小結(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è)，2022年，5月20日，14點(diǎn)10分，星期二例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è)

14、，2022年，5月20日，14點(diǎn)10分，星期二等級(jí)工資額(元/年)現(xiàn)有人數(shù)編制人數(shù)一20001012二15001215三10001515合計(jì)3742第25頁(yè)，共35頁(yè)，2022年，5月20日，14點(diǎn)10分，星期二參考模型如下：設(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è)，2022年，5月20日，14點(diǎn)10分，星期二首先給出基本模型：年工資總額不超過(guò)60000元： 2000 ( 10-10*0.1+

15、x1 ) + 1500 ( 12-x1+x2 ) + 1000 ( 15-x2+x3 ) 60000即 500 x1+500 x2+1000 x3 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è)，2022年，5月20日，14點(diǎn)10分，星期二一、三級(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è)，2022年，5月20日，14

16、點(diǎn)10分，星期二 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ī)劃模型500 x1+500 x2+1000 x3 900500 x1+500 x2+1000 x3 + d1 -d1+900d1+極小化d2+ + d3+ + d4+極小化第29頁(yè)，共35頁(yè)，2022年，5月20日，14點(diǎn)10分，星期二x1 2.4x2 3x1 + d5 -d5+ 2.4x2 + d6 -d6+ 3D5+ + d6+極小化目標(biāo)函數(shù)： min z = P1 d1+ + P2( d2+ + d3+

17、 + d4+ )+ P3( d5+ + d6+ )第30頁(yè)，共35頁(yè)，2022年，5月20日，14點(diǎn)10分，星期二目標(biāo)規(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頁(yè)，共35頁(yè)，2022年，5月20日，14點(diǎn)10分，星期二三、目標(biāo)規(guī)劃的求解主要思想：化成單目標(biāo)問(wèn)題，多階