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

2023/2/41運(yùn)籌學(xué)

OPERATIONSRESEARCH

2023/2/42第五章目標(biāo)規(guī)劃

目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形解法目標(biāo)規(guī)劃的層次算法目標(biāo)規(guī)劃的應(yīng)用2023/2/43§1目標(biāo)規(guī)劃的提出與數(shù)學(xué)模型

§1.1引例例1生產(chǎn)計(jì)劃問(wèn)題

Ⅰ

Ⅱ能力設(shè)備A2212設(shè)備B4

016設(shè)備C0515利潤(rùn)23Ⅰ，Ⅱ各生產(chǎn)多少,可獲最大利潤(rùn)?2023/2/44解:設(shè)產(chǎn)品Ⅰ,Ⅱ產(chǎn)量分別為變量最優(yōu)解：這里的目標(biāo)只有一個(gè)！2023/2/45有時(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ī)劃的方法解決。2023/2/46目標(biāo)規(guī)劃是在線(xiàn)性規(guī)劃的基礎(chǔ)上，為適應(yīng)企業(yè)經(jīng)營(yíng)管理中多目標(biāo)決策的需要而逐步發(fā)展起來(lái)的。目標(biāo)規(guī)劃是一種數(shù)學(xué)方法。基本含義：在一定約束條件下，要求多個(gè)目標(biāo)達(dá)到或盡可能接近于給定的對(duì)應(yīng)目標(biāo)值。特點(diǎn)：既保持了線(xiàn)性規(guī)劃易于計(jì)算的特點(diǎn)，又克服了線(xiàn)性規(guī)劃只能解決單一目標(biāo)優(yōu)化問(wèn)題的局限性。2023/2/47目標(biāo)規(guī)劃產(chǎn)生與發(fā)展目標(biāo)規(guī)劃的有關(guān)概念和數(shù)學(xué)模型是在1961年由美國(guó)學(xué)者查恩斯(A.Charnes)和庫(kù)伯(W.W.Cooper)首次在《管理模型及線(xiàn)性規(guī)劃的工業(yè)應(yīng)用》一書(shū)中提出。當(dāng)時(shí)是作為解一個(gè)沒(méi)有可行解的線(xiàn)性規(guī)劃而引入的一種方法。這種方法把規(guī)劃問(wèn)題表達(dá)為盡可能地接近預(yù)期的目標(biāo)。1965年，尤吉·艾吉里(Yuji·Ijiri)在處理多目標(biāo)問(wèn)題，分析各類(lèi)目標(biāo)的重要性時(shí)，引入了賦予各目標(biāo)一個(gè)優(yōu)先因子及加權(quán)系數(shù)的概念；并進(jìn)一步完善了目標(biāo)規(guī)劃的數(shù)學(xué)模型。表達(dá)和求解目標(biāo)規(guī)劃問(wèn)題的方法是由杰斯基萊恩(Jashekilaineu)和桑李(SangLi)給出并加以改進(jìn)的。2023/2/48§1.2

目標(biāo)規(guī)劃的有關(guān)概念1、正、負(fù)偏差變量：

等是決策變量；

是正偏差變量，表決策值超過(guò)目標(biāo)值的部分；是負(fù)偏差變量，表決策值未達(dá)目標(biāo)值的部分。

且有。2、絕對(duì)約束和目標(biāo)約束

：

絕對(duì)約束：必須滿(mǎn)足的等式約束或不等式約束。

如：A設(shè)備嚴(yán)格禁止超時(shí)使用，則

2023/2/49目標(biāo)約束：對(duì)于不嚴(yán)格限定的約束，在達(dá)到此目標(biāo)時(shí)允許發(fā)生正或負(fù)的偏差，可在這些約束中加入正負(fù)偏差變量，成為目標(biāo)約束。如：（1）“Ⅰ、Ⅱ兩種產(chǎn)品的產(chǎn)量保持1：2”可表示為●當(dāng)允許此比例時(shí)，即，則引入負(fù)偏差，則該條件可表示為：●類(lèi)似地有，表示允許此比例。●表示“力求Ⅰ、Ⅱ兩種產(chǎn)品的產(chǎn)量比例不”2023/2/410（2）目標(biāo)函數(shù)也可轉(zhuǎn)化為目標(biāo)約束：如：“力求利潤(rùn)指標(biāo)不低于15元”可表示為（3）“設(shè)備C可適當(dāng)加班，但要控制”可表示為（4）“設(shè)備B既要充分利用，又要盡量不加班”可表示為2023/2/4113、目標(biāo)的優(yōu)先級(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)函數(shù)：目標(biāo)函數(shù)是要盡量縮小偏離目標(biāo)值2023/2/412于是按照上例中的有關(guān)要求，該目標(biāo)規(guī)劃的目標(biāo)函數(shù)約束條件：2023/2/413目標(biāo)規(guī)劃特點(diǎn)：可以同時(shí)考慮多個(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)。2023/2/414一般的目標(biāo)規(guī)劃數(shù)學(xué)模型剛性約束柔性約束2023/2/415§2目標(biāo)規(guī)劃的圖解分析法求解目標(biāo)規(guī)劃的思路：剛性約束必須嚴(yán)格滿(mǎn)足；按優(yōu)先級(jí)次序，從高層到低層逐層優(yōu)化；在不增加高層偏差值的情況下，使本層的偏差達(dá)到最小。只有兩個(gè)決策變量的目標(biāo)規(guī)劃可用圖解法分析。以上例為例，圖解分析如下。2023/2/416滿(mǎn)意解F2023/2/417§3目標(biāo)規(guī)劃的單純形解法單純形法求解目標(biāo)規(guī)劃的思路：1.求解步驟與一般線(xiàn)性規(guī)劃問(wèn)題的單純形法基本相同；2.根據(jù)目標(biāo)函數(shù)中的優(yōu)先級(jí)次序，從高層到低層逐層優(yōu)化；3.單純形表中，檢驗(yàn)數(shù)按優(yōu)先級(jí)次序分行表示。例：2023/2/41800P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+P1d1-10[1]01-10d2-40211-1P2d3-100321-1P1-111P2-3-21第一步：列初始單純形表2023/2/419第二步：確定進(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)到第二步。2023/2/42000P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0x110[1]01-10d2-2001-2[2]1-1P2d3-7002-331-1P111P2-23-3100P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0x12011/2001/2-1/20d1+100[1/2]-111/2-1/2P2d3-4001/200-3/23/21-1P111P2-1/23/2-3/212023/2/42100P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0x110101-1000X22001-221-1P2d3-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)。2023/2/422說(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ù)，迭代終止。2023/2/423§4目標(biāo)規(guī)劃的層次算法（思想同前）第一步：先對(duì)目標(biāo)函數(shù)中的層次進(jìn)行優(yōu)化。建立第一層次的線(xiàn)性規(guī)劃模型，記為L(zhǎng)P1.目標(biāo)函數(shù)：由第一優(yōu)先級(jí)的偏差變量構(gòu)成約束條件：由原約束構(gòu)成。設(shè)第一級(jí)優(yōu)化的最優(yōu)目標(biāo)值是2023/2/424第二步：對(duì)目標(biāo)函數(shù)中的層次進(jìn)行優(yōu)化。建立第二層次的線(xiàn)性規(guī)劃模型，記為L(zhǎng)P2.目標(biāo)函數(shù)：由第二優(yōu)先級(jí)的偏差變量構(gòu)成約束條件：在原約束基礎(chǔ)上增加新約束：設(shè)第二級(jí)優(yōu)化的最優(yōu)目標(biāo)值是。以此類(lèi)推。2023/2/425§5目標(biāo)規(guī)劃應(yīng)用舉例例1：某電子廠生產(chǎn)錄音機(jī)和電視機(jī)兩種產(chǎn)品，分別經(jīng)由甲、乙兩個(gè)車(chē)間生產(chǎn)。已知除外構(gòu)件外，生產(chǎn)一臺(tái)錄音機(jī)需甲車(chē)間加工2h，乙車(chē)間裝配1h；生產(chǎn)一臺(tái)電視機(jī)需甲車(chē)間加工1h，乙車(chē)間裝配3h；檢驗(yàn)銷(xiāo)售環(huán)節(jié)：一臺(tái)錄音機(jī)檢驗(yàn)銷(xiāo)售費(fèi)用50元；一臺(tái)電視機(jī)檢驗(yàn)銷(xiāo)售費(fèi)用30元；2023/2/426工時(shí)及管理費(fèi)用：甲車(chē)間每月可用生產(chǎn)工時(shí)120h，車(chē)間管理費(fèi)用80元/h;乙車(chē)間每月可用生產(chǎn)工時(shí)150h，車(chē)間管理費(fèi)用20元/h;利潤(rùn)及銷(xiāo)量：每臺(tái)錄音機(jī)利潤(rùn)100元，平均每月可銷(xiāo)售50臺(tái)；每臺(tái)電視機(jī)利潤(rùn)75元，平均每月可銷(xiāo)售80臺(tái)；月度計(jì)劃的目標(biāo)如下：2023/2/4271、第一優(yōu)先級(jí)：檢驗(yàn)和銷(xiāo)售費(fèi)用每月不超過(guò)4600元；2、第二優(yōu)先級(jí)：每月銷(xiāo)售錄音機(jī)不少于50臺(tái)；3、第三優(yōu)先級(jí)：兩車(chē)間的工時(shí)得到充分利用（重要性權(quán)系數(shù)按每小時(shí)的管理費(fèi)用比）；4、第四優(yōu)先級(jí)：甲車(chē)間加班不超過(guò)20小時(shí)；5、第五優(yōu)先級(jí)：每月銷(xiāo)售電視機(jī)不少于80臺(tái)；6、第六優(yōu)先級(jí)：兩車(chē)間的加班總時(shí)間要控制（權(quán)系數(shù)分配如3）試確定該廠為達(dá)到上述目標(biāo)的最優(yōu)月度生產(chǎn)計(jì)劃。2023/2/428解：假設(shè)每月生產(chǎn)錄音機(jī)臺(tái)，電視機(jī)臺(tái)。1、兩車(chē)間可用工時(shí):2、檢驗(yàn)和銷(xiāo)售費(fèi)用:3、每月銷(xiāo)售量:4、加班限制:于是模型如下2023/2/429約束：目標(biāo)函數(shù)2023/2/430例2：書(shū)P143例5解：設(shè)是i工廠調(diào)配給j用戶(hù)的產(chǎn)品數(shù)量。約束如下1、供應(yīng)量約束:2、需求量約束:3、用戶(hù)1需要量中工廠3的產(chǎn)品數(shù)量不少于100:2023/2/4314、各用戶(hù)滿(mǎn)足率不低于80%：5、運(yùn)費(fèi)限制：6、道路通過(guò)限制：7、用戶(hù)1和3的滿(mǎn)足率保持平衡：2023/2/4328、力求總運(yùn)費(fèi)減小：目標(biāo)函數(shù)：2023/2/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è)滿(mǎn)意的方案。2023/2/434等級(jí)工資額（元/年）現(xiàn)有人數(shù)編制人數(shù)Ⅰ400001012Ⅱ300001215Ⅲ200001515合計(jì)3742解：設(shè)分別表示提升到Ⅰ、Ⅱ級(jí)和錄用到Ⅲ級(jí)的職工人數(shù)。則模型如下：目標(biāo)函數(shù)各目標(biāo)約束：2023/2/435（1）年工資總額不超過(guò)120萬(wàn)元；（2）每級(jí)的人數(shù)不超過(guò)編制規(guī)定的人數(shù)；（3）Ⅱ、Ⅲ級(jí)的升級(jí)面盡可能達(dá)到現(xiàn)有人數(shù)的20%；例4：某農(nóng)場(chǎng)有3萬(wàn)畝農(nóng)田，欲種植玉米、大豆和小麥。各種作物每畝需施化肥分別為0.12,0.20,0.15噸。預(yù)