2多目標規(guī)劃方法第6章

2多目標規(guī)劃方法第6章第3節(jié)目標規(guī)劃方法

目標規(guī)劃模型

求解目標規(guī)劃的單純形方法

通過上節(jié)的介紹和討論，我們知道，目標規(guī)劃方法是解決多目標規(guī)劃問題的重要技術(shù)之一。這一方法是美國學(xué)者查恩斯（A.Charnes）和庫伯（）于1961年在線性規(guī)劃的基礎(chǔ)上提出來的。后來，查斯基萊恩（U.Jaashelainen）和李（S.Lee）等人，進一步給出了求解目標規(guī)劃問題的一般性方法——單純形方法。

一、目標規(guī)劃模型

給定若干目標以及實現(xiàn)這些目標的優(yōu)先順序，在有限的資源條件下，使總的偏離目標值的偏差最小。（一）基本思想例1：某一個企業(yè)利用某種原材料和現(xiàn)有設(shè)備可生產(chǎn)甲、乙兩種產(chǎn)品，其中，甲、乙兩種產(chǎn)品的單價分別為8元和10元；生產(chǎn)單位甲、乙兩種產(chǎn)品需要消耗的原材料分別為2個單位和1個單位，需要占用的設(shè)備分別為1臺時和2臺時；原材料擁有量為11個單位；可利用的設(shè)備總臺時為10臺時。試問：如何確定其生產(chǎn)方案？（二）目標規(guī)劃的有關(guān)概念

如果決策者所追求的唯一目標是使總產(chǎn)值達到最大，則這個企業(yè)的生產(chǎn)方案可以由如下線性規(guī)劃模型給出：求，，使

（）

而且滿足

式中：和為決策變量，為目標函數(shù)值。將上述問題化為標準后，用單純形方法求解可得最佳決策方案為（萬元）。

但是，在實際決策時，企業(yè)領(lǐng)導(dǎo)者必須考慮市場等一系列其他條件，如：①根據(jù)市場信息，甲種產(chǎn)品的需求量有下降的趨勢，因此甲種產(chǎn)品的產(chǎn)量不應(yīng)大于乙種產(chǎn)品的產(chǎn)量。②超過計劃供應(yīng)的原材料，需用高價采購，這就會使生產(chǎn)成本增加。③應(yīng)盡可能地充分利用設(shè)備的有效臺時，但不希望加班。④應(yīng)盡可能達到并超過計劃產(chǎn)值指標56萬元。

這樣，該企業(yè)生產(chǎn)方案的確定，便成為一個多目標決策問題，這一問題可以運用目標規(guī)劃方法進行求解。

為了建立目標規(guī)劃數(shù)學(xué)模型，下面引入有關(guān)概念。

偏差變量在目標規(guī)劃模型中，除了決策變量外，還需要引入正、負偏差變量、。其中，正偏差變量表示決策值超過目標值的部分，負偏差變量表示決策值未達到目標值的部分。因為決策值不可能既超過目標值同時又未達到目標值，故有成立。絕對約束和目標約束絕對約束，必須嚴格滿足的等式約束和不等式約束，譬如，線性規(guī)劃問題的所有約束條件都是絕對約束，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。

目標約束，目標規(guī)劃所特有的，可以將約束方程右端項看做是追求的目標值，在達到此目標值時允許發(fā)生正的或負的偏差，可加入正負偏差變量，是軟約束。線性規(guī)劃問題的目標函數(shù)，在給定目標值和加入正、負偏差變量后可以轉(zhuǎn)化為目標約束，也可以根據(jù)問題的需要將絕對約束轉(zhuǎn)化為目標約束。

優(yōu)先因子（優(yōu)先等級）與權(quán)系數(shù)一個規(guī)劃問題,常常有若干個目標，決策者對各個目標的考慮,往往是有主次或輕重緩急的。凡要求第一位達到的目標賦予優(yōu)先因子，次位的目標賦予優(yōu)先因子，…并規(guī)定表示比有更大的優(yōu)先權(quán)。這就是說，首先保證級目標的實現(xiàn)，這時可以不考慮次級目標；而級目標是在實現(xiàn)級目標的基礎(chǔ)上考慮的；依此類推。，

若要區(qū)別具有相同優(yōu)先因子的目標的差別，就可以分別賦予它們不同的權(quán)系數(shù)。這些優(yōu)先因子和權(quán)系數(shù)都由決策者按照具體情況而定。目標函數(shù)目標規(guī)劃的目標函數(shù)（準則函數(shù)）是按照各目標約束的正、負偏差變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)造的。當每一目標確定后，盡可能縮小與目標值的偏離。因此，目標規(guī)劃的目標函數(shù)只能是基本形式有3種：）

①

要求恰好達到目標值，就是正、負偏差變量都要盡可能小,即

（）

②要求不超過目標值，即允許達不到目標值，就是正偏差變量要盡可能小，即（）

③

要求超過目標值，也就是超過量不限，但負偏差變量要盡可能小，即

（）

在實際問題中，可以根據(jù)決策者的要求，引入正、負偏差變量和目標約束，并給不同目標賦予相應(yīng)的優(yōu)先因子和權(quán)系數(shù)，構(gòu)造目標函數(shù)，建立模型。

例2：在例1中，如果決策者在原材料供應(yīng)受嚴格控制的基礎(chǔ)上考慮：首先是甲種產(chǎn)品的產(chǎn)量不超過乙種產(chǎn)品的產(chǎn)量；其次是充分利用設(shè)備的有限臺時，不加班；再次是產(chǎn)值不小于56萬元。并分別賦予這3個目標優(yōu)先因子。試建立該問題的目標規(guī)劃模型。解：根據(jù)題意，這一決策問題的目標規(guī)劃模型是（）（）（）（）（）（）

假定有L個目標，K個優(yōu)先級(K≤L)，n個變量。在同一優(yōu)先級中不同目標的正、負偏差變量的權(quán)系數(shù)分別為、，則多目標規(guī)劃問題可以表示為（三）目標規(guī)劃模型的一般形式（）（）（）（）（）在以上各式中：、分別為賦予優(yōu)先因子的第個目標的正、負偏差變量的權(quán)系數(shù)；為第個目標的預(yù)期值；為決策變量；、分別為第個目標的正、負偏差變量。（）式為目標函數(shù);（）式為目標約束;（）式為絕對約束;（）式和（）式為非負約束;

、、分別為目標約束和絕對約束中決策變量的系數(shù)及約束值。其中：

；；；。二、求解目標規(guī)則的單純形方法

目標規(guī)劃模型仍可以用單純形方法求解，在求解時作以下規(guī)定：①因為目標函數(shù)都是求最小值，所以，最優(yōu)判別檢驗數(shù)為②因為非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子

所以檢驗數(shù)的正、負首先決定于的系數(shù)的正、負，若，則檢驗數(shù)的正、負就決定于的系數(shù)的正、負，下面可依此類推。

據(jù)此，我們可以總結(jié)出求解目標規(guī)劃問題的單純形方法的計算步驟如下：①建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別排成L行，置。

②檢查該行中是否存在負數(shù)，且對應(yīng)的前L-1行的系數(shù)是零。若有，取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)③。若無負數(shù)，則轉(zhuǎn)⑤。③按最小比值規(guī)則（規(guī)則）確定換出變量，當存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。④按單純形法進行基變換運算，建立新的計算表，返回②。⑤當l=L時，計算結(jié)束，表中的解即為滿意解。否則置l=l+1，返回②。例3：試用單純形法求解例2所描述的目標規(guī)劃問題解：首先將這一問題化為如下標準形式

(1)取,,,,為初始基變量，列出初始單純形表。表(2)取，檢查檢驗數(shù)的行，因該行無負檢驗數(shù)，故轉(zhuǎn)(5)。

(5)因為，置，返回(2)。

(2)檢查發(fā)現(xiàn)檢驗數(shù)行中有，，因為有，所以為換入變量，轉(zhuǎn)入(3)。

(3按規(guī)則計算：，所以為換出變量，轉(zhuǎn)入(4)。

(4)進行換基運算，得到表。以此類推，直至得到最終單純形表為止，如表所示。

表表

由表6.３.3可知，，，為滿意解。檢查檢驗數(shù)行，發(fā)現(xiàn)非基變量的檢驗數(shù)為0，這表明該問題存在多重解。表

在表中，以非基變量為換入變量，為換出變量，經(jīng)迭代得到表。

從表可以看出，，也是該問題的滿意解。

土地利用問題

生產(chǎn)計劃問題投資問題第4節(jié)多目標規(guī)劃應(yīng)用實例

第5章第1節(jié)中，我們運用線性規(guī)劃方法討論了表所描述的農(nóng)場作物種植計劃的問題。但是，由于線性規(guī)劃只有單一的目標函數(shù)，所以當時我們建立的作物種植計劃模型屬于單目標規(guī)劃模型，給出的種植計劃方案，要么使總產(chǎn)量最大，要么使總產(chǎn)值最大；兩個目標無法兼得。那么，究竟怎樣制定作物種植計劃，才能兼顧總產(chǎn)量和總產(chǎn)值雙重目標呢？下面我們用多目標規(guī)劃的思想方法解決這個問題。

一、土地利用問題

取為決策變量，它表示在第j等級的耕地上種植第i種作物的面積。如果追求總產(chǎn)量最大和總產(chǎn)值最大雙重目標，那么，目標函數(shù)包括：①追求總產(chǎn)量最大（）

②追求總產(chǎn)值最大（）

根據(jù)題意，約束方程包括：耕地面積約束最低收獲量約束（）

（）

（）

非負約束

對上述多目標規(guī)劃問題，我們可以采用如下方法，求其非劣解。用線性加權(quán)方法

取，重新構(gòu)造目標函數(shù)

這樣，就將多目標規(guī)劃轉(zhuǎn)化為單目標線性規(guī)劃。

用單純形方法對該問題求解，可以得到一個滿意解（非劣解）方案，結(jié)果見表。此方案是：III等耕地全部種植水稻，I等耕地全部種植玉米，II等耕地種植大豆19.1176hm2、種植玉米280.8824hm2。在此方案下，線性加權(quán)目標函數(shù)的最大取值為6445600。表6.4.1線性加權(quán)目標下的非劣解方案（單位：hm2）

目標規(guī)劃方法

實際上，除了線性加權(quán)求和法以外，我們還可以用目標規(guī)劃方法求解上述多目標規(guī)劃問題。如果我們對總產(chǎn)量和總產(chǎn)值，分別提出一個期望目標值（kg）（元）

并將兩個目標視為相同的優(yōu)先級。

如果、分別表示對應(yīng)第1個目標期望值的正、負偏差變量，、分別表示對應(yīng)于第2個目標期望值的正、負偏差變量，而且將每一個目標的正、負偏差變量同等看待（即可將它們的權(quán)系數(shù)都賦為1），那么，該目標規(guī)劃問題的目標函數(shù)為

對應(yīng)的兩個目標約束為（）

（）即

除了目標約束以外，該模型的約束條件，還包括硬約束和非負約束的限制。其中，硬約束包括耕地面積約束（）式和最低收獲量約束（）式；非負約束，不但包括決策變量的非負約束（）式，還包括正、負偏差變量的非負約束

解上述目標規(guī)劃問題，可以得到一個非劣解方案，詳見表。

表6.4.2目標規(guī)劃的非劣解方案（單位:hm2）

在此非劣解方案下，兩個目標的正、負差變量分為，，，。

二、生產(chǎn)計劃問題

某企業(yè)擬生產(chǎn)A和B兩種產(chǎn)品，其生產(chǎn)投資費用分別為2100元/t和4800元/t。A、B兩種產(chǎn)品的利潤分別為3600元/t和6500元/t。A、B產(chǎn)品每月的最大生產(chǎn)能力分別為5t和8t；市場對這兩種產(chǎn)品總量的需求每月不少于9t。試問該企業(yè)應(yīng)該如何安排生產(chǎn)計劃，才能既能滿足市場需求，又節(jié)約投資，而且使生產(chǎn)利潤達到最大?

該問題是一個線性多目標規(guī)劃問題。如果計劃決策變量用和表示，它們分別代表A、B產(chǎn)品每月的生產(chǎn)量（單位：t）；表示生產(chǎn)A、B兩種產(chǎn)品的總投資費用（單位：元）；表示生產(chǎn)A、B兩種產(chǎn)品獲得的總利潤（單位：元）。那么，該多目標規(guī)劃問題就是：求和，使

而且滿足

對于上述多目標規(guī)劃問題，如果決策者提出的期望目標是：（1）每個月的總投資不超30000元；（2）每個月的總利潤達到或超過45000元；（3）兩個目標同等重要。那么，借助Matlab軟件系統(tǒng)中的優(yōu)化計算工具進行求解