多目標(biāo)規(guī)劃模型

關(guān)于多目標(biāo)規(guī)劃模型第一頁(yè)，共三十一頁(yè)，2022年，8月28日多目標(biāo)決策由于考慮的目標(biāo)多,有些目標(biāo)之間又彼此有矛盾,這就使多目標(biāo)問(wèn)題成為一個(gè)復(fù)雜而困難的問(wèn)題.但由于客觀實(shí)際的需要,多目標(biāo)決策問(wèn)題越來(lái)越受到重視,因而出現(xiàn)了許多解決此決策問(wèn)題的方法.一般來(lái)說(shuō),其基本途徑是,把求解多目標(biāo)問(wèn)題轉(zhuǎn)化為求解單目標(biāo)問(wèn)題.其主要步驟是,先轉(zhuǎn)化為單目標(biāo)問(wèn)題,然后利用單目標(biāo)模型的方法,求出單目標(biāo)模型的最優(yōu)解,以此作為多目標(biāo)問(wèn)題的解.化多目標(biāo)問(wèn)題為單目標(biāo)問(wèn)題的方法大致可分為兩類,一類是轉(zhuǎn)化為一個(gè)單目標(biāo)問(wèn)題,另一類是轉(zhuǎn)化為多個(gè)單目標(biāo)問(wèn)題,關(guān)鍵是如何轉(zhuǎn)化.下面,我們介紹幾種主要的轉(zhuǎn)化方法:主要目標(biāo)法、線性加權(quán)和法、字典序法、步驟法。第二頁(yè)，共三十一頁(yè)，2022年，8月28日f(shuō)1f212345678§10.1多目標(biāo)決策問(wèn)題的特征在解決單目標(biāo)問(wèn)題時(shí)，我們的任務(wù)是選擇一個(gè)或一組變量X，使目標(biāo)函數(shù)f(X)取得最大（或最?。?。對(duì)于任意兩方案所對(duì)應(yīng)的解，只要比較它們相應(yīng)的目標(biāo)值，就可以判斷誰(shuí)優(yōu)誰(shuí)劣。但在多目標(biāo)情況下，問(wèn)題卻不那么單純了。例如，有兩個(gè)目標(biāo)f1(X)，f2(X),希望它們都越大越好。下圖列出在這兩個(gè)目標(biāo)下共有8個(gè)解的方案。其中方案1，2，3，4稱為劣解，因?yàn)樗鼈冊(cè)趦蓚€(gè)目標(biāo)值上都比方案5差，是可以淘汰的解。而方案5，6，7，8是非劣解（或稱為有效解，滿意解），因?yàn)檫@些解都不能輕易被淘汰掉，它們中間的一個(gè)與其余任何一個(gè)相比，總有一個(gè)指標(biāo)更優(yōu)越，而另一個(gè)指標(biāo)卻更差。一、解的特點(diǎn)第三頁(yè)，共三十一頁(yè)，2022年，8月28日二、模型結(jié)構(gòu)多目標(biāo)決策問(wèn)題包含有三大要素：目標(biāo)、方案和決策者。在多目標(biāo)決策問(wèn)題中，目標(biāo)有多層次的含義。從最高層次來(lái)看，目標(biāo)代表了問(wèn)題要達(dá)到的總目標(biāo)。如確定最滿意的投資項(xiàng)目、選擇最滿意的食品。從較低層次來(lái)看，目標(biāo)可看成是體現(xiàn)總目標(biāo)得以實(shí)現(xiàn)的各個(gè)具體的目標(biāo)，如投資項(xiàng)目的盈利要大、成本要低、風(fēng)險(xiǎn)要小；目標(biāo)也可看成衡量總目標(biāo)得以實(shí)現(xiàn)的各個(gè)準(zhǔn)則，如食品的味道要好，質(zhì)量要好，花費(fèi)要少。多目標(biāo)決策問(wèn)題中的方案即為決策變量，也稱為多目標(biāo)問(wèn)題的解。備選方案即決策問(wèn)題的可行解。在多目標(biāo)決策中，有些問(wèn)題的方案是有限的，有些問(wèn)題的方案是無(wú)限的。方案有其特征或特性，稱之為屬性。第四頁(yè)，共三十一頁(yè)，2022年，8月28日1、多目標(biāo)規(guī)劃問(wèn)題的模型結(jié)構(gòu)為決策變量如對(duì)于求極大(max)型，其各種解定義如下：絕對(duì)最優(yōu)解：若對(duì)于任意的X，都有F（X*）≥F(X)有效解：若不存在X，使得F（X*）≤F(X)弱有效解：若不存在X，使得F（X*)<F(X)第五頁(yè)，共三十一頁(yè)，2022年，8月28日第六頁(yè)，共三十一頁(yè)，2022年，8月28日第七頁(yè)，共三十一頁(yè)，2022年，8月28日§10.2多目標(biāo)規(guī)劃問(wèn)題的求解1、主要目標(biāo)法在有些多目標(biāo)決策問(wèn)題中，各種目標(biāo)的重要性程度往往不一樣。其中一個(gè)重要性程度最高和最為關(guān)鍵的目標(biāo)，稱之為主要目標(biāo)法。其余的目標(biāo)則稱為非主要目標(biāo)。例如，在上述多目標(biāo)問(wèn)題中，假定f1(X)為主要目標(biāo)，其余p-1個(gè)為非主要目標(biāo)。這時(shí)，希望主要目標(biāo)達(dá)到極大值，并要求其余的目標(biāo)滿足一定的條件，即第八頁(yè)，共三十一頁(yè)，2022年，8月28日例題1某工廠在一個(gè)計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，各產(chǎn)品都要消耗A，B，C三種不同的資源。每件產(chǎn)品對(duì)資源的單位消耗、各種資源的限量以及各產(chǎn)品的單位價(jià)格、單位利潤(rùn)和所造成的單位污染如下表。假定產(chǎn)品能全部銷售出去，問(wèn)每期怎樣安排生產(chǎn)，才能使利潤(rùn)和產(chǎn)值都最大，且造成的污染最??？甲乙資源限量資源A單位消耗資源B單位消耗資源C單位消耗9434510240200300單位產(chǎn)品的價(jià)格400600單位產(chǎn)品的利潤(rùn)70120單位產(chǎn)品的污染32第九頁(yè)，共三十一頁(yè)，2022年，8月28日解：?jiǎn)栴}的多目標(biāo)模型如下對(duì)于上述模型的三個(gè)目標(biāo)，工廠確定利潤(rùn)最大為主要目標(biāo)。另兩個(gè)目標(biāo)則通過(guò)預(yù)測(cè)預(yù)先給定的希望達(dá)到的目標(biāo)值轉(zhuǎn)化為約束條件。經(jīng)研究，工廠認(rèn)為總產(chǎn)值至少應(yīng)達(dá)到20000個(gè)單位，而污染控制在90個(gè)單位以下，即由主要目標(biāo)法化為單目標(biāo)問(wèn)題用單純形法求得其最優(yōu)解為第十頁(yè)，共三十一頁(yè)，2022年，8月28日2、線性加權(quán)和目標(biāo)規(guī)劃在上述目標(biāo)規(guī)劃中，假定f1(X),f2(X),…,fp(X)具有相同的量綱,按照一定的規(guī)則分別給fi賦予相同的權(quán)系數(shù)ωi，作線性加權(quán)和評(píng)價(jià)函數(shù)則多目標(biāo)問(wèn)題化為如下的單目標(biāo)問(wèn)題第十一頁(yè)，共三十一頁(yè)，2022年，8月28日例如，某公司計(jì)劃購(gòu)進(jìn)一批新卡車，可供選擇的卡車有如下4種類型：A1，A2，A3，A4?，F(xiàn)考慮6個(gè)方案屬性：維修期限f1，每100升汽油所跑的里數(shù)f2，最大載重噸數(shù)f3，價(jià)格（萬(wàn)元）f4，可靠性f5，靈敏性f6。這4種型號(hào)的卡車分別關(guān)于目標(biāo)屬性的指標(biāo)值fij如下表所示。fijf1f2f3f4f5f6A12.01500455一般高A22.527003.665低一般A32.020004.245高很高A42.21800450很高一般首先對(duì)不同度量單位和不同數(shù)量級(jí)的指標(biāo)值進(jìn)行標(biāo)準(zhǔn)化處理。先將定性指標(biāo)定量化：第十二頁(yè)，共三十一頁(yè)，2022年，8月28日效益型指標(biāo)很低低一般高很高13579很高高一般低很低成本型指標(biāo)可靠性和靈敏性都屬于效益型指標(biāo)，其打分如下可靠性一般低高很高5379靈敏性高一般很高一般7595按以下公式作無(wú)量綱的標(biāo)準(zhǔn)化處理其中：第十三頁(yè)，共三十一頁(yè)，2022年，8月28日變換后的指標(biāo)值矩陣為：aijf1f2f3f4f5f6A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.751001設(shè)權(quán)系數(shù)向量為W=（0.2,0.1,0.1,0.1,0.2,0.3),則故最優(yōu)方案為選購(gòu)A3型卡車第十四頁(yè)，共三十一頁(yè)，2022年，8月28日3、分層序列法：1.基本步驟：把(VP)中的p個(gè)目標(biāo)按其重要程度排序。依次求單目標(biāo)規(guī)劃的最優(yōu)解。2.過(guò)程：無(wú)妨設(shè)其次序?yàn)橄惹蠼獾米顑?yōu)值，記再解得最優(yōu)值，依次進(jìn)行，直到得最優(yōu)值則是在分層序列意義下的最優(yōu)解集合。第十五頁(yè)，共三十一頁(yè)，2022年，8月28日3.性質(zhì)：，即在分層序列意義下的最優(yōu)解是有效解。證明：反證。設(shè)，但，則必存在使即至少有一個(gè)j0

，使,由于，即，矛盾。得證。4.進(jìn)一步討論：上述方法過(guò)程中，當(dāng)某個(gè)問(wèn)題(Pj)的解唯一時(shí)，則問(wèn)題的求解無(wú)意義，因?yàn)榻舛际俏ㄒ坏摹?shí)際求解時(shí)，有較寬容意義下的分層序列法：取為預(yù)先給定的寬容值，整個(gè)解法同原方法類似，只是取各約束集合時(shí)，分別取為：第十六頁(yè)，共三十一頁(yè)，2022年，8月28日目標(biāo)規(guī)劃模型線性規(guī)劃問(wèn)題都是處理單個(gè)目標(biāo)的情況，但是在現(xiàn)實(shí)世界中有許多問(wèn)題具有多個(gè)目標(biāo)，這些目標(biāo)的重要性各不相同，往往有不同的量綱，有的目標(biāo)相互依賴，例如決策者既希望實(shí)現(xiàn)利潤(rùn)最大，又希望實(shí)現(xiàn)產(chǎn)值最大；有的相互抵觸，如決策者既希望充分利用資源，又不希望超越資源限量。而決策者希望在某些限制條件下，依次實(shí)現(xiàn)這些目標(biāo)。這就是目標(biāo)規(guī)劃所要解決的問(wèn)題。當(dāng)所有的目標(biāo)函數(shù)和約束條件都是線性時(shí)，我們稱其為線性目標(biāo)規(guī)劃問(wèn)題。在這里我們主要討論線性目標(biāo)規(guī)劃問(wèn)題。一、目標(biāo)規(guī)劃模型的建立

第十七頁(yè)，共三十一頁(yè)，2022年，8月28日引例1：對(duì)于生產(chǎn)計(jì)劃問(wèn)題：

甲乙資源限額材料2324工時(shí)3226單位利潤(rùn)43

現(xiàn)在工廠領(lǐng)導(dǎo)要考慮市場(chǎng)等一系列其他因素，提出如下目標(biāo)：（1）根據(jù)市場(chǎng)信息，甲產(chǎn)品的銷量有下降的趨勢(shì)，而乙產(chǎn)品的銷量有上升的趨勢(shì)，故考慮乙產(chǎn)品的產(chǎn)量應(yīng)大于甲產(chǎn)品的產(chǎn)量。（2）盡可能充分利用工時(shí)，不希望加班。（3）應(yīng)盡可能達(dá)到并超過(guò)計(jì)劃利潤(rùn)30元。現(xiàn)在的問(wèn)題是：在原材料不能超計(jì)劃使用的前提下，如何安排生產(chǎn)才能使上述目標(biāo)依次實(shí)現(xiàn)？第十八頁(yè)，共三十一頁(yè)，2022年，8月28日解：（1）決策變量：仍設(shè)每天生產(chǎn)甲、乙兩種產(chǎn)品各為x1和x2

偏差變量：對(duì)于每一目標(biāo)，我們引進(jìn)正、負(fù)偏差變量。如對(duì)于目標(biāo)1，設(shè)d1-表示乙產(chǎn)品的產(chǎn)量低于甲產(chǎn)品產(chǎn)量的數(shù)，d1+表示乙產(chǎn)品的產(chǎn)量高于甲產(chǎn)品產(chǎn)量的數(shù)。稱它們分別為產(chǎn)量比較的負(fù)偏差變量和正偏差變量。則對(duì)于目標(biāo)1，可將它表示為等式約束的形式-x1+x2+d1--d1+=0(目標(biāo)約束)

同樣設(shè)d2-和d2+分別表示安排生產(chǎn)時(shí)，低于可利用工時(shí)和高于可利用工時(shí)，即加班工時(shí)的偏差變量，則對(duì)目標(biāo)2，有3x1+2x2+d2--d2+=26

對(duì)于目標(biāo)3，設(shè)d3-和d3+分別表示安排生產(chǎn)時(shí)，低于計(jì)劃利潤(rùn)30元和高于計(jì)劃利潤(rùn)30元的偏差變量，有：第十九頁(yè)，共三十一頁(yè)，2022年，8月28日4x1+3x2+d3--d3+=30

（2）約束條件：有資源約束和目標(biāo)約束資源約束：2x1+3x2≤24

目標(biāo)約束：為上述各目標(biāo)中得出的約束（3）目標(biāo)函數(shù)：三個(gè)目標(biāo)依次為：

minZ1=d1-

，minZ2=d2++d2-

，minZ3=d3-

因而該問(wèn)題的數(shù)學(xué)模型可表述如下：

minZ1=d1-，minZ2=d2++d2-，minZ3=d3-2x1+3x2≤24s．t．-x1+x2+d1--d1+=03x1+2x2+d2--d2+=264x1+3x2+d3--d3+=30第二十頁(yè)，共三十一頁(yè)，2022年，8月28日

案例2（提級(jí)加新問(wèn)題）某公司的員工工資有四級(jí)，根據(jù)公司的業(yè)務(wù)發(fā)展情況，準(zhǔn)備招收部分新員工，并將部分員工的工資提升一級(jí)。該公司的員工工資及提級(jí)前后的編制表如下，其中提級(jí)后編制是計(jì)劃編制，允許有變化，其中1級(jí)員工中有8%要退休。公司領(lǐng)導(dǎo)的目標(biāo)如下：（1）提級(jí)后在職員工的工資總額不超過(guò)550千元；（2）各級(jí)員工不要超過(guò)定編人數(shù)；（3）為調(diào)動(dòng)積極性，各級(jí)員工的升級(jí)面不少于現(xiàn)有人數(shù)的18%；（4）總提級(jí)面不大于20%，但盡可能多提；（5）4級(jí)不足編制人數(shù)可錄用新工人。第二十一頁(yè)，共三十一頁(yè)，2022年，8月28日問(wèn)：應(yīng)如何擬定一具滿意的方案，才能接近上述目標(biāo)？級(jí)別1234工資（千元）8643現(xiàn)有員工數(shù)10204030編制員工數(shù)10225230解：（1）決策變量：設(shè)x1,x2,x3,x4分別表示提升到1，2，3級(jí)和新錄用的員工數(shù)。偏差變量：為各目標(biāo)的正、負(fù)偏差變量。（2）約束條件：1）

提級(jí)后在職員工的工資總額不超過(guò)550千元；8(10-108%+x1)+6(20-x1+x2)+4(40-x2+x3)+3(30-x3+x4)+d1--d1+=550

第二十二頁(yè)，共三十一頁(yè)，2022年，8月28日

2）各級(jí)員工不要超過(guò)定編人數(shù)1級(jí)有：10-108%+x1+d2--d2+=102級(jí)有：20-x1+x2+d3--d3+=223級(jí)有：40-x2+x3+d4--d4+=524級(jí)有：30-x3+x4+d5--d5+=303）各級(jí)員工的升級(jí)面不少于現(xiàn)有人數(shù)的18%對(duì)2級(jí)有：x1+d6--d6+=2218%對(duì)3級(jí)有：x2+d7--d7+=4018%

對(duì)4級(jí)有：x3+d8--d8+=3018%

4）總提級(jí)面人數(shù)不大于20%，但盡可能多提

x1+x2+x3+d9--d9+=10020%第二十三頁(yè)，共三十一頁(yè)，2022年，8月28日（3）目標(biāo)函數(shù)：minZ1=d1+minZ2=d2++d3++d4++d5+minZ3=d6-+d7-+d8-minZ4=d9++d9-案例3有三個(gè)產(chǎn)地向四個(gè)銷地供應(yīng)物資。產(chǎn)地Ai(i=1,2,3)的供應(yīng)量ai、銷地Bj(j=1,2,3,4)的需要量bj、各產(chǎn)銷地之間的單位物資運(yùn)費(fèi)Cij如表2所示。表中，ai和bj的單位為噸，Cij的單位為元/噸。編制調(diào)運(yùn)方案時(shí)要求按照相應(yīng)的優(yōu)先級(jí)依次考慮下列七個(gè)目標(biāo)：P1：B4是重點(diǎn)保證單位，其需要量應(yīng)盡可能全部滿足；P2：A3向B1提供的物資不少于100噸；P3：每個(gè)銷地得到的物資數(shù)量不少于其需要量的80%；第二十四頁(yè)，共三十一頁(yè)，2022年，8月28日P4：實(shí)際的總運(yùn)費(fèi)不超過(guò)最小總運(yùn)費(fèi)a的110%，這里的最小總費(fèi)用利用第三大題中第2小題求出的結(jié)果；P5：因路況原因，盡量避免安排A2的物資運(yùn)往B4；P6：對(duì)B1和B3的供應(yīng)率要盡可能相同；P7：力求使總運(yùn)費(fèi)最省。試建立該問(wèn)題的運(yùn)籌學(xué)模型。CijBjAiB1B2B3B4aiA15267300A23546200A34523400bj200100450250解：用表上作業(yè)法可求得不考慮P1至P6各目標(biāo)時(shí)的最小運(yùn)費(fèi)調(diào)運(yùn)方案，相應(yīng)的最小運(yùn)費(fèi)為2950元第二十五頁(yè)，共三十一頁(yè)，2022年，8月28日（1）決策變量：設(shè)Ai運(yùn)往Bj的物資為xij噸（2）約束條件：產(chǎn)量約束B(niǎo)4銷量要滿足銷量80%的限制供應(yīng)率盡可能相同第二十六頁(yè)，共三十一頁(yè)，2022年，8月28日二、目標(biāo)規(guī)劃的解法由于目標(biāo)規(guī)劃有多個(gè)目標(biāo)，各個(gè)目標(biāo)又有相對(duì)不同的重要性，求解時(shí)是首先滿足重要性權(quán)數(shù)大的目標(biāo)，再滿足重要性權(quán)數(shù)次大的目標(biāo)，所以并不能保證所有的目標(biāo)都能達(dá)到，所求的解也不一定是最優(yōu)解，而只能求出滿意解。（3）目標(biāo)函數(shù)第二十七頁(yè)，共三十一頁(yè)，2022年，8月28日

求解目標(biāo)規(guī)劃的仍用單純形法，但是與線性規(guī)劃的單純形法不同的是，此時(shí)檢驗(yàn)數(shù)行不再是一行，而是變化為一個(gè)檢驗(yàn)數(shù)矩陣。

例4

用單純形法求解如下線性目標(biāo)規(guī)劃模型

minZ1=d1-，minZ2=d2++d2-，minZ3=d3-2x1+3x2≤24加入松馳變量化為標(biāo)準(zhǔn)形

2x1+3x2+x3=24s．t．-x1+x2+d1--d1+=03x1+2x2