(5.3.12)-2.6多目標規(guī)劃數(shù)學建模

腳本——多目標規(guī)劃(ppt,ppt2)同學，你好！這節(jié)課我們來學習規(guī)劃模型的最后一個問題，多目標規(guī)劃問題。(ppt3)先來講解一下多目標規(guī)劃問題的數(shù)學模型。(ppt4)（動畫1）前面所討論的都是只有一個目標函數(shù)的數(shù)學規(guī)劃模型，但在實際問題中往往還會經(jīng)常遇到多個目標函數(shù)的問題，即多目標規(guī)劃模型。例如，在生產(chǎn)產(chǎn)品時，可能既要考慮利潤最大又要考慮材料最省等等。(ppt5)（動畫1）解決問題的關(guān)鍵是將多目標化規(guī)劃問題化為單目標規(guī)劃問題來處理。（動畫2）多目標規(guī)劃問題的數(shù)學模型一般形式為：????????_??(??_??,??_??,?,??_??)，一直到????????_??(??_??,??_??,?,??_??)。約束條件為??_??(??_??,??_??,?,??_??)≥??，??_??(??_??,??_??,?,??_??)=??。（動畫3）記F(X)等于??_??(??),??_??(??),?,??_??(??)組成向量的轉(zhuǎn)置。（動畫4）聯(lián)立目標函數(shù)和約束條件，則可以得到多目標規(guī)劃模型。(ppt6)下面我們來求解多目標規(guī)劃問題。(ppt7)（動畫1）先來講第一種方法：約束法。（動畫2）根據(jù)問題的實際意義，從多規(guī)劃問題的??個目標中，選取一個主要的目標作為單目標規(guī)劃問題的目標函數(shù)，例如就取??_1(??)作為單目標規(guī)劃問題的目標函數(shù)，其他的目標函數(shù)只要它不超過某個給定的數(shù)即可，那么就可以化為如下的單目標規(guī)劃模型：????????_??(??),約束條件為??_??(??)≥??；??_??(??)=??；??_??(??)≤??_??。(ppt8)（動畫1）第二種方法：分層序列法。（動畫2）根據(jù)實際問題的需要，將其??個目標按重要程度排一個次序，最重要的排在最前面，依此排下去，并選取一組適當小的正數(shù)??_1,??_2,?,??_(???1)，逐層次的求解。（動畫3）例如，若??個目標的重要程度排序為??_1(??),??_2(??),?,??_??(??)，則先求出????????_??(??)=??_??星。（動畫3）再在第一個目標函數(shù)求出的X的范圍下，求f_2(x)得最小值f_2星。同樣的求解f_3(x)得最小值。一次下去，最后求得f_m(x)在第(m-1)個目標函數(shù)求出的范圍下的最小值，記為f_m星。(ppt9)（動畫1）第三種方法功效系數(shù)法。（動畫2）對于多目標規(guī)劃問題，有時候目標函數(shù)的量綱不一致，直接計算沒有什么意義，計算出的結(jié)果也無法判別其最優(yōu)性，為此，就用功效系數(shù)來判別目標的好壞程度。（動畫3）設(shè)f_j(x)的最小值為f_j，最大值為??

???。（動畫4）當目標為f_j(x)的最小值時，定義功效函數(shù)為：當f_j(x)等于其最小值時，d_j等于1；當f_j(x)等于其最大值時，d_j等于0；當f_j(x)位于其最大值和最小值之間時，d_j等于最大值減去最小值分之最大值減去f_j(x)。(ppt10)（動畫1）當目標為f_j(x)的最大值時，類似的定義功效函數(shù)如下所示。（動畫2）上面定義的??_??(??_??(??))是??_??(??)的嚴格單調(diào)的線性函數(shù)，最“滿意”時，??_??=1，最“不滿意”時，??_??=0，一般情況下就是0<??_??<1，功效系數(shù)??_??較好的反映了??_??(??)逼近最優(yōu)解的程度，然后我們考慮所有目標函數(shù)的功效系數(shù)的幾何平均數(shù)：??(??(??))等于d_1到d_m的連乘的m分之1次方。（動畫3）并求解滿足其最大值的最優(yōu)解。(ppt11)（動畫1）第四種方法，評價函數(shù)法。（動畫2）先構(gòu)造一個與所有目標函數(shù)有關(guān)的函數(shù)，然后求相應的單目標規(guī)劃問題的最優(yōu)解。（動畫3）第一個乘除法。（動畫4）設(shè)在目標函數(shù)中要求??_1,??_2,?,??_??越小越好，??_(??+1),??_(??+2),?,??_??越大越好，且??_??(??)>0，(??=1,2,?,??)，可以構(gòu)造評價函數(shù)：??(??(??))=f_1(x)到f_r(x)的連乘除以f_(r+1)(x)到f_m(x)的連乘。求解??(??(??))的最小值。(ppt12)（動畫1）第二個、平方和加權(quán)法。（動畫2）對于給定的多目標規(guī)劃問題，設(shè)??_??(??)的最小值的下界為??_j0，即f_j(x)的最小值大于等于f_j0。（動畫3）根據(jù)實際問題，考慮??_1(??),??_2(??),?,??_??(??)的不同重要程度，確定一組權(quán)系數(shù)??_1≥0,??_2≥0,???_??≥0，且??_??求和等于1，做評價函數(shù)：??(??(??))=??_??(??_??(??)???_??^??)的平方求和。（動畫4）然后求解單目標規(guī)劃問題：??(??(??))的最小值。(ppt13)（動畫1）第三個、線性權(quán)和法。（動畫2）對于給定的多目標規(guī)劃問題，根據(jù)??個目標函數(shù)考慮├??_1(??),??_2(??),?,??_??(??)的不同重要程度，確定一組權(quán)系數(shù)??_1≥0,??_2≥0,???_??≥0，且??_??求和等于1，做評價函數(shù)：??(??(??))=??_??*f_j(x)求和。（動畫3）然后求解單目標規(guī)劃問題：??(??(??))的最小值。（動畫4）在線性權(quán)和法中，若某些權(quán)系數(shù)取值為0，則相應的目標函數(shù)在最終目標中的重要性得不到體現(xiàn)，則可以給定這些函數(shù)一個取值范圍，將它作為一個約束條件加入最終目標規(guī)劃問題。這相當于前面已經(jīng)敘述過的約束法。(ppt14)（動畫1）在平方和加權(quán)法和線性權(quán)和法中，都涉及到權(quán)系數(shù)，那么權(quán)系數(shù)要如何確定才算是比較合理呢？(ppt15)（動畫1）我們來看權(quán)系數(shù)確定方法中的第一種，阿爾法方法。（動畫2）對給定的多目標規(guī)劃模型，設(shè)??_??(??^??)取極小值。然后求出各目標函數(shù)在??^??處的函數(shù)值。（動畫3）由定義可知??_????=??_??(??^??)大于等于??_??(??^??)。在此我們不妨假設(shè)??^??只是??_??(??)的極小點，不是其他函數(shù)??_??(??)的極小點。（動畫4）現(xiàn)在我們引進參數(shù)??，并作如下??+1階線性方程：??_????*??_??，i從1到m求和等于阿爾法。??_??從1到m求和d等于1。（動畫5）解方程組，即可以求出權(quán)系數(shù)向量??=(??_1,??_2,???_??)。(ppt16)（動畫1）第二中權(quán)系數(shù)確定方法：均差排序法。（動畫2）設(shè)??_??(??)在??上的極小點為??^??。利用這??個極小點，可以求出第??個目標關(guān)于其他極小點的離差:??_????=??_??(??^??)???_??(??^??)，??,??,=1,2,?,??.（動畫3）特別地當??=??時，有??_????=0。其他的離差因為??^??為??_??(??)的極小點，故有??_????≥0。（動畫4）設(shè)各??^??(??=1,2,?,??)不全相同，則至少有一個??≠??使得??_????>0，令Detai等于??_????，j從1到m求和除以(m-1)，（動畫5）我們將Detai從大到小排序，可以得到??_??等于deta(m+1-i)除以detaj，j從1到m求和。（動畫6）向量??=(??_1,??_2,?,??_??)^??就是我們確定的權(quán)向量。(ppt17)（動畫1）第三種權(quán)系數(shù)確定法：判斷矩陣法。（動畫2）當某個問題需要確定的權(quán)系數(shù)的項數(shù)非常多時，就難于對所有各項的重要程度作一個比較準確的把握和較正確的判斷。但兩兩各項之間的重要程度比較判別，我們就用下面的矩陣判別法來確定權(quán)系數(shù)。（動畫3）設(shè)??_????=1表示事項??_??相對于??_??同等重要；類似的可以得到a_ij等于23……的情況。(ppt18)（動畫1）為了確定權(quán)系數(shù)，作判斷矩陣??=(??_????)，其中??_????=??_????分之1，??_????=1,(??,??=1,2,?,??)。（動畫2）對于??中的每一行作幾何平均，得到阿爾法_??，然后將向量??=(??_1,??_2,?,??_??)^??規(guī)范化，得到問題的一組權(quán)系數(shù)??_??等于阿爾法i除以阿爾法j，j從1到m求和。(ppt19)我們來看一個案例分析了解一下多目標規(guī)劃。(ppt20)某學校規(guī)定,運籌學專業(yè)的學生畢業(yè)時必須至少學習過兩門數(shù)學課三門運籌學課和兩門計算機課.這些課程的編號名稱、學分、所屬類別和先修課要求如下表所示。那么畢業(yè)時學生最少可以學習這些課程中的哪些課程?如果某個學生既希望選修課程的數(shù)少，又希望所獲得的學分多，他可以選修哪些課程?（ppt21）（動畫1）用??_??=1表示選修表中按編號順序的9門課程（??_??=0）表示不選"；"??=1,2,3,4,5,6,7,8,9問題的目標為選修課的課程總數(shù)最少，即min??=x_i求和。（動畫2）約束條件有兩個，分別為：1.每人最少學習2門數(shù)學課、3門運籌學和2門計算機課，相應的表達式如下。(ppt22)（動畫1）2.部分課程有先修課要求，可表示為如下約束。（動畫2）如果一個學生既希望選修課程數(shù)少,又希望所獲得的學分數(shù)盡可能多,則除了目標課程要求之外,還應根據(jù)表的學分數(shù)寫出另一個目標,即????????=????_??+????_??+????_??+????_??+????_??+????_??+????_??+????_??+????_??。(ppt23)（動畫1）要得到多目標規(guī)劃問題的解，通常需要知道決策者對每個目標的重視程度，稱為偏好程度。下面通過幾個例子討論處理這類問題的方法。（動畫2）1.同學甲只考慮獲得盡可能多的學分，而不管所修課程的多少，那么他可以不用考慮課程目標,這就變成了一個單目標優(yōu)化問題。顯然，這個問題不必計算就知道最優(yōu)解是選修所有9門課程。(ppt24)（動畫1）2.同學乙認為選修課程數(shù)最少是基本的前提，那么他可以不考慮學分目標，這就是前面得到的，最少為6門。如果這個解是惟一的，則他已別無選擇，只能選修上面的6門課，總學分為21。但他還可能在選修6門課的條件下，使總學分多于21。為探索這種可能，應在上面的規(guī)劃問題中增加約束：x_i求和等于6。（動畫2）綜上，此情況下的最優(yōu)解??_1=??_2=??_3=??_5=??_7=??_9=1，其他變量為0，共22個學分。(ppt25)（動畫1）3.同學丙不像甲、乙那樣,只考慮學分最多或以課程最少為前提，而是覺得學分數(shù)和課程數(shù)這兩個目標大致上應該三七開，這時有????????=??.???????.????。（動畫2）此種情況下的最優(yōu)解為??_1=??_2=??_3=??_4=??_5=??_6=??_7=??_9=1只有預測理論不需選修，共28個學分。(ppt26)（動畫1）實際上,0.7和0.3是??和???的權(quán)重，一般地，將權(quán)重記作??_1,??_2且令??_1+??_2=1，0≤??_1，??_2≤1則規(guī)劃模型的新目標為：????????=??_???????_????。（動畫2）前面同學甲的考慮相當于??_1=0,??