運(yùn)籌08(第五章目標(biāo)規(guī)劃)課件

1、運(yùn)籌08(第五章目標(biāo)規(guī)劃)運(yùn)籌08(第五章目標(biāo)規(guī)劃)第五章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃的數(shù)學(xué)模型 目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形解法目標(biāo)規(guī)劃的層次算法目標(biāo)規(guī)劃的應(yīng)用2022/9/102第五章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃的數(shù)學(xué)模型 2022/9/441 目標(biāo)規(guī)劃的提出與數(shù)學(xué)模型 一、 引例例1、生產(chǎn)計(jì)劃問(wèn)題 能力 設(shè)備A 2 2 12 設(shè)備B 4 0 16 設(shè)備C 0 5 15 利潤(rùn) 2 3，各生產(chǎn)多少, 可獲最大利潤(rùn)?2022/9/1031 目標(biāo)規(guī)劃的提出與數(shù)學(xué)模型 一、 引例例1、生產(chǎn)計(jì)劃問(wèn) 2x1+2x2 12 4x1 16 5x2 15 x1，x2 0max Z= 2x1 +3x2解:設(shè)產(chǎn)品, 產(chǎn)量分別為

2、變量x1 ， x2最優(yōu)解：2022/9/104 2x1+2x2 有時(shí)目標(biāo)不只一個(gè)，例如考慮下列要求：1、力求利潤(rùn)指標(biāo)不低于15元；2、兩種產(chǎn)品的產(chǎn)量保持1：2；3、A為貴重設(shè)備，嚴(yán)格禁止超時(shí)使用；4、設(shè)備C可適當(dāng)加班，但要控制；5、設(shè)備B既要充分利用，又要盡量不加班，在重要性上，設(shè)備B是設(shè)備C的3倍。 要解決這樣的問(wèn)題，將上述的要求都加以考慮，就要用目標(biāo)規(guī)劃的方法解決。2022/9/105有時(shí)目標(biāo)不只一個(gè)，例如考慮下列要求：2022/9/47目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)企業(yè)經(jīng)營(yíng)管理中多目標(biāo)決策的需要而逐步發(fā)展起來(lái)的。目標(biāo)規(guī)劃是一種數(shù)學(xué)方法?；竞x：在一定約束條件下，要求多個(gè)目標(biāo)達(dá)到或

3、盡可能接近于給定的對(duì)應(yīng)目標(biāo)值。特點(diǎn)：既保持了線性規(guī)劃易于計(jì)算的特點(diǎn)，又克服了線性規(guī)劃只能解決單一目標(biāo)優(yōu)化問(wèn)題的局限性。2022/9/106目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)企業(yè)經(jīng)營(yíng)管理中多目標(biāo)決策目標(biāo)規(guī)劃產(chǎn)生與發(fā)展目標(biāo)規(guī)劃的有關(guān)概念和數(shù)學(xué)模型是在1961年由美國(guó)學(xué)者查恩斯(A.Charnes)和庫(kù)伯(W.W.Cooper)首次在管理模型及線性規(guī)劃的工業(yè)應(yīng)用一書中提出。當(dāng)時(shí)是作為解一個(gè)沒(méi)有可行解的線性規(guī)劃而引入的一種方法。這種方法把規(guī)劃問(wèn)題表達(dá)為盡可能地接近預(yù)期的目標(biāo)。1965年，尤吉艾吉里(Yuji Ijiri)在處理多目標(biāo)問(wèn)題，分析各類目標(biāo)的重要性時(shí)，引入了賦予各目標(biāo)一個(gè)優(yōu)先因子及加權(quán)系數(shù)

4、的概念；并進(jìn)一步完善了目標(biāo)規(guī)劃的數(shù)學(xué)模型。表達(dá)和求解目標(biāo)規(guī)劃問(wèn)題的方法是由杰斯基萊恩(Jashekilaineu)和桑李(SangLi)給出并加以改進(jìn)的。2022/9/107目標(biāo)規(guī)劃產(chǎn)生與發(fā)展目標(biāo)規(guī)劃的有關(guān)概念和數(shù)學(xué)模型是在1961年二、 目標(biāo)規(guī)劃的有關(guān)概念1、正、負(fù)偏差變量 ： 等是決策變量； 是正偏差變量，表決策值超過(guò)目標(biāo)值的部分； 是負(fù)偏差變量，表決策值未達(dá)目標(biāo)值的部分。 且有 。2、絕對(duì)約束和目標(biāo)約束 ： 絕對(duì)約束：必須滿足的等式約束或不等式約束。 如A設(shè)備嚴(yán)格禁止超時(shí)使用，則 2022/9/108二、 目標(biāo)規(guī)劃的有關(guān)概念1、正、負(fù)偏差變量 ： 目標(biāo)約束：對(duì)于不嚴(yán)格限定的約束，在達(dá)到此

5、目標(biāo)時(shí)允許發(fā)生正或負(fù)的偏差，可在這些約束中加入正負(fù)偏差變量，成為目標(biāo)約束。如：（1） “、兩種產(chǎn)品的產(chǎn)量保持1：2”可表示為當(dāng)允許此比例 時(shí)，即 ，則引入負(fù)偏差 則該條件可表示為：類似地有 ，表示允許此比例 。 表示“力求、兩種產(chǎn)品 的產(chǎn)量比例不 ”2022/9/109目標(biāo)約束：對(duì)于不嚴(yán)格限定的約束，在達(dá)到此目標(biāo)時(shí)允2022/9（2）目標(biāo)函數(shù)也可轉(zhuǎn)化為目標(biāo)約束：如： “力求利潤(rùn)指標(biāo)不低于15元”可表示為（3） “設(shè)備C可適當(dāng)加班，但要控制”可表示為（4） “設(shè)備B既要充分利用，又要盡量不加班”可表示為2022/9/1010（2）目標(biāo)函數(shù)也可轉(zhuǎn)化為目標(biāo)約束：（3） “設(shè)備C可適當(dāng)加班3、目標(biāo)的優(yōu)

6、先級(jí)和權(quán)系數(shù) 不同的目標(biāo)重要程度不同，優(yōu)先級(jí)不同； 同一層次優(yōu)先級(jí)的不同目標(biāo)，重要程度不同，權(quán)重不同優(yōu)先級(jí)因子： ，且權(quán)重系數(shù)： ，數(shù)值的大小決定目標(biāo)的重要程度。假設(shè) 第一優(yōu)先級(jí)：利潤(rùn)不低于15元； 第二優(yōu)先級(jí)：、產(chǎn)品的數(shù)量盡量保持1：2； 第三優(yōu)先級(jí)：C、B的工作時(shí)間控制，且B的重要性是C的3倍。4、目標(biāo)規(guī)劃的目標(biāo)函數(shù) 目標(biāo)函數(shù)是要盡量縮小偏離目標(biāo)值2022/9/10113、目標(biāo)的優(yōu)先級(jí)和權(quán)系數(shù)假設(shè) 第一優(yōu)先級(jí)：利潤(rùn)不低于15于是按照上例中的有關(guān)要求，該目標(biāo)規(guī)劃的目標(biāo)函數(shù)構(gòu)成：約束條件：2022/9/1012于是按照上例中的有關(guān)要求，該目標(biāo)規(guī)劃的目標(biāo)函數(shù)構(gòu)成：約束條件目標(biāo)規(guī)劃特點(diǎn)：可以同時(shí)考

7、慮多個(gè)目標(biāo)；可以區(qū)分不同目標(biāo)的優(yōu)先程度及重要程度；更加切合實(shí)際，更加靈活目標(biāo)規(guī)劃中的優(yōu)先級(jí)及權(quán)重系數(shù)的確定往往需要靠人的主觀判斷，是定性的，常常是模糊的，不是一個(gè)確定的數(shù)值，但現(xiàn)在也有很多將其定量化的方法，如層次分析法等這是處理目標(biāo)規(guī)劃時(shí)的一個(gè)難點(diǎn)。2022/9/1013目標(biāo)規(guī)劃特點(diǎn)：目標(biāo)規(guī)劃中的優(yōu)先級(jí)及權(quán)重系數(shù)的確定往往需要靠人一般的目標(biāo)規(guī)劃數(shù)學(xué)模型剛性約束柔性約束2022/9/1014一般的目標(biāo)規(guī)劃數(shù)學(xué)模型剛性約束柔性約束2022/9/4165.2 目標(biāo)規(guī)劃的圖解分析法求解目標(biāo)規(guī)劃的思路： 剛性約束必須嚴(yán)格滿足； 按優(yōu)先級(jí)次序，從高層到低層逐層優(yōu)化； 在不增加高層偏差值的情況下，使本層的偏

8、差達(dá)到最小。只有兩個(gè)決策變量的目標(biāo)規(guī)劃可用圖解法分析。以上例為例，圖解分析如下。2022/9/10155.2 目標(biāo)規(guī)劃的圖解分析法求解目標(biāo)規(guī)劃的思路：2022滿意解2022/9/1016滿意解2022/9/4185.3 目標(biāo)規(guī)劃的單純形解法單純形法求解目標(biāo)規(guī)劃的思路：求解步驟與一般線性規(guī)劃問(wèn)題的單純形法基本相同； 根據(jù)目標(biāo)函數(shù)中的優(yōu)先級(jí)次序，從高層到低層逐層優(yōu)化；單純形表中，檢驗(yàn)數(shù)按優(yōu)先級(jí)次序分行表示。例：2022/9/10175.3 目標(biāo)規(guī)劃的單純形解法單純形法求解目標(biāo)規(guī)劃的思路：00P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+P1d1-10101-10d2-40

9、211-1P2d3-100321-1P1-111P2-3-21第一步：列初始單純形表2022/9/101800P100P1P20CBXBbx1X2d1-d1+d2-d第二步：確定進(jìn)基變量。按照優(yōu)先級(jí)次序，檢查P1，P2，,Pk行檢驗(yàn)數(shù)是否仍有負(fù)值（0）若有，找優(yōu)先級(jí)最高一行的負(fù)值最小檢驗(yàn)數(shù)對(duì)應(yīng)變量作為進(jìn)基變量。此例中選x1第三步：確定出基變量。按照最小比值規(guī)則確定出基變量，此例中選d1-第四步：迭代運(yùn)算，得到新的基可行解，判斷是否最優(yōu)。本例中， P2行仍有負(fù)檢驗(yàn)數(shù)，轉(zhuǎn)到第二步。2022/9/1019第二步：確定進(jìn)基變量。第三步：確定出基變量。第四步：迭代運(yùn)算00P100P1P20CBXBbx1

10、X2d1-d1+d2-d2+d3-d3+0 x110101-10d2-2001-221-1P2d3-7002-331-1P111P2-23-3100P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0 x12011/2001/2-1/20d1+1001/2-111/2-1/2P2d3-4001/200-3/23/21-1P111P2-1/23/2-3/212022/9/102000P100P1P20CBXBbx1X2d1-d1+d2-d00P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0 x110101-1 000X22001-221-1P2d3

11、-30001-1-221-1P111P2-112-21注意：此時(shí)， P2行仍有負(fù)檢驗(yàn)數(shù)，要選X2進(jìn)基，因?yàn)閐2+的檢驗(yàn)數(shù)是 。此時(shí)， 已達(dá)最優(yōu)。2022/9/102100P100P1P20CBXBbx1X2d1-d1+d2-d說(shuō)明：1、進(jìn)行優(yōu)化是按照優(yōu)先級(jí)進(jìn)行的，當(dāng)高一級(jí)的目標(biāo)行的檢驗(yàn)數(shù)全部非負(fù)時(shí)，可進(jìn)行下一級(jí)的優(yōu)化；2、判別迭代終止的準(zhǔn)則： （1）所有級(jí)別 的檢驗(yàn)數(shù)行均非負(fù)，迭代終止； （2）若 行檢驗(yàn)數(shù)均非負(fù)，而 行有負(fù)檢驗(yàn)數(shù)，但這些負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的上面行中有正檢驗(yàn)數(shù)，迭代終止。2022/9/1022說(shuō)明：2022/9/4245.4 目標(biāo)規(guī)劃的層次算法（思想同前）第一步：先對(duì)目標(biāo)函數(shù)中的 層

12、次進(jìn)行優(yōu)化。 建立第一層次的線性規(guī)劃模型，記為L(zhǎng)P1.目標(biāo)函數(shù)：由第一優(yōu)先級(jí)的偏差變量構(gòu)成約束條件：由原約束構(gòu)成。設(shè)第一級(jí)優(yōu)化的最優(yōu)目標(biāo)值是2022/9/10235.4 目標(biāo)規(guī)劃的層次算法（思想同前）第一步：先對(duì)目標(biāo)函第二步：對(duì)目標(biāo)函數(shù)中的 層次進(jìn)行優(yōu)化。 建立第二層次的線性規(guī)劃模型，記為L(zhǎng)P2.目標(biāo)函數(shù)：由第二優(yōu)先級(jí)的偏差變量構(gòu)成約束條件：在原約束基礎(chǔ)上增加新約束：設(shè)第二級(jí)優(yōu)化的最優(yōu)目標(biāo)值是 。以此類推。2022/9/1024第二步：對(duì)目標(biāo)函數(shù)中的 層次進(jìn)行優(yōu)化。2022/9/45.5 目標(biāo)規(guī)劃應(yīng)用舉例例1：某電子廠生產(chǎn)錄音機(jī)和電視機(jī)兩種產(chǎn)品，分別經(jīng)由甲、乙兩個(gè)車間生產(chǎn)。已知除外構(gòu)件外，生產(chǎn)

13、一臺(tái)錄音機(jī)需甲車間加工2h，以車間裝配1h；生產(chǎn)一臺(tái)電視機(jī)需甲車間加工1h，以車間裝配3h；檢驗(yàn)銷售環(huán)節(jié)：一臺(tái)錄音機(jī)檢驗(yàn)銷售費(fèi)用50元； 一臺(tái)電視機(jī)檢驗(yàn)銷售費(fèi)用30元；工時(shí)及管理費(fèi)用：甲車間每月可用生產(chǎn)工時(shí)120h，車間管理費(fèi)用80元/h;乙車間每月可用生產(chǎn)工時(shí)150h，車間管理費(fèi)用20元/h;利潤(rùn)及銷量：每臺(tái)錄音機(jī)利潤(rùn)100元，平均每月可銷售50臺(tái)；每臺(tái)電視機(jī)利潤(rùn)75元，平均每月可銷售80臺(tái)；2022/9/10255.5 目標(biāo)規(guī)劃應(yīng)用舉例例1：某電子廠生產(chǎn)錄音機(jī)和電視機(jī)月度計(jì)劃的目標(biāo)如下：1、第一優(yōu)先級(jí)：檢驗(yàn)和銷售費(fèi)用每月不超過(guò)4600元；2、第二優(yōu)先級(jí)：每月銷售錄音機(jī)不少于50臺(tái)；3、第三

14、優(yōu)先級(jí)：兩車間的工時(shí)得到充分利用（重要性權(quán)系數(shù)按每小時(shí)的管理費(fèi)用比）；4、第四優(yōu)先級(jí)：甲車間加班不超過(guò)20小時(shí)；5、第五優(yōu)先級(jí)：每月銷售電視機(jī)不少于80臺(tái)；6、第六優(yōu)先級(jí)：兩車間的加班總時(shí)間要控制（權(quán)系數(shù)分配如3） 試確定該廠為達(dá)到上述目標(biāo)的最優(yōu)月度生產(chǎn)計(jì)劃。2022/9/1026月度計(jì)劃的目標(biāo)如下：2022/9/428解：假設(shè)每月生產(chǎn)錄音機(jī) 臺(tái)，電視機(jī) 臺(tái)。約束：1、兩車間可用工時(shí): 2、檢驗(yàn)和銷售費(fèi)用: 3、每月銷售量: 4、加班限制:于是目標(biāo)函數(shù)： 2022/9/1027解：假設(shè)每月生產(chǎn)錄音機(jī) 臺(tái)，電視機(jī) 臺(tái)。約束：2約束：2022/9/1028約束：2022/9/430例2：書P143

15、 例5解：設(shè) 是i工廠調(diào)配給j用戶的產(chǎn)品數(shù)量。約束如下1、供應(yīng)量約束:2、需求量約束:3、用戶1需要量中工廠3的產(chǎn)品數(shù)量不少于100:2022/9/1029例2：書P143 例5解：設(shè) 是i工廠調(diào)配給j用戶的4、各用戶滿足率不低于80%：5、運(yùn)費(fèi)限制：6、道路通過(guò)限制：7、用戶1和3的滿足率保持平衡：2022/9/10304、各用戶滿足率不低于80%：5、運(yùn)費(fèi)限制：6、道路通過(guò)限制8、力求總運(yùn)費(fèi)減?。耗繕?biāo)函數(shù)：2022/9/10318、力求總運(yùn)費(fèi)減?。耗繕?biāo)函數(shù)：2022/9/433例3：某單位領(lǐng)導(dǎo)在考慮本單位職工的升級(jí)調(diào)資方案時(shí)，依次遵守以下規(guī)定：1、年工資總額不超過(guò)120萬(wàn)元；2、每級(jí)的人數(shù)不超過(guò)定編規(guī)定的人數(shù)；3、級(jí)的升級(jí)面盡可能達(dá)到現(xiàn)有人數(shù)的20%；4、級(jí)不足編制的人數(shù)可錄用新職工，又級(jí)的職工中有 10%要退休。有關(guān)資料匯總于下表，請(qǐng)為該單位領(lǐng)導(dǎo)制定一個(gè)滿意的方案。等級(jí)工資額（元/年）現(xiàn)有人數(shù)編制人數(shù)40000101230000