第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è)干目的以及實(shí)現(xiàn)這些目的的優(yōu)先順序，在有限的資源條件下，使總的偏離目的值的偏向最小。一根本思想例1：某一個(gè)企業(yè)利用某種原資料和現(xiàn)有設(shè)備可消費(fèi)甲、乙兩種產(chǎn)品，其中，甲、乙兩種產(chǎn)品的單價(jià)分別為8元和10元；消費(fèi)

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

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

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

5、級(jí)目的；而 級(jí)目的是在實(shí)現(xiàn) 級(jí)目的的根底上思索的；依此類推。， 假設(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)每一目確實(shí)定后，盡能夠減少與目的值的偏離。因此，目的規(guī)劃的目的函數(shù)只能是根本方式有3種： (6.3.5 要求恰好到達(dá)目的值，就是正、負(fù)偏向變量都要盡能夠小,即 6.3.6 要求不超越目的值，即允許達(dá)不到目的值，就是正偏向變量要盡能夠小，即6.3.7 要求超越目的值，也就是超越量不限，但負(fù)偏向變量要盡能夠小，

6、即 6.3.8 在實(shí)踐問題中，可以根據(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è)備的有限臺(tái)時(shí)，不加班；再次是產(chǎn)值不小于56萬元。并分別賦予這3個(gè)目的優(yōu)先因子 。試建立該問題的目的規(guī)劃模型。解：根據(jù)題意，這一決策問題的目的規(guī)劃模型是...14 假定有L個(gè)目的，K個(gè)優(yōu)先級(jí)(KL)，n個(gè)變量。在同一優(yōu)先級(jí) 中不同目的的正、負(fù)偏向變量的權(quán)系數(shù)分別為 、 ，那

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

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

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

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

11、值雙重目的呢？下面我們用多目的規(guī)劃的思想方法處理這個(gè)問題。 一、土地利用問題 取 為決策變量，它表示在第 j 等級(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ù)約束 對(duì)上述多目的規(guī)劃問題，我們可以采用如下方法，求其非劣解。用線性加權(quán)方法 取 ，重新構(gòu)造目的函數(shù) 這樣，就將多目的規(guī)劃轉(zhuǎn)化為單目的線性規(guī)劃。 用單純形方法對(duì)該問題求解，可以得到一個(gè)稱心解非劣解方案，結(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ī)劃方法 實(shí)踐上，除了線性加權(quán)求和法以外，我們還可以用目的規(guī)劃方法求解上述多目的規(guī)劃問題。 假設(shè)我們對(duì)總產(chǎn)量 和總產(chǎn)值 ，分別提出一個(gè)期望目的值kg元 并將兩個(gè)目的視為一樣的優(yōu)先級(jí)。 假設(shè) 、 分別表示對(duì)應(yīng)第1個(gè)目的期望值的正、負(fù)偏向變量， 、 分別表示對(duì)應(yīng)于第2個(gè)目的期望值的正、負(fù)偏向變量，而且將每一個(gè)目的的正、負(fù)偏向變量同等對(duì)待即可將它們的權(quán)系數(shù)都賦為1，那

13、么，該目的規(guī)劃問題的目的函數(shù)為 對(duì)應(yīng)的兩個(gè)目的約束為 6.4.8 6.4.9即 除了目的約束以外，該模型的約束條件，還包括硬約束和非負(fù)約束的限制。其中，硬約束包括耕地面積約束6.4.3式和最低收獲量約束6.4.4式；非負(fù)約束，不但包括決策變量的非負(fù)約束6.4.5式，還包括正、負(fù)偏向變量的非負(fù)約束 解上述目的規(guī)劃問題，可以得到一個(gè)非劣解方案，詳見表6.4.2。 表6.4.2 目的規(guī)劃的非劣解方案單位:hm2 在此非劣解方案下，兩個(gè)目的的正、負(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；市場對(duì)這兩種產(chǎn)品總量的需求每月不少于9 t。試問該企業(yè)應(yīng)該如何安排消費(fèi)方案，才干既能滿足市場需求，又節(jié)約投資，而且使消費(fèi)利潤到達(dá)最大? 該問題是一個(gè)線性多目的規(guī)劃問題。假設(shè)方案決策變量用 和 表示，它們分別代表A、B產(chǎn)品每月的消費(fèi)量單位：t； 表示消費(fèi)A、B兩種產(chǎn)品的總投資費(fèi)用單位：元； 表示消費(fèi)A、B兩種產(chǎn)品獲得的總利潤單位：元。那么，該多目的規(guī)劃問題就是：求 和 ，使 而且滿足 對(duì)于上述多目的規(guī)劃問題，假設(shè)斷策者提出的期望目的是：1每個(gè)月的總投資不超30 000元；2每個(gè)月的總利潤到達(dá)或超越45 000元；3兩個(gè)目的同等重要。那么，借助Matlab軟件系統(tǒng)中的優(yōu)化計(jì)算工具進(jìn)展求解，可以得到一個(gè)非劣解方案為 按照此方案進(jìn)展消費(fèi)，該企業(yè)每個(gè)月可以獲得利潤44 000元，同時(shí)需求投資29 700元。 某企業(yè)擬用1 000萬元投資于A、B兩個(gè)工程的技術(shù)改造。設(shè) 、 分別表示分配給A、B工程的投資萬元。據(jù)估計(jì)，投資工程A、B的年收益分別為投資的60%和70%；但投資風(fēng)險(xiǎn)損失，與總投資和單項(xiàng)投資均有關(guān)系 據(jù)市場調(diào)查顯示， A工程的投資前景好于B工程，因此希望A工程的投資額不小B工程。試問應(yīng)該如何在A、B兩個(gè)工程之間分配投資，才干既使年利潤最大，又使風(fēng)險(xiǎn)損