多目標規劃

多目標規劃

多目標規劃是數學規劃的一個分支。研究多於一個的目標函式在給定區域上的最最佳化。又稱多目標最最佳化。通常記為 MOP(multi-objective programming)。 多目標規劃的概念是 1961年由美國數學家查爾斯和庫柏首先提出的。多目標最最佳化思想,最早是在1896年由法國經濟學家V.帕雷托提出來的。他從政治經濟學的角度考慮把本質上是不可比較的許多目標化成單個目標的最 最佳化問題,從而涉及了多目標規劃問題和多目標的概念。

基本定義

多目標規劃

multiple objectives programming

多目標規劃 多目標規劃

數學規劃 的一個分支。研究多於一個目標函式在給定區域上的最最佳化。又稱多目標最最佳化。通常記為 VMP。在很多實際問題中,例如經濟、管理、軍事、科學和工程設計等領域,衡量一個方案的好壞往往難以用一個指標來判斷,而需要用多個目標來比較,而 這些目標有時不甚協調,甚至是矛盾的。因此有許多學者致力於這方面的研究。1896年法國經濟學家 V.帕雷托最早研究不可比較目標的最佳化問題 ,之後,J.馮·諾伊曼 、H.W.庫恩、A.W.塔克爾、A.M.日夫里翁等數學家做了深入的探討,但是尚未有一個完全令人滿意的定義。求解多目標規劃的方法大體上有以下幾種:一種是化多為少的方法 , 即把多目標 化為比較容易求解的單目標或雙目標,如主要目標法、線性加權法、理想點法等;另一種叫分層序列法,即把目標按其重要性給出一個序列,每次都在前一目標最優 解集內求下一個目標最優解,直到求出共同的最優解。對多目標的線性規劃除以上方法外還可以適當修正單純形法來求解;還有一種稱為層次分析法,是由美國運籌 學家沙旦於70年代提出的,這是一種定性與定量相結合的多目標決策與分析方法,對於目標結構複雜且缺乏必要的數據的情況更為實用。

規劃簡史

數學規劃 數學規劃

1947年,J.馮·諾伊曼和O.莫根施特恩從對策論的角度提出了有多個決策者在彼此有矛盾的情況下 的多目標問題。1951年,T.C.庫普曼斯從生產和分配的活動中提出多目標最最佳化問題,引入有效解的概念,並得到一些基本結果。同年,H.W.庫恩和 A.W.塔克爾從研究數學規劃的角度提出向量極值問題,引入庫恩-塔克爾有效解概念,並研究了它的必要和充分條件。1963年,L.A.扎德從控制論方面 提出多指標最最佳化問題,也給出了一些基本結果。1968年,A.M.日夫里翁為了排除變態的有效解,引進了真有效解概念,並得到了有關的結果。自70年代 以來,多目標規劃的研究越來越受到人們的重視。至今關於多目標最優解尚無一種完全令人滿意的定義,所以在理論上多目標規劃仍處於發展階段。

求解方法

化多為少

線性規劃 線性規劃
經濟學家帕雷托 經濟學家帕雷托

即把多目標規劃問題歸為單目標的數學規劃(線性規劃或非線 性規劃)問題進行求解,即所謂標 量化的方法,這是基本的算法之一。

①線性加權和法 對於多目標規劃問題(VMP),先選取向量

要求λi>0(i=1,2,…,m)

作各目標線性加權和

然後求解單目標數學規 劃問題。

λ 的各個分量λi(i=1,2,…,m)通常叫做權係數。它的大小反映了各相應分目標在問題中的重要程度。一般,對權係數的不同選取,可以得到問題 (VMP)的不同的有效解或弱有效解。如何選取權係數,對於不同的問題可以有不同的處理方法。

線性規劃 線性規劃

② 理想點法 為了求解多目標規劃問題(VMP),先依次極小化各個分目標。設求得第 i個目標的極小值多目標規劃,則得到R中的一個點多目標規劃多目標規劃。由於點ƒ多目標規劃的各個分量對於相應的分目標而言是最理想的值,故稱ƒ多目標規 劃為問題(VMP)的理想點。選取權係數λi>0(i=1,2,…,m),並作偏差(函式)多目標規劃,最後求解數學規劃問題

問題 (2)的最優解是問題(VMP)的有效解。理想點法的基本思想是在某種意義下使向量目標函式與所考慮問題的理想點的偏差為極小,來求出多目標規劃問題的有 效解。在上述偏差中,p的不同取值代表了不同意義的偏差。當取p=2,λi=1(i=1,2,…,m),則偏差就為距離多目標規劃多目標規劃。這種情形, 理想點法也叫做最短距離法。

分層求解

生態規劃 生態規劃
馮·諾伊曼 馮·諾伊曼

對於問題(VMP),假若目標函式多目標規劃 的各個分目標可以按其在問題中的重要程度排出先後次序,並設這個次序為:ƒ1(x),ƒ2(x),…,ƒm(x)。先對第一個目標進行極小化:多目標規 劃,設得到的最優解為x。然後,按下述格式依次分層對各目標進行極小化:

式中多目標規劃。設k=m時得到問題(3)的最優解x,則在每一多目標規 劃的條件下,x是多目標規劃(VMP)的有效解。在實用中,為了保證每一多目標規劃,常把上述Xk中的等式約束作適當的寬容,即給出一組所謂寬容量 δi(i=1,2,…,m- 1),並以多目標規劃代替 (3)中的Xk。在δi>0 的條件下,由多目標規劃k代替Xk所得到的x是多目標規劃 (VMP)的弱有效解。

其它方法

對多目標的線性規劃除以上方法外還可以適當修正單純形法來求解;還有一種稱為層次分析法,是由美國運籌學家沙旦於70年代提出的,這是一種定性與定量相結 合的多目標決策與分析方法,對於目標結構複雜且缺乏必要的數據的情況更為實用。

規劃方法

在很多實際問題中,例如經濟、管理、軍事、科學和工程設計等領域,衡量一個方案的好壞往往難以用一個指標來判 斷,而需要用多個目標來比較,而這些目標有時不甚協調,甚至是矛盾的。因此有許多學者致力於這方面的研究。

1896年法國經濟學家 V.帕雷托最早研究不可比較目標的最佳化問題,之後,J.馮·諾伊曼、H.W.庫恩、A.W.塔克、A.M.日夫里翁等數學家做了深入的探討,但是尚未有一個完 全令人滿意的定義。

非劣解

規劃模型

多目標規劃模型環境 多目標規劃模型環境

任何多目標規劃問題,都由兩個基本部分組成:(1)兩個以上的目標函式;

(2)若干個約束條件。

有n個決策變數,k個目標函式, m個約束方程,

則:

Z=F(X)是k維函式向量,

Φ(X)是m維函式向量;

G是m維常數向量;

規劃的非劣解

投資 投資

多目標規劃問題的求解不能只追求一個目標的最最佳化(最大或最小),而不顧其它目標。

對於上述多目標規劃問題,求解就意味著需要做出如下的複合 選擇:

▲每一個目標函式取什麼值,原問題可以得到最滿意的解決?

▲每一個決策變數取什麼值,原問題可以得到最滿意的解決 ?

而對於方案⑤、⑥、⑦之間則無法確定優劣,而且又沒有比它們更好的其他方案,所以它們就被稱為多目標規劃問題的非劣解或有效解,

其餘方案都稱為劣解。

所有非劣解構成的集合稱為非劣解集。

當目標函式處於衝突狀態時,就不會存在使所有目標函式同時達到最大或 最小值的最優解,於是我們只能尋求非劣解(又稱非支配解或帕累托解)。

效用最最佳化模型

最最佳化模型 最最佳化模型

線性加權法思想:規劃問題 的各個目標函式可以通過一定的方式進行求和運算。這種方法將一系列的目標函式與效用函式建立相關關係,各目標之間通過效用函式協調,使多目標規劃問題轉化 為傳統的單目標規劃問題 :

罰款模型

線性規劃 線性規劃

理想點法

思想:規劃決策者對每一個目標函式都能提出所期望的值(或稱滿意 值);

通過比較實際值fi與期望值fi* 之間的偏差來選擇問題的解。

約束模型

極大極小法

最最佳化 最最佳化

理論依據 :若規劃問題的某一目標可以給出一個可供選擇的範圍,則該目標就可以作為約束條件而被排除出目標組,進入約束條件組中。

假如,除 第一個目標外,其餘目標都可以提出一個可供選擇的範圍,則該多目標規劃問題就可以轉化為單目標規劃問題。

在求解之前,先設計與目標函式相應的 一組目標值理想化的期望目標fi* ( i=1,2,…,k ),

每一個目標對應的權重係數為ω i* ( i=1,2,…,k ) ,再設γ為一鬆弛因子。

目標規劃模型

目標規劃法

需要預先確定各個目標的期望值fi* ,同時給每一個目標賦予一個優先因子和權係數,假定有K個目標,L個優先權( L≤K)。

收益風險

1.風險大,收益也大。

投資 投資

2.當投資越分散時,投資者承擔的風險越小,這與題意一致。即:冒險的投資者會出現集中投資的情況,保守的投資者則儘量分散投資。

3. 曲線上的任一點都表示該風險水平的最大可能收益和該收益要求的最小風險。對於不同風險的承受能力,選擇該風險水平下的最優投資組合。

生態規劃 生態規劃
O.莫根施特恩 O.莫根施特恩

相關詞條

相關搜尋

熱門詞條

聯絡我們