最優(yōu)化方法-第五章多目標(biāo)規(guī)劃

第四章多目標(biāo)規(guī)劃

本書大部分章節(jié)討論的基本上都是單目標(biāo)優(yōu)化問題，實際上，許多實際問題的優(yōu)化牽涉的目標(biāo)往往不止一個，如設(shè)計一個工廠的施工方案，就要考慮工期、成本、質(zhì)量、污染等目標(biāo),再如找工作,購買家用電器,追求的目標(biāo)往往都不止一個。由于這類問題需同時考慮多個目標(biāo)，而有些目標(biāo)之間又相互矛盾，從而使決策問題變得復(fù)雜,這類決策問題稱為多目標(biāo)決策問題。多目標(biāo)決策方法是現(xiàn)代管理科學(xué)的重要內(nèi)容，也是系統(tǒng)分析的基本工具。按照決策變量是連續(xù)的還是離散的，多目標(biāo)決策可以分為多目標(biāo)規(guī)劃決策(MultipleObjectiveDecisionMaking)和多準(zhǔn)則決策(MultipleAttributeDecisionMaking)兩大類，前者是以數(shù)學(xué)規(guī)劃的形式呈現(xiàn)的決策問題，后者則是已知各個方案及它產(chǎn)生的結(jié)局向量，由此選擇最優(yōu)方案的決策。

多目標(biāo)決策主要指多目標(biāo)最優(yōu)化，即多目標(biāo)規(guī)劃。對于某些問題，可以先用多目標(biāo)規(guī)劃選出幾個備選方案，然后再用多準(zhǔn)則決策方法作進一步處理，因此，這兩者既有區(qū)別又有聯(lián)系。多目標(biāo)最優(yōu)化的思想萌芽于1776年經(jīng)濟學(xué)中的效用理論。1896年，法國經(jīng)濟學(xué)家V·Pareto首先在經(jīng)濟理論的研究中提出了多目標(biāo)最優(yōu)化問題。1951年，美國數(shù)理經(jīng)濟學(xué)家T·C·Koopans從生產(chǎn)和分配的活動分析中考慮了多目標(biāo)決策問題，并首次提出了多目標(biāo)最優(yōu)化問題解的概念，將其命名為“Pareto解”(即有效解)。同年，H·W·Kuhn和A·W·Tucker從數(shù)學(xué)規(guī)劃論角度首次提出向量極值問題及有關(guān)概念。進入20世紀70年代，隨著第一次國際多目標(biāo)決策研討會的召開及這方面專著的問世，多目標(biāo)決策問題的研究工作迅速、蓬勃地開展起來，到目前為止，已取得若干有價值的研究成果。第一節(jié)多目標(biāo)規(guī)劃模型

線性規(guī)劃及非線性規(guī)劃研究的都是在給定的約束集合

R={X|gi(X)≥0，i=1，2，……，m)}X∈En上，求單目標(biāo)f(x)的最大或最小的問題，即方案的好壞是以一個目標(biāo)去衡量。然而，在很多實際問題中，衡量一個方案的好壞往往難以用一個指標(biāo)來判斷。也就是說，需要用一個以上的目標(biāo)去判斷方案的好壞，而這些目標(biāo)之間又往往不是那么協(xié)調(diào)，甚至是相互矛盾的。本章將以實例歸結(jié)出幾類常見的描述多目標(biāo)最優(yōu)化問題的數(shù)學(xué)模型。第四章多目標(biāo)規(guī)劃一.一般多目標(biāo)規(guī)劃模型例1：【喜糖問題】設(shè)市場上有甲級糖及乙級糖，單價分別為4元/斤及2元/斤。今要籌辦一樁喜事?！盎I備小組”計劃總花費不超過40元，糖的總斤數(shù)不少于10斤，甲級糖不少于5斤。問如何確定最佳的采購方案。我們先確定此問題應(yīng)滿足的條件（即約束條件）。不難看出，當(dāng)甲級糖數(shù)量為x1，乙級糖數(shù)量為x2時，有：

在研究以什么為“最佳”的衡量標(biāo)準(zhǔn)時，“籌備小組”的成員們意見可能會發(fā)生分歧，其原因是他們會提出各種各樣的目標(biāo)來。如果要求總花費最小，即要求：

f1(x1,x2)=4x1+2x2

→min

如果要求糖的總數(shù)量最大，即要求：如果要求甲級糖的數(shù)量最大，即要求：易見，這是具有3個目標(biāo)的規(guī)劃問題（由于約束及目標(biāo)均為線性函數(shù)，故它為多目標(biāo)線性規(guī)劃問題）。例2：【投資決策問題】某投資開發(fā)公司擁有總資金A萬元，今有n(≥2)個項目可供選擇。設(shè)投資第i(i=1，2，……，n)個項目要用資金ai萬元，預(yù)計可得到收益bi萬元。問應(yīng)如何使用總資金A萬元，才能得到最佳的經(jīng)濟效益？xi=0或1

所謂“最佳的經(jīng)濟效益”，如果理解為“少花錢多辦事”，則變?yōu)閮蓚€目標(biāo)的問題，即投資最少，收益最大：這是具有兩個目標(biāo)的0－1規(guī)劃問題。例3：【木梁設(shè)計問題】把橫截面為圓形的樹干加工成矩形橫截面的木梁。為使木梁滿足一定的規(guī)格和應(yīng)力及強度條件，要求木梁的高度不超過H，橫截面的慣性矩不少于給定值W，且橫截面的高度要介于其寬度和4倍寬度之間。問應(yīng)如何確定木梁尺寸，可使木梁的重量最輕，并且成本最低。設(shè)所設(shè)計的木梁橫截面的高為x1

，寬為x2（圖1）。為使具有一定長度的木梁重量最輕，應(yīng)要求其橫截面面積x1x2為最小，即要求x1x2→min

x1

x2圖1r

由于矩形橫截面的木梁是由橫截面為圓形的樹干加工而成的，故其成本與樹干橫截面面積的大小成正比。由此，為使木梁的成本最低還應(yīng)要求盡可能的小，或即：根據(jù)問題的要求，應(yīng)滿足下述約束條件：這是具有兩個目標(biāo)的非線性規(guī)劃問題。

由以上實例可見，多目標(biāo)最優(yōu)化模型與單目標(biāo)最優(yōu)化模型的區(qū)別主要是目標(biāo)多于一個。在這些目標(biāo)中，有的是追求極大化，有的是追求極小化，而極大化與極小化是可以相互轉(zhuǎn)化的。因此，我們不難將多目標(biāo)最優(yōu)化模型統(tǒng)一成一般形式：決策變量：x1，……，xn

目標(biāo)函數(shù)：minf1(x1，……，xn)………………minfp(x1，……，xn)

若記X=(x1，……，xn)，V-min表示對向量F(X)=[f1(X)，

……，fp(X)]T中的各目標(biāo)函數(shù)f1(X)，……，fp(X)同等的進行極小化。R={X|gi(X)≥0，i=1，……，m}表示約束集。則模型一般式也可簡記為這里(VMP)為向量數(shù)學(xué)規(guī)劃(VectorMathematicalProgramming)的簡寫。二.分層多目標(biāo)規(guī)劃模型

本節(jié)介紹一類不同于(VMP)形式的多目標(biāo)最優(yōu)化模型。這類模型的特點是：在約束條件下，各個目標(biāo)函數(shù)不是同等的被優(yōu)化，而是按不同的優(yōu)先層次先后的進行優(yōu)化。例如，在例1中，若籌備小組希望把所考慮的三個目標(biāo)按重要性分成以下兩個優(yōu)先層。第1優(yōu)先層——總的花費最小。第2優(yōu)先層——糖的總數(shù)量最大。甲級糖數(shù)量最大。

那么這種先在第1優(yōu)先層次極小化總花費，然后在此基礎(chǔ)上再在第2優(yōu)先層次同等的極大化糖的總數(shù)量和甲級糖的問題，就是所謂分層多目標(biāo)最優(yōu)化問題。可將其目標(biāo)函數(shù)表示為：

L-min{P1[f1(X)]，P2[f2(X)，f3(X)]}

其中P1，P2是優(yōu)先層次的記號，L-min表示按優(yōu)先層次序進行極小化。下面，我們來看一個建立分層多目標(biāo)最優(yōu)化模型的例子例4：某水稻區(qū)一農(nóng)民承包10畝農(nóng)田從事農(nóng)業(yè)種植。已知有三類復(fù)種方式可供選擇，其相應(yīng)的經(jīng)濟效益如表

方案復(fù)種方式糧食產(chǎn)量(公斤/畝)油料產(chǎn)量(公斤/畝)利潤(元/畝)投入氮素(公斤/畝)用工量(小時/畝)1大麥－早稻－晚梗1056——120.27503202大麥－早稻－玉米1008——111.46483503油菜－玉米－蔬菜336130208.2740390

設(shè)該農(nóng)戶全年至多可以出工3410小時，至少需要油料156公斤。今該農(nóng)戶希望優(yōu)先考慮總利潤最大和糧食總產(chǎn)量最高，然后考慮使投入氮素最少。問如何確定種植方案。首先設(shè)立決策變量如下方案1的種植畝數(shù)：x1，方案2的種植畝數(shù)：x2，方案3的種植畝數(shù)：x3，根據(jù)農(nóng)戶的要求確定問題的三個目標(biāo)函數(shù)為：

年總利潤：

f1(x1，x2，x3)=120.27x1+111.46x2+208.27x3

糧食總產(chǎn)量：

f2(x1，x2，x3)=1056x1+1008x2+336x3

投入氮素量：

f3(x1，x2，x3)=50x1+48x2+40x3

根據(jù)農(nóng)戶的全年出工能力，對油料需求量，所承包農(nóng)田數(shù)以及種植畝數(shù)應(yīng)為非負等限制，應(yīng)有約束條件：

總用工量：320x1+350x2+390x3≤3410

油料需求：130x3≥156

農(nóng)田數(shù)：x1+x2+x3＝10

種植畝數(shù)非負：x1≥0，x2≥0，x3≥0。

根據(jù)農(nóng)戶對目標(biāo)重要性的排序，將前兩個目標(biāo)作為第一優(yōu)先層，將第三個目標(biāo)作為第二優(yōu)先層，再把其中的求最大化轉(zhuǎn)化為求其負數(shù)的最小，便得到下列具有兩個優(yōu)先層次的分層多目標(biāo)極小化模型：對它進行求解便可得到農(nóng)戶滿意的種植方案。三.目標(biāo)規(guī)劃模型

本節(jié)介紹一類在實際中有著廣泛應(yīng)用的特殊多目標(biāo)最優(yōu)化模型。這類模型并不是去考慮對各個目標(biāo)進行極小化或極大化，而是希望在約束條件的限制下，每一目標(biāo)都盡可能的接近于事先給定的各目標(biāo)值。設(shè)p個目標(biāo)函數(shù)的給定目標(biāo)值分別為：例5：某機器制造廠生產(chǎn)兩種型號的機器，同時也進行機器的零部件和工業(yè)性作業(yè)生產(chǎn)。已知有關(guān)數(shù)據(jù)如下表，并且該工廠全年能承擔(dān)生產(chǎn)的總工時為58萬小時。生產(chǎn)項目單位產(chǎn)值利潤工時需要量1號機套5萬元/套1萬元/套1000小時/套160套(指令性計劃)2號機臺1.6萬元/套0.2萬元/臺400小時/臺320～500臺(市場預(yù)測)零部件和工業(yè)性作業(yè)萬小時50元/小時8.1元/小時26萬小時(市場預(yù)測)

今決策者希望在完成上級下達的指令性計劃的前提下，全年總產(chǎn)值達到2750萬元左右，總利潤不低于440萬元，并且要避免開工不足。然后，還希望工人的加班時間不超過總工時的4％，以及依據(jù)市場預(yù)測的信息進行生產(chǎn)。試問應(yīng)如何安排工廠的年生產(chǎn)計劃。首先，設(shè)立決策變量為

x1：生產(chǎn)1號機套數(shù)

x2：生產(chǎn)2號機臺數(shù)

x3：生產(chǎn)零部件和工業(yè)性作業(yè)的工時數(shù)(萬小時)第二節(jié)多目標(biāo)規(guī)劃問題的解

在單目標(biāo)規(guī)劃問題中，任意兩個可行方案都可通過比較其目標(biāo)函數(shù)值來確定其優(yōu)劣。在所有可行方案中，使目標(biāo)達最優(yōu)的就是最優(yōu)解。而在多目標(biāo)規(guī)劃問題中，約束集R中的兩個方案x1，x2其優(yōu)劣往往不能進行比較。這是因為它們的目標(biāo)值F(X1)與F(X2)是向量，而向量是無法直接比較大小的。所以，在R中也往往不存在一個方案對每個目標(biāo)都是最優(yōu)的。這種多目標(biāo)規(guī)劃問題區(qū)別于單目標(biāo)規(guī)劃問題的本質(zhì)表明，僅僅將單目標(biāo)問題最優(yōu)解的概念平移到多目標(biāo)問題中是不行的。本章將介紹多目標(biāo)規(guī)劃問題各種解的概念及其相互關(guān)系。一.各種解的概念圖2給出了兩個目標(biāo)，一維變量時絕對最優(yōu)解的例子圖3給出了兩個目標(biāo)，一維變量時有效解集合的例子二.各種解之間的關(guān)系多目標(biāo)決策與單目標(biāo)決策區(qū)別點評價與向量評價 單目標(biāo)：方案dj←評價值f(dj)

多目標(biāo)：方案dj←評價向量(f1(dj)，f2(dj)…，fp(dj))全序與半序:方案di與dj之間 單目標(biāo)問題:di<dj;di=dj;di>dj

多目標(biāo)問題：除了這三種情況之外,還有一種情況 是不可比較大小決策者偏好：多目標(biāo)決策過程中，反映決策者對 目標(biāo)的偏好。解概念區(qū)別解的概念單目標(biāo)決策的解只有一種（絕對）最優(yōu)解多目標(biāo)決策的解有下面四種情況：絕對最優(yōu)解劣解有效解(pereto解)弱有效解d1807588有效解d2758185有效解d3767889有效解劣解d5797486d4858292絕對最優(yōu)解數(shù)學(xué)外語專業(yè)解的類型多目標(biāo)決策解的例子第三節(jié)多目標(biāo)最優(yōu)化問題的解法

求解多目標(biāo)最優(yōu)化模型，就是要根據(jù)問題的特點和決策者的意圖，選擇適當(dāng)解法，求得模型的有效解或弱有效解。本章將介紹一些常用的多目標(biāo)最優(yōu)化問題解法。一.評價函數(shù)法λkp……λk2λk1k…………………………λ2p……λ22λ212λ1p……λ12λ111……fp(X)……f2(X)f1(X)

目標(biāo)權(quán)系數(shù)老手二.分層求解法

本節(jié)將針對第一節(jié)中介紹的分層多目標(biāo)最優(yōu)化模型，介紹一般的分層評價法和適用于線性分層模型的分層單純形法。

1、分層評價法設(shè)將目標(biāo)分為L個優(yōu)先層，則可首先在約束集R上對第一優(yōu)先層進行多目標(biāo)極小化，然后在第一層優(yōu)化所得的（弱）有效解集上對第二層進行優(yōu)化，然后在第二層優(yōu)化所得的（弱）有效解集上對第三層進行優(yōu)化……

可以證明，按分層評價法進行求解時，只要每一層選用的評價函數(shù)都是嚴格增的，則最后所得的解必為相應(yīng)的不分層多目標(biāo)最小化模型的有效解。

上述結(jié)果表明：若該農(nóng)戶認為利潤和糧食目標(biāo)在問題中的重要程度分別為0.6和0.4的話，則他應(yīng)該選擇如下的種植方案：方案1種植7畝，方案2不種植，方案3種植3畝。這時，還可算出年總利潤＝1466.66元糧食總產(chǎn)量＝8400公斤氮素投入量＝470公斤油料產(chǎn)量＝390公斤總用工量＝3410小時

2、分層單純形法將普通單純形法加以適當(dāng)推廣，便可用來求解分層多目標(biāo)線性規(guī)劃模型。其一般步驟如下：

(1)將每一優(yōu)先層中各目標(biāo)函數(shù)通過評價函數(shù)法（如線性加權(quán)和）轉(zhuǎn)化為單目標(biāo)；

(2)用單純形法求解各層目標(biāo)相應(yīng)的線性規(guī)劃問題。設(shè)共有L個優(yōu)先層，則在每張單純形表上的檢驗數(shù)位置有L行檢驗數(shù)(Cj-CBB-1pj)，將P1層對應(yīng)的檢驗數(shù)寫在最下行，PL層對應(yīng)的檢驗數(shù)寫在最上行。

(3)檢驗調(diào)整時由下往上，先調(diào)P1行（迭代方法同單純形法），直至P1行檢驗數(shù)滿足最優(yōu)性要求（檢驗數(shù)≥0），再開始調(diào)P2行。若某行負檢驗數(shù)相應(yīng)下行中有正檢驗數(shù)，則根據(jù)“高級優(yōu)先”的原則，放棄調(diào)整該列。這樣進行直至無法再調(diào)時（全部檢驗數(shù)為非負或雖有某為負，但其下方有正的）為止。0000000001-2020-31-1-1P3P2P10010101000011[1]-110-1x45x52x64x6x5x4x3x2x1XBB-1b0000030001-200001-1-1P3P2P1001-111100001010[1]0-1x43x22x66x6x5x4x3x2x1XBB-1b0001-12-1111-20000000P3P2P1001-11010100[1]010100x13x22x69x6x5x4x3x2x1XBB-1bXBB-1bx1x2x3x4x5x6x13x22x39100010001101-110001P3P2P1000000000-231-1-12-120三.目標(biāo)規(guī)劃法

第一節(jié)提出的目標(biāo)規(guī)劃模型(3)已經(jīng)化為單目標(biāo)問題。特別，當(dāng)目標(biāo)函數(shù)fi(X)(i=1，……，p)和約束R均為線性時，它就是一個線性規(guī)劃，其解法不必贅述。本節(jié)主要舉例說明在實際中常用的分層加權(quán)線性目標(biāo)規(guī)劃的解法。例12有一紡織廠生產(chǎn)尼龍和棉布，平均生產(chǎn)能力都是1千米/小時，工廠生產(chǎn)能力為每周80小時。根據(jù)市場預(yù)測，下周最大銷量為：尼龍布70千米，棉布45千米，尼龍布利潤為2.5元/米，棉布利潤為1.5元