6 目標(biāo)規(guī)劃方法

1、第第6 6節(jié)節(jié) 目標(biāo)規(guī)劃方法目標(biāo)規(guī)劃方法 目標(biāo)規(guī)劃模型目標(biāo)規(guī)劃模型 求解目標(biāo)規(guī)劃的單純形方法求解目標(biāo)規(guī)劃的單純形方法 通過(guò)上節(jié)的介紹和討論，我們知道，目標(biāo)規(guī)劃方法是解決多目標(biāo)規(guī)劃問(wèn)題的重要技術(shù)之一。 這一方法是美國(guó)學(xué)者查恩斯（A.Charnes）和庫(kù)伯（W.W.Cooper）于1961年在線性規(guī)劃的基礎(chǔ)上提出來(lái)的。后來(lái)，查斯基萊恩（U.Jaashelainen）和李（S.Lee）等人，進(jìn)一步給出了求解目標(biāo)規(guī)劃問(wèn)題的一般性方法單純形方法。 一、目標(biāo)規(guī)劃模型一、目標(biāo)規(guī)劃模型 給定若干目標(biāo)以及實(shí)現(xiàn)這些目標(biāo)的優(yōu)先順序，在有限的資源條件下，使總的偏離目標(biāo)值的偏差最小。（一）基本思想（一）基本思想例例1：

2、某一個(gè)企業(yè)利用某種原材料和現(xiàn)有設(shè)備可生產(chǎn)甲、乙兩種產(chǎn)品，其中，甲、乙兩種產(chǎn)品的單價(jià)分別為8元和10元；生產(chǎn)單位甲、乙兩種產(chǎn)品需要消耗的原材料分別為2個(gè)單位和1個(gè)單位，需要占用的設(shè)備分別為1臺(tái)時(shí)和2臺(tái)時(shí)；原材料擁有量為11個(gè)單位；可利用的設(shè)備總臺(tái)時(shí)為10臺(tái)時(shí)。試問(wèn)：如何確定其生產(chǎn)方案？（二）目標(biāo)規(guī)劃的有關(guān)概念（二）目標(biāo)規(guī)劃的有關(guān)概念 如果決策者所追求的唯一目標(biāo)是使總產(chǎn)值達(dá)到最大，則這個(gè)企業(yè)的生產(chǎn)方案可以由如下線性規(guī)劃模型給出：求 ， ，使 1x2x 21108maxxxz（.1） 而且滿(mǎn)足 )4 . 3 . 6(0,) 3 . 3 . 6(102)2 . 3 . 6(112212

3、121xxxxxx 式中：和為決策變量，為目標(biāo)函數(shù)值。將上述問(wèn)題化為標(biāo)準(zhǔn)后，用單純形方法求解可得最佳決策方案為 （萬(wàn)元）。 62, 3, 421Zxx 但是，在實(shí)際決策時(shí)，企業(yè)領(lǐng)導(dǎo)者必須考慮市場(chǎng)等一系列其他條件，如： 根據(jù)市場(chǎng)信息，甲種產(chǎn)品的需求量有下降的趨勢(shì)，因此甲種產(chǎn)品的產(chǎn)量不應(yīng)大于乙種產(chǎn)品的產(chǎn)量。 超過(guò)計(jì)劃供應(yīng)的原材料，需用高價(jià)采購(gòu)，這就會(huì)使生產(chǎn)成本增加。 應(yīng)盡可能地充分利用設(shè)備的有效臺(tái)時(shí)，但不希望加班。 應(yīng)盡可能達(dá)到并超過(guò)計(jì)劃產(chǎn)值指標(biāo)56萬(wàn)元。 這樣，該企業(yè)生產(chǎn)方案的確定，便成為一個(gè)多目標(biāo)決策問(wèn)題，這一問(wèn)題可以運(yùn)用目標(biāo)規(guī)劃方法進(jìn)行求解。 為了建立目標(biāo)規(guī)劃數(shù)學(xué)模型，下面引入有關(guān)概念。 n

4、偏差變量偏差變量 在目標(biāo)規(guī)劃模型中，除了決策變量外，還 需要引入正、負(fù)偏差變量 、 。其中，正偏差變量表示決策值超過(guò)目標(biāo)值的部分，負(fù)偏差變量表示決策值未達(dá)到目標(biāo)值的部分。 因?yàn)闆Q策值不可能既超過(guò)目標(biāo)值同時(shí)又未達(dá)到目標(biāo)值，故有 成立。dd0ddn絕對(duì)約束和目標(biāo)約束絕對(duì)約束和目標(biāo)約束 絕對(duì)約束，必須嚴(yán)格滿(mǎn)足的等式約束和不等式約束，譬如，線性規(guī)劃問(wèn)題的所有約束條件都是絕對(duì)約束，不能滿(mǎn)足這些約束條件的解稱(chēng)為非可行解，所以它們是硬約束。 目標(biāo)約束，目標(biāo)規(guī)劃所特有的，可以將約束方程右端項(xiàng)看做是追求的目標(biāo)值，在達(dá)到此目標(biāo)值時(shí)允許發(fā)生正的或負(fù)的偏差 ，可加入正負(fù)偏差變量，是軟約束。 線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)，在

5、給定目標(biāo)值和加入正、負(fù)偏差變量后可以轉(zhuǎn)化為目標(biāo)約束，也可以根據(jù)問(wèn)題的需要將絕對(duì)約束轉(zhuǎn)化為目標(biāo)約束。 n優(yōu)先因子（優(yōu)先等級(jí)）與權(quán)系數(shù)優(yōu)先因子（優(yōu)先等級(jí)）與權(quán)系數(shù) 一個(gè)規(guī)劃問(wèn)題,常常有若干個(gè)目標(biāo)，決策者對(duì)各個(gè)目標(biāo)的考慮,往往是有主次或輕重緩急的。凡要求第一位達(dá)到的目標(biāo)賦予優(yōu)先因子 ，次位的目標(biāo)賦予優(yōu)先因子 ，并規(guī)定 表示 比 有更大的優(yōu)先權(quán)。這就是說(shuō)，首先保證 級(jí)目標(biāo)的實(shí)現(xiàn)，這時(shí)可以不考慮次級(jí)目標(biāo)；而 級(jí)目標(biāo)是在實(shí)現(xiàn) 級(jí)目標(biāo)的基礎(chǔ)上考慮的；依此類(lèi)推。1p2p1(1,2, )llpplLL1lp1p2p1plp， 若要區(qū)別具有相同優(yōu)先因子 的目標(biāo)的差別，就可以分別賦予它們不同的權(quán)系數(shù) 。這些優(yōu)先因子

6、和權(quán)系數(shù)都由決策者按照具體情況而定。 lp(1,2,)lkkKLn目標(biāo)函數(shù)目標(biāo)函數(shù) 目標(biāo)規(guī)劃的目標(biāo)函數(shù)（準(zhǔn)則函數(shù)）是按照各目標(biāo)約束的正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)造的。當(dāng)每一目標(biāo)確定后，盡可能縮小與目標(biāo)值的偏離。因此，目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是基本形式有3種： ),(minddfZ (6.3.5） 要求恰好達(dá)到目標(biāo)值，就是正、負(fù)偏差變量都要盡可能小,即 ),(minddfZ（6.3.6） 要求不超過(guò)目標(biāo)值，即允許達(dá)不到目標(biāo)值，就是正偏差變量要盡可能小，即)(mindfZ（6.3.7） 要求超過(guò)目標(biāo)值，也就是超過(guò)量不限，但負(fù)偏差變量要盡可能小，即 )(mindfZ（6.3.8） 在實(shí)際問(wèn)題

7、中，可以根據(jù)決策者的要求，引入正、負(fù)偏差變量和目標(biāo)約束，并給不同目標(biāo)賦予相應(yīng)的優(yōu)先因子和權(quán)系數(shù)，構(gòu)造目標(biāo)函數(shù)，建立模型。 例例2 2：在例1中，如果決策者在原材料供應(yīng)受?chē)?yán)格控制的基礎(chǔ)上考慮：首先是甲種產(chǎn)品的產(chǎn)量不超過(guò)乙種產(chǎn)品的產(chǎn)量；其次是充分利用設(shè)備的有限臺(tái)時(shí)，不加班；再次是產(chǎn)值不小于56萬(wàn)元。并分別賦予這3個(gè)目標(biāo)優(yōu)先因子 。試建立該問(wèn)題的目標(biāo)規(guī)劃模型。321,PPP解解：根據(jù)題意，這一決策問(wèn)題的目標(biāo)規(guī)劃模型是3322211)(mindpddpdpZ11221 xx01121ddxx1022221ddxx561083321ddxx)3 , 2 , 1(0,21iddxxii（6.3.9）（6.

8、3.10）（6.3.11）（6.3.12）（6.3.13）（6.3.14） 假定有L個(gè)目標(biāo)，K個(gè)優(yōu)先級(jí)(KL)，n個(gè)變量。在同一優(yōu)先級(jí) 中不同目標(biāo)的正、負(fù)偏差變量的權(quán)系數(shù)分別為 、 ，則多目標(biāo)規(guī)劃問(wèn)題可以表示為kPklkl KkLllkllklkddPZ11)(min( )1(1,2, )nljjllljc xddglLL1( , )(1,2,)nijjija xbim L0(1,2, )jxjnL,0(1,2, )llddlLL（三）目標(biāo)規(guī)劃模型的一般形式（三）目標(biāo)規(guī)劃模型的一般形式 （6.3.15）（6.3.16）（6.3.17）（6.3.18）（6.3.19）在以上各式中： 、 分別為賦

9、予 優(yōu)先因子的第 個(gè)目標(biāo)的正、負(fù)偏差變量的權(quán)系數(shù)； 為第 個(gè)目標(biāo)的預(yù)期值； 為決策變量； 、 分別為第 個(gè)目標(biāo)的正、負(fù)偏差變量。lklklpkkgkjxkdkdk（6.3.15）式為目標(biāo)函數(shù);（6.3.16）式為目標(biāo)約束;（6.3.17）式為絕對(duì)約束;（6.3.18）式和（6.3.19）式為非負(fù)約束; 、 、 分別為目標(biāo)約束和絕對(duì)約束中決策變量的系數(shù)及約束值。其中： ； ； ； 。 )(kjcijaib1,2,imL1,2,jnL1,2,lLL1,2,kKL二、求解目標(biāo)規(guī)則的單純形方法二、求解目標(biāo)規(guī)則的單純形方法 目標(biāo)規(guī)劃模型仍可以用單純形方法求解 ，在求解時(shí)作以下規(guī)定： 因?yàn)槟繕?biāo)函數(shù)都是求最

10、小值，所以，最優(yōu)判別檢驗(yàn)數(shù)為 因?yàn)榉腔兞康臋z驗(yàn)數(shù)中含有不同等級(jí)的優(yōu)先因子 0(1,2, )jjczjnL12KPPPLKkkkjjjPazc1(1,2,1,2,)jnkKLL； 所以檢驗(yàn)數(shù)的正、負(fù)首先決定于 的系數(shù) 的正、負(fù)，若 ，則檢驗(yàn)數(shù)的正、負(fù)就決定于 的系數(shù) 的正、負(fù)，下面可依此類(lèi)推。1pj101j2pj2 據(jù)此，我們可以總結(jié)出求解目標(biāo)規(guī)劃問(wèn)題的單純形方法的計(jì)算步驟如下： 建立初始單純形表，在表中將檢驗(yàn)數(shù) 行 按 優(yōu) 先 因 子 個(gè) 數(shù) 分 別 排 成 L 行 ，置 。 1l 檢查該行中是否存在負(fù)數(shù)，且對(duì)應(yīng)的前L-1行的系數(shù)是零。若有，取其中最小者對(duì)應(yīng)的變量為換入變量，轉(zhuǎn)。若無(wú)負(fù)數(shù)，則

11、轉(zhuǎn)。 按最小比值規(guī)則（ 規(guī)則）確定換出變量，當(dāng)存在兩個(gè)和兩個(gè)以上相同的最小比值時(shí)，選取具有較高優(yōu)先級(jí)別的變量為換出變量。 按單純形法進(jìn)行基變換運(yùn)算，建立新的計(jì)算表，返回。 當(dāng)l=L時(shí)，計(jì)算結(jié)束，表中的解即為滿(mǎn)意解。否則置l=l+1，返回 。例例3 3：試用單純形法求解例2所描述的目標(biāo)規(guī)劃問(wèn)題解：解：首先將這一問(wèn)題化為如下標(biāo)準(zhǔn)形式 3322211)(mindpddpdpZ112321xxx01121ddxx1022221ddxx561083321ddxx)3 , 2 , 1(0,iddxiii (1)取 , , , ,為初始基變量，列出初始單純形表。表6.3.13x1d2d3d (2)取 ，檢查檢驗(yàn)數(shù)的 行，因該行無(wú)負(fù)檢驗(yàn)數(shù)，故轉(zhuǎn)(5) 。 (5) 因?yàn)?，置 ，返回(2)。 (2) 檢查發(fā)現(xiàn)檢驗(yàn)數(shù) 行中有 ， ，因?yàn)橛?，所以 為換入變量，轉(zhuǎn)入(3)。 1l1p31Ll21 ll2p1222, 1min2x (3按 規(guī)則計(jì)算： ，所以 為換出變量，轉(zhuǎn)入(4)。 (4)進(jìn)行換基運(yùn)算，得到表6.3.2。以此類(lèi)推，直至得到最終單純形表為止，如表6.3.3