【正文】 序列法 第三步，計(jì)算3p等級(jí)目標(biāo)的最優(yōu)解。 序列法 ? 具體計(jì)算步驟 序列法 第四步 ： 建立相應(yīng)于下一個(gè)優(yōu)先級(jí)別ip的單目標(biāo)線性規(guī)劃模型： ? ?? ?121*m in , . , , 1 , 2 , ..., 1, , 0iinij j i i i ijssffc x d d e i p p pf f s i?????????????? ? ? ? ? ????? ? ??????DDDDx D D 這里，12 ii p p p? ? ?是指在考慮下一級(jí)目標(biāo)的最優(yōu)值時(shí)必須同時(shí)考慮上一級(jí)別目標(biāo)相應(yīng)的約束條件，并且還需考慮增加約束條件? ?*,ssff???DD，這樣可保證在優(yōu)化較低級(jí)目標(biāo)時(shí)不會(huì)退化或破壞已得的較高級(jí)目標(biāo)的最優(yōu)值 *sf。 320x d d x d d? ? ? ?? ? ? ? ? ? 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 ③ 加班時(shí)間限制 目標(biāo)規(guī)劃為要達(dá)到某一目標(biāo)，必須使其偏差變量達(dá)到最 小。有了優(yōu)先等級(jí)和權(quán)系數(shù)之后．所建立起來的目標(biāo)規(guī)劃亦稱為字典序（優(yōu)先級(jí)）線性目標(biāo)規(guī)劃。 值得注意的是經(jīng)過這樣處理之后，約束條件（目標(biāo)）都允許在 — 定范圍內(nèi) “ 伸縮 ” ，即約束集合是松弛的。多目標(biāo)決策就是要在這些目標(biāo)中建立優(yōu)先次序，分清主次輕重，使得只有在較高級(jí)目標(biāo)被滿足或不能再改進(jìn)之后，才考慮較低級(jí)目標(biāo)。 線性目標(biāo)規(guī)劃 ? 線性目標(biāo)規(guī)劃也是解決多目標(biāo)數(shù)學(xué)規(guī)劃的一種方法，它是在線性規(guī)劃基礎(chǔ)上發(fā)展起來的．這種方法的基本思想是：對(duì)每一個(gè)目標(biāo)函數(shù)，預(yù)先給定一個(gè)期望值，在現(xiàn)有的約束條件下，這組期望值也許能夠達(dá)到，也許達(dá)不到。 [x , fv a l ]=fm i n c o n (o b j f u n , x 0 , [], [], A e q , b e q , l b , []) 結(jié)果說明，問題的最優(yōu)解為：? ?*1* * *2*3 , xxfx?? ???? ??? ? ??? ???? ??????xx 多目標(biāo)規(guī)劃的 MATLAB求解 我們在求解多目標(biāo)規(guī) 劃問題時(shí)，可 以采用評(píng)價(jià)函數(shù)法中的最大最 小法，而M A T L A B 也為這種方法提供了專門的求解函數(shù) f m i n im a x ，在講解這方面的例題之前，我們 首先介紹一下 M A T L A B 優(yōu)化工具箱中所提供的最大最小法的求解函數(shù)f m i n im a x 。 c =[ 5。并規(guī)定：對(duì)? ?if x產(chǎn)生功效最好的 x ，評(píng)分為1id ?；功效最壞的 x ，評(píng)分為0id ?；對(duì)不是最好也不是最壞的中間狀態(tài)，評(píng)分為01 id??。 求? ?1 2 2m i n ,Tf f R??? ? ?λ F F F的過程就是在? ?RF中找一點(diǎn)，使得 T C?λ F 取最小值 TC ? λ F ，從圖上 可以看出，12[]Tff?F是目標(biāo)函數(shù) Tλ F 的等值線與? ?RF在左下角的切點(diǎn)，即? ?RF的有效點(diǎn)。 1 5 5 0 0A A Aq x q x q x? ? ? ? ? ? 同時(shí)考慮到生產(chǎn)時(shí)間的非負(fù)性，總結(jié)得到該問題的數(shù)學(xué)模型為： ? ?? ?1 1 2 32 1 2 31 2 31 2 31231 2 3m a x 5 0 0 4 0 0 6 0 0m in 0 .4 8 0 .6 5 0 .4 2s. t. 4 00 .4 8 0 .6 5 0 .4 2 2 02 0 7 0 02 5 8 0 01 5 5 0 0, , 0f x x xf x x xx x xx x xxxxx x x? ? ? ??? ? ???? ? ??? ? ?????????????xx 多目標(biāo)規(guī)劃問題的數(shù)學(xué)模型 上述問題可以歸結(jié)為標(biāo)準(zhǔn)形式： ? ?? ?? ?V m in. 0 ( 1 , 2 , .. ., )0 ( 1 , 2 , .. ., )iig i mh i l?????????Fxxx 其中：? ?12Tnx x x?x；? ? ? ? ? ? ? ?12 ,2pf f f p??????F x x x x 令? ?? ?| 0 , 1 , 2 , . . . ,iR g i m? ? ?xx，則稱 R 為問題的可行域，? ?V m i n Fx指的是對(duì)向量形式的 p 個(gè)目標(biāo)函數(shù)求最小，且目標(biāo)函數(shù)? ?Fx和約束函數(shù)? ?ig x、? ?ih x可以是線性函數(shù)也可以是非線性函數(shù)。例如研究生產(chǎn)過程時(shí)，人們既要提高生產(chǎn)效率，同時(shí)還要考慮產(chǎn)品質(zhì)量，又要考慮成本以降低生產(chǎn)費(fèi)用，可能還希望生產(chǎn)過程中的環(huán)保問題，即廢渣、廢水、廢氣造成的污染小。 處理多目標(biāo)規(guī)劃的方法 ? 約束法 ? 評(píng)價(jià)函數(shù)法 ? 功效系數(shù)法 約束法 ? 原理 評(píng)價(jià)函數(shù)法 求解多目標(biāo)規(guī)劃問題時(shí)，還有一種常見的方法就是評(píng)價(jià)函數(shù)法，其基本思想就是將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為一個(gè)單目標(biāo)規(guī)劃問題來求解，而且該單目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)是用多目標(biāo)問題的各個(gè)目標(biāo)函數(shù)構(gòu)造出來的，稱為評(píng)價(jià)函數(shù)，例如若原多目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)為? ?Fx，則我們可以通過各種不同的方式構(gòu)造評(píng)價(jià)函數(shù)? ?? ?h Fx，然后求解如下問題： ? ?? ?m ins. t.hR??????Fxx 求解 上述問題 之后，可以用上述問題的最優(yōu)解 *x 作為多目標(biāo)規(guī)劃問題的最優(yōu)解，正是由于可以用不同的方法來構(gòu)造評(píng)價(jià)函數(shù)，因此有各種不同的評(píng)價(jià)函數(shù)方法，下面介紹幾種常用的方法。 在乘除法中我們是把求最大的目標(biāo)作為分母，把求最小的目標(biāo)作為分子，如此化為單目標(biāo)問題后再求最小。為了確定0b和1b，規(guī)定：? ? ? ?1 1 1 0 00 . 3 7 。 8 ] l b =[0 。 之后調(diào)用 f mi n im a x 函數(shù)進(jìn)行求解，同樣設(shè)置初始點(diǎn)為 [ 1。 2 5xx ?? 于是，最優(yōu)化問題可以歸結(jié)為： ? ?12121212m a x 80 00 60 00 30 00 00. 602 902025f x xxxxxxx? ? ? ???????????????x 我們可以利用單純形法求解上述問題，結(jié)果為當(dāng)123 0 , 3 0xx ??，即兩種產(chǎn)品的產(chǎn)量均為 30 噸時(shí)，工廠所獲的最大利潤為120230f ?。 60 。 則原線性規(guī)劃的目標(biāo)函數(shù)對(duì)應(yīng)于目標(biāo)規(guī)劃中的一個(gè)目標(biāo)約束： 1 2 1 12 3 12x x d d??? ? ? ? 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 ( 3) 目標(biāo)規(guī)劃中的目標(biāo)函數(shù) （ 達(dá)成函數(shù) ） 多目標(biāo)規(guī)劃中的各個(gè)目標(biāo)函數(shù)、在通過引入偏差變量而列入到約束條件后，那么在目標(biāo)規(guī)劃中的目標(biāo)函數(shù)就是要使各目標(biāo)函數(shù)值最接近各自的期望值，即要使得偏差達(dá)到最小值。上述問題中的這些變量和系數(shù)在目標(biāo)規(guī)劃中均起著各自的作用。限制全時(shí)售貨員的加班時(shí)數(shù)不超過 100 小時(shí)。 將 目標(biāo)函數(shù)變換為13m i n fd??，用線性規(guī)劃的方法求解， 一個(gè)最優(yōu)解是：1 2 3 3160 00 , 0 , 0x x d d??? ? ? ?； 另一個(gè)最優(yōu)解是：2 1 3 3160 00 , 0 , 0x x d d??? ? ? ?。 將目標(biāo)函數(shù)變?yōu)? 1 2m i n d d????，得到最優(yōu)解為：129 0 0 0 , 7 0 0 0 ,xx ?? 1 2 3 3 4 45000 , 3000 , 0d d d d d d? ? ? ? ? ?? ? ? ? ? ?于是得到最優(yōu)目標(biāo)函數(shù)值*31800f ?。 3 , 4i j jf p dx x d dddx x d dx d d i j?????????? ??? ? ? ???????? ? ? ??? ? ??? 其中，約束條件 l 是1p目標(biāo)的目標(biāo)約束；約束條件 2 是1p目標(biāo)達(dá)到最優(yōu)時(shí)該目標(biāo)方程中設(shè)計(jì)變量的值，該約束用于保證在求解當(dāng)前2p目標(biāo)最優(yōu)值時(shí)，1p目標(biāo)的最優(yōu)值不被改變。于是有：全時(shí)售貨員每加班 l 小時(shí)，賣出 5 張唱片的總利潤為 15 元，扣去加班費(fèi) 9 元，則商店得利潤 15 9= 6 元。 設(shè)計(jì)如下變量： 1x：全體全時(shí)售貨員下月的工作時(shí)間（小時(shí)） 2x：全體半時(shí)售貨員下月的工作時(shí)間（小時(shí)） 1d? ：達(dá)不到銷售目標(biāo)的負(fù)偏差 1d? ：超過銷售目標(biāo)的正偏差 由于制定的目標(biāo)為銷售量 5500 ，于是該約束可以表達(dá)為： 1 2 1 15 2 5500x x d d??? ? ? ? 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 ② 正常工作時(shí)間約束 銷售時(shí)間由兩種售貨員的正常工作時(shí)數(shù)和人數(shù)所決定。 為反映這一點(diǎn)，必須給這些偏差變量以適當(dāng)?shù)臋?quán)系數(shù)，注意到在現(xiàn)實(shí)的決策環(huán)境中各個(gè)目標(biāo)的重要程度是不可能完全 — 致的，決策者總要運(yùn)用他的判斷能力分析各個(gè)目標(biāo)的重要性，給出其輕重緩急，而目標(biāo)規(guī)劃法又允許我們可以根據(jù)目標(biāo)的重要程度給予每個(gè)目標(biāo)以不同的優(yōu)先等級(jí)．這樣，低級(jí)的目標(biāo)只有在高級(jí)的目標(biāo)完成之后才順序考慮以后我們將會(huì)看到在相同的條件之下，對(duì)于不同的權(quán)系數(shù)與不同的優(yōu)先等級(jí)會(huì)得出完全不同的最優(yōu)方案。在例 8 2 中我們已經(jīng)提及了偏差變量、目標(biāo)規(guī)劃的目標(biāo)函數(shù)等等，下面對(duì)這些概念進(jìn)行詳細(xì)的分析。這是因?yàn)榭梢栽诰€性目標(biāo)規(guī)劃的每個(gè)約束條件中引入一對(duì)正負(fù)偏差變量，通過偏差變量可以表達(dá)條件是否可以被滿足。 0 ]。 0 。 1 1 ]。 若? ?? ?h Fx是? ?Fx的單調(diào)增函數(shù)，則轉(zhuǎn)化后的單目標(biāo)規(guī)劃問題的最優(yōu)解是多目標(biāo)規(guī)劃問題的弱有效解。 若所有權(quán)系數(shù)0 , 1 , 2 , . . . ,iip? ??，則稱這組權(quán)系數(shù)為正權(quán)，正權(quán)的全體可以記為： 210 , 1 , 2 , ..., 。其概念和數(shù)學(xué)模型是由 1961年提出的，經(jīng)過 Ijiri,，并逐步發(fā)展和成熟，它在經(jīng)濟(jì)管理與規(guī)劃、人力資源管理、政府管理、大型工程的最優(yōu)化等重要問題上都有廣泛的應(yīng)用。 ? 多目標(biāo)規(guī)劃問題的發(fā)展 ? 多目標(biāo)規(guī)劃法（ Goal Programming，簡稱 GP）也是最優(yōu)化理論和方法中的一個(gè)重要分支，它是在線性規(guī)劃的基礎(chǔ)上，為解決多目標(biāo)決策問題而發(fā)展起來的一種數(shù)學(xué)方法。當(dāng)然我們也可以采用其他評(píng)價(jià)函數(shù)的方式，例如更一般的將 (8 7) 進(jìn)行推廣，得到評(píng)價(jià)函數(shù)為： ? ?? ? ? ?? ?1*1,1pqqiiih f f q???? ? ??????F x x 且 取 整 數(shù) 值 或者是如下形式： ? ?? ? ? ?*1m a xiiiph f f????F x x 基于加權(quán)的方法 如果p個(gè)非負(fù)實(shí)數(shù)12, , ...,p? ? ?滿足其和為 1 ，則稱12[ , , . . . , ]Tp? ? ??λ為一組權(quán)向量，或者將12, , ...,p? ? ?稱為一組 權(quán)系數(shù) 。 在上述定義下，轉(zhuǎn)化后的單目標(biāo)規(guī)劃問題是多目標(biāo)規(guī)劃問題的有效解或者弱有效解的條件由下面兩個(gè)定理描述： 若? ?? ?h Fx是? ?Fx的嚴(yán)格單調(diào)增函數(shù)，則轉(zhuǎn)化后的單目標(biāo)規(guī)劃問題的最優(yōu)解是多目標(biāo)規(guī)劃問題的有效解。 A =[3 2 。 l b =[0 。 0 。 ? 然而，線性目標(biāo)規(guī)劃的約束條件卻有較大的靈活性。 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 工廠要盡可能地把經(jīng)營目標(biāo)與上述三個(gè)目標(biāo)靠攏，這顯然是三個(gè)目標(biāo)的多目標(biāo)線性規(guī)劃，如果單純追求利潤最大化，則就是熟悉的線性規(guī)劃問題，如果需要同時(shí)考慮三個(gè)目標(biāo)，則需要采用目標(biāo)規(guī)劃的方法，引入特殊的變量來求解。例如1d? 減少 l 元可以認(rèn)為相當(dāng)于2d? 減少 2 元或相當(dāng)于3d? 減少 4 元 。 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 ① 銷售目標(biāo)約束 完成 5500 銷售目標(biāo)是全時(shí)和半時(shí)售貨員全部工作時(shí)間和其生產(chǎn)率（即每小時(shí)銷售量）的函數(shù)。應(yīng)該指出的是上 面 的約束條件可以用不同的方式 表示 出來，即在正常工作的約 束條件的右端加上 100 ：1 4 4900x d d