【正文】 ( 2) 用單純形法求解。新增加的約束條件 3 是對應(yīng)于2p等級目標(biāo)的目標(biāo)約束。 ( 1) 建立由1p等級目標(biāo)構(gòu)成的單一目標(biāo)線性規(guī)劃模型如下： 131 2 3 31 2 3 3m in. 16000, , , 0f p dx x d dx x d d?????? ??? ? ? ????? ( 2) 用單純形法求解。半時售貨員每加班 1 小時，賣出 2 張唱片的總利潤為 6 元，扣去加班費 4 元，商店得利潤 6 4= 2 元。關(guān)于全時售貨員的加班有兩個不同目標(biāo)。因1x代表全時售貨員全體下月工作時數(shù)。 這是一個有 n 個設(shè)計變量， m 個目標(biāo)， 2 m 個偏差變量， l 個約束條件的線性目標(biāo)規(guī)劃。 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 ( 1) 優(yōu)先等級 設(shè)目標(biāo)分成 k 個等級，分別用優(yōu)先因子12, , . . . , kp p p表示，并且規(guī)定各優(yōu)先因子必須滿足如下不等式：1 , 1 , 2 . . .kkp p k??? 目標(biāo)的優(yōu)先等級是個定性的概念，不同的優(yōu)先等級無法從數(shù)量上加以衡量比較。 建立了這兩個概念后，則例中約束條件的構(gòu)成如下，設(shè)： 1d? ：實際利潤不足目標(biāo)函數(shù)期望值 12 萬元的偏差； 1d? ：實際利潤超過目標(biāo)函數(shù)期望值 12 萬元的偏差。 ( 1) 偏差變量 表明實際數(shù)值與超出或未達(dá)到目標(biāo)值的差距，用下列符號表示： d ? ：超出目標(biāo)值的偏差 d ? ：未達(dá)到目標(biāo)值的偏差 注意，偏差變量需要滿足如下關(guān)系式： 0dd ?? ?? ， 即,dd??兩者中必有一個為零。 設(shè)利潤的偏差為1d?和1d?，則可以得到關(guān)于利潤的約束條件為： 1 2 1 18000 6000 300000 120230x x d d??? ? ? ? ? 同 樣的，設(shè)產(chǎn)品乙的訂貨約束偏差變量為22,dd??，原料 A 庫存的偏差變量為33,dd??，原料 B 庫存的偏差變量為44,dd??，則得到相應(yīng)的約束條件為： 2 2 2 1 2 3 3 1 2 4 440 。是過緊還是過松，差多少或多剩余多少。 2 9 0x x x x? ? ? ? 同時根據(jù)合同約束，則需要滿足122 0 。 x 0 =[1 。 f (2 )=0 . 2 * (x (1 )^ 2 + 2 * x (2 )^ 2 + 3 * x (3 )^ 2 )。 0 ]。 b =[1 2 。 b =[1 2 。 f1f ? ?f x? ?? ?,fd xO ? ?if xid 線性功效系數(shù)法 指數(shù)功效系數(shù)法 指數(shù)功效系數(shù)法 可見，? ?? ? , 1 , 2 , . . . ,iid f i p?x是? ?if x的嚴(yán)格單調(diào)增函數(shù)，而且當(dāng)? ?if x充分大時，? ?? ? 1iidf ?x。 可以證明，評價函數(shù)法中所給的評價函數(shù)都是嚴(yán)格單調(diào)增函數(shù)或單調(diào)增函數(shù)，因而其最優(yōu)解是多目標(biāo)規(guī)劃問題的有效解或弱有效解。而且對于任意的 R?x ，均滿足函數(shù)值非負(fù)的條件? ? 0 , 1 , 2 , . . . ,if i p??x，此時可以令： ? ?? ?? ?1 , 2 , . . . ,11 , 2 , . . . ,iiif i kfi k k pf? ????? ? ???xxx (8 12) 這樣 就可以把多目標(biāo)規(guī)劃問題統(tǒng)一為：? ? ? ? ? ? ? ?? ?12m i n , , . . . ,TpRf f f??xF x x x x 乘除法 的 原理 就是構(gòu)造如下目標(biāo)函數(shù)： ? ?? ? ? ?? ?? ?? ? ? ? ? ?? ? ? ? ? ?1211121...m in...kkikii pRik k piikff f fhff f ff????????? ? ?? ? ? ?? ? ??xxx x xF x xx x xx 則多目標(biāo)規(guī)劃問題已經(jīng)轉(zhuǎn)化為單目標(biāo)規(guī)劃問題。 1piiiip??????? ? ? ? ??????λ； 若所有權(quán)系數(shù)0 , 1 , 2 , . . . ,iip? ??，則稱這組權(quán)系數(shù)為非負(fù)權(quán)，非負(fù)權(quán)的全體可以記為：10 , 1 , 2 , ..., 。 有效解和有效點、弱有效解和弱有效點之間有如下的關(guān)系： 若已知象集? ?RF的有 效點集*eF，則多目標(biāo)規(guī)劃問題的有效解集*eR可以表示為： ? ?? ?**|,eeRR?? ? ? ?FFx F x F x 若已知象集? ?RF的有弱效點集*weF，則多目標(biāo)規(guī)劃問題的弱有效解集*weR可以表示為： ? ?? ?**|,weweRR?? ? ? ?FFx F x F x 這兩個定理說明，? ?RF的有效點和弱有效點的原象分別為多目標(biāo)規(guī)劃問題的有效解和弱有效解。 多目標(biāo)規(guī)劃問題的典型實例 ? 例 1 木梁設(shè)計問題 多目標(biāo)規(guī)劃問題的典型實例 ? 例 2 工廠采購問題 多目標(biāo)規(guī)劃問題的典型實例 同時要滿足所花的總費用不得超過 300 元，原料的總重量不得少于 120kg ， A 原料不得少于 60kg ，于是得到約束條件如下： 12120xx ?? 122 300xx ?? 160x ? 又考慮到購買的數(shù)量必須要滿足非負(fù)的條件，由于對1x已經(jīng)有相應(yīng)的約束條件，故只需添加對2x的非負(fù)約束即可。但在實際問題中，衡量一個設(shè)計方案的好壞往往不止一個標(biāo)準(zhǔn)，常常要考慮多個目標(biāo)。我們把在這樣的背景下建立起來的最優(yōu)化稱之為多目標(biāo)規(guī)劃問題。 多目標(biāo)規(guī)劃問題域線性規(guī)劃和非線性規(guī)劃問題的主要區(qū)別就在于，它所追求的目標(biāo)不止一個，而是多個。 下面我們給出最短距離理想點法，這種方法是將 取為 pR 中的2的形式，即構(gòu)造如下的單目標(biāo)規(guī)劃問題： ? ?? ? ? ? ? ?? ?20*21m inpiiRih f f??? ? ? ??xF x F x F x 這里的評價函數(shù)? ?? ?h Fx是? ?Fx到 0F 的距離。對應(yīng)于 F ，存在 R?x 使得? ??F F x，則 x 為多目標(biāo)規(guī)劃問題的有效解。 如果對于,pR??? FF，當(dāng)滿足 ??FF 時均滿足? ? ? ?hh ??FF，則? ?h F稱為 F 的單調(diào)增函數(shù)。換句話說，我們用一個值在 0 與 1 之間的功效函數(shù)? ?? ? ,iid f R?xx來反映? ?if x的好壞。 3 ]。 3 ]。 b e q =[3 ]。 最大最小法問題的 M A T L A B 標(biāo)準(zhǔn)形式為： ? ?? ?? ?m in m a x. 00ix ieqe q e qf?????????????????xcxcxA x bA x blb x u b 函數(shù) f mi n im a x 的調(diào)用方式和其他的最優(yōu)化函數(shù)類似，其中所涉及的輸入?yún)?shù)和輸出參數(shù)的含 義與非線性規(guī)劃的求解函數(shù) f mi n c o n 類似，使用方法也基本相同，細(xì)節(jié)問題讀者可以參考 M A T L A B 的幫助文件。 l b =[0 。決策者的任務(wù)是求出盡可能接近這組預(yù)定期望值的解。當(dāng)線性規(guī)劃中的某個約束無法滿足時，線性規(guī)劃無解，例如在例子中，如果將產(chǎn)品甲的合同約束改為 40噸，產(chǎn)品乙的合同約束改為 15噸，則問題無解。當(dāng)然，如果決策者能夠決定這些目標(biāo)的優(yōu)先次序，而且所有的目標(biāo)和約束都是線性的，這樣的多目標(biāo)決策就能用目標(biāo)規(guī)劃解決 ? 為了說明線性目標(biāo)規(guī)劃的上述特點，同時讓讀者對目標(biāo)規(guī)劃有一個直觀的認(rèn)識，我們可將上例中的問題修改為另一種形式 線性目標(biāo)規(guī)劃 例 某工廠生產(chǎn)甲、乙兩種產(chǎn)品以滿足市場的需要，生產(chǎn)這兩種產(chǎn)品需要消耗 A 、B 兩種原料，其有關(guān)的數(shù)據(jù)如表 所示： 工廠生產(chǎn)數(shù)據(jù)表 原料A消耗 ( t/ t ) 原料B消耗 ( t/ t ) 售價 ( 元 / t ) 產(chǎn)品甲 1. 0 2. 0 15000 產(chǎn)品乙 1. 0 1. 0 11000 已知原料 A 、 B 的購入價分別為 3000 元 /噸及 2 000 元 /噸，除原料費以外的其它固定費用 ( 包工資、折舊費、管理費等 ) 為每月 300000 元。所以這是個偏高的指標(biāo)，經(jīng)決策后決定把最大利潤 14萬元降到 12 萬元，但又要力求超過一些； ( 2) 從市場信息反饋得知，對甲、乙兩種產(chǎn)品的需求且的比例大致是 1:1 ； ( 3) 四臺設(shè)備的能力并非沒有一點機動余地，如設(shè)備 B 不必充分利用但必要時可以加班運轉(zhuǎn)，當(dāng)然希望加班的時間盡可能地少而設(shè)備 A 既要充分利用，又要盡可能地不加班。當(dāng)目標(biāo)與約束集之間互不相容時（即無可行域），也能找到 —組 “ 最優(yōu)解 ” 這是在另一種意義下的最優(yōu)解，它允許 “ 最優(yōu)值 ” 與預(yù)定目標(biāo)存在偏離，但是偏離量盡量滿足優(yōu)化要求。而實際上id? 和id? 各自完全可以賦予不同的含義。 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 假定該廠作出如下判斷：把目標(biāo) ( 1) 列為第一優(yōu)先級，記為1p；把目標(biāo) ( 2) 列為第二優(yōu)先級，記為2p；把目標(biāo) ( 3) 列為第三優(yōu)先級，記為3p，并在3p中假設(shè)設(shè)備 A 的重要性比設(shè)備 B 的重要性大 3 倍，從而我們得到問題的線性目標(biāo)規(guī)劃的數(shù)學(xué)模型： ? ? ? ?? ?1 1 2 2 2 3 3 3 41 2 1 11 2 2 2121 2 3 31 2 4 4m in 3. 2 3 1204 164 122 2 1228, , 0 , 1 , 2 。但是注意到模型的建立是靈活的，所以不一定要完全嚴(yán)格按上述一般步驟進(jìn)行。假如 沒有 ，則 需要進(jìn)一步引進(jìn)新的約束條件。因而有一個偏差變量21d?，使之達(dá)到極小以實現(xiàn)第 2 個目標(biāo)。 第五步 ： 最后一個單目標(biāo)線性規(guī)劃模型的解是原目標(biāo)規(guī)劃模型的解，并且如下向量： ? ?* * * *12, , . . . ,kf f f?f 也反映了各目標(biāo)實現(xiàn)的程度亦稱達(dá)成向量。 序列法 第二步，計算2p等級目標(biāo)的最優(yōu)解。 ( 1) 建立由3p等級目標(biāo)構(gòu)成的單一目標(biāo)線性規(guī)劃模型如下： ? ?3 1 21 2 3 3331 2 4 4441 2 1 11 2 2 2m in . 1600003 4 5500002 202302 3 36000, , 0 , 1 , 2 。因為，最后的這個線性規(guī)劃數(shù)學(xué)模型中已經(jīng)包含1p目標(biāo)和2p目標(biāo)的目標(biāo)約束以及 它們的最優(yōu)解信息。 由于440dd????，表明440dd????，所以，在后面其他優(yōu)先等級目標(biāo)對應(yīng)的線性規(guī)劃模型中只有加上440dd????和330dd????的約束，才能保證求解時不影響1p等級目標(biāo)和2p等級目 標(biāo)已經(jīng)得到的最優(yōu)目標(biāo)函數(shù)值。 由最優(yōu)目標(biāo)函數(shù)值知道，因為30d??，故1p優(yōu)先目標(biāo)已經(jīng)達(dá)到最優(yōu)。在求解過程中進(jìn)基變量、出基變量及樞點元素的選擇原則與線性規(guī)劃的單純形法相同，不同的是要以不影響較高級目標(biāo)的達(dá)成值為前提選擇較低級目標(biāo)的達(dá)成值，如此反復(fù)迭代，直至進(jìn)行到最低級目標(biāo)的達(dá)成函數(shù)達(dá)最優(yōu)為止。 由于2d?代表全體售貨員實際加班時間，于是設(shè)計如下偏差變量： 21d?： 全體全 時 售貨員 下月加班不足 100 小時的負(fù)偏差 ； 21d?： 全體全時售貨員下月加班超過 100 小時的正偏差 。 則有約束條件： 1 2 2 2 3 3800 。一般比較重要的偏差變量應(yīng)賦子較大的權(quán)系數(shù)。權(quán)系數(shù)是一種可以用數(shù)量來衡量的指標(biāo)，對屬于同一優(yōu)先等級的不同目標(biāo)可按其重要程度分別給予不同的權(quán)系數(shù)來反映各目標(biāo)的差異。目標(biāo)規(guī)劃中的達(dá)成函數(shù)是偏差變量的函數(shù)，反映了各目標(biāo)得以實現(xiàn)的程度。引入了目標(biāo)函數(shù)的期望值與正負(fù)偏差變量,dd?? 之后，原來的目標(biāo)函數(shù)變成了約束條件的一部分，這正是線性目標(biāo)規(guī)劃的一個特征。 1 , 2 , 3 , 4i j jf p