【正文】 一般步驟如下： ( 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)引進偏差變量,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ī)劃。但是注意到模型的建立是靈活的，所以不一定要完全嚴(yán)格按上述一般步驟進行。 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 ① 銷售目標(biāo)約束 完成 5500 銷售目標(biāo)是全時和半時售貨員全部工作時間和其生產(chǎn)率（即每小時銷售量）的函數(shù)。 設(shè)計如下變量： 1x：全體全時售貨員下月的工作時間（小時） 2x：全體半時售貨員下月的工作時間（小時） 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ù)所決定。因1x代表全時售貨員全體下月工作時數(shù)。 5 個全時售貨員，故正常的每月工作時數(shù)為 5 160 ＝ 800 小時，半時工作的售貨員的每月工作時數(shù)為 4 80 ＝ 320 小時。 設(shè)計如下偏差變量： 2d? ：全體全時售貨員下月的停工時間；2d? ：全體全時售貨員下月的加班時間； 3d? ：全體半時售貨員下月的停工時問；3d? ：全體半時售貨員下月的加班時間。 則有約束條件： 1 2 2 2 3 3800 。 320x d d x d d? ? ? ?? ? ? ? ? ? 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 ③ 加班時間限制 目標(biāo)規(guī)劃為要達(dá)到某一目標(biāo)，必須使其偏差變量達(dá)到最 小。假如 沒有 ，則 需要進一步引進新的約束條件。在本例中， 第 二個目標(biāo)是給全時售貨員的加班時間一個限制， 不 超過 100 小時。在前面的約束中我們不能得到一個偏差變量使之滿足這個目標(biāo)，所以必須引進新的約束條件 ，故 把全時售貨員加班時間列為第四個目標(biāo)。關(guān)于全時售貨員的加班有兩個不同目標(biāo)。限制全時售貨員的加班時數(shù)不超過 100 小時。為此引進下面的約束條件。 由于2d?代表全體售貨員實際加班時間，于是設(shè)計如下偏差變量： 21d?： 全體全 時 售貨員 下月加班不足 100 小時的負(fù)偏差 ； 21d?： 全體全時售貨員下月加班超過 100 小時的正偏差 。 則有約束條件：2 2 1 2 1100d d d? ? ?? ? ? 因為實際的加班時數(shù)可能超過也可能 等于 或少于 l 00 小時，故引進對 100 小時的正負(fù)偏差變量。因而有一個偏差變量21d?，使之達(dá)到極小以實現(xiàn)第 2 個目標(biāo)。應(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 元。于是有：全時售貨員每加班 l 小時，賣出 5 張唱片的總利潤為 15 元，扣去加班費 9 元，則商店得利潤 15 9= 6 元。半時售貨員每加班 1 小時，賣出 2 張唱片的總利潤為 6 元，扣去加班費 4 元，商店得利潤 6 4= 2 元。因此，全時的和半時售貨員加班 1 小時所獲得利潤的比為 3: 1 ，故權(quán)因子之比為23: 1 : 3dd??? 線性目標(biāo)規(guī)劃的數(shù)學(xué)模型 所以，這個問題的目標(biāo)規(guī)劃模型為： ? ? ? ?1 1 2 21 3 2 3 4 3 21 2 1 11 2 22 3 32 21 2121 21m in 2 3 . 5 2 5500800320100, , , , 0 , 1 , 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)的單純形方法逐一完成其求解過程。在求解過程中進基變量、出基變量及樞點元素的選擇原則與線性規(guī)劃的單純形法相同，不同的是要以不影響較高級目標(biāo)的達(dá)成值為前提選擇較低級目標(biāo)的達(dá)成值，如此反復(fù)迭代，直至進行到最低級目標(biāo)的達(dá)成函數(shù)達(dá)最優(yōu)為止。 序列法 ? 具體計算步驟 序列法 第四步 ： 建立相應(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ī)劃模型的解是原目標(biāo)規(guī)劃模型的解，并且如下向量： ? ?* * * *12, , . . . ,kf f f?f 也反映了各目標(biāo)實現(xiàn)的程度亦稱達(dá)成向量。 序列法 例 求解如下目標(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 , 2 , 3 , 4i j jf p d p d p d dx x d dx x d dx x d dx x d dx d d i j? ? ? ????????????? ? ? ??? ? ? ???? ? ? ? ??? ? ? ???? ? ? ??? ? ??? 序列法 第一步，計算1p等級目標(biāo)的最優(yōu)解。 ( 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) 用單純形法求解。 將 目標(biāo)函數(shù)變換為13m i n fd??，用線性規(guī)劃的方法求解， 一個最優(yōu)解是：1 2 3 3160 00 , 0 , 0x x d d??? ? ? ?； 另一個最優(yōu)解是：2 1 3 3160 00 , 0 , 0x x d d??? ? ? ?。 于是得到最優(yōu)目標(biāo)函數(shù)值 *10f ?。 由最優(yōu)目標(biāo)函數(shù)值知道，因為30d??，故1p優(yōu)先目標(biāo)已經(jīng)達(dá)到最優(yōu)。 由于330dd????，表明330dd????，所以，在后面其他優(yōu)先等級目標(biāo)對應(yīng)的線性規(guī)劃模型中只有加上330dd????的約束，才能保證求解時不影響1p等級目標(biāo)已經(jīng)得到的最優(yōu)目標(biāo)函數(shù)值，由于33,0dd???，故這個約束世界上就等價于330dd????。 序列法 第二步，計算2p等級目標(biāo)的最優(yōu)解。 ( 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 , 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)時該目標(biāo)方程中設(shè)計變量的值，該約束用于保證在求解當(dāng)前2p目標(biāo)最優(yōu)值時，1p目標(biāo)的最優(yōu)值不被改變。新增加的約束條件 3 是對應(yīng)于2p等級目標(biāo)的目標(biāo)約束。 ( 2) 用單純形法求解 將目標(biāo)函數(shù)變換為24mi n fd??，得到最優(yōu)解：1 2 3 3 4 49000 , 7000 , 0x x d d d d? ? ? ?? ? ? ? ? ?， *20f ?。由最優(yōu)目標(biāo)函數(shù)值知道，因為40d??，故2p優(yōu)先目標(biāo)已經(jīng)達(dá)到最優(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ù)值。 序列法 第三步，計算3p等級目標(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 。 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)值不被改變。新增加的約束條件 5 和約束條件 6 是對應(yīng)于3p等級目標(biāo)的目標(biāo)約束。 ( 2) 用單純形法求解。 將目標(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 ?。 序列法 正如前面的方法所述，最終的這個線性規(guī)劃模型的最優(yōu)解就是原來的目標(biāo)規(guī)劃問題的最優(yōu)解。因為，最后的這個線性規(guī)劃數(shù)學(xué)模型中已經(jīng)包含1p目標(biāo)和2p目標(biāo)的目標(biāo)約束以及 它們的最優(yōu)