例1(物資調運優化): 假設物資排程部門計畫將某種物資從若干個儲存倉庫,調運到若干個銷售網點。考慮到物資的時效性和銷售效益,排程部門希望物資在運輸過程中盡可能快地到達目的地;考慮到運輸的成本,排程部門還希望物資的總運輸費用最小。
假設個倉庫的物資庫存量為,…,(單位:t);個銷售網點預計銷售量為,…,(單位:t)。
倉庫i與銷售網點j之間的路程為(單位:km),單位物資的運費為(元)。
用物資噸公里總數來衡量物資的運輸品質,噸公里總數最小意味著有適量的物資盡可能快地到達目的地。
記從倉庫i到銷售網點j運送的物資量為。
目標函式:
(1)物資在運輸過程中的噸公里總數為
(2)物資運輸費用總和為
約束條件為產銷平衡條件:
優化問題模型:
多目標規劃(mop)問題描述:
稱為向量值目標函式。變數可行域記為
s的像集稱為目標可行域,z中的元素稱為目標向量。
如果不指明約束函式的具體形式,多目標規劃問題可以簡記為
若每個目標函式都是凸函式,並且可行域s是凸集,則(mop)稱為多目標凸規劃問題。
在討論向量集的有效點之前,約定如下記號:對於任意兩個向量
令(1)(2)
(3)(4)
(5)定義1:給定乙個向量集,對於點,若,有,則稱是x的絕對最小點(即絕對最小向量)。若不存在,使得(),則稱是x的有效點(弱有效點)。
集合x的所有絕對最小點、有效點和弱有效點的集合分別記為,和。
例2:考慮橢圓。
從幾何上看,表示橢圓的左下部(包括端點)。
約定:非負錐:
正錐:定理1:給定,考慮下面條件:
(1)對某,函式()在處取到最小值;
(2)對某個,,函式()在處取到嚴格最小值;
(3)對某個,,函式()在處取到最小值。
若條件(1)或(2)成立,則是x的有效點。
若條件(3)成立,則是x的弱有效點。
考慮形如式(1)-(3)的多目標規劃問題,變數可行域,目標可行域。
定義2:給定一可行點,若,有,則稱為問題(mop)的絕對最優解(絕對最小解)。若不存在,使得() , 則稱為問題(mop)的有效解(弱有效解)。
問題(mop)有效解也稱pareto最優解。將問題(mop)絕對最優解、有效解、弱有效解集合分別記為,和。
多目標規劃的(弱)有效解與其目標可行域的(弱)有效點之間有緊密的聯絡,概括為如下定理:
定理2:對於問題(mop),令表示目標函式在定義域s上的值域(目標可行域),z的有效點集和弱有效點集分別記為和,則(mop)的有效解集和弱有效解集,由下面式子給出:
(1)(2)
解集合,和之間的關係,有如下定理:
定理3:對多目標規劃問題(mop),必有
(1)(2)當時,
(3)若可行域s為凸集,f是s上嚴格凸的向量值函式,則。
如果記單目標優化問題
的最小點的集合為,那麼多目標規劃問題的絕對最優解的集合
此外,容易證明成立。
根據定理3,有如下結論:
例3:求解兩目標優化問題
其中。記目標,。
單目標優化問題的最優解集,,故絕對最優解集。該問題的目標可行域為
根據z的(弱)有效點定義以及定理2,該問題的有效解集與弱有效解集相等。特別地,。
例4:求解兩目標優化問題
其中。記目標,.
單目標優化問題最優解集,,故絕對最優解集。
根據定理3中結論(3),該問題的有效解集與弱有效解集相等.另外,該問題的目標可行域z為
根據z的(弱)有效點定義,可以知道
利用定理2,有。
多目標規劃問題(mop)的本質在於:各個子目標有可能是相互矛盾的,乙個子目標的改善有可能引起另乙個子目標的惡化,同時使所有子目標都達到最優值一般是不可能的,只能是在這多個子目標之間進行協調和權衡,使各個子目標盡可能地達到理想值。
多目標規劃問題的直接解法,就是尋找它的整個最優解集(pareto有效解集)。除了特殊的情形,計算所有的最優解是比較困難的,因為確定整個有效解集的問題是np-hard的。
目前對直接解法的研究結果還比較少,主要採用間接解法。
直接解法的最新進展——多目標遺傳演算法(moga)。
多目標規劃pareto最優解一般是乙個集合。由於ga是對整個群體所進行的進化運算操作,它處理的是個體的集合,這種相似性使得ga可以作為求解多目標規劃問題的pareto最優解集的乙個有效手段。
注1:間接解法的共同特點:
將多目標規劃問題轉化為乙個或多個單目標優化問題。
通過求解單目標優化問題得到(mop)的乙個或多個最優解。
一般並不要求間接解法給出問題的所有最優解。
基本思想:首先將原來的多目標規劃問題(mop)轉化成乙個單目標優化問題;然後利用非線性優化演算法求解該單目標問題,把所求得的最優解作為問題(mop)的最優解.
— 線性加權和法
— 主要目標法
— 理想點法
— 極小化極**
這類方法的核心:保證所構造的單目標問題的最優解是(mop)的有效解或者弱有效解.
線性加權和法:
根據個目標函式的重要程度,分別賦予一定的權係數,然後將所有的目標函式加權求和作為新的目標函式,在(mop)的可行域s上求出新目標函式的最優值。
問題轉化為如下單目標優化問題:
()其中。f, g, h為向量值函式。
主要目標法:
根據實際情況,首先確定乙個目標函式為主要目標,不妨假設為主要目標,而把其餘的個目標函式作為次要目標。
然後借助於決策者的經驗,通過選定一定的界限值(),把次要目標轉化為約束條件,通過求解如下的單目標優化問題獲得問題(mop)的最優解:
()基本思想:根據某種規則,首先將(mop)問題轉化為有一定次序的多個單目標優化問題;然後,依次分別求解這些單目標優化問題,並且把最後乙個單目標優化問題的最優解作為原問題的最優解。
— 分層排序法
— 重點目標法
— 分組排序法
這類方法的核心:保證最後乙個單目標優化問題的最優解是(mop)的有效解或者弱有效解。
分層排序法:
根據目標的重要程度將它們一一排序;然後分別在前乙個目標的最優解集中,尋找後乙個目標的最優解集,並把最後乙個目標的最優解集作為問題(mop)的最優解。
首先,通過求解單目標問題
得到的最優解集。然後對於,依次求解單目標優化問題
得到的最優解集。最後,將中的點作為(mop)的最優解。
重點目標法:
在p個目標函式中,首先確定最重要的目標,比如,並且在s上求出的最優解集;然後,在上求解其餘個目標對應的多目標規劃問題
把(mop')的有效解或弱有效解作為(mop)的最優解.
在求解問題(mop')時,可以利用前面介紹的方法,將(mop')轉化為乙個單目標優化問題求解。
分組排序法:
根據某種規則,首先將(mop)的目標分成若干個組,使得在每個組內的目標的重要程度相差不多,此時,每組目標實際上對應著乙個新的多目標規劃問題;
然後,依次在前一組目標對應問題的最優解集中,尋找後一組目標對應問題的最優解集,並把最後一組目標對應問題的最優解作為(mop)的最優解.
注2:分組排序法實際上是分層排序法的推廣形式。
分層排序法是針對單個的目標進行分層,求解相應的單目標優化問題;
分組排序法則是對一些目標的集合進行分層,求解相應的小規模多目標規劃問題.
1 求解雙目標優化問題
2對於雙目標優化問題
(1) 若取權向量,試利用線性加權和法求出乙個有效解;
(2) 利用線性加權和法能否求出該問題的所有有效解?
(3) 你能求出該問題的有效解集嗎?
Matlab學習系列27多目標規劃
27.多目標規劃 一 線性規劃的侷限性 1.線性規劃要求所求解問題必須滿足全部的約束,而實際問題中並非所有約束都需要嚴格的滿足 2.線性規劃只能處理單目標的優化問題,從而對一些次目標只能轉化為約束處理,而實際問題中,目標和約束是可以相互轉化的,處理時不一定要嚴格區分 3.線性規劃在處理問題時,將各個...
多目標電網規劃的分層最優化方法
摘要 電網規劃是乙個不確定的 多目標的 非線性和多階段性的複雜系統優化問題。隨著市場經濟的發展,電網規劃的經濟性與可靠性之間的矛盾日益加劇,如何選擇合理的電網規劃的最優模型已成為現代電力事業面臨的挑戰。本文 了多目標電網規劃的分層最優方法,並利用算例進行了校驗,證明了該方法的有效性。關鍵詞 多目標 ...
線性規劃多目標線性規劃讀書筆記
多目標線性規劃模型 的讀書筆記 一 線性規劃 一 線性規劃的概述 線性規劃是運籌學中研究較早 發展較快 應用廣泛 方法較成熟的乙個重要分支,它是輔助人們進行科學管理的一種數學方法.在經濟管理 交通運輸 工農業生產等經濟活動中,提高經濟效果是人們不可缺少的要求,而提高經濟效果一般通過兩種途徑 一是技術...