數(shù)學(xué)建模培訓(xùn)多目標(biāo)規(guī)劃

數(shù)學(xué)建模培訓(xùn)多目標(biāo)規(guī)劃第1頁(yè)，共113頁(yè)，2023年，2月20日，星期六多目標(biāo)規(guī)化模型多目標(biāo)規(guī)劃是數(shù)學(xué)規(guī)劃的一個(gè)分支。研究多于一個(gè)的目標(biāo)函數(shù)在給定區(qū)域上的最優(yōu)化。又稱多目標(biāo)最優(yōu)化。通常記為MOP(multi-objectiveprogramming)。在很多實(shí)際問(wèn)題中，例如經(jīng)濟(jì)、管理、軍事、科學(xué)和工程設(shè)計(jì)等領(lǐng)域，衡量一個(gè)方案的好壞往往難以用一個(gè)指標(biāo)來(lái)判斷，而需要用多個(gè)目標(biāo)來(lái)比較，而這些目標(biāo)有時(shí)不甚協(xié)調(diào)，甚至是矛盾的。因此有許多學(xué)者致力于這方面的研究。

第2頁(yè)，共113頁(yè)，2023年，2月20日，星期六

例如,對(duì)企業(yè)產(chǎn)品的生產(chǎn)管理,既希望達(dá)到高利潤(rùn),又希望優(yōu)質(zhì)和低消耗,還希望減少對(duì)環(huán)境的污染等。這就是一個(gè)多目標(biāo)決策的問(wèn)題。又如選購(gòu)一個(gè)好的計(jì)算機(jī)系統(tǒng),似乎只有一個(gè)目標(biāo),但由于要從多方面去反映,要用多個(gè)不同的準(zhǔn)則來(lái)衡量,比如,性能要好,維護(hù)要容易,費(fèi)用要省。這些準(zhǔn)則自然構(gòu)成了多個(gè)目標(biāo),故也是一個(gè)多目標(biāo)決策問(wèn)題。一般來(lái)說(shuō),多目標(biāo)決策問(wèn)題有兩類。一類是多目標(biāo)規(guī)劃問(wèn)題,其對(duì)象是在管理決策過(guò)程中求解使多個(gè)目標(biāo)都達(dá)到滿意結(jié)果的最優(yōu)方案。另一類是多目標(biāo)優(yōu)選問(wèn)題,其對(duì)象是在管理決策過(guò)程中根據(jù)多個(gè)目標(biāo)或多個(gè)準(zhǔn)則衡量和得出各種備選方案的優(yōu)先等級(jí)與排序。第3頁(yè)，共113頁(yè)，2023年，2月20日，星期六多目標(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)化.以下,我們會(huì)介紹幾種主要的轉(zhuǎn)化方法:主要目標(biāo)法、線性加權(quán)和法、字典序法、步驟法。第4頁(yè)，共113頁(yè)，2023年，2月20日，星期六一、多目標(biāo)規(guī)劃及其解多目標(biāo)規(guī)劃包含有三大要素：目標(biāo)、方案和決策者。在多目標(biāo)規(guī)劃中，目標(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)規(guī)劃中的方案即為決策變量，也稱為多目標(biāo)問(wèn)題的解。備選方案即決策問(wèn)題的可行解。在多目標(biāo)決策中，有些問(wèn)題的方案是有限的，有些問(wèn)題的方案是無(wú)限的。方案有其特征或特性，稱之為屬性。第5頁(yè)，共113頁(yè)，2023年，2月20日，星期六（一）任何多目標(biāo)規(guī)劃問(wèn)題，都由兩個(gè)基本部分組成:（1）兩個(gè)以上的目標(biāo)函數(shù)；（2）若干個(gè)約束條件。

（二）對(duì)于多目標(biāo)規(guī)劃問(wèn)題，可以將其數(shù)學(xué)模型一般地描寫為如下形式：第6頁(yè)，共113頁(yè)，2023年，2月20日，星期六（2）（1）式中：為決策變量向量。第7頁(yè)，共113頁(yè)，2023年，2月20日，星期六第8頁(yè)，共113頁(yè)，2023年，2月20日，星期六第9頁(yè)，共113頁(yè)，2023年，2月20日，星期六

（三）多目標(biāo)規(guī)劃解的特點(diǎn)對(duì)于上述多目標(biāo)規(guī)劃問(wèn)題，求解就意味著需要做出如下的復(fù)合選擇：（1）每一個(gè)目標(biāo)函數(shù)取什么值，原問(wèn)題可以得到最滿意的解決？（2）每一個(gè)決策變量取什么值，原問(wèn)題可以得到最滿意的解決？多目標(biāo)規(guī)劃問(wèn)題的求解不能只追求一個(gè)目標(biāo)的最優(yōu)化（最大或最小），而不顧其它目標(biāo)。第10頁(yè)，共113頁(yè)，2023年，2月20日，星期六第11頁(yè)，共113頁(yè)，2023年，2月20日，星期六第12頁(yè)，共113頁(yè)，2023年，2月20日，星期六第13頁(yè)，共113頁(yè)，2023年，2月20日，星期六

當(dāng)目標(biāo)函數(shù)處于沖突狀態(tài)時(shí)，就不會(huì)存在使所有目標(biāo)函數(shù)同時(shí)達(dá)到最大或最小值的最優(yōu)解，于是我們只能尋求非劣解（又稱非支配解或帕累托解）。第14頁(yè)，共113頁(yè)，2023年，2月20日，星期六非劣解：可以用圖3說(shuō)明。圖3多目標(biāo)規(guī)劃的劣解與非劣解第15頁(yè)，共113頁(yè)，2023年，2月20日，星期六第16頁(yè)，共113頁(yè)，2023年，2月20日，星期六第17頁(yè)，共113頁(yè)，2023年，2月20日，星期六二、多目標(biāo)規(guī)劃問(wèn)題的建模方法

為了求得多目標(biāo)規(guī)劃問(wèn)題的非劣解，常常需要將多目標(biāo)規(guī)劃問(wèn)題轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題去處理。實(shí)現(xiàn)這種轉(zhuǎn)化，有如下幾種建模方法。第18頁(yè)，共113頁(yè)，2023年，2月20日，星期六第19頁(yè)，共113頁(yè)，2023年，2月20日，星期六第20頁(yè)，共113頁(yè)，2023年，2月20日，星期六第21頁(yè)，共113頁(yè)，2023年，2月20日，星期六第22頁(yè)，共113頁(yè)，2023年，2月20日，星期六（三）約束模型理論依據(jù)：若規(guī)劃問(wèn)題的某一目標(biāo)可以給出一個(gè)可供選擇的范圍，則該目標(biāo)就可以作為約束條件而被排除出目標(biāo)組，進(jìn)入約束條件組中。假如，除第一個(gè)目標(biāo)外，其余目標(biāo)都可以提出一個(gè)可供選擇的范圍，則該多目標(biāo)規(guī)劃問(wèn)題就可以轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題：

第23頁(yè)，共113頁(yè)，2023年，2月20日，星期六第24頁(yè)，共113頁(yè)，2023年，2月20日，星期六第25頁(yè)，共113頁(yè)，2023年，2月20日，星期六第26頁(yè)，共113頁(yè)，2023年，2月20日，星期六第27頁(yè)，共113頁(yè)，2023年，2月20日，星期六第28頁(yè)，共113頁(yè)，2023年，2月20日，星期六

用目標(biāo)達(dá)到法求解多目標(biāo)規(guī)劃的計(jì)算過(guò)程，可以通過(guò)調(diào)用Matlab軟件系統(tǒng)優(yōu)化工具箱中的fgoalattain函數(shù)實(shí)現(xiàn)。第29頁(yè)，共113頁(yè)，2023年，2月20日，星期六三、多目標(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)。第30頁(yè)，共113頁(yè)，2023年，2月20日，星期六例如，在上述多目標(biāo)問(wèn)題中，假定f1(X)為主要目標(biāo)，其余p-1個(gè)為非主要目標(biāo)。這時(shí)，希望主要目標(biāo)達(dá)到極大值，并要求其余的目標(biāo)滿足一定的條件，即第31頁(yè)，共113頁(yè)，2023年，2月20日，星期六例題某工廠在一個(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第32頁(yè)，共113頁(yè)，2023年，2月20日，星期六解：?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è)單位以下，即第33頁(yè)，共113頁(yè)，2023年，2月20日，星期六由主要目標(biāo)法化為單目標(biāo)問(wèn)題用單純形法求得其最優(yōu)解為第34頁(yè)，共113頁(yè)，2023年，2月20日，星期六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ù)第35頁(yè)，共113頁(yè)，2023年，2月20日，星期六則多目標(biāo)問(wèn)題化為如下的單目標(biāo)問(wèn)題第36頁(yè)，共113頁(yè)，2023年，2月20日，星期六例如，某公司計(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)定量化：第37頁(yè)，共113頁(yè)，2023年，2月20日，星期六第38頁(yè)，共113頁(yè)，2023年，2月20日，星期六變換后的指標(biāo)值矩陣為：aijf1f2f3f4f5f6A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.751001第39頁(yè)，共113頁(yè)，2023年，2月20日，星期六設(shè)權(quán)系數(shù)向量為W=（0.2,0.1,0.1,0.1,0.2,0.3),則故最優(yōu)方案為選購(gòu)A3型卡車第40頁(yè)，共113頁(yè)，2023年，2月20日，星期六第41頁(yè)，共113頁(yè)，2023年，2月20日，星期六第42頁(yè)，共113頁(yè)，2023年，2月20日，星期六第43頁(yè)，共113頁(yè)，2023年，2月20日，星期六第44頁(yè)，共113頁(yè)，2023年，2月20日，星期六4、步驟法（STEM法）這是一種交互方法，其求解過(guò)程通過(guò)分析者與決策者之間的對(duì)話逐步進(jìn)行，故稱步驟法。步驟法的基本思想是，首先需要求出原多目標(biāo)問(wèn)題的一組理想解(f1*,f2*,…,fk*)。實(shí)際上，這些解fi*(i=1,2,…,k)無(wú)法同時(shí)達(dá)到，但可以當(dāng)作一組理想的最優(yōu)值。以理想解作為一個(gè)標(biāo)準(zhǔn)，可以估計(jì)有效解，然后通過(guò)對(duì)話，不斷修改目標(biāo)值，并把降低要求的目標(biāo)作為新的約束條件加入原來(lái)的約束條件中去重新計(jì)算，直到?jīng)Q策者得到滿意的解。第45頁(yè)，共113頁(yè)，2023年，2月20日，星期六第46頁(yè)，共113頁(yè)，2023年，2月20日，星期六把上述計(jì)算結(jié)果列入下表第47頁(yè)，共113頁(yè)，2023年，2月20日，星期六第48頁(yè)，共113頁(yè)，2023年，2月20日，星期六第49頁(yè)，共113頁(yè)，2023年，2月20日，星期六例題：某公司考慮生產(chǎn)兩種光電太陽(yáng)能電池：產(chǎn)品甲和產(chǎn)品乙。這種生產(chǎn)過(guò)程會(huì)在空氣中引起放射性污染。因此，公司經(jīng)理有兩個(gè)目標(biāo)：極大化利潤(rùn)與極小化總的放射性污染。已知在一個(gè)生產(chǎn)周期內(nèi)，每單位甲產(chǎn)品的收益是1元，每單位乙產(chǎn)品的收益是3元。而放射性污染的數(shù)量，每單位甲產(chǎn)品是1.5個(gè)單位,每單位乙產(chǎn)品是1個(gè)單位.由于機(jī)器能力(小時(shí))、裝配能力（人時(shí)）和可用的原材料（單位）的限制，約束條件是第50頁(yè)，共113頁(yè)，2023年，2月20日，星期六目標(biāo)有兩個(gè):一是利潤(rùn)最大,二是污染最小.該問(wèn)題的多目標(biāo)規(guī)劃模型如下:第51頁(yè)，共113頁(yè)，2023年，2月20日，星期六解:首先,分別求解兩個(gè)單目標(biāo)問(wèn)題的最優(yōu)解,由它們得到的目標(biāo)函數(shù)值組成理想解.第52頁(yè)，共113頁(yè)，2023年，2月20日，星期六由此,構(gòu)造支付表Xf1*f2*(7,13)(0,0)460-23.50由此計(jì)算兩個(gè)目標(biāo)與理想值偏離的權(quán)重：解下列線性規(guī)劃問(wèn)題:第53頁(yè)，共113頁(yè)，2023年，2月20日，星期六第54頁(yè)，共113頁(yè)，2023年，2月20日，星期六進(jìn)行下一輪迭代.首先設(shè)π2=0,并計(jì)算得π1=1.將模型修改為第55頁(yè)，共113頁(yè)，2023年，2月20日，星期六由此求得:決策者把這一結(jié)果與前一輪的解及理想值作比較,認(rèn)為兩個(gè)目標(biāo)值都比較滿意,則迭代結(jié)束.第56頁(yè)，共113頁(yè)，2023年，2月20日，星期六線性目標(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)題。第57頁(yè)，共113頁(yè)，2023年，2月20日，星期六一、線性目標(biāo)規(guī)劃模型的建立

例1：某一個(gè)企業(yè)利用某種原材料和現(xiàn)有設(shè)備可生產(chǎn)甲、乙兩種產(chǎn)品，其中，甲、乙兩種產(chǎn)品的單價(jià)分別為8元和10元；生產(chǎn)單位甲、乙兩種產(chǎn)品需要消耗的原材料分別為2個(gè)單位和1個(gè)單位，需要占用的設(shè)備分別為1臺(tái)時(shí)和2臺(tái)時(shí)；原材料擁有量為11個(gè)單位；可利用的設(shè)備總臺(tái)時(shí)為10臺(tái)時(shí)。試問(wèn)：如何確定其生產(chǎn)方案？第58頁(yè)，共113頁(yè)，2023年，2月20日，星期六第59頁(yè)，共113頁(yè)，2023年，2月20日，星期六但是，在實(shí)際決策時(shí)，企業(yè)領(lǐng)導(dǎo)者必須考慮市場(chǎng)等一系列其它條件，如：①根據(jù)市場(chǎng)信息，甲種產(chǎn)品的需求量有下降的趨勢(shì)，因此甲種產(chǎn)品的產(chǎn)量不應(yīng)大于乙種產(chǎn)品的產(chǎn)量。②超過(guò)計(jì)劃供應(yīng)的原材料，需用高價(jià)采購(gòu)，這就會(huì)使生產(chǎn)成本增加。③應(yīng)盡可能地充分利用設(shè)備的有效臺(tái)時(shí)，但不希望加班。④應(yīng)盡可能達(dá)到并超過(guò)計(jì)劃產(chǎn)值指標(biāo)56元。這樣，該企業(yè)生產(chǎn)方案的確定，便成為一個(gè)多目標(biāo)決策問(wèn)題，這一問(wèn)題可以運(yùn)用目標(biāo)規(guī)劃方法進(jìn)行求解。第60頁(yè)，共113頁(yè)，2023年，2月20日，星期六目標(biāo)規(guī)劃模型的有關(guān)概念第61頁(yè)，共113頁(yè)，2023年，2月20日，星期六2、絕對(duì)約束和目標(biāo)約束

絕對(duì)約束：必須嚴(yán)格滿足的等式約束和不等式約束，譬如，線性規(guī)劃問(wèn)題的所有約束條件都是絕對(duì)約束，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。

目標(biāo)約束：目標(biāo)規(guī)劃所特有的，可以將約束方程右端項(xiàng)看作是追求的目標(biāo)值，在達(dá)到此目標(biāo)值時(shí)允許發(fā)生正的或負(fù)的偏差，可加入正負(fù)偏差變量，是軟約束。線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、負(fù)偏差變量后可以轉(zhuǎn)化為目標(biāo)約束，也可以根據(jù)問(wèn)題的需要將絕對(duì)約束轉(zhuǎn)化為目標(biāo)約束。目標(biāo)規(guī)劃模型的有關(guān)概念第62頁(yè)，共113頁(yè)，2023年，2月20日，星期六目標(biāo)規(guī)劃模型的有關(guān)概念第63頁(yè)，共113頁(yè)，2023年，2月20日，星期六目標(biāo)規(guī)劃模型的有關(guān)概念第64頁(yè)，共113頁(yè)，2023年，2月20日，星期六b)要求不超過(guò)目標(biāo)值，即允許達(dá)不到目標(biāo)值，就是正偏差變量要盡可能小，即（23）c)要求超過(guò)目標(biāo)值，也就是超過(guò)量不限，但負(fù)偏差變量要盡可能小，即（24）在實(shí)際問(wèn)題中，可以根據(jù)決策者的要求，引入正、負(fù)偏差變量和目標(biāo)約束，并給不同目標(biāo)賦予相應(yīng)的優(yōu)先因子和權(quán)系數(shù)，構(gòu)造目標(biāo)函數(shù)，建立模型。第65頁(yè)，共113頁(yè)，2023年，2月20日，星期六例2：在例1中，如果決策者在原材料供應(yīng)受嚴(yán)格控制的基礎(chǔ)上考慮：首先是甲種產(chǎn)品的產(chǎn)量不超過(guò)乙種產(chǎn)品的產(chǎn)量；其次是充分利用設(shè)備的有限臺(tái)時(shí)，不加班；再次是產(chǎn)值不小于56元。并分別賦予這三個(gè)目標(biāo)優(yōu)先因子。試建立該問(wèn)題的目標(biāo)規(guī)劃模型。第66頁(yè)，共113頁(yè)，2023年，2月20日，星期六第67頁(yè)，共113頁(yè)，2023年，2月20日，星期六第68頁(yè)，共113頁(yè)，2023年，2月20日，星期六在以上各式中，、分別為賦予優(yōu)先因子的第個(gè)目標(biāo)的正、負(fù)偏差變量的權(quán)系數(shù)，為第個(gè)目標(biāo)的預(yù)期值，為決策變量，、分別為第個(gè)目標(biāo)的正、負(fù)偏差變量，（25）式為目標(biāo)函數(shù)，（26）式為目標(biāo)約束，（27）式為絕對(duì)約束，（28）式和（29）式為非負(fù)約束，、、分別為目標(biāo)約束和絕對(duì)約束中決策變量的系數(shù)及約束值。其中，；；；。第69頁(yè)，共113頁(yè)，2023年，2月20日，星期六圖解法求解例2第70頁(yè)，共113頁(yè)，2023年，2月20日，星期六首先考慮具有優(yōu)先因子的目標(biāo)的實(shí)現(xiàn)，在目標(biāo)函數(shù)中要求實(shí)現(xiàn)，圖中可以滿足.這時(shí)的取值只能在OBC的邊界和內(nèi)部取得。接著考慮優(yōu)先因子的目標(biāo)的實(shí)現(xiàn)，在目標(biāo)函數(shù)中要求實(shí)現(xiàn)，當(dāng)時(shí)，其值可在線段ED上取得。第71頁(yè)，共113頁(yè)，2023年，2月20日，星期六最后考慮優(yōu)先因子的目標(biāo)的實(shí)現(xiàn)，在目標(biāo)函數(shù)中要求實(shí)現(xiàn)，當(dāng)時(shí)，其值縮小到在線段GD上取得.這就是該目標(biāo)規(guī)劃問(wèn)題的解.G和D點(diǎn)凸組合都是此目標(biāo)規(guī)劃的解.注：在目標(biāo)規(guī)劃問(wèn)題求解時(shí)，把絕對(duì)約束作最高優(yōu)先級(jí)考慮。在此例中，能依先后次序都滿足因而。但是大多數(shù)問(wèn)題中并非如此，還可能出現(xiàn)非可行解，故將目標(biāo)規(guī)劃問(wèn)題的最優(yōu)解成為滿意解。第72頁(yè)，共113頁(yè)，2023年，2月20日，星期六例如，某電視機(jī)廠裝配黑白和彩色兩種電視機(jī)，每裝配一臺(tái)電視機(jī)需占用裝配線1小時(shí)，裝配線每周計(jì)劃開(kāi)動(dòng)40小時(shí)。預(yù)計(jì)市場(chǎng)每周彩色電視機(jī)的銷量是24臺(tái)，每臺(tái)可獲利80元；黑白電視的銷量是30臺(tái)，每臺(tái)可獲利40元。該廠確定的目標(biāo)為：第一優(yōu)先級(jí)：充分利用裝配線每周計(jì)劃開(kāi)動(dòng)40小時(shí)；第二優(yōu)先級(jí)：允許裝配線加班，但加班時(shí)間每周盡量不超過(guò)10小時(shí)；第三優(yōu)先級(jí)：裝配電視機(jī)的數(shù)量盡量滿足市場(chǎng)需求。因彩色電視機(jī)的利潤(rùn)高，取其權(quán)系數(shù)為2.試建立此問(wèn)題的目標(biāo)規(guī)劃模型，并求解黑白和彩色電視機(jī)的產(chǎn)量。第73頁(yè)，共113頁(yè)，2023年，2月20日，星期六解：設(shè)分別為黑白和彩色電視機(jī)的產(chǎn)量。目標(biāo)規(guī)劃模型為第74頁(yè)，共113頁(yè)，2023年，2月20日，星期六從圖中可以看到，再考慮具有的目標(biāo)實(shí)現(xiàn)后，的取值范圍為ABCD。考慮的目標(biāo)要求時(shí)，因的權(quán)系數(shù)大于，故先取。這時(shí)的取值范圍為ABEF。在ABEF中，只有E點(diǎn)使得取值最小，故去E點(diǎn)為滿意解。其坐標(biāo)為(24,26)，即該廠每周應(yīng)裝配彩色電視機(jī)24臺(tái)，黑白電視機(jī)26臺(tái)。第75頁(yè)，共113頁(yè)，2023年，2月20日，星期六第76頁(yè)，共113頁(yè)，2023年，2月20日，星期六所以檢驗(yàn)數(shù)的正、負(fù)首先決定于的系數(shù)的正、負(fù)，若，則檢驗(yàn)數(shù)的正、負(fù)就決定于的系數(shù)的正、負(fù)，下面可依此類推。據(jù)此，我們可以總結(jié)出求解目標(biāo)規(guī)劃問(wèn)題的單純形方法的計(jì)算步驟如下：①建立初始單純形表，在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個(gè)數(shù)分別排成L行，置。第77頁(yè)，共113頁(yè)，2023年，2月20日，星期六②檢查該行中是否存在負(fù)數(shù)，且對(duì)應(yīng)的前L-1行的系數(shù)是零。若有，取其中最小者對(duì)應(yīng)的變量為換入變量，轉(zhuǎn)③。若無(wú)負(fù)數(shù)，則轉(zhuǎn)⑤。③按最小比值規(guī)則（規(guī)則）確定換出變量，當(dāng)存在兩個(gè)和兩個(gè)以上相同的最小比值時(shí)，選取具有較高優(yōu)先級(jí)別的變量為換出變量。④按單純形法進(jìn)行基變換運(yùn)算，建立新的計(jì)算表，返回②。⑤當(dāng)l=L時(shí)，計(jì)算結(jié)束，表中的解即為滿意解。否則置l=l+1，返回②。第78頁(yè)，共113頁(yè)，2023年，2月20日，星期六例3：試用單純形法求解例2所描述的目標(biāo)規(guī)劃問(wèn)題解：首先將這一問(wèn)題化為如下標(biāo)準(zhǔn)形式：第79頁(yè)，共113頁(yè)，2023年，2月20日，星期六①取、、、為初始基變量，列出初始單純形表。表1第80頁(yè)，共113頁(yè)，2023年，2月20日，星期六②取，檢查檢驗(yàn)數(shù)的行，因該行無(wú)負(fù)檢驗(yàn)數(shù)，故轉(zhuǎn)⑤。⑤因?yàn)?，置，返回②。②檢查發(fā)現(xiàn)檢驗(yàn)數(shù)行中有，，因?yàn)橛校詾閾Q入變量，轉(zhuǎn)入③。③按規(guī)則計(jì)算：，所以為換出變量，轉(zhuǎn)入④。④進(jìn)行換基運(yùn)算，得到表2。以此類推，直至得到最終單純形表為止，如表3所示。第81頁(yè)，共113頁(yè)，2023年，2月20日，星期六表2第82頁(yè)，共113頁(yè)，2023年，2月20日，星期六表3由表3可知，，，為滿意解。檢查檢驗(yàn)數(shù)行，發(fā)現(xiàn)非基變量的檢驗(yàn)數(shù)為0，這表明該問(wèn)題存在多重解。第83頁(yè)，共113頁(yè)，2023年，2月20日，星期六表4在表3中，以非基變量為換入變量，為換出變量，經(jīng)迭代得到表4。從表4可以看出，，也是該問(wèn)題的滿意解。第84頁(yè)，共113頁(yè)，2023年，2月20日，星期六

案例（提級(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ù)可錄用新工人。

第85頁(yè)，共113頁(yè)，2023年，2月20日，星期六問(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ù)。偏差變量：di+,di-為各目標(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

第86頁(yè)，共113頁(yè)，2023年，2月20日，星期六

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%第87頁(yè)，共113頁(yè)，2023年，2月20日，星期六（3）目標(biāo)函數(shù)：或者：第88頁(yè)，共113頁(yè)，2023年，2月20日，星期六五、層次分析法（一）層次分析法的基本原理層次分析法，又稱AHP(AnalyticHirrarchyProcess)方法，是美國(guó)運(yùn)籌學(xué)家薩蒂(T.Saaty)提出的一種多目標(biāo)、多準(zhǔn)則的決策分析方法。該方法被廣泛應(yīng)用于工程、經(jīng)濟(jì)、軍事、政治、外交等領(lǐng)域，解決了諸如系統(tǒng)評(píng)價(jià)、資源分配、價(jià)格預(yù)測(cè)、項(xiàng)目選擇等許多重要問(wèn)題，是一種定量分析與定性分析相結(jié)合的有效方法。第89頁(yè)，共113頁(yè)，2023年，2月20日，星期六用層次分析法作決策分析，首先要把問(wèn)題層次化。根據(jù)問(wèn)題的性質(zhì)和要達(dá)到的總目標(biāo)，將問(wèn)題分解為不同的組成因素，并按照因素間的相互影響以及隸屬關(guān)系按不同層次聚集組合，形成一個(gè)多層次的分析結(jié)構(gòu)模型。最終把系統(tǒng)分析歸結(jié)為最低層（如決策方案）相對(duì)于最高層（總目標(biāo)）的相對(duì)重要性權(quán)值的確定或相對(duì)優(yōu)劣次序的排序問(wèn)題，從而為決策方案的選擇提供依據(jù)。第90頁(yè)，共113頁(yè)，2023年，2月20日，星期六

（二)層次分析法大體分為六個(gè)步驟1）明確問(wèn)題：為了運(yùn)用AHP進(jìn)行系統(tǒng)分析，首先要對(duì)問(wèn)題有明確的認(rèn)識(shí)，弄清問(wèn)題范圍、所包含的因素及其相互關(guān)系、解決問(wèn)題的目的、是否具有AHP所描述的特征。2）建立層次結(jié)構(gòu)模型：將問(wèn)題中所包含的因素劃分為不同層次。例如，對(duì)于決策問(wèn)題，通常可以劃分為下面幾個(gè)層次：最高層：表示解決問(wèn)題的目的，稱為目標(biāo)層。中間層：表示采取某種措施或政策實(shí)現(xiàn)預(yù)定目標(biāo)的涉及的中間環(huán)節(jié)，一般又分為策略層、準(zhǔn)則層等。最低層：表示解決問(wèn)題的措施或方案，稱為措施層或方案層。如下圖所示。第91頁(yè)，共113頁(yè)，2023年，2月20日，星期六決策目標(biāo)準(zhǔn)則1準(zhǔn)則1準(zhǔn)則m子準(zhǔn)則1子準(zhǔn)則2子準(zhǔn)則k方案1方案2方案n目標(biāo)層準(zhǔn)則層子準(zhǔn)則層方案層………………第92頁(yè)，共113頁(yè)，2023年，2月20日，星期六3）構(gòu)造判斷矩陣針對(duì)上一層某元素，對(duì)每一層次各個(gè)元素的相對(duì)重要性進(jìn)行兩兩比較，并給出判斷。這些判斷用數(shù)值表示出來(lái)，寫成矩陣形式，即所謂的判斷矩陣。其中bij表示對(duì)于Ak而言，Bi對(duì)Bj的相對(duì)重要性，通常bij取1,2,…,9及它們的倒數(shù)，其含義為：第93頁(yè)，共113頁(yè)，2023年，2月20日，星期六1表示Bi與Bj相比，兩者重要性相同3表示Bi比Bj稍重要5表示Bi比Bj重要7表示Bi比Bj強(qiáng)烈重要9表示Bi比Bj極端重要它們之間的數(shù)2，4，6，8及各數(shù)的倒數(shù)有相應(yīng)的類似意義。顯然，對(duì)判斷矩陣有因此，對(duì)于n階判斷矩陣，我們僅需對(duì)n(n-1)/2個(gè)元素給出數(shù)值。第94頁(yè)，共113頁(yè)，2023年，2月20日，星期六4）層次單排序及其一致性檢驗(yàn)所謂層次單排序，即把同一層次相應(yīng)元素對(duì)于上一層次某元素相對(duì)重要性的排序權(quán)值求出來(lái)。其方法是計(jì)算判斷矩陣A的滿足等式的最大特征值和對(duì)應(yīng)的特征向量W，這個(gè)特征向量就是單排序權(quán)值?？梢宰C明，對(duì)于n階判斷矩陣，其最大特征根為單根，且，所對(duì)應(yīng)的特征向量均由正數(shù)組成。特別，當(dāng)判斷矩陣具有完全一致性時(shí),有這里，所謂完全一致性是指對(duì)于判斷矩陣來(lái)說(shuō)，存在第95頁(yè)，共113頁(yè)，2023年，2月20日，星期六1.451.411.321.241.120.900.850.000.00RI987654321階數(shù)為檢驗(yàn)判斷矩陣的一致性，需要計(jì)算一致性指標(biāo)此外，還需要判斷矩陣的平均隨機(jī)一致性指標(biāo)RI。對(duì)于1至9階矩陣，RI的值如下表。在這里，對(duì)于1,2階判斷矩陣，RI只是形式上的，因?yàn)?，2階判斷矩陣總具有完全一致性，當(dāng)階數(shù)大于2時(shí)，判斷矩陣的一致性指標(biāo)CI與同階平均隨機(jī)一致性指標(biāo)RI之比稱謂隨機(jī)一致性比率，記為CR，CR=CI/RI<0.10時(shí)，即認(rèn)為判斷矩陣具有滿意的一致性，否則就需要調(diào)整判斷矩陣，使其具有滿意的一致性。第96頁(yè)，共113頁(yè)，2023年，2月20日，星期六5）層次總排序計(jì)算同一層次所有元素對(duì)于最高層相對(duì)重要性的排序權(quán)值，稱為層次總排序。這一過(guò)程是最高層次到最低層次逐層進(jìn)行的。若上一層次A包含m個(gè)元素A1,A2,…,Am，其層次總排序權(quán)值分別為a1,a2,…,am，下一層次B包含n個(gè)元素B1,B2,…Bn，它們對(duì)于元素Aj的層次單排序權(quán)值分別為b1j,b2j,…,bnj（當(dāng)Bk與Aj無(wú)關(guān)系時(shí),bkj=0），此時(shí)，層次總排序權(quán)值為第97頁(yè)，共113頁(yè)，2023年，2月20日，星期六B層次總排序權(quán)重層次第98頁(yè)，共113頁(yè)，2023年，2月20日，星期六6）層次總排序的一致性檢驗(yàn)。這一步也是從高到低逐層進(jìn)行的。如果B層次某些元素對(duì)于Aj單排序的一致性指標(biāo)為CIj，相應(yīng)的平均隨機(jī)一致性指標(biāo)為RIj，則B層次總排序隨機(jī)一致性比率為類似地，當(dāng)CR<0.10時(shí)，認(rèn)為層次總排序結(jié)果具有滿意的一致性，否則需要重新調(diào)整判斷矩陣的元素取值。第99頁(yè)，共113頁(yè)，2023年，2月20日，星期六(三)層次分析法的計(jì)算問(wèn)題層次分析法計(jì)算的根本問(wèn)題是如何計(jì)算判斷矩陣的最大特征根其對(duì)應(yīng)的特征向量.一般來(lái)說(shuō),計(jì)算判斷矩陣最大特征根及其對(duì)應(yīng)特征向量,并不需要追求較高的精確定度.這是因?yàn)榕袛嗑仃嚤旧硐喈?dāng)?shù)恼`差范圍.應(yīng)用層次分析法給出的層次中各種元素優(yōu)先排序權(quán)值從本質(zhì)上來(lái)說(shuō)是表達(dá)某種定性的概念.因此,從實(shí)用性來(lái)看,往往希望使用較為簡(jiǎn)單的近似算法.下面介紹二種稱之為方根法和和積法的近似算法.

第100頁(yè)，共113頁(yè)，2023年，2月20日，星期六(2)計(jì)算Mi的n次方根Vi(3)對(duì)向量V=(V1,V2,…,Vn)T規(guī)一化,即則W=(W1,W2,…,Wn)T.即為所求的特征向量1、方根法的步驟如下:(1)計(jì)算判斷矩陣B每一行元素的乘積Mi.第101頁(yè)，共113頁(yè)，2023年，2月20日，星期六(4)計(jì)算判斷矩陣的最大特征根式中(BW)i表示向量BW的第i個(gè)分量.第102頁(yè)，共113頁(yè)，2023年，2月20日，星期六容易證明：當(dāng)正互反矩陣為一致性矩陣時(shí)，方根法可得到精確的最大特征值與相應(yīng)的特征向量。證明：設(shè)為一致性矩陣，為其最大特征值，為相應(yīng)的特征向量，且是歸一化的。由于令顯然，歸一化后，于是用公式，求得的最大特征值為n。第103頁(yè)，共113頁(yè)，2023年，2月20日，星期六例題某廠準(zhǔn)備購(gòu)買一臺(tái)計(jì)算機(jī),希望功能強(qiáng),價(jià)格低,維護(hù)容易.現(xiàn)有A,B,C三種機(jī)型可供選擇.其中A的性能較好,價(jià)格一般,維護(hù)需要一般水平;B的性能最好,價(jià)格較貴,維護(hù)也只需一般水平;C的性能差,但價(jià)格便宜,容易維護(hù).首先構(gòu)成分析層次,如圖購(gòu)置一臺(tái)滿意的計(jì)算機(jī)功能強(qiáng)價(jià)格低易維護(hù)CBA第104頁(yè)，共113頁(yè)，2023年，2月20日，星期六對(duì)于三個(gè)準(zhǔn)則(S1,S2,S3)關(guān)于目標(biāo)G的優(yōu)先順序,根據(jù)討論,該廠在計(jì)算機(jī)應(yīng)用上首先要求功能強(qiáng),其次要求易維護(hù),再次才是價(jià)格低.其判斷矩陣如下表131/3S31/311/5S2351S1S3S2S1G用方根法計(jì)算這三個(gè)準(zhǔn)則關(guān)于目標(biāo)的排序權(quán)值如下:第105頁(yè)，共113頁(yè)，2023年，2月20日，星期六一致性檢驗(yàn)結(jié)果為:同樣,三個(gè)方案對(duì)于各個(gè)準(zhǔn)則的判斷矩陣以及運(yùn)算所得的結(jié)果分別見(jiàn)表0.09100.72720.1818W11/81/2C814B21/41ACBAS1對(duì)準(zhǔn)則S1(功能強(qiáng))來(lái)說(shuō):對(duì)準(zhǔn)則S2(價(jià)格低)來(lái)說(shuō):第106頁(yè)，共113頁(yè)，2023年，2月20日，星期六0.67080.07330.2559W183C1/811/4B1/341ACBAS2對(duì)準(zhǔn)則S3(易維護(hù))來(lái)說(shuō):0.65870.15620.1851W153C1/511B1/311ACBAS3第107頁(yè)，共113頁(yè)，2023年，2月20日，星期六層次總排序的結(jié)果:0.2580.1050.6370.29840.51120.1904總排序權(quán)值0.65870.67080.0910C0.15620.07330.7272B0.18150.25590.1818A