【正文】 90, , 0 , 1 , 2 。 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 例 最佳生產(chǎn)計劃問題 某工廠計劃生產(chǎn)甲、乙兩種產(chǎn)品，此兩種產(chǎn)品需要在 A 、 B 、 C 、 D 四種不同的設(shè)備上進(jìn)行加工，加工臺時及四種設(shè)備的日臺時能力如表所示： 加工產(chǎn)品所需臺時 設(shè)備A 設(shè)備B 設(shè)備C 設(shè)備D 產(chǎn)品甲 2 1 4 0 產(chǎn)品乙 2 2 0 4 日臺時能力 12 8 16 12 現(xiàn)已知每生 產(chǎn)一件產(chǎn)品，甲、乙分別可獲利潤為 2 元、 3 元，如果現(xiàn)在廠長經(jīng)營的目標(biāo)不僅僅是追求利潤最大，而是要同時考慮如下幾個目標(biāo)： ( 1) 若單純追求利潤最大可得最大利潤為 14 萬元，工廠從實踐中認(rèn)識到在不考慮附加條件下才能使利潤指標(biāo)達(dá)到 14 萬元。 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 工廠要盡可能地把經(jīng)營目標(biāo)與上述三個目標(biāo)靠攏，這顯然是三個目標(biāo)的多目標(biāo)線性規(guī)劃，如果單純追求利潤最大化，則就是熟悉的線性規(guī)劃問題，如果需要同時考慮三個目標(biāo)，則需要采用目標(biāo)規(guī)劃的方法，引入特殊的變量來求解。 ( 1) 偏差變量 表明實際數(shù)值與超出或未達(dá)到目標(biāo)值的差距，用下列符號表示： d ? ：超出目標(biāo)值的偏差 d ? ：未達(dá)到目標(biāo)值的偏差 注意，偏差變量需要滿足如下關(guān)系式： 0dd ?? ?? ， 即,dd??兩者中必有一個為零。 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 這樣，我們對多目標(biāo)規(guī)劃問題個的諸多目標(biāo)函數(shù)可以建立起目標(biāo)函數(shù)方程如下： ??? ? ?C x D D E 1 1 1,l l ld d ed d e??????? ? ? ???? ? ? ???? ? ?? ? ? ???? ? ? ?????? ? ? ?D D E E 是一個期望值向量，在例 中112e ?，線性規(guī)劃的目標(biāo)函數(shù)變成目標(biāo)函數(shù)方程： 1 2 1 12 3 12x x d d??? ? ? ? 線性規(guī)劃問題的目標(biāo)函數(shù)在線性目標(biāo)規(guī)劃中只是成為問題要達(dá)到的目標(biāo)之一，即成為一個目標(biāo) 約束。 值得注意的是經(jīng)過這樣處理之后，約束條件（目標(biāo)）都允許在 — 定范圍內(nèi) “ 伸縮 ” ，即約束集合是松弛的。 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 ( 2) 系統(tǒng)約束與目標(biāo)約束 系統(tǒng)約束是指對某種資源的使用加以嚴(yán)格限制的約束。 建立了這兩個概念后，則例中約束條件的構(gòu)成如下，設(shè)： 1d? ：實際利潤不足目標(biāo)函數(shù)期望值 12 萬元的偏差； 1d? ：實際利潤超過目標(biāo)函數(shù)期望值 12 萬元的偏差。這是一個關(guān)于偏差變量達(dá)最小的單一的綜合性目標(biāo)，從而可將一個多目標(biāo)規(guī)劃轉(zhuǎn)化為 — 個單目標(biāo)規(guī)劃。對偏差變量的運用要根據(jù)各個目標(biāo)的不同要求而確定，一般有以下三種情況： ? 若要求盡可能準(zhǔn)確地實現(xiàn)第 i 個目標(biāo)的期望值，則應(yīng)要求相應(yīng)的正、負(fù)偏差變量id? 和id? 盡可能小，故應(yīng)將id? 和id? 列入達(dá)成函數(shù)之中：? ?m in iidd??? ? 若要求第 i 個目標(biāo)允許超過其期望值，但又要盡可能 的避免低于其期望值，則應(yīng)要求相應(yīng)的負(fù)偏差 變量id? 盡可能小，故應(yīng)將id? 列入達(dá)成函數(shù)之中：? ?m in id? ? 若要求第 i 個目標(biāo)允許低于其期望值，但又要盡可能地避免超過其期望值，則應(yīng)要求相應(yīng)的正偏差變量id? 盡可能小，故應(yīng)將id? 列入達(dá)成函數(shù)之中：? ?m in id? 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 ( 4) 達(dá)成函數(shù)的優(yōu)先級與權(quán)系數(shù) 在上面得出的達(dá)成函數(shù)中，id? 或 , 1 , 2 , 3 , 4idi? ? 的系數(shù)均為 1 ，形式上看所有偏差變量在數(shù)值上具有同等的意義，也就是說1d? 減少 1 元與2d? 或者3d? 減少 1 元有相同的目標(biāo)價值；2d? 增加 1 元與3d? 或者4d? 增加 1 元有相同的目標(biāo)價值，所求的僅僅是它們之和的最小。例如1d? 減少 l 元可以認(rèn)為相當(dāng)于2d? 減少 2 元或相當(dāng)于3d? 減少 4 元 。 線性目標(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ù)量上加以衡量比較。 ( 2) 權(quán)系數(shù) 權(quán)系數(shù)即達(dá)成函數(shù)中各自標(biāo)偏差變量的系數(shù)。有了優(yōu)先等級和權(quán)系數(shù)之后．所建立起來的目標(biāo)規(guī)劃亦稱為字典序（優(yōu)先級）線性目標(biāo)規(guī)劃。 1 , 2 , 3 , 4i j jf p d p d d p d d dx x d dx x d dxxx x d dx x d dx d d i j? ? ? ? ? ????????????? ? ? ? ? ???? ? ? ??? ? ? ????????? ? ? ??? ? ? ???? ? ?? 從此例中可看出，線性目標(biāo)規(guī)劃比線性規(guī)劃靈活，適用于現(xiàn)實中動態(tài)變化的多個目標(biāo)，而且還帶有從屬目標(biāo)的規(guī)劃問題。 這是一個有 n 個設(shè)計變量， m 個目標(biāo)， 2 m 個偏差變量， l 個約束條件的線性目標(biāo)規(guī)劃。如：ijf?與ijf?反映了同一級別下各偏差變量間的相互關(guān)系。 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 建立一個實際問題的線性目標(biāo)規(guī)劃模型的一般步驟如下： ( 1) 由實際問題建立具有 m 個目標(biāo)的線性規(guī)劃模型 ( 2) 將多目標(biāo)線性規(guī)劃模型化為目標(biāo)規(guī)劃模型： ? 由實際問題對第 i 個目標(biāo)給予適當(dāng)?shù)钠谕? 1 , 2 , . . . ,ie i m?； ? 對第 i 個目標(biāo)引進(jìn)偏差變量,iidd??，建立目標(biāo)約束方程并將其列入原約 束條件中； ? 若原約束條件巾有互相矛盾的方程，則對它們同樣引入,iidd??，更一般的做法是對所有的約束方程均引入,iidd??； ? 確定 k 個目標(biāo)的優(yōu)先級別, 1 , 2 , . . . ,ip i k?以及權(quán)系數(shù),i j i jff?? ? 建立達(dá)成函數(shù)m i n f 完成這些步驟后就建 立 了具有一般形式的字典序或優(yōu)先級的線性目標(biāo)規(guī)劃。 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 ① 銷售目標(biāo)約束 完成 5500 銷售目標(biāo)是全時和半時售貨員全部工作時間和其生產(chǎn)率（即每小時銷售量）的函數(shù)。因1x代表全時售貨員全體下月工作時數(shù)。 設(shè)計如下偏差變量： 2d? ：全體全時售貨員下月的停工時間；2d? ：全體全時售貨員下月的加班時間； 3d? ：全體半時售貨員下月的停工時問；3d? ：全體半時售貨員下月的加班時間。 320x d d x d d? ? ? ?? ? ? ? ? ? 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 ③ 加班時間限制 目標(biāo)規(guī)劃為要達(dá)到某一目標(biāo)，必須使其偏差變量達(dá)到最 小。在本例中， 第 二個目標(biāo)是給全時售貨員的加班時間一個限制， 不 超過 100 小時。關(guān)于全時售貨員的加班有兩個不同目標(biāo)。為此引進(jìn)下面的約束條件。 則有約束條件：2 2 1 2 1100d d d? ? ?? ? ? 因為實際的加班時數(shù)可能超過也可能 等于 或少于 l 00 小時，故引進(jìn)對 100 小時的正負(fù)偏差變量。應(yīng)該指出的是上 面 的約束條件可以用不同的方式 表示 出來，即在正常工作的約 束條件的右端加上 100 ：1 4 4900x d d??? ? ? 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 根據(jù)優(yōu)先等級的約定可以得到： 1p：1d? ； 2p：21d? ； 3p：232 dd???，除了保持全體售貨員充分就業(yè)，但加倍優(yōu)先考慮全時售貨員； 4p：323 dd??? 確定4p表達(dá)形式的理由是：全時售貨員和半時售貨員每小時生產(chǎn)率的比是 5:2 ，而每小時的加班費分別是 9 元和 4 元。半時售貨員每加班 1 小時，賣出 2 張唱片的總利潤為 6 元，扣去加班費 4 元，商店得利潤 6 4= 2 元。 1 , 2 , 3i j jf p d p d p d d p d dx x d dx d dx d dd d dx d d d d i j? ? ? ? ? ???????? ? ?? ? ? ??? ? ? ? ? ??? ? ? ???? ? ? ??? ? ???? ? ??? ? ??? 線性目標(biāo)規(guī)劃的求解方法 ? 線性目標(biāo)規(guī)劃的序列法 ? 線性目標(biāo)規(guī)劃的多階段法 ? 線性目標(biāo)規(guī)劃的單純形法 序列法 ? 線性目標(biāo)規(guī)劃序列（序子）算法的基本思想是依達(dá)成函數(shù)中各目標(biāo)的優(yōu)先級別，順序?qū)⒛繕?biāo)規(guī)劃模型分解為一系列的單一的線性規(guī)劃模型，用傳統(tǒng)的單純形方法逐一完成其求解過程。 序列法 ? 具體計算步驟 序列法 第四步 ： 建立相應(yīng)于下一個優(yōu)先級別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? ? ?是指在考慮下一級目標(biāo)的最優(yōu)值時必須同時考慮上一級別目標(biāo)相應(yīng)的約束條件，并且還需考慮增加約束條件? ?*,ssff???DD，這樣可保證在優(yōu)化較低級目標(biāo)時不會退化或破壞已得的較高級目標(biāo)的最優(yōu)值 *sf。 序列法 例 求解如下目標(biāo)規(guī)劃問題 ? ?1 3 2 4 3 1 21 2 1 11 2 2 21 2 3 31 2 4 4m in . 2 202302 3 36000160003 4 55000, , 0 , 1 , 2 。 ( 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) 用單純形法求解。 于是得到最優(yōu)目標(biāo)函數(shù)值 *10f ?。 由于330dd????，表明330dd????，所以，在后面其他優(yōu)先等級目標(biāo)對應(yīng)的線性規(guī)劃模型中只有加上330dd????的約束，才能保證求解時不影響1p等級目標(biāo)已經(jīng)得到的最優(yōu)目標(biāo)函數(shù)值，由于33,0dd???，故這個約束世界上就等價于330dd????。 ( 1) 建立由2p等級目標(biāo)構(gòu)成的單一目標(biāo)線性規(guī)劃模型如下： 241 2 3 3331 2 4 4m ins. t. 1 6 0 0 003 4 5 5 0 0 0, , 0 , 1 , 2 。新增加的約束條件 3 是對應(yīng)于2p等級目標(biāo)的目標(biāo)約束。由最優(yōu)目標(biāo)函數(shù)值知道，因為40d??，故2p優(yōu)先目標(biāo)已經(jīng)達(dá)到最優(yōu)。 序列法 第三步，計算3p等級目標(biāo)的最優(yōu)解。 1 , 2 , 3 , 4i j jf p d dx x d dddx x d dddx x d dx x d dx d d i j????????????????????? ? ? ???????? ? ? ??????? ? ? ??? ? ? ???? ? ?? 其中，約束條件 l 和約束條件 3 分別是1p目標(biāo)和2p目標(biāo)的目標(biāo)約束；約束條件 2 和約束條件 4 分別是1p目標(biāo)和2p目標(biāo)達(dá)到最優(yōu)時該目標(biāo)方程中設(shè)計變量的值，這 4 個約束的條件的加入用于保證在求解當(dāng)前3p目標(biāo)最優(yōu)值時，1p目標(biāo)和2p目標(biāo)的最優(yōu)值不被改變。 ( 2) 用單純形法求解。 序列法 正如前面的方法所述，最終的這個線性規(guī)劃模型的最優(yōu)解就是原來的目標(biāo)規(guī)劃問題的最優(yōu)