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

1、 例如例如, ,對(duì)企業(yè)產(chǎn)品的生產(chǎn)管理對(duì)企業(yè)產(chǎn)品的生產(chǎn)管理, ,既希望達(dá)到高利既希望達(dá)到高利潤(rùn)潤(rùn), ,又希望優(yōu)質(zhì)和低消耗又希望優(yōu)質(zhì)和低消耗, ,還希望減少對(duì)環(huán)境的污染等。還希望減少對(duì)環(huán)境的污染等。這就是一個(gè)多目標(biāo)決策的問(wèn)題。又如選購(gòu)一個(gè)好的計(jì)這就是一個(gè)多目標(biāo)決策的問(wèn)題。又如選購(gòu)一個(gè)好的計(jì)算機(jī)系統(tǒng)算機(jī)系統(tǒng), ,似乎只有一個(gè)目標(biāo)似乎只有一個(gè)目標(biāo), ,但由于要從多方面去反但由于要從多方面去反映映, ,要用多個(gè)不同的準(zhǔn)則來(lái)衡量要用多個(gè)不同的準(zhǔn)則來(lái)衡量, ,比如比如, ,性能要好性能要好, ,維護(hù)維護(hù)要容易要容易, ,費(fèi)用要省。這些準(zhǔn)則自然構(gòu)成了多個(gè)目標(biāo)費(fèi)用要省。這些準(zhǔn)則自然構(gòu)成了多個(gè)目標(biāo), ,故故也是一

2、個(gè)多目標(biāo)決策問(wèn)題。一般來(lái)說(shuō)也是一個(gè)多目標(biāo)決策問(wèn)題。一般來(lái)說(shuō), ,多目標(biāo)決策問(wèn)多目標(biāo)決策問(wèn)題有兩類。一類是多目標(biāo)規(guī)劃問(wèn)題題有兩類。一類是多目標(biāo)規(guī)劃問(wèn)題, ,其對(duì)象是在管理其對(duì)象是在管理決策過(guò)程中求解使多個(gè)目標(biāo)都達(dá)到滿意結(jié)果的最優(yōu)方?jīng)Q策過(guò)程中求解使多個(gè)目標(biāo)都達(dá)到滿意結(jié)果的最優(yōu)方案。另一類是多目標(biāo)優(yōu)選問(wèn)題案。另一類是多目標(biāo)優(yōu)選問(wèn)題, ,其對(duì)象是在管理決策其對(duì)象是在管理決策過(guò)程中根據(jù)多個(gè)目標(biāo)或多個(gè)準(zhǔn)則衡量和得出各種備選過(guò)程中根據(jù)多個(gè)目標(biāo)或多個(gè)準(zhǔn)則衡量和得出各種備選方案的優(yōu)先等級(jí)與排序。方案的優(yōu)先等級(jí)與排序。第1頁(yè)/共112頁(yè)多目標(biāo)決策由于考慮的目標(biāo)多多目標(biāo)決策由于考慮的目標(biāo)多, ,有些目標(biāo)之間又彼有些

3、目標(biāo)之間又彼此有矛盾此有矛盾, ,這就使多目標(biāo)問(wèn)題成為一個(gè)復(fù)雜而困難這就使多目標(biāo)問(wèn)題成為一個(gè)復(fù)雜而困難的問(wèn)題的問(wèn)題. .但由于客觀實(shí)際的需要但由于客觀實(shí)際的需要, ,多目標(biāo)決策問(wèn)題多目標(biāo)決策問(wèn)題越來(lái)越受到重視越來(lái)越受到重視, ,因而出現(xiàn)了許多解決此決策問(wèn)題因而出現(xiàn)了許多解決此決策問(wèn)題的方法的方法. .一般來(lái)說(shuō)一般來(lái)說(shuō), ,其基本途徑是其基本途徑是, ,把求解多目標(biāo)問(wèn)把求解多目標(biāo)問(wèn)題轉(zhuǎn)化為求解單目標(biāo)問(wèn)題題轉(zhuǎn)化為求解單目標(biāo)問(wèn)題. .其主要步驟是其主要步驟是, ,先轉(zhuǎn)化先轉(zhuǎn)化為單目標(biāo)問(wèn)題為單目標(biāo)問(wèn)題, ,然后利用單目標(biāo)模型的方法然后利用單目標(biāo)模型的方法, ,求出求出單目標(biāo)模型的最優(yōu)解單目標(biāo)模型的最優(yōu)

4、解, ,以此作為多目標(biāo)問(wèn)題的解以此作為多目標(biāo)問(wèn)題的解. . 化多目標(biāo)問(wèn)題為單目標(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)題, ,另一類是另一類是轉(zhuǎn)化為多個(gè)單目標(biāo)問(wèn)題轉(zhuǎn)化為多個(gè)單目標(biāo)問(wèn)題, ,關(guān)鍵是如何轉(zhuǎn)化關(guān)鍵是如何轉(zhuǎn)化. . 以下以下, ,我們會(huì)介紹幾種主要的轉(zhuǎn)化方法我們會(huì)介紹幾種主要的轉(zhuǎn)化方法: :主要主要目標(biāo)法、線性加權(quán)和法、字典序法、步驟法。目標(biāo)法、線性加權(quán)和法、字典序法、步驟法。第2頁(yè)/共112頁(yè)一、多一、多 目標(biāo)目標(biāo) 規(guī)規(guī) 劃劃 及及 其其 解解 多目標(biāo)規(guī)劃包含有三大要素：目標(biāo)、方案和決策者。多目標(biāo)規(guī)

5、劃包含有三大要素：目標(biāo)、方案和決策者。 在多目標(biāo)規(guī)劃中，目標(biāo)有多層次的含義。從最高層次來(lái)在多目標(biāo)規(guī)劃中，目標(biāo)有多層次的含義。從最高層次來(lái)看，目標(biāo)代表了問(wèn)題要達(dá)到的總目標(biāo)。如確定最滿意的看，目標(biāo)代表了問(wèn)題要達(dá)到的總目標(biāo)。如確定最滿意的投資項(xiàng)目、選擇最滿意的食品。從較低層次來(lái)看，目標(biāo)投資項(xiàng)目、選擇最滿意的食品。從較低層次來(lái)看，目標(biāo)可看成是體現(xiàn)總目標(biāo)得以實(shí)現(xiàn)的各個(gè)具體的目標(biāo)，如投可看成是體現(xiàn)總目標(biāo)得以實(shí)現(xiàn)的各個(gè)具體的目標(biāo)，如投資項(xiàng)目的盈利要大、成本要低、風(fēng)險(xiǎn)要??；目標(biāo)也可看資項(xiàng)目的盈利要大、成本要低、風(fēng)險(xiǎn)要??；目標(biāo)也可看成衡量總目標(biāo)得以實(shí)現(xiàn)的各個(gè)準(zhǔn)則，如食品的味道要好，成衡量總目標(biāo)得以實(shí)現(xiàn)的各個(gè)準(zhǔn)則

6、，如食品的味道要好，質(zhì)量要好，花費(fèi)要少。質(zhì)量要好，花費(fèi)要少。 多目標(biāo)規(guī)劃中的方案即為決策變量，也稱為多目標(biāo)問(wèn)題多目標(biāo)規(guī)劃中的方案即為決策變量，也稱為多目標(biāo)問(wèn)題的解。備選方案即決策問(wèn)題的可行解。在多目標(biāo)決策中，的解。備選方案即決策問(wèn)題的可行解。在多目標(biāo)決策中，有些問(wèn)題的方案是有限的，有些問(wèn)題的方案是無(wú)限的。有些問(wèn)題的方案是有限的，有些問(wèn)題的方案是無(wú)限的。方案有其特征或特性，稱之為屬性。方案有其特征或特性，稱之為屬性。第3頁(yè)/共112頁(yè) （一）任何多目標(biāo)規(guī)劃問(wèn)題，都由兩個(gè)基本部分組成（一）任何多目標(biāo)規(guī)劃問(wèn)題，都由兩個(gè)基本部分組成: : （1 1）兩個(gè)以上的目標(biāo)函數(shù)；）兩個(gè)以上的目標(biāo)函數(shù)； （2 2

7、）若干個(gè)約束條件。）若干個(gè)約束條件。 （二）對(duì)于多目標(biāo)規(guī)劃問(wèn)題，可以將（二）對(duì)于多目標(biāo)規(guī)劃問(wèn)題，可以將其數(shù)學(xué)模型一般地描寫為如下形式：其數(shù)學(xué)模型一般地描寫為如下形式： 第4頁(yè)/共112頁(yè)（2 2）)(max(min)(max(min)(max(min)(max(min)21XfXfXfXFZkmmgggGXXXX2121)()()()(（1 1）式中：式中： 為決策變量向量。為決策變量向量。 TnxxxX,21第5頁(yè)/共112頁(yè)第6頁(yè)/共112頁(yè)第7頁(yè)/共112頁(yè) （三）多目標(biāo)規(guī)劃解的特點(diǎn)（三）多目標(biāo)規(guī)劃解的特點(diǎn) 對(duì)于上述多目標(biāo)規(guī)劃問(wèn)題，求解就意味著需要對(duì)于上述多目標(biāo)規(guī)劃問(wèn)題，求解就意味著需要

8、做出如下的復(fù)合選擇：做出如下的復(fù)合選擇： （1 1）每一個(gè)目標(biāo)函數(shù)取什么值，原問(wèn)題可以得）每一個(gè)目標(biāo)函數(shù)取什么值，原問(wèn)題可以得到最滿意的解決？到最滿意的解決？ （2 2）每一個(gè)決策變量取什么值，原問(wèn)題可以得）每一個(gè)決策變量取什么值，原問(wèn)題可以得到最滿意的解決到最滿意的解決 ？ 多目標(biāo)規(guī)劃問(wèn)題的求解不能只追求一個(gè)目標(biāo)的多目標(biāo)規(guī)劃問(wèn)題的求解不能只追求一個(gè)目標(biāo)的最優(yōu)化（最大或最?。?，而不顧其它目標(biāo)。最優(yōu)化（最大或最?。?，而不顧其它目標(biāo)。第8頁(yè)/共112頁(yè)第9頁(yè)/共112頁(yè)第10頁(yè)/共112頁(yè)第11頁(yè)/共112頁(yè) 當(dāng)目標(biāo)函數(shù)處于沖突狀態(tài)時(shí)，就不會(huì)當(dāng)目標(biāo)函數(shù)處于沖突狀態(tài)時(shí)，就不會(huì)存在使所有目標(biāo)函數(shù)同時(shí)達(dá)

9、到最大或最小存在使所有目標(biāo)函數(shù)同時(shí)達(dá)到最大或最小值的最優(yōu)解，于是我們只能尋求非劣解值的最優(yōu)解，于是我們只能尋求非劣解（又稱非支配解或帕累托解）。（又稱非支配解或帕累托解）。 第12頁(yè)/共112頁(yè)非劣解：可以用圖非劣解：可以用圖3 3說(shuō)明。說(shuō)明。圖3 多目標(biāo)規(guī)劃的劣解與非劣解第13頁(yè)/共112頁(yè)第14頁(yè)/共112頁(yè)第15頁(yè)/共112頁(yè)二、多二、多 目目 標(biāo)標(biāo) 規(guī)規(guī) 劃劃 問(wèn)問(wèn) 題題 的的 建建 模模 方方 法法 為了求得多目標(biāo)規(guī)劃問(wèn)題的非劣解，常常需要將多目標(biāo)規(guī)劃問(wèn)題轉(zhuǎn)化為為了求得多目標(biāo)規(guī)劃問(wèn)題的非劣解，常常需要將多目標(biāo)規(guī)劃問(wèn)題轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題去處理。實(shí)現(xiàn)這種轉(zhuǎn)化，有如下幾種建模方法。單目標(biāo)

10、規(guī)劃問(wèn)題去處理。實(shí)現(xiàn)這種轉(zhuǎn)化，有如下幾種建模方法。第16頁(yè)/共112頁(yè)第17頁(yè)/共112頁(yè)第18頁(yè)/共112頁(yè)第19頁(yè)/共112頁(yè)第20頁(yè)/共112頁(yè)（三）約束模型三）約束模型 理論依據(jù)理論依據(jù) ：若規(guī)劃問(wèn)題的某一目標(biāo)可以給：若規(guī)劃問(wèn)題的某一目標(biāo)可以給出一個(gè)可供選擇的范圍，則該目標(biāo)就可以出一個(gè)可供選擇的范圍，則該目標(biāo)就可以作為約束條件而被排除出目標(biāo)組，進(jìn)入約作為約束條件而被排除出目標(biāo)組，進(jìn)入約束條件組中。束條件組中。假如，除第一個(gè)目標(biāo)外，其余目標(biāo)都可以假如，除第一個(gè)目標(biāo)外，其余目標(biāo)都可以提出一個(gè)可供選擇的范圍，則該多目標(biāo)規(guī)提出一個(gè)可供選擇的范圍，則該多目標(biāo)規(guī)劃問(wèn)題就可以轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題：劃

11、問(wèn)題就可以轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題： 第21頁(yè)/共112頁(yè)第22頁(yè)/共112頁(yè)第23頁(yè)/共112頁(yè)第24頁(yè)/共112頁(yè)第25頁(yè)/共112頁(yè)第26頁(yè)/共112頁(yè) 用目標(biāo)達(dá)到法求解多目標(biāo)規(guī)劃的計(jì)用目標(biāo)達(dá)到法求解多目標(biāo)規(guī)劃的計(jì)算過(guò)程，可以通過(guò)調(diào)用算過(guò)程，可以通過(guò)調(diào)用MatlabMatlab軟件系統(tǒng)軟件系統(tǒng)優(yōu)化工具箱中的優(yōu)化工具箱中的fgoalattainfgoalattain函數(shù)實(shí)現(xiàn)。函數(shù)實(shí)現(xiàn)。第27頁(yè)/共112頁(yè)三、多目標(biāo)規(guī)劃問(wèn)題的求解(化多為少的方法)1 1、主要目標(biāo)法、主要目標(biāo)法 在有些多目標(biāo)決策問(wèn)題中，各種目標(biāo)的重在有些多目標(biāo)決策問(wèn)題中，各種目標(biāo)的重要性程度往往不一樣。其中一個(gè)重要性程度最要性程

12、度往往不一樣。其中一個(gè)重要性程度最高和最為關(guān)鍵的目標(biāo)，稱之為主要目標(biāo)法。其高和最為關(guān)鍵的目標(biāo)，稱之為主要目標(biāo)法。其余的目標(biāo)則稱為非主要目標(biāo)。余的目標(biāo)則稱為非主要目標(biāo)。0)(0)(. .)(. .)(),.,(),()(21XhXgtsorGXtsXfXfXfXoptFjiTk第28頁(yè)/共112頁(yè)例如，在上述多目標(biāo)問(wèn)題中，假定例如，在上述多目標(biāo)問(wèn)題中，假定f1(X)為主要為主要目標(biāo)，其余目標(biāo)，其余p p-1-1個(gè)為非主要目標(biāo)。這時(shí)，希望個(gè)為非主要目標(biāo)。這時(shí)，希望主要目標(biāo)達(dá)到極大值，并要求其余的目標(biāo)滿足主要目標(biāo)達(dá)到極大值，并要求其余的目標(biāo)滿足一定的條件，即一定的條件，即1,.,2 , 1,)(,.

13、,2 , 1, 0)(,.,2 , 1, 0)(. .)(max1pkXfmjXhniXgtsXfkkji第29頁(yè)/共112頁(yè)例題例題 某工廠在一個(gè)計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，某工廠在一個(gè)計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，各產(chǎn)品都要消耗各產(chǎn)品都要消耗A A，B B，C C三種不同的資源。每件產(chǎn)品三種不同的資源。每件產(chǎn)品對(duì)資源的單位消耗、各種資源的限量以及各產(chǎn)品的對(duì)資源的單位消耗、各種資源的限量以及各產(chǎn)品的單位價(jià)格、單位利潤(rùn)和所造成的單位污染如下表。單位價(jià)格、單位利潤(rùn)和所造成的單位污染如下表。假定產(chǎn)品能全部銷售出去，問(wèn)每期怎樣安排生產(chǎn)，假定產(chǎn)品能全部銷售出去，問(wèn)每期怎樣安排生產(chǎn)，才能使利潤(rùn)和產(chǎn)值都最大

14、，且造成的污染最??？才能使利潤(rùn)和產(chǎn)值都最大，且造成的污染最??？甲甲乙乙資源限量資源限量資源資源A A單位消耗單位消耗資源資源B B單位消耗單位消耗資源資源C C單位消耗單位消耗9 94 43 34 45 51010240240200200300300單位產(chǎn)品的價(jià)格單位產(chǎn)品的價(jià)格400400600600單位產(chǎn)品的利潤(rùn)單位產(chǎn)品的利潤(rùn)7070120120單位產(chǎn)品的污染單位產(chǎn)品的污染3 32 2第30頁(yè)/共112頁(yè)解：?jiǎn)栴}的多目標(biāo)模型如下解：?jiǎn)栴}的多目標(biāo)模型如下0,300103200542404923)(max(600400)(max12070)(max21212121213212211xxxxxxx

15、xxxXfxxXfxxXf對(duì)于此模型的三個(gè)目標(biāo)，工對(duì)于此模型的三個(gè)目標(biāo)，工廠確定利潤(rùn)最大為主要目標(biāo)。廠確定利潤(rùn)最大為主要目標(biāo)。另兩個(gè)目標(biāo)則通過(guò)預(yù)測(cè)預(yù)先另兩個(gè)目標(biāo)則通過(guò)預(yù)測(cè)預(yù)先給定的希望達(dá)到的目標(biāo)值轉(zhuǎn)給定的希望達(dá)到的目標(biāo)值轉(zhuǎn)化為約束條件。經(jīng)研究，工化為約束條件。經(jīng)研究，工廠認(rèn)為總產(chǎn)值至少應(yīng)達(dá)到廠認(rèn)為總產(chǎn)值至少應(yīng)達(dá)到2000020000個(gè)單位，而污染控制個(gè)單位，而污染控制在在9090個(gè)單位以下，即個(gè)單位以下，即9023)(20000600400)(213212xxXfxxXf第31頁(yè)/共112頁(yè)由主要目標(biāo)法化為單目標(biāo)問(wèn)題由主要目標(biāo)法化為單目標(biāo)問(wèn)題0,300103200542404990232000

16、060040012070)(max212121212121211xxxxxxxxxxxxxxXf用單純形法求得其最優(yōu)解為用單純形法求得其最優(yōu)解為90)(,20750)(,4025)(,25.26, 5 .1232121xfxfxfxx第32頁(yè)/共112頁(yè)2 2、線性加權(quán)和目標(biāo)規(guī)劃、線性加權(quán)和目標(biāo)規(guī)劃0)(0)(. .)(),.,(),()(21XhXgtsXfXfXfXoptFjiTp在上述目標(biāo)規(guī)劃中，假定在上述目標(biāo)規(guī)劃中，假定f1 1(X),(X),f2 2(X),(X),fp p(X)(X)具有具有相同的量綱相同的量綱, ,按照一定的規(guī)則分別給按照一定的規(guī)則分別給f fi i賦予相同的權(quán)賦

17、予相同的權(quán)系數(shù)系數(shù)i，作線性加權(quán)和評(píng)價(jià)函數(shù)，作線性加權(quán)和評(píng)價(jià)函數(shù)piiiXfXU1)()(第33頁(yè)/共112頁(yè)0)(0)(. .)()(max1XhXgtsXfXUjipiii則多目標(biāo)問(wèn)題化為如下的單目標(biāo)問(wèn)題則多目標(biāo)問(wèn)題化為如下的單目標(biāo)問(wèn)題第34頁(yè)/共112頁(yè)例如，某公司計(jì)劃購(gòu)進(jìn)一批新卡車，可供選擇的卡車有例如，某公司計(jì)劃購(gòu)進(jìn)一批新卡車，可供選擇的卡車有如下如下4 4種類型：種類型：A1A1，A2A2，A3A3，A4A4?，F(xiàn)考慮?，F(xiàn)考慮6 6個(gè)方案屬性：個(gè)方案屬性：維修期限維修期限f1 1，每，每100100升汽油所跑的里數(shù)升汽油所跑的里數(shù)f2 2，最大載重噸數(shù)，最大載重噸數(shù)f3 3，價(jià)格（萬(wàn)

18、元），價(jià)格（萬(wàn)元）f4 4，可靠性，可靠性f5 5，靈敏性，靈敏性f6 6。這。這4 4種型號(hào)的種型號(hào)的卡車分別關(guān)于目標(biāo)屬性的指標(biāo)值卡車分別關(guān)于目標(biāo)屬性的指標(biāo)值fijij如下表所示。如下表所示。fijf1f2f3f4f5f6A12.01500455一般一般高高A22.527003.665低低一般一般A32.020004.245高高很高很高A42.21800450很高很高一般一般首先對(duì)不同度量單位和不同數(shù)量級(jí)的指標(biāo)值進(jìn)行標(biāo)準(zhǔn)首先對(duì)不同度量單位和不同數(shù)量級(jí)的指標(biāo)值進(jìn)行標(biāo)準(zhǔn)化處理。先將定性指標(biāo)定量化：化處理。先將定性指標(biāo)定量化：第35頁(yè)/共112頁(yè)第36頁(yè)/共112頁(yè)變換后的指標(biāo)值矩陣為：變換后的指

19、標(biāo)值矩陣為：aijf1f2f3f4f5f6A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.751001第37頁(yè)/共112頁(yè)設(shè)權(quán)系數(shù)向量為設(shè)權(quán)系數(shù)向量為W=（0.2,0.1,0.1,0.1,0.2,0.3),則則925.57)(max*27.40)(925.57)(6 .40)(34)(36144613361226111XUUUaXUaXUaXUaXUjjjjjjjjjjjj故最優(yōu)方案為選購(gòu)故最優(yōu)方案為選購(gòu)A3A3型卡車型卡車第38頁(yè)/共112頁(yè)第39頁(yè)/共112頁(yè)第40頁(yè)/共112頁(yè)第41頁(yè)/共112頁(yè)第42頁(yè)/共1

20、12頁(yè)4 4、步驟法（、步驟法（STEMSTEM法）法） 這是一種交互方法，其求解過(guò)程通過(guò)分析者與決策這是一種交互方法，其求解過(guò)程通過(guò)分析者與決策者之間的對(duì)話逐步進(jìn)行，故稱步驟法。者之間的對(duì)話逐步進(jìn)行，故稱步驟法。 步驟法的基本思想是，首先需要求出原多目標(biāo)問(wèn)題步驟法的基本思想是，首先需要求出原多目標(biāo)問(wèn)題的一組理想解的一組理想解(f(f1 1* *,f,f2 2* *,f,fk k* *) )。實(shí)際上，這些解。實(shí)際上，這些解f fi i* *(i=1,2,k)(i=1,2,k)無(wú)法同時(shí)達(dá)到，但可以當(dāng)作一組理想的無(wú)法同時(shí)達(dá)到，但可以當(dāng)作一組理想的最優(yōu)值。以理想解作為一個(gè)標(biāo)準(zhǔn)，可以估計(jì)有效解，然后最

21、優(yōu)值。以理想解作為一個(gè)標(biāo)準(zhǔn)，可以估計(jì)有效解，然后通過(guò)對(duì)話，不斷修改目標(biāo)值，并把降低要求的目標(biāo)作為新通過(guò)對(duì)話，不斷修改目標(biāo)值，并把降低要求的目標(biāo)作為新的約束條件加入原來(lái)的約束條件中去重新計(jì)算，直到?jīng)Q策的約束條件加入原來(lái)的約束條件中去重新計(jì)算，直到?jīng)Q策者得到滿意的解。者得到滿意的解。第43頁(yè)/共112頁(yè)第44頁(yè)/共112頁(yè)把上述計(jì)算結(jié)果列入下表把上述計(jì)算結(jié)果列入下表*21*21*11211*121pipppppiiiiipipifzzzXzfzzXzzzfXffffX第45頁(yè)/共112頁(yè)第46頁(yè)/共112頁(yè)第47頁(yè)/共112頁(yè)例題：例題：某公司考慮生產(chǎn)兩種光電太陽(yáng)能電池：產(chǎn)品甲和某公司考慮生產(chǎn)兩種

22、光電太陽(yáng)能電池：產(chǎn)品甲和產(chǎn)品乙。這種生產(chǎn)過(guò)程會(huì)在空氣中引起放射性污染。因產(chǎn)品乙。這種生產(chǎn)過(guò)程會(huì)在空氣中引起放射性污染。因此，公司經(jīng)理有兩個(gè)目標(biāo)：極大化利潤(rùn)與極小化總的放此，公司經(jīng)理有兩個(gè)目標(biāo)：極大化利潤(rùn)與極小化總的放射性污染。已知在一個(gè)生產(chǎn)周期內(nèi)，每單位甲產(chǎn)品的收射性污染。已知在一個(gè)生產(chǎn)周期內(nèi)，每單位甲產(chǎn)品的收益是益是1 1元，每單位乙產(chǎn)品的收益是元，每單位乙產(chǎn)品的收益是3 3元。而放射性污染的元。而放射性污染的數(shù)量，每單位甲產(chǎn)品是數(shù)量，每單位甲產(chǎn)品是1.51.5個(gè)單位個(gè)單位, ,每單位乙產(chǎn)品是每單位乙產(chǎn)品是1 1個(gè)個(gè)單位單位. .由于機(jī)器能力由于機(jī)器能力( (小時(shí)小時(shí)) )、裝配能力（人時(shí)）

23、和可用、裝配能力（人時(shí)）和可用的原材料（單位）的限制，約束條件是的原材料（單位）的限制，約束條件是)(725)(42 . 02 . 0)(825. 05 . 0212121原材料裝配能力機(jī)器能力xxxxxx第48頁(yè)/共112頁(yè))(725)(42 . 02 . 0)(825. 05 . 05 . 1)(,3)()(),()(max21212121221121原材料裝配能力機(jī)器能力xxxxxxxxXfxxXfXfXfXFT目標(biāo)有兩個(gè)目標(biāo)有兩個(gè): :一是利潤(rùn)最大一是利潤(rùn)最大, ,二是污染最小二是污染最小. .該問(wèn)題該問(wèn)題的多目標(biāo)規(guī)劃模型如下的多目標(biāo)規(guī)劃模型如下: :第49頁(yè)/共112頁(yè)解解: :首先

24、首先, ,分別求解兩個(gè)單目標(biāo)問(wèn)題的最優(yōu)解分別求解兩個(gè)單目標(biāo)問(wèn)題的最優(yōu)解, ,由它們由它們得到的目標(biāo)函數(shù)值組成理想解得到的目標(biāo)函數(shù)值組成理想解. .)(725)(42 . 02 . 0)(825. 05 . 03)(max212121211原材料裝配能力機(jī)器能力xxxxxxxxXf)(725)(42 . 02 . 0)(825. 05 . 05 . 1)(max212121212原材料裝配能力機(jī)器能力xxxxxxxxXf46*)13, 7(1*1fX0*)0 , 0(1*2fX第50頁(yè)/共112頁(yè)由此由此, ,構(gòu)造支付表構(gòu)造支付表Xf1*f2*(7,13)(0,0)460-23.50由此計(jì)算兩個(gè)

25、目標(biāo)與理由此計(jì)算兩個(gè)目標(biāo)與理想值偏離的權(quán)重：想值偏離的權(quán)重：637. 0,363. 0,555. 0,316. 02121解下列線性規(guī)劃問(wèn)題解下列線性規(guī)劃問(wèn)題: :0,7254)2 . 02 . 08)25. 05 . 0)230(637. 0)346(363. 0min212121212121xxxxxxxxxxxx第51頁(yè)/共112頁(yè)第52頁(yè)/共112頁(yè)0,7254)2 . 02 . 08)25. 05 . 0192.21310)5 . 1346min21212121212121xxxxxxxxxxxxxx進(jìn)行下一輪迭代進(jìn)行下一輪迭代. .首先設(shè)首先設(shè)2 2=0,=0,并計(jì)算得并計(jì)算得1

26、1=1.=1.將將模型修改為模型修改為第53頁(yè)/共112頁(yè)由此求得由此求得: :10,3010, 02121ffxx決策者把這一結(jié)果與前一輪的解及理想值作比較決策者把這一結(jié)果與前一輪的解及理想值作比較, ,認(rèn)為兩個(gè)目標(biāo)值都比較滿意認(rèn)為兩個(gè)目標(biāo)值都比較滿意, ,則迭代結(jié)束則迭代結(jié)束. .第54頁(yè)/共112頁(yè)線線 性性 目目 標(biāo)標(biāo) 規(guī)規(guī) 劃劃 模模 型型 線性規(guī)劃問(wèn)題都是處理單個(gè)目標(biāo)的情況，但是在現(xiàn)實(shí)世線性規(guī)劃問(wèn)題都是處理單個(gè)目標(biāo)的情況，但是在現(xiàn)實(shí)世界中有許多問(wèn)題具有多個(gè)目標(biāo)，這些目標(biāo)的重要性各不界中有許多問(wèn)題具有多個(gè)目標(biāo)，這些目標(biāo)的重要性各不相同，往往有不同的量綱，有的目標(biāo)相互依賴，例如決相同，

27、往往有不同的量綱，有的目標(biāo)相互依賴，例如決策者既希望實(shí)現(xiàn)利潤(rùn)最大，又希望實(shí)現(xiàn)產(chǎn)值最大；有的策者既希望實(shí)現(xiàn)利潤(rùn)最大，又希望實(shí)現(xiàn)產(chǎn)值最大；有的相互抵觸，如決策者既希望充分利用資源，又不希望超相互抵觸，如決策者既希望充分利用資源，又不希望超越資源限量。而決策者希望在某些限制條件下，依次實(shí)越資源限量。而決策者希望在某些限制條件下，依次實(shí)現(xiàn)這些目標(biāo)。這就是目標(biāo)規(guī)劃所要解決的問(wèn)題。當(dāng)所有現(xiàn)這些目標(biāo)。這就是目標(biāo)規(guī)劃所要解決的問(wèn)題。當(dāng)所有的目標(biāo)函數(shù)和約束條件都是線性時(shí)，我們稱其為線性目的目標(biāo)函數(shù)和約束條件都是線性時(shí)，我們稱其為線性目標(biāo)規(guī)劃問(wèn)題。在這里我們主要討論線性目標(biāo)規(guī)劃問(wèn)題。標(biāo)規(guī)劃問(wèn)題。在這里我們主要討論

28、線性目標(biāo)規(guī)劃問(wèn)題。第55頁(yè)/共112頁(yè)一、線性目標(biāo)規(guī)劃模型的建立一、線性目標(biāo)規(guī)劃模型的建立 例例1 1：某一個(gè)企業(yè)利用某種原材料和現(xiàn)有設(shè)備可生某一個(gè)企業(yè)利用某種原材料和現(xiàn)有設(shè)備可生產(chǎn)甲、乙兩種產(chǎn)品，其中，甲、乙兩種產(chǎn)品的單價(jià)產(chǎn)甲、乙兩種產(chǎn)品，其中，甲、乙兩種產(chǎn)品的單價(jià)分別為分別為8 8元和元和1010元；生產(chǎn)單位甲、乙兩種產(chǎn)品需要元；生產(chǎn)單位甲、乙兩種產(chǎn)品需要消耗的原材料分別為消耗的原材料分別為2 2個(gè)單位和個(gè)單位和1 1個(gè)單位，需要占用個(gè)單位，需要占用的設(shè)備分別為的設(shè)備分別為1 1臺(tái)時(shí)和臺(tái)時(shí)和2 2臺(tái)時(shí)；原材料擁有量為臺(tái)時(shí)；原材料擁有量為1111個(gè)個(gè)單位；可利用的設(shè)備總臺(tái)時(shí)為單位；可利用的設(shè)

29、備總臺(tái)時(shí)為1010臺(tái)時(shí)。試問(wèn)：如何臺(tái)時(shí)。試問(wèn)：如何確定其生產(chǎn)方案？確定其生產(chǎn)方案？第56頁(yè)/共112頁(yè)第57頁(yè)/共112頁(yè) 但是，在實(shí)際決策時(shí)，企業(yè)領(lǐng)導(dǎo)者必須考慮市場(chǎng)但是，在實(shí)際決策時(shí)，企業(yè)領(lǐng)導(dǎo)者必須考慮市場(chǎng)等一系列其它條件，如：等一系列其它條件，如：根據(jù)市場(chǎng)信息，甲種產(chǎn)品的需求量有下降的趨勢(shì)，根據(jù)市場(chǎng)信息，甲種產(chǎn)品的需求量有下降的趨勢(shì)，因此甲種產(chǎn)品的產(chǎn)量不應(yīng)大于乙種產(chǎn)品的產(chǎn)量。因此甲種產(chǎn)品的產(chǎn)量不應(yīng)大于乙種產(chǎn)品的產(chǎn)量。超過(guò)計(jì)劃供應(yīng)的原材料，需用高價(jià)采購(gòu)，這就會(huì)使超過(guò)計(jì)劃供應(yīng)的原材料，需用高價(jià)采購(gòu)，這就會(huì)使生產(chǎn)成本增加。生產(chǎn)成本增加。應(yīng)盡可能地充分利用設(shè)備的有效臺(tái)時(shí)，但不希望加應(yīng)盡可能地充分利

30、用設(shè)備的有效臺(tái)時(shí)，但不希望加班。班。應(yīng)盡可能達(dá)到并超過(guò)計(jì)劃產(chǎn)值指標(biāo)應(yīng)盡可能達(dá)到并超過(guò)計(jì)劃產(chǎn)值指標(biāo)5656元。元。 這樣，該企業(yè)生產(chǎn)方案的確定，便成為一個(gè)多這樣，該企業(yè)生產(chǎn)方案的確定，便成為一個(gè)多目標(biāo)決策問(wèn)題，這一問(wèn)題可以運(yùn)用目標(biāo)規(guī)劃方法進(jìn)目標(biāo)決策問(wèn)題，這一問(wèn)題可以運(yùn)用目標(biāo)規(guī)劃方法進(jìn)行求解。行求解。第58頁(yè)/共112頁(yè)目標(biāo)規(guī)劃模型的有關(guān)概念第59頁(yè)/共112頁(yè)2 2、絕對(duì)約束和目標(biāo)約束、絕對(duì)約束和目標(biāo)約束 絕對(duì)約束：絕對(duì)約束：必須嚴(yán)格滿足的等式約束和不必須嚴(yán)格滿足的等式約束和不等式約束，譬如，線性規(guī)劃問(wèn)題的所有約束條等式約束，譬如，線性規(guī)劃問(wèn)題的所有約束條件都是絕對(duì)約束，不能滿足這些約束條件的解

31、件都是絕對(duì)約束，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。稱為非可行解，所以它們是硬約束。 目標(biāo)約束：目標(biāo)約束：目標(biāo)規(guī)劃所特有的，可以將目標(biāo)規(guī)劃所特有的，可以將約束方程右端項(xiàng)看作是追求的目標(biāo)值，在達(dá)到約束方程右端項(xiàng)看作是追求的目標(biāo)值，在達(dá)到此目標(biāo)值時(shí)允許發(fā)生正的或負(fù)的偏差此目標(biāo)值時(shí)允許發(fā)生正的或負(fù)的偏差 ，可加，可加入正負(fù)偏差變量，是軟約束。入正負(fù)偏差變量，是軟約束。 線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)，在給定目標(biāo)線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、負(fù)偏差變量后可以轉(zhuǎn)化為目標(biāo)約值和加入正、負(fù)偏差變量后可以轉(zhuǎn)化為目標(biāo)約束，也可以根據(jù)問(wèn)題的需要將絕對(duì)約束轉(zhuǎn)化為束，也可以根據(jù)問(wèn)題的需要將

32、絕對(duì)約束轉(zhuǎn)化為目標(biāo)約束。目標(biāo)約束。 目標(biāo)規(guī)劃模型的有關(guān)概念第60頁(yè)/共112頁(yè)目標(biāo)規(guī)劃模型的有關(guān)概念第61頁(yè)/共112頁(yè)目標(biāo)規(guī)劃模型的有關(guān)概念第62頁(yè)/共112頁(yè)b) b) 要求不超過(guò)目標(biāo)值，即允許達(dá)不到目標(biāo)要求不超過(guò)目標(biāo)值，即允許達(dá)不到目標(biāo)值，就是正偏差變量要盡可能小，即值，就是正偏差變量要盡可能小，即)(mindfZ（23） c) c) 要求超過(guò)目標(biāo)值，也就是超過(guò)量不限，要求超過(guò)目標(biāo)值，也就是超過(guò)量不限，但負(fù)偏差變量要盡可能小，即但負(fù)偏差變量要盡可能小，即 )(mindfZ（24） 在實(shí)際問(wèn)題中，可以根據(jù)決策者的要求，在實(shí)際問(wèn)題中，可以根據(jù)決策者的要求，引入正、負(fù)偏差變量和目標(biāo)約束，并給不

33、同引入正、負(fù)偏差變量和目標(biāo)約束，并給不同目標(biāo)賦予相應(yīng)的優(yōu)先因子和權(quán)系數(shù)，構(gòu)造目目標(biāo)賦予相應(yīng)的優(yōu)先因子和權(quán)系數(shù)，構(gòu)造目標(biāo)函數(shù)，建立模型。標(biāo)函數(shù)，建立模型。 第63頁(yè)/共112頁(yè)例例2 2：在例在例1 1中，如果決策者在原材料供中，如果決策者在原材料供應(yīng)受嚴(yán)格控制的基礎(chǔ)上考慮：首先是甲應(yīng)受嚴(yán)格控制的基礎(chǔ)上考慮：首先是甲種產(chǎn)品的產(chǎn)量不超過(guò)乙種產(chǎn)品的產(chǎn)量；種產(chǎn)品的產(chǎn)量不超過(guò)乙種產(chǎn)品的產(chǎn)量；其次是充分利用設(shè)備的有限臺(tái)時(shí)，不加其次是充分利用設(shè)備的有限臺(tái)時(shí)，不加班；再次是產(chǎn)值不小于班；再次是產(chǎn)值不小于5656元。并分別賦元。并分別賦予這三個(gè)目標(biāo)優(yōu)先因子予這三個(gè)目標(biāo)優(yōu)先因子 。試建立。試建立該問(wèn)題的目標(biāo)規(guī)劃模

34、型。該問(wèn)題的目標(biāo)規(guī)劃模型。321,PPP第64頁(yè)/共112頁(yè)第65頁(yè)/共112頁(yè)第66頁(yè)/共112頁(yè)在以上各式中，在以上各式中， 、 分別為賦予分別為賦予 優(yōu)先因子的第優(yōu)先因子的第 個(gè)目標(biāo)的正、負(fù)個(gè)目標(biāo)的正、負(fù)偏差變量的權(quán)系數(shù)，偏差變量的權(quán)系數(shù)， 為第為第 個(gè)目標(biāo)的預(yù)期值，個(gè)目標(biāo)的預(yù)期值， 為決策變量，為決策變量， 、 分別為第分別為第 個(gè)目標(biāo)的正、負(fù)偏差變量，個(gè)目標(biāo)的正、負(fù)偏差變量，（2525）式為目標(biāo)函數(shù)，（）式為目標(biāo)函數(shù)，（2626）式為目標(biāo)約束，（）式為目標(biāo)約束，（2727）式）式為絕對(duì)約束，（為絕對(duì)約束，（2828）式和（）式和（2929）式為非負(fù)約束，）式為非負(fù)約束， 、 、 分別

35、為目標(biāo)約束和絕對(duì)約束中決策變量的系數(shù)及約束值。分別為目標(biāo)約束和絕對(duì)約束中決策變量的系數(shù)及約束值。其中，其中， ； ； ； 。 lklklpkkgkjxkdkdk)(kjcijaibmi, 2 , 1nj, 2 , 1Ll, 2 , 1Kk, 2 , 1第67頁(yè)/共112頁(yè)圖解法求解例圖解法求解例2 2第68頁(yè)/共112頁(yè)首先考慮具有首先考慮具有 優(yōu)先因子優(yōu)先因子的目標(biāo)的實(shí)現(xiàn)，在目標(biāo)函的目標(biāo)的實(shí)現(xiàn)，在目標(biāo)函數(shù)中要求實(shí)現(xiàn)數(shù)中要求實(shí)現(xiàn) ，圖，圖中可以滿足中可以滿足 . .這時(shí)這時(shí) 的取值只能在的取值只能在OBCOBC的邊界和的邊界和內(nèi)部取得。內(nèi)部取得。 1p1mind01d21,xx接著考慮接著考慮

36、 優(yōu)先因子的優(yōu)先因子的目標(biāo)的實(shí)現(xiàn)，在目標(biāo)函目標(biāo)的實(shí)現(xiàn)，在目標(biāo)函數(shù)中要求實(shí)現(xiàn)數(shù)中要求實(shí)現(xiàn) ，當(dāng)時(shí)當(dāng)時(shí) ，其值，其值 可在線段可在線段EDED上取得。上取得。 2p)min(22 dd022dd21,xx第69頁(yè)/共112頁(yè)最后考慮最后考慮 優(yōu)先因子的目標(biāo)優(yōu)先因子的目標(biāo)的實(shí)現(xiàn)，在目標(biāo)函數(shù)中要求實(shí)的實(shí)現(xiàn)，在目標(biāo)函數(shù)中要求實(shí)現(xiàn)現(xiàn) ，當(dāng)，當(dāng) 時(shí)，其值時(shí)，其值 縮小到在線段縮小到在線段GDGD上取得上取得. .這就這就是該目標(biāo)規(guī)劃問(wèn)題的解是該目標(biāo)規(guī)劃問(wèn)題的解.G.G和和D D點(diǎn)凸組合都是此目標(biāo)規(guī)劃的解點(diǎn)凸組合都是此目標(biāo)規(guī)劃的解. .3p3mind03d21,xx注注：在目標(biāo)規(guī)劃問(wèn)題求解時(shí)，把絕對(duì)約束作最高

37、優(yōu)先級(jí)考慮。：在目標(biāo)規(guī)劃問(wèn)題求解時(shí)，把絕對(duì)約束作最高優(yōu)先級(jí)考慮。在此例中，能依先后次序都滿足在此例中，能依先后次序都滿足 因因而而 。但是大多數(shù)問(wèn)題中并非如此，還可能出現(xiàn)非可行解，。但是大多數(shù)問(wèn)題中并非如此，還可能出現(xiàn)非可行解，故將目標(biāo)規(guī)劃問(wèn)題的最優(yōu)解成為滿意解。故將目標(biāo)規(guī)劃問(wèn)題的最優(yōu)解成為滿意解。 0, 0, 03221dddd0*z第70頁(yè)/共112頁(yè)例如例如， 某電視機(jī)廠裝配黑白和彩色兩種電視機(jī)，每某電視機(jī)廠裝配黑白和彩色兩種電視機(jī)，每裝配一臺(tái)電視機(jī)需占用裝配線裝配一臺(tái)電視機(jī)需占用裝配線1 1小時(shí)，裝配線每周計(jì)劃小時(shí)，裝配線每周計(jì)劃開動(dòng)開動(dòng)4040小時(shí)。預(yù)計(jì)市場(chǎng)每周彩色電視機(jī)的銷量是小時(shí)

38、。預(yù)計(jì)市場(chǎng)每周彩色電視機(jī)的銷量是2424臺(tái)，臺(tái)，每臺(tái)可獲利每臺(tái)可獲利8080元；黑白電視的銷量是元；黑白電視的銷量是3030臺(tái)，每臺(tái)可獲臺(tái)，每臺(tái)可獲利利4040元。該廠確定的目標(biāo)為：元。該廠確定的目標(biāo)為：第一優(yōu)先級(jí)：充分利用裝配線每周計(jì)劃開動(dòng)第一優(yōu)先級(jí)：充分利用裝配線每周計(jì)劃開動(dòng)4040小時(shí)；小時(shí)；第二優(yōu)先級(jí)：允許裝配線加班，但加班時(shí)間每周盡量第二優(yōu)先級(jí)：允許裝配線加班，但加班時(shí)間每周盡量不超過(guò)不超過(guò)1010小時(shí)；小時(shí)；第三優(yōu)先級(jí)：裝配電視機(jī)的數(shù)量盡量滿足市場(chǎng)需求。第三優(yōu)先級(jí)：裝配電視機(jī)的數(shù)量盡量滿足市場(chǎng)需求。因彩色電視機(jī)的利潤(rùn)高，取其權(quán)系數(shù)為因彩色電視機(jī)的利潤(rùn)高，取其權(quán)系數(shù)為2.2.試建立此

39、問(wèn)題的目標(biāo)規(guī)劃模型，并求解黑白和彩色電試建立此問(wèn)題的目標(biāo)規(guī)劃模型，并求解黑白和彩色電視機(jī)的產(chǎn)量。視機(jī)的產(chǎn)量。第71頁(yè)/共112頁(yè)解：設(shè)解：設(shè) 分別為黑白分別為黑白和和彩色電視機(jī)的產(chǎn)量。彩色電視機(jī)的產(chǎn)量。 目標(biāo)規(guī)劃模型為目標(biāo)規(guī)劃模型為21,xx4,.,1, 0,30245040)2(min21442331222111214332211iddxxddxddxddxxddxxddpdpdpzii第72頁(yè)/共112頁(yè)從圖中可以看到，再考慮具有從圖中可以看到，再考慮具有 的目標(biāo)實(shí)現(xiàn)的目標(biāo)實(shí)現(xiàn)后，后， 的取值范圍為的取值范圍為ABCDABCD?？紤]。考慮 的目標(biāo)要求的目標(biāo)要求時(shí)，因時(shí)，因 的權(quán)系數(shù)大于的權(quán)

40、系數(shù)大于 ，故先取，故先取 。這時(shí)。這時(shí) 的取值范圍為的取值范圍為ABEFABEF。在。在ABEFABEF中，只有中，只有E E點(diǎn)使得點(diǎn)使得 取值最小，故去取值最小，故去E E點(diǎn)為滿意解。其坐標(biāo)點(diǎn)為滿意解。其坐標(biāo)為為(24,26)(24,26)，即該廠每，即該廠每周應(yīng)裝配彩色電視機(jī)周應(yīng)裝配彩色電視機(jī)2424臺(tái)，黑白電視機(jī)臺(tái)，黑白電視機(jī)2626臺(tái)。臺(tái)。21, pp21,xx3p3d4d03d21, xx4d第73頁(yè)/共112頁(yè)第74頁(yè)/共112頁(yè)所以檢驗(yàn)數(shù)的正、負(fù)首先決定于所以檢驗(yàn)數(shù)的正、負(fù)首先決定于 的系數(shù)的系數(shù) 的的正、負(fù)，若正、負(fù)，若 ，則檢驗(yàn)數(shù)的正、負(fù)就決定于，則檢驗(yàn)數(shù)的正、負(fù)就決定于

41、的系數(shù)的系數(shù) 的正、負(fù)，下面可依此類推。的正、負(fù)，下面可依此類推。1pj101j2pj2 據(jù)此，我們可以總結(jié)出求解目標(biāo)規(guī)劃問(wèn)題的單純據(jù)此，我們可以總結(jié)出求解目標(biāo)規(guī)劃問(wèn)題的單純形方法的計(jì)算步驟如下：形方法的計(jì)算步驟如下：建立初始單純形表，在表中將檢驗(yàn)數(shù)行按優(yōu)先因建立初始單純形表，在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個(gè)數(shù)分別排成子個(gè)數(shù)分別排成L L行，置行，置 。 1l第75頁(yè)/共112頁(yè)檢查該行中是否存在負(fù)數(shù)，且對(duì)應(yīng)的前檢查該行中是否存在負(fù)數(shù)，且對(duì)應(yīng)的前L-1L-1行行的系數(shù)是零。若有，取其中最小者對(duì)應(yīng)的變量為的系數(shù)是零。若有，取其中最小者對(duì)應(yīng)的變量為換入變量，轉(zhuǎn)。若無(wú)負(fù)數(shù)，則轉(zhuǎn)。換入變量，轉(zhuǎn)。若無(wú)負(fù)數(shù)，

42、則轉(zhuǎn)。按最小比值規(guī)則（按最小比值規(guī)則（ 規(guī)則）確定換出變量，當(dāng)規(guī)則）確定換出變量，當(dāng)存在兩個(gè)和兩個(gè)以上相同的最小比值時(shí)，選取具存在兩個(gè)和兩個(gè)以上相同的最小比值時(shí)，選取具有較高優(yōu)先級(jí)別的變量為換出變量。有較高優(yōu)先級(jí)別的變量為換出變量。按單純形法進(jìn)行基變換運(yùn)算，建立新的計(jì)算表，按單純形法進(jìn)行基變換運(yùn)算，建立新的計(jì)算表，返回。返回。當(dāng)當(dāng)l=Ll=L時(shí)，計(jì)算結(jié)束，表中的解即為滿意解。時(shí)，計(jì)算結(jié)束，表中的解即為滿意解。否則置否則置l=l+1l=l+1，返回，返回 。第76頁(yè)/共112頁(yè)例例3 3：試用單純形法求解例試用單純形法求解例2 2所描述的目標(biāo)規(guī)劃問(wèn)題所描述的目標(biāo)規(guī)劃問(wèn)題解：首先將這一問(wèn)題化為如下

43、標(biāo)準(zhǔn)形式：解：首先將這一問(wèn)題化為如下標(biāo)準(zhǔn)形式： 3322211)(mindpddpdpZ112. .321xxxts01121ddxx1022221ddxx561083321ddxx)3 , 2 , 1(0,iddxiii第77頁(yè)/共112頁(yè)取取 、 、 、 為初始基變量，列出初為初始基變量，列出初始單純形表。始單純形表。表13x1d2d3d第78頁(yè)/共112頁(yè) 取取 ，檢查檢驗(yàn)數(shù)的，檢查檢驗(yàn)數(shù)的 行，因該行無(wú)負(fù)檢驗(yàn)行，因該行無(wú)負(fù)檢驗(yàn)數(shù)，故轉(zhuǎn)。數(shù)，故轉(zhuǎn)。 因?yàn)橐驗(yàn)?，置，置 ，返回。，返回。 檢查發(fā)現(xiàn)檢驗(yàn)數(shù)檢查發(fā)現(xiàn)檢驗(yàn)數(shù) 行中有行中有 ， ，因?yàn)橛?，因?yàn)橛?，所以，所以 為換入變量，轉(zhuǎn)入。為換

44、入變量，轉(zhuǎn)入。 1l1p31Ll21ll2p1222, 1min2x 按按 規(guī)則計(jì)算：規(guī)則計(jì)算： ，所以，所以 為換為換出變量，轉(zhuǎn)入。出變量，轉(zhuǎn)入。 進(jìn)行換基運(yùn)算，得到表進(jìn)行換基運(yùn)算，得到表2 2。以此類推，直至得到。以此類推，直至得到最終單純形表為止，如表最終單純形表為止，如表3 3所示。所示。 2101056,210,111min2d第79頁(yè)/共112頁(yè)表2第80頁(yè)/共112頁(yè)表3由表由表3 3可知，可知， ， ，為滿意解。檢查，為滿意解。檢查檢驗(yàn)數(shù)行，發(fā)現(xiàn)非基變量的檢驗(yàn)數(shù)為檢驗(yàn)數(shù)行，發(fā)現(xiàn)非基變量的檢驗(yàn)數(shù)為0 0，這表，這表明該問(wèn)題存在多重解。明該問(wèn)題存在多重解。2*1x42x第81頁(yè)/共

45、112頁(yè)表表4 4在表在表3 3中，以非基變量中，以非基變量 為換入變量，為換入變量， 為換出變量，為換出變量，經(jīng)迭代得到表經(jīng)迭代得到表4 4。 3d1d 從表從表4 4可以看出，可以看出， ， 也是該也是該問(wèn)題的滿意解。問(wèn)題的滿意解。 3/101x3/102x第82頁(yè)/共112頁(yè) 案例（提級(jí)加新問(wèn)題） 某公司的員工工資有四級(jí)，根據(jù)公司某公司的員工工資有四級(jí)，根據(jù)公司的業(yè)務(wù)發(fā)展情況，準(zhǔn)備招收部分新員工，并將部分員工的工的業(yè)務(wù)發(fā)展情況，準(zhǔn)備招收部分新員工，并將部分員工的工資提升一級(jí)。該公司的員工工資及提級(jí)前后的編制表如下，資提升一級(jí)。該公司的員工工資及提級(jí)前后的編制表如下，其中提級(jí)后編制是計(jì)劃編

46、制，允許有變化，其中其中提級(jí)后編制是計(jì)劃編制，允許有變化，其中1 1級(jí)員工中有級(jí)員工中有8%8%要退休。公司領(lǐng)導(dǎo)的目標(biāo)如下：要退休。公司領(lǐng)導(dǎo)的目標(biāo)如下：1 1）提級(jí)后在職員工的工資總額不超過(guò)）提級(jí)后在職員工的工資總額不超過(guò)550550千元；千元；2 2）各級(jí)員工不要超過(guò)定編人數(shù)；）各級(jí)員工不要超過(guò)定編人數(shù)；3)3)為調(diào)動(dòng)積極性，各級(jí)員工的升級(jí)面不少于現(xiàn)有人數(shù)的為調(diào)動(dòng)積極性，各級(jí)員工的升級(jí)面不少于現(xiàn)有人數(shù)的18%18%；4 4）總提級(jí)面不大于）總提級(jí)面不大于20%20%，但盡可能多提；，但盡可能多提；5 5）4 4級(jí)不足編制人數(shù)可錄用新工人。級(jí)不足編制人數(shù)可錄用新工人。 第83頁(yè)/共112頁(yè)問(wèn)：

47、應(yīng)如何擬定一具滿意的方案，才能接近上述目標(biāo)？問(wèn)：應(yīng)如何擬定一具滿意的方案，才能接近上述目標(biāo)？ 級(jí)別級(jí)別1 12 23 34 4工資（千元）工資（千元）8 86 64 43 3現(xiàn)有員工數(shù)現(xiàn)有員工數(shù)1010202040403030編制員工數(shù)編制員工數(shù)1010222252523030解：（解：（1 1）決策變量：設(shè)）決策變量：設(shè)x x1 1, ,x x2 2, ,x x3 3, ,x x4 4分別表示提升到分別表示提升到1 1，2 2，3 3級(jí)和新錄用的員工數(shù)。級(jí)和新錄用的員工數(shù)。 偏差變量：偏差變量：d di i+, +, d di i- -為各目標(biāo)的正、負(fù)偏差變量。為各目標(biāo)的正、負(fù)偏差變量。 （

48、2 2）約束條件：）約束條件：1 1） 提級(jí)后在職員工的工資總額不超過(guò)提級(jí)后在職員工的工資總額不超過(guò)550550千元；千元；8(10-10 8%+x1)+6(20-x1+x2)+4(40-x2+x3)+ 3(30-x3+x4)+ d1-d1+=550 第84頁(yè)/共112頁(yè) 2）各級(jí)員工不要超過(guò)定編人數(shù)各級(jí)員工不要超過(guò)定編人數(shù) 1級(jí)有：級(jí)有： 10-10 8%+x1+d2-d2+=10 2級(jí)有：級(jí)有： 20-x1+ x2+d3-d3+=22 3級(jí)有：級(jí)有： 40-x2+ x3+d4-d4+=52 4級(jí)有：級(jí)有： 30-x3+ x4+d5-d5+=303）各級(jí)員工的升級(jí)面不少于現(xiàn)有人數(shù)的各級(jí)員工的

49、升級(jí)面不少于現(xiàn)有人數(shù)的18% 對(duì)對(duì)2級(jí)有：級(jí)有： x1+d6-d6+=22 18% 對(duì)對(duì)3級(jí)有：級(jí)有： x2+d7-d7+=40 18% 對(duì)對(duì)4級(jí)有：級(jí)有： x3+d8-d8+=30 18% 4）總提級(jí)面人數(shù)不大于總提級(jí)面人數(shù)不大于20%，但盡可能多提，但盡可能多提 x1+ x2+ x3+d9-d9+=100 20% 第85頁(yè)/共112頁(yè))()()(min99487635432211ddpdddpddddpdpZ99487635432211minminminminddZdddZddddZdZ（3 3）目標(biāo)函數(shù)：）目標(biāo)函數(shù)：或者：或者：第86頁(yè)/共112頁(yè)五、五、層層 次次 分分 析析 法法（一

50、）層次分析法的基本原理（一）層次分析法的基本原理 層次分析法，又稱層次分析法，又稱AHP(Analytic AHP(Analytic Hirrarchy Process)Hirrarchy Process)方法，是美國(guó)運(yùn)籌學(xué)家薩蒂方法，是美國(guó)運(yùn)籌學(xué)家薩蒂(T.Saaty)(T.Saaty)提出的一種多目標(biāo)、多準(zhǔn)則的決策分提出的一種多目標(biāo)、多準(zhǔn)則的決策分析方法。該方法被廣泛應(yīng)用于工程、經(jīng)濟(jì)、軍事析方法。該方法被廣泛應(yīng)用于工程、經(jīng)濟(jì)、軍事、政治、外交等領(lǐng)域，解決了諸如系統(tǒng)評(píng)價(jià)、資、政治、外交等領(lǐng)域，解決了諸如系統(tǒng)評(píng)價(jià)、資源分配、價(jià)格預(yù)測(cè)、項(xiàng)目選擇等許多重要問(wèn)題，源分配、價(jià)格預(yù)測(cè)、項(xiàng)目選擇等許多重要

51、問(wèn)題，是一種定量分析與定性分析相結(jié)合的有效方法。是一種定量分析與定性分析相結(jié)合的有效方法。第87頁(yè)/共112頁(yè)用層次分析法作決策分析，首先要把問(wèn)題層用層次分析法作決策分析，首先要把問(wèn)題層次化。根據(jù)問(wèn)題的性質(zhì)和要達(dá)到的總目標(biāo)，次化。根據(jù)問(wèn)題的性質(zhì)和要達(dá)到的總目標(biāo)，將問(wèn)題分解為不同的組成因素，并按照因素將問(wèn)題分解為不同的組成因素，并按照因素間的相互影響以及隸屬關(guān)系按不同層次聚集間的相互影響以及隸屬關(guān)系按不同層次聚集組合，形成一個(gè)多層次的分析結(jié)構(gòu)模型。最組合，形成一個(gè)多層次的分析結(jié)構(gòu)模型。最終把系統(tǒng)分析歸結(jié)為最低層（如決策方案）終把系統(tǒng)分析歸結(jié)為最低層（如決策方案）相對(duì)于最高層（總目標(biāo)）的相對(duì)重要性

52、權(quán)值相對(duì)于最高層（總目標(biāo)）的相對(duì)重要性權(quán)值的確定或相對(duì)優(yōu)劣次序的排序問(wèn)題，從而為的確定或相對(duì)優(yōu)劣次序的排序問(wèn)題，從而為決策方案的選擇提供依據(jù)。決策方案的選擇提供依據(jù)。第88頁(yè)/共112頁(yè) （二（二) )層次分析法大體分為六個(gè)步驟層次分析法大體分為六個(gè)步驟1 1）明確問(wèn)題：為了運(yùn)用）明確問(wèn)題：為了運(yùn)用AHPAHP進(jìn)行系統(tǒng)分析，首先要對(duì)問(wèn)題進(jìn)行系統(tǒng)分析，首先要對(duì)問(wèn)題有明確的認(rèn)識(shí)，弄清問(wèn)題范圍、所包含的因素及其相互關(guān)有明確的認(rèn)識(shí)，弄清問(wèn)題范圍、所包含的因素及其相互關(guān)系、解決問(wèn)題的目的、是否具有系、解決問(wèn)題的目的、是否具有AHPAHP所描述的特征。所描述的特征。2 2）建立層次結(jié)構(gòu)模型：將問(wèn)題中所包含

53、的因素劃分為不）建立層次結(jié)構(gòu)模型：將問(wèn)題中所包含的因素劃分為不同層次。例如，對(duì)于決策問(wèn)題，通?？梢詣澐譃橄旅鎺讉€(gè)同層次。例如，對(duì)于決策問(wèn)題，通?？梢詣澐譃橄旅鎺讉€(gè)層次：層次：最高層：表示解決問(wèn)題的目的，稱為目標(biāo)層。最高層：表示解決問(wèn)題的目的，稱為目標(biāo)層。中間層：表示采取某種措施或政策實(shí)現(xiàn)預(yù)定目標(biāo)的涉及的中間層：表示采取某種措施或政策實(shí)現(xiàn)預(yù)定目標(biāo)的涉及的中間環(huán)節(jié)，一般又分為策略層、準(zhǔn)則層等。中間環(huán)節(jié)，一般又分為策略層、準(zhǔn)則層等。最低層：表示解決問(wèn)題的措施或方案，稱為措施層或方案最低層：表示解決問(wèn)題的措施或方案，稱為措施層或方案層。如下圖所示。層。如下圖所示。第89頁(yè)/共112頁(yè)決策目標(biāo)準(zhǔn)則1準(zhǔn)則

54、1準(zhǔn)則m子準(zhǔn)則1子準(zhǔn)則2子準(zhǔn)則k方案1方案2方案n目標(biāo)層準(zhǔn)則層子準(zhǔn)則層方案層第90頁(yè)/共112頁(yè)3 3）構(gòu)造判斷矩陣）構(gòu)造判斷矩陣針對(duì)上一層某元素，對(duì)每一層次各個(gè)元素的相對(duì)重要性進(jìn)針對(duì)上一層某元素，對(duì)每一層次各個(gè)元素的相對(duì)重要性進(jìn)行兩兩比較，并給出判斷。這些判斷用數(shù)值表示出來(lái)，寫行兩兩比較，并給出判斷。這些判斷用數(shù)值表示出來(lái)，寫成矩陣形式，即所謂的判斷矩陣。成矩陣形式，即所謂的判斷矩陣。nnnnnnnnkbbbBbbbBbbbBBBA2122221211211121B其中其中b bijij表示對(duì)于表示對(duì)于A Ak k而言，而言，B Bi i對(duì)對(duì)B Bj j的相對(duì)重要性，通常的相對(duì)重要性，通常b

55、 bijij取取1,2,91,2,9及它們的倒數(shù)，其含義為：及它們的倒數(shù)，其含義為：第91頁(yè)/共112頁(yè)1 1表示表示B Bi i與與B Bj j相比，兩者重要性相同相比，兩者重要性相同3 3表示表示B Bi i比比B Bj j稍重要稍重要5 5表示表示B Bi i比比B Bj j重要重要7 7表示表示B Bi i比比B Bj j強(qiáng)烈重要強(qiáng)烈重要9 9表示表示B Bi i比比B Bj j極端重要極端重要它們之間的數(shù)它們之間的數(shù)2 2，4 4，6 6，8 8及各數(shù)的倒數(shù)有相應(yīng)的類似意義及各數(shù)的倒數(shù)有相應(yīng)的類似意義。顯然，對(duì)判斷矩陣有。顯然，對(duì)判斷矩陣有).,2 , 1,( , 1,1njibbb

56、iijiij因此，對(duì)于因此，對(duì)于n n階判斷矩陣，我們僅需對(duì)階判斷矩陣，我們僅需對(duì)n(n-1)/2n(n-1)/2個(gè)元素給個(gè)元素給出數(shù)值。出數(shù)值。第92頁(yè)/共112頁(yè)4 4）層次單排序及其一致性檢驗(yàn)）層次單排序及其一致性檢驗(yàn) 所謂層次單排序，即把同一層次相應(yīng)元素對(duì)于上一所謂層次單排序，即把同一層次相應(yīng)元素對(duì)于上一層次某元素相對(duì)重要性的排序權(quán)值求出來(lái)。其方法是計(jì)算層次某元素相對(duì)重要性的排序權(quán)值求出來(lái)。其方法是計(jì)算判斷矩陣判斷矩陣A A的滿足等式的滿足等式 的最大特征值的最大特征值 和對(duì)應(yīng)的特征向量和對(duì)應(yīng)的特征向量W W，這個(gè)特征向量就是單排序權(quán)值。，這個(gè)特征向量就是單排序權(quán)值。WAWmaxmax

57、 可以證明，對(duì)于可以證明，對(duì)于n n階判斷矩陣，其最大特征根階判斷矩陣，其最大特征根 為單根，且為單根，且 ， 所對(duì)應(yīng)的特征向量均由正數(shù)所對(duì)應(yīng)的特征向量均由正數(shù)組成。特別，當(dāng)判斷矩陣具有完全一致性時(shí)組成。特別，當(dāng)判斷矩陣具有完全一致性時(shí), ,有有 這里，所謂完全一致性是指對(duì)于判斷矩陣來(lái)說(shuō)，存在這里，所謂完全一致性是指對(duì)于判斷矩陣來(lái)說(shuō)，存在maxnmaxmaxnmax),.,2 , 1,(nkjibbbjkikij第93頁(yè)/共112頁(yè)1.451.451.411.411.321.321.241.241.121.120.900.900.850.850.000.000.000.00RIRI9 98 8

58、7 76 65 54 43 32 21 1階數(shù)階數(shù)為檢驗(yàn)判斷矩陣的一致性，需要計(jì)算一致性指標(biāo)為檢驗(yàn)判斷矩陣的一致性，需要計(jì)算一致性指標(biāo)1maxnnCI此外，還需要判斷矩陣的平均隨機(jī)一致性指標(biāo)此外，還需要判斷矩陣的平均隨機(jī)一致性指標(biāo)RIRI。對(duì)于。對(duì)于1 1至至9 9階矩陣，階矩陣，RIRI的值如下表。的值如下表。 在這里，對(duì)于在這里，對(duì)于1,21,2階判斷矩陣，階判斷矩陣，RIRI只是形式上的，只是形式上的，因?yàn)橐驗(yàn)? 1，2 2階判斷矩陣總具有完全一致性，當(dāng)階數(shù)大于階判斷矩陣總具有完全一致性，當(dāng)階數(shù)大于2 2時(shí)時(shí)，判斷矩陣的一致性指標(biāo)，判斷矩陣的一致性指標(biāo)CICI與同階平均隨機(jī)一致性指標(biāo)與同

59、階平均隨機(jī)一致性指標(biāo)RIRI之比稱謂隨機(jī)一致性比率，記為之比稱謂隨機(jī)一致性比率，記為CRCR，CR=CI/RI0.10CR=CI/RI0.10時(shí)，時(shí)，即認(rèn)為判斷矩陣具有滿意的一致性，否則就需要調(diào)整判斷即認(rèn)為判斷矩陣具有滿意的一致性，否則就需要調(diào)整判斷矩陣，使其具有滿意的一致性。矩陣，使其具有滿意的一致性。第94頁(yè)/共112頁(yè)5 5）層次總排序）層次總排序 計(jì)算同一層次所有元素對(duì)于最高層相對(duì)重計(jì)算同一層次所有元素對(duì)于最高層相對(duì)重要性的排序權(quán)值，稱為層次總排序。這一過(guò)程是要性的排序權(quán)值，稱為層次總排序。這一過(guò)程是最高層次到最低層次逐層進(jìn)行的。若上一層次最高層次到最低層次逐層進(jìn)行的。若上一層次A A

60、包包含含m m個(gè)元素個(gè)元素A A1 1,A,A2 2,A,Am m，其層次總排序權(quán)值分別為，其層次總排序權(quán)值分別為a a1 1,a,a2 2,a,am m，下一層次，下一層次B B包含包含n n個(gè)元素個(gè)元素B B1 1,B,B2 2,B,Bn n，它們對(duì)于元素它們對(duì)于元素A Aj j的層次單排序權(quán)值分別為的層次單排序權(quán)值分別為b b1j1j,b,b2j2j,b,bnjnj（當(dāng)（當(dāng)B Bk k與與A Aj j無(wú)關(guān)系時(shí)無(wú)關(guān)系時(shí),b,bkjkj=0=0），此時(shí)），此時(shí)，層次總排序權(quán)值為，層次總排序權(quán)值為第95頁(yè)/共112頁(yè)B B層次總排序權(quán)重層次總排序權(quán)重層次層次mAAA21maaa21nBBB21