【正文】 一般步驟如下： ( 1) 由實(shí)際問(wèn)題建立具有 m 個(gè)目標(biāo)的線(xiàn)性規(guī)劃模型 ( 2) 將多目標(biāo)線(xiàn)性規(guī)劃模型化為目標(biāo)規(guī)劃模型： ? 由實(shí)際問(wèn)題對(duì)第 i 個(gè)目標(biāo)給予適當(dāng)?shù)钠谕? 1 , 2 , . . . ,ie i m?； ? 對(duì)第 i 個(gè)目標(biāo)引進(jìn)偏差變量,iidd??，建立目標(biāo)約束方程并將其列入原約 束條件中； ? 若原約束條件巾有互相矛盾的方程，則對(duì)它們同樣引入,iidd??，更一般的做法是對(duì)所有的約束方程均引入,iidd??； ? 確定 k 個(gè)目標(biāo)的優(yōu)先級(jí)別, 1 , 2 , . . . ,ip i k?以及權(quán)系數(shù),i j i jff?? ? 建立達(dá)成函數(shù)m i n f 完成這些步驟后就建 立 了具有一般形式的字典序或優(yōu)先級(jí)的線(xiàn)性目標(biāo)規(guī)劃。但是注意到模型的建立是靈活的，所以不一定要完全嚴(yán)格按上述一般步驟進(jìn)行。 線(xiàn)性目標(biāo)規(guī)劃的數(shù)學(xué)模型 線(xiàn)性目標(biāo)規(guī)劃的數(shù)學(xué)模型 ① 銷(xiāo)售目標(biāo)約束 完成 5500 銷(xiāo)售目標(biāo)是全時(shí)和半時(shí)售貨員全部工作時(shí)間和其生產(chǎn)率（即每小時(shí)銷(xiāo)售量）的函數(shù)。 設(shè)計(jì)如下變量： 1x：全體全時(shí)售貨員下月的工作時(shí)間（小時(shí)） 2x：全體半時(shí)售貨員下月的工作時(shí)間（小時(shí)） 1d? ：達(dá)不到銷(xiāo)售目標(biāo)的負(fù)偏差 1d? ：超過(guò)銷(xiāo)售目標(biāo)的正偏差 由于制定的目標(biāo)為銷(xiāo)售量 5500 ，于是該約束可以表達(dá)為： 1 2 1 15 2 5500x x d d??? ? ? ? 線(xiàn)性目標(biāo)規(guī)劃的數(shù)學(xué)模型 ② 正常工作時(shí)間約束 銷(xiāo)售時(shí)間由兩種售貨員的正常工作時(shí)數(shù)和人數(shù)所決定。因1x代表全時(shí)售貨員全體下月工作時(shí)數(shù)。 5 個(gè)全時(shí)售貨員，故正常的每月工作時(shí)數(shù)為 5 160 ＝ 800 小時(shí)，半時(shí)工作的售貨員的每月工作時(shí)數(shù)為 4 80 ＝ 320 小時(shí)。 設(shè)計(jì)如下偏差變量： 2d? ：全體全時(shí)售貨員下月的停工時(shí)間；2d? ：全體全時(shí)售貨員下月的加班時(shí)間； 3d? ：全體半時(shí)售貨員下月的停工時(shí)問(wèn)；3d? ：全體半時(shí)售貨員下月的加班時(shí)間。 則有約束條件： 1 2 2 2 3 3800 。 320x d d x d d? ? ? ?? ? ? ? ? ? 線(xiàn)性目標(biāo)規(guī)劃的數(shù)學(xué)模型 ③ 加班時(shí)間限制 目標(biāo)規(guī)劃為要達(dá)到某一目標(biāo)，必須使其偏差變量達(dá)到最 小。假如 沒(méi)有 ，則 需要進(jìn)一步引進(jìn)新的約束條件。在本例中， 第 二個(gè)目標(biāo)是給全時(shí)售貨員的加班時(shí)間一個(gè)限制， 不 超過(guò) 100 小時(shí)。在前面的約束中我們不能得到一個(gè)偏差變量使之滿(mǎn)足這個(gè)目標(biāo)，所以必須引進(jìn)新的約束條件 ，故 把全時(shí)售貨員加班時(shí)間列為第四個(gè)目標(biāo)。關(guān)于全時(shí)售貨員的加班有兩個(gè)不同目標(biāo)。限制全時(shí)售貨員的加班時(shí)數(shù)不超過(guò) 100 小時(shí)。為此引進(jìn)下面的約束條件。 由于2d?代表全體售貨員實(shí)際加班時(shí)間，于是設(shè)計(jì)如下偏差變量： 21d?： 全體全 時(shí) 售貨員 下月加班不足 100 小時(shí)的負(fù)偏差 ； 21d?： 全體全時(shí)售貨員下月加班超過(guò) 100 小時(shí)的正偏差 。 則有約束條件：2 2 1 2 1100d d d? ? ?? ? ? 因?yàn)閷?shí)際的加班時(shí)數(shù)可能超過(guò)也可能 等于 或少于 l 00 小時(shí)，故引進(jìn)對(duì) 100 小時(shí)的正負(fù)偏差變量。因而有一個(gè)偏差變量21d?，使之達(dá)到極小以實(shí)現(xiàn)第 2 個(gè)目標(biāo)。應(yīng)該指出的是上 面 的約束條件可以用不同的方式 表示 出來(lái)，即在正常工作的約 束條件的右端加上 100 ：1 4 4900x d d??? ? ? 線(xiàn)性目標(biāo)規(guī)劃的數(shù)學(xué)模型 根據(jù)優(yōu)先等級(jí)的約定可以得到： 1p：1d? ； 2p：21d? ； 3p：232 dd???，除了保持全體售貨員充分就業(yè)，但加倍優(yōu)先考慮全時(shí)售貨員； 4p：323 dd??? 確定4p表達(dá)形式的理由是：全時(shí)售貨員和半時(shí)售貨員每小時(shí)生產(chǎn)率的比是 5:2 ，而每小時(shí)的加班費(fèi)分別是 9 元和 4 元。于是有：全時(shí)售貨員每加班 l 小時(shí)，賣(mài)出 5 張唱片的總利潤(rùn)為 15 元，扣去加班費(fèi) 9 元，則商店得利潤(rùn) 15 9= 6 元。半時(shí)售貨員每加班 1 小時(shí)，賣(mài)出 2 張唱片的總利潤(rùn)為 6 元，扣去加班費(fèi) 4 元，商店得利潤(rùn) 6 4= 2 元。因此，全時(shí)的和半時(shí)售貨員加班 1 小時(shí)所獲得利潤(rùn)的比為 3: 1 ，故權(quán)因子之比為23: 1 : 3dd??? 線(xiàn)性目標(biāo)規(guī)劃的數(shù)學(xué)模型 所以，這個(gè)問(wèn)題的目標(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? ? ? ? ? ???????? ? ?? ? ? ??? ? ? ? ? ??? ? ? ???? ? ? ??? ? ???? ? ??? ? ??? 線(xiàn)性目標(biāo)規(guī)劃的求解方法 ? 線(xiàn)性目標(biāo)規(guī)劃的序列法 ? 線(xiàn)性目標(biāo)規(guī)劃的多階段法 ? 線(xiàn)性目標(biāo)規(guī)劃的單純形法 序列法 ? 線(xiàn)性目標(biāo)規(guī)劃序列（序子）算法的基本思想是依達(dá)成函數(shù)中各目標(biāo)的優(yōu)先級(jí)別，順序?qū)⒛繕?biāo)規(guī)劃模型分解為一系列的單一的線(xiàn)性規(guī)劃模型，用傳統(tǒng)的單純形方法逐一完成其求解過(guò)程。在求解過(guò)程中進(jìn)基變量、出基變量及樞點(diǎn)元素的選擇原則與線(xiàn)性規(guī)劃的單純形法相同，不同的是要以不影響較高級(jí)目標(biāo)的達(dá)成值為前提選擇較低級(jí)目標(biāo)的達(dá)成值，如此反復(fù)迭代，直至進(jìn)行到最低級(jí)目標(biāo)的達(dá)成函數(shù)達(dá)最優(yōu)為止。 序列法 ? 具體計(jì)算步驟 序列法 第四步 ： 建立相應(yīng)于下一個(gè)優(yōu)先級(jí)別ip的單目標(biāo)線(xiàn)性規(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。 第五步 ： 最后一個(gè)單目標(biāo)線(xiàn)性規(guī)劃模型的解是原目標(biāo)規(guī)劃模型的解，并且如下向量： ? ?* * * *12, , . . . ,kf f f?f 也反映了各目標(biāo)實(shí)現(xiàn)的程度亦稱(chēng)達(dá)成向量。 序列法 例 求解如下目標(biāo)規(guī)劃問(wèn)題 ? ?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? ? ? ????????????? ? ? ??? ? ? ???? ? ? ? ??? ? ? ???? ? ? ??? ? ??? 序列法 第一步，計(jì)算1p等級(jí)目標(biāo)的最優(yōu)解。 ( 1) 建立由1p等級(jí)目標(biāo)構(gòu)成的單一目標(biāo)線(xiàn)性規(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??，用線(xiàn)性規(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??? ? ? ?。 于是得到最優(yōu)目標(biāo)函數(shù)值 *10f ?。 由最優(yōu)目標(biāo)函數(shù)值知道，因?yàn)?0d??，故1p優(yōu)先目標(biāo)已經(jīng)達(dá)到最優(yōu)。 由于330dd????，表明330dd????，所以，在后面其他優(yōu)先等級(jí)目標(biāo)對(duì)應(yīng)的線(xiàn)性規(guī)劃模型中只有加上330dd????的約束，才能保證求解時(shí)不影響1p等級(jí)目標(biāo)已經(jīng)得到的最優(yōu)目標(biāo)函數(shù)值，由于33,0dd???，故這個(gè)約束世界上就等價(jià)于330dd????。 序列法 第二步，計(jì)算2p等級(jí)目標(biāo)的最優(yōu)解。 ( 1) 建立由2p等級(jí)目標(biāo)構(gòu)成的單一目標(biāo)線(xiàn)性規(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)時(shí)該目標(biāo)方程中設(shè)計(jì)變量的值，該約束用于保證在求解當(dāng)前2p目標(biāo)最優(yōu)值時(shí)，1p目標(biāo)的最優(yōu)值不被改變。新增加的約束條件 3 是對(duì)應(yīng)于2p等級(jí)目標(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ù)值知道，因?yàn)?0d??，故2p優(yōu)先目標(biāo)已經(jīng)達(dá)到最優(yōu)。 由于440dd????，表明440dd????，所以，在后面其他優(yōu)先等級(jí)目標(biāo)對(duì)應(yīng)的線(xiàn)性規(guī)劃模型中只有加上440dd????和330dd????的約束，才能保證求解時(shí)不影響1p等級(jí)目標(biāo)和2p等級(jí)目 標(biāo)已經(jīng)得到的最優(yōu)目標(biāo)函數(shù)值。 序列法 第三步，計(jì)算3p等級(jí)目標(biāo)的最優(yōu)解。 ( 1) 建立由3p等級(jí)目標(biāo)構(gòu)成的單一目標(biāo)線(xiàn)性規(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)時(shí)該目標(biāo)方程中設(shè)計(jì)變量的值，這 4 個(gè)約束的條件的加入用于保證在求解當(dāng)前3p目標(biāo)最優(yōu)值時(shí)，1p目標(biāo)和2p目標(biāo)的最優(yōu)值不被改變。新增加的約束條件 5 和約束條件 6 是對(duì)應(yīng)于3p等級(jí)目標(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 ?。 序列法 正如前面的方法所述，最終的這個(gè)線(xiàn)性規(guī)劃模型的最優(yōu)解就是原來(lái)的目標(biāo)規(guī)劃問(wèn)題的最優(yōu)解。因?yàn)椋詈蟮倪@個(gè)線(xiàn)性規(guī)劃數(shù)學(xué)模型中已經(jīng)包含1p目標(biāo)和2p目標(biāo)的目標(biāo)約束以及 它們的最優(yōu)