第6章2多目標(biāo)規(guī)劃方法ppt課件

1、第3節(jié) 目的規(guī)劃方法 目的規(guī)劃模型 求解目的規(guī)劃的單純形方法 經(jīng)過上節(jié)的引見和討論，我們知道，目的規(guī)劃方法是處理多目的規(guī)劃問題的重要技術(shù)之一。 這一方法是美國學(xué)者查恩斯A.Charnes和庫伯W.W.Cooper于1961年在線性規(guī)劃的根底上提出來的。后來，查斯基萊恩U.Jaashelainen和李S.Lee等人，進(jìn)一步給出了求解目的規(guī)劃問題的普通性方法單純形方法。 一、目的規(guī)劃模型 給定假設(shè)干目的以及實現(xiàn)這些目的的優(yōu)先順序，在有限的資源條件下，使總的偏離目的值的偏向最小。一根本思想例1：某一個企業(yè)利用某種原資料和現(xiàn)有設(shè)備可消費(fèi)甲、乙兩種產(chǎn)品，其中，甲、乙兩種產(chǎn)品的單價分別為8元和10元；消費(fèi)

2、單位甲、乙兩種產(chǎn)品需求耗費(fèi)的原資料分別為2個單位和1個單位，需求占用的設(shè)備分別為1臺時和2臺時；原資料擁有量為11個單位；可利用的設(shè)備總臺時為10臺時。試問：如何確定其消費(fèi)方案？二目的規(guī)劃的有關(guān)概念 假設(shè)斷策者所追求的獨(dú)一目的是使總產(chǎn)值到達(dá)最大，那么這個企業(yè)的消費(fèi)方案可以由如下線性規(guī)劃模型給出：求 ， ，使 6.3.1 而且滿足 式中：和為決策變量，為目的函數(shù)值。將上述問題化為規(guī)范后，用單純形方法求解可得最正確決策方案為 萬元。 但是，在實踐決策時，企業(yè)指點(diǎn)者必需思索市場等一系列其他條件，如： 根據(jù)市場信息，甲種產(chǎn)品的需求量有下降的趨勢，因此甲種產(chǎn)品的產(chǎn)量不應(yīng)大于乙種產(chǎn)品的產(chǎn)量。 超越方案供應(yīng)

3、的原資料，需用高價采購，這就會使消費(fèi)本錢添加。 應(yīng)盡能夠地充分利用設(shè)備的有效臺時，但不希望加班。 應(yīng)盡能夠到達(dá)并超越方案產(chǎn)值目的56萬元。 這樣，該企業(yè)消費(fèi)方案確實定，便成為一個多目的決策問題，這一問題可以運(yùn)用目的規(guī)劃方法進(jìn)展求解。 為了建立目的規(guī)劃數(shù)學(xué)模型，下面引入有關(guān)概念。 偏向變量 在目的規(guī)劃模型中，除了決策變量外，還 需求引入正、負(fù)偏向變量 、 。其中，正偏向變量表示決策值超越目的值的部分，負(fù)偏向變量表示決策值未到達(dá)目的值的部分。 由于決策值不能夠既超越目的值同時又未到達(dá)目的值，故有 成立。絕對約束和目的約束 絕對約束，必需嚴(yán)厲滿足的等式約束和不等式約束，譬如，線性規(guī)劃問題的一切約束條

4、件都是絕對約束，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。 目的約束，目的規(guī)劃所特有的，可以將約束方程右端項看做是追求的目的值，在到達(dá)此目的值時允許發(fā)生正的或負(fù)的偏向 ，可參與正負(fù)偏向變量，是軟約束。 線性規(guī)劃問題的目的函數(shù)，在給定目的值和參與正、負(fù)偏向變量后可以轉(zhuǎn)化為目的約束，也可以根據(jù)問題的需求將絕對約束轉(zhuǎn)化為目的約束。 優(yōu)先因子優(yōu)先等級與權(quán)系數(shù) 一個規(guī)劃問題,經(jīng)常有假設(shè)干個目的，決策者對各個目的的思索,往往是有主次或輕重緩急的。凡要求第一位到達(dá)的目的賦予優(yōu)先因子 ，次位的目的賦予優(yōu)先因子 ，并規(guī)定 表示 比 有更大的優(yōu)先權(quán)。這就是說，首先保證 級目的的實現(xiàn)，這時可以不思索次

5、級目的；而 級目的是在實現(xiàn) 級目的的根底上思索的；依此類推。， 假設(shè)要區(qū)別具有一樣優(yōu)先因子 的目的的差別，就可以分別賦予它們不同的權(quán)系數(shù) 。這些優(yōu)先因子和權(quán)系數(shù)都由決策者按照詳細(xì)情況而定。 目的函數(shù) 目的規(guī)劃的目的函數(shù)準(zhǔn)那么函數(shù)是按照各目的約束的正、負(fù)偏向變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)造的。當(dāng)每一目確實定后，盡能夠減少與目的值的偏離。因此，目的規(guī)劃的目的函數(shù)只能是根本方式有3種： (6.3.5 要求恰好到達(dá)目的值，就是正、負(fù)偏向變量都要盡能夠小,即 6.3.6 要求不超越目的值，即允許達(dá)不到目的值，就是正偏向變量要盡能夠小，即6.3.7 要求超越目的值，也就是超越量不限，但負(fù)偏向變量要盡能夠小，

6、即 6.3.8 在實踐問題中，可以根據(jù)決策者的要求，引入正、負(fù)偏向變量和目的約束，并給不同目的賦予相應(yīng)的優(yōu)先因子和權(quán)系數(shù)，構(gòu)造目的函數(shù)，建立模型。 例2：在例1中，假設(shè)斷策者在原資料供應(yīng)受嚴(yán)厲控制的根底上思索：首先是甲種產(chǎn)品的產(chǎn)量不超越乙種產(chǎn)品的產(chǎn)量；其次是充分利用設(shè)備的有限臺時，不加班；再次是產(chǎn)值不小于56萬元。并分別賦予這3個目的優(yōu)先因子 。試建立該問題的目的規(guī)劃模型。解：根據(jù)題意，這一決策問題的目的規(guī)劃模型是...14 假定有L個目的，K個優(yōu)先級(KL)，n個變量。在同一優(yōu)先級 中不同目的的正、負(fù)偏向變量的權(quán)系數(shù)分別為 、 ，那

7、么多目的規(guī)劃問題可以表示為三目的規(guī)劃模型的普通方式 ..186.3.19在以上各式中： 、 分別為賦予 優(yōu)先因子的第 個目的的正、負(fù)偏向變量的權(quán)系數(shù)； 為第 個目的的預(yù)期值； 為決策變量； 、 分別為第 個目的的正、負(fù)偏向變量。6.3.15式為目的函數(shù);6.3.16式為目的約束;6.3.17式為絕對約束;6.3.18式和6.3.19式為非負(fù)約束; 、 、 分別為目的約束和絕對約束中決策變量的系數(shù)及約束值。其中： ； ； ； 。 二、求解目的規(guī)那么的單純形方法 目的規(guī)劃模型仍可以用單純形方法求解 ，在求解時作以下規(guī)定： 由于目的函數(shù)都是求最小值，所以，最優(yōu)

8、判別檢驗數(shù)為 由于非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子 所以檢驗數(shù)的正、負(fù)首先決議于 的系數(shù) 的正、負(fù)，假設(shè) ，那么檢驗數(shù)的正、負(fù)就決議于 的系數(shù) 的正、負(fù)，下面可依此類推。 據(jù)此，我們可以總結(jié)出求解目的規(guī)劃問題的單純形方法的計算步驟如下： 建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別排成L行，置 。 檢查該行中能否存在負(fù)數(shù)，且對應(yīng)的前L-1行的系數(shù)是零。假設(shè)有，取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)。假設(shè)無負(fù)數(shù)，那么轉(zhuǎn)。 按最小比值規(guī)那么 規(guī)那么確定換出變量，當(dāng)存在兩個和兩個以上一樣的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。 按單純形法進(jìn)展基變換運(yùn)算，建立新的計算表，前往

9、。 當(dāng)l=L時，計算終了，表中的解即為稱心解。否那么置l=l+1，前往 。例3：試用單純形法求解例2所描畫的目的規(guī)劃問題解：首先將這一問題化為如下規(guī)范方式 (1)取 , , , ,為初始基變量，列出初始單純形表。表6.3.1 (2)取 ，檢查檢驗數(shù)的 行，因該行無負(fù)檢驗數(shù)，故轉(zhuǎn)(5) 。 (5) 由于 ，置 ，前往(2)。 (2) 檢查發(fā)現(xiàn)檢驗數(shù) 行中有 ， ，由于有 ，所以 為換入變量，轉(zhuǎn)入(3)。 (3按 規(guī)那么計算： ，所以 為換出變量，轉(zhuǎn)入(4)。 (4)進(jìn)展換基運(yùn)算，得到表6.3.2。以此類推，直至得到最終單純形表為止，如表6.3.3所示。 表6.3.2表6.3.3 由表6.3可知，

10、 ， ，為稱心解。檢查檢驗數(shù)行，發(fā)現(xiàn)非基變量的檢驗數(shù)為0，這闡明該問題存在多重解。表6.3.4 在表6.3.3中，以非基變量 為換入變量， 為換出變量，經(jīng)迭代得到表6.3.4。 從表6.3.4可以看出， ， 也是該問題的稱心解。 土地利用問題 消費(fèi)方案問題 投資問題 第4節(jié) 多目的規(guī)劃運(yùn)用實例 第5章第1節(jié)中，我們運(yùn)用線性規(guī)劃方法討論了表5.1.4所描畫的農(nóng)場作物種植方案的問題。但是，由于線性規(guī)劃只需單一的目的函數(shù)，所以當(dāng)時我們建立的作物種植方案模型屬于單目的規(guī)劃模型，給出的種植方案方案，要么使總產(chǎn)量最大，要么使總產(chǎn)值最大；兩個目的無法兼得。那么，終究怎樣制定作物種植方案，才干兼顧總產(chǎn)量和總產(chǎn)

11、值雙重目的呢？下面我們用多目的規(guī)劃的思想方法處理這個問題。 一、土地利用問題 取 為決策變量，它表示在第 j 等級的耕地上種植第i種作物的面積。假設(shè)追求總產(chǎn)量最大和總產(chǎn)值最大雙重目的，那么，目的函數(shù)包括： 追求總產(chǎn)量最大 6.4.1 追求總產(chǎn)值最大6.4.2 根據(jù)題意，約束方程包括： 耕地面積約束 最低收獲量約束6.4.3 6.4.4 6.4.5 非負(fù)約束 對上述多目的規(guī)劃問題，我們可以采用如下方法，求其非劣解。用線性加權(quán)方法 取 ，重新構(gòu)造目的函數(shù) 這樣，就將多目的規(guī)劃轉(zhuǎn)化為單目的線性規(guī)劃。 用單純形方法對該問題求解，可以得到一個稱心解非劣解方案，結(jié)果見表6.4.1。 此方案是：III等耕地

12、全部種植水稻，I等耕地全部種植玉米，II等耕地種植大豆19.117 6 hm2、種植玉米280.882 4 hm2。在此方案下，線性加權(quán)目的函數(shù)的最大取值為6 445 600。 表6.4.1 線性加權(quán)目的下的非劣解方案單位：hm2 目的規(guī)劃方法 實踐上，除了線性加權(quán)求和法以外，我們還可以用目的規(guī)劃方法求解上述多目的規(guī)劃問題。 假設(shè)我們對總產(chǎn)量 和總產(chǎn)值 ，分別提出一個期望目的值kg元 并將兩個目的視為一樣的優(yōu)先級。 假設(shè) 、 分別表示對應(yīng)第1個目的期望值的正、負(fù)偏向變量， 、 分別表示對應(yīng)于第2個目的期望值的正、負(fù)偏向變量，而且將每一個目的的正、負(fù)偏向變量同等對待即可將它們的權(quán)系數(shù)都賦為1，那

13、么，該目的規(guī)劃問題的目的函數(shù)為 對應(yīng)的兩個目的約束為 6.4.8 6.4.9即 除了目的約束以外，該模型的約束條件，還包括硬約束和非負(fù)約束的限制。其中，硬約束包括耕地面積約束6.4.3式和最低收獲量約束6.4.4式；非負(fù)約束，不但包括決策變量的非負(fù)約束6.4.5式，還包括正、負(fù)偏向變量的非負(fù)約束 解上述目的規(guī)劃問題，可以得到一個非劣解方案，詳見表6.4.2。 表6.4.2 目的規(guī)劃的非劣解方案單位:hm2 在此非劣解方案下，兩個目的的正、負(fù)差變量分為 ， ， ， 。 二、消費(fèi)方案問題 某企業(yè)擬消費(fèi)A和B兩種產(chǎn)品，其消費(fèi)投資費(fèi)用分別為2 100元/t和4 800元/t。A、B兩種產(chǎn)品的利潤分別為

14、3 600元/t和6 500元/t。A、B產(chǎn)品每月的最大消費(fèi)才干分別為5 t和8 t；市場對這兩種產(chǎn)品總量的需求每月不少于9 t。試問該企業(yè)應(yīng)該如何安排消費(fèi)方案，才干既能滿足市場需求，又節(jié)約投資，而且使消費(fèi)利潤到達(dá)最大? 該問題是一個線性多目的規(guī)劃問題。假設(shè)方案決策變量用 和 表示，它們分別代表A、B產(chǎn)品每月的消費(fèi)量單位：t； 表示消費(fèi)A、B兩種產(chǎn)品的總投資費(fèi)用單位：元； 表示消費(fèi)A、B兩種產(chǎn)品獲得的總利潤單位：元。那么，該多目的規(guī)劃問題就是：求 和 ，使 而且滿足 對于上述多目的規(guī)劃問題，假設(shè)斷策者提出的期望目的是：1每個月的總投資不超30 000元；2每個月的總利潤到達(dá)或超越45 000元；3兩個目的同等重要。那么，借助Matlab軟件系統(tǒng)中的優(yōu)化計算工具進(jìn)展求解，可以得到一個非劣解方案為 按照此方案進(jìn)展消費(fèi)，該企業(yè)每個月可以獲得利潤44 000元，同時需求投資29 700元。 某企業(yè)擬用1 000萬元投資于A、B兩個工程的技術(shù)改造。設(shè) 、 分別表示分配給A、B工程的投資萬元。據(jù)估計，投資工程A、B的年收益分別為投資的60%和70%；但投資風(fēng)險損失，與總投資和單項投資均有關(guān)系 據(jù)市場調(diào)查顯示， A工程的投資前景好于B工程，因此希望A工程的投資額不小B工程。試問應(yīng)該如何在A、B兩個工程之間分配投資，才干既使年利潤最大，又使風(fēng)險損