運(yùn)籌學(xué)——目標(biāo)規(guī)劃OR21第一頁(yè)，共三十頁(yè)，2022年，8月28日OR22第五章目標(biāo)規(guī)劃要求1、理解概念2、掌握建模3、掌握?qǐng)D解法和單純形解法4、理解目標(biāo)規(guī)劃的靈敏度分析第二頁(yè)，共三十頁(yè)，2022年，8月28日OR235.1目標(biāo)規(guī)劃的概念及數(shù)學(xué)模型1多目標(biāo)問(wèn)題多目標(biāo)線性規(guī)劃例1產(chǎn)品資源AB限量原材料（kg)設(shè)備（臺(tái)時(shí)）

2112

1110單位利潤(rùn)

810求利潤(rùn)最大的生產(chǎn)方案。第三頁(yè)，共三十頁(yè)，2022年，8月28日OR24例2：例1的要求多元化：決策者在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上：

1、首先是產(chǎn)品A的產(chǎn)量不大于產(chǎn)品B的產(chǎn)量。

2、其次是充分利用設(shè)備的有效臺(tái)時(shí)，不加班。

3、再次是使利潤(rùn)額盡可能達(dá)到并超過(guò)計(jì)劃利潤(rùn)指標(biāo)56元。此問(wèn)題即為多目標(biāo)決策問(wèn)題，目標(biāo)規(guī)劃就是解這類問(wèn)題的方法。

AB限量原材料（kg)設(shè)備（臺(tái)時(shí)）

2112

1110單位利潤(rùn)

810minZ=P1d1++P2(d2-+d2+)+P3d3-第四頁(yè)，共三十頁(yè)，2022年，8月28日OR25例2的解法解：?jiǎn)栴}分析：找差別、定概念（與單目標(biāo)規(guī)劃相比）

1）絕對(duì)約束：必須嚴(yán)格滿足的等式約束和不等式約束，稱之為絕對(duì)約束。

2x1+1.5x2≤50(1)

x1+2x2

＝40(2)2）目標(biāo)約束：那些不必嚴(yán)格滿足的等式約束和不等式約束，稱之為目標(biāo)約束（軟約束）。目標(biāo)約束是目標(biāo)規(guī)劃特有的，這些約束不一定要求嚴(yán)格完全滿足，允許發(fā)生正或負(fù)偏差，因此在這些約束中可以加入正負(fù)偏差變量。第五頁(yè)，共三十頁(yè)，2022年，8月28日OR263）偏差變量：目標(biāo)約束不是剛性的，而是彈性的，允許在一定范圍內(nèi)有偏差，這更接近于實(shí)際。為表達(dá)這種靈活性，便引入了偏差變量的概念，偏差變量有正負(fù)之分，正偏差變量表示為：d+，d+表示超過(guò)目標(biāo)值的部分；負(fù)偏差變量表示為：d-，

d-表示不足目標(biāo)值的部分.顯然有d-·

d+=0（？）第六頁(yè)，共三十頁(yè)，2022年，8月28日OR274）目標(biāo)（期望）值：是指預(yù)先給定的某個(gè)目標(biāo)的期望值。5）實(shí)際值：是指當(dāng)決策變量選定以后，目標(biāo)函數(shù)的對(duì)應(yīng)值。顯然：d+＝實(shí)際值－目標(biāo)值≥0d-＝目標(biāo)值－實(shí)際值≥0盡可能達(dá)到并超過(guò)計(jì)劃利潤(rùn)指標(biāo)56元，此處的56元即為目標(biāo)值第七頁(yè)，共三十頁(yè)，2022年，8月28日OR286）目標(biāo)函數(shù)的優(yōu)先級(jí)與權(quán)系數(shù):目標(biāo)的重要程度不同，因此目標(biāo)的滿足有先有后，即有優(yōu)先級(jí)別。設(shè)最重要的為P1級(jí)，次之者為P2級(jí)……P看成實(shí)數(shù)，且有P1>>P2注：目標(biāo)的優(yōu)先級(jí)是一個(gè)定性概念，不同的優(yōu)先級(jí)之間無(wú)法用數(shù)量衡量，僅僅表示優(yōu)化過(guò)程中的目標(biāo)考慮的先后次序。對(duì)于同一優(yōu)先級(jí)的不同目標(biāo)，按其重要程度可分別賦予不同的權(quán)系數(shù)。權(quán)系數(shù)是一種可以用數(shù)量表示的指數(shù)，因此，對(duì)于一個(gè)具體的目標(biāo)規(guī)劃問(wèn)題，它是一個(gè)數(shù)字。第八頁(yè)，共三十頁(yè)，2022年，8月28日OR297）目標(biāo)規(guī)劃的目標(biāo)函數(shù)：目標(biāo)規(guī)劃的目標(biāo)函數(shù)是按各約束的正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)造的。目標(biāo)函數(shù)的基本形式有三種：1、要求恰好達(dá)到目標(biāo)值，即正負(fù)偏差變量都要盡可能地小，這時(shí)，minZ＝f(d+＋d-).2、要求不超過(guò)目標(biāo)值，即允許達(dá)不到目標(biāo)值但正偏差變量要盡可能地小，這時(shí)，minZ＝f(d+).3、要求超過(guò)目標(biāo)值，即超過(guò)量不限但負(fù)偏差變量要盡可能的小，這時(shí)，minZ＝f(d-)

顯然，本題目標(biāo)函數(shù)表示為：minZ=P1d1+

+P2(d2-+

d2+)

+P3d3-

第九頁(yè)，共三十頁(yè)，2022年，8月28日OR210綜上所述，本題的數(shù)學(xué)模型為：

minZ=P1d1+

+P2(d2-+

d2+)

+P3d3-

2x1+x2≤11

x1-x2+d1-

-d1+=0

x1+2x2+d2--d2+

=108x1+10x2+d3--d3+=56x1，x2，di-，di+≥0,i=1,2,3第十頁(yè)，共三十頁(yè)，2022年，8月28日OR211幾點(diǎn)說(shuō)明：1）有時(shí)絕對(duì)約束轉(zhuǎn)化為目標(biāo)約束，則不再表示為絕對(duì)約束。2）有時(shí)同級(jí)別的目標(biāo)中，其重要程度又有差別，則設(shè)置不同的權(quán)重。第十一頁(yè)，共三十頁(yè)，2022年，8月28日OR212目標(biāo)規(guī)劃問(wèn)題的特點(diǎn)：1）問(wèn)題的目標(biāo)函數(shù)是關(guān)于優(yōu)先等級(jí)、權(quán)系數(shù)和偏差變量的極小化函數(shù)；2）約束條件由絕對(duì)約束或目標(biāo)約束構(gòu)成；3）所有決策變量和偏差變量都受到非負(fù)約束。第十二頁(yè)，共三十頁(yè)，2022年，8月28日OR213例3：請(qǐng)建立以下問(wèn)題的數(shù)學(xué)模型某建筑施工單位計(jì)劃生產(chǎn)A,B兩種預(yù)制構(gòu)件。決策者首先考慮要充分利用供電部門分配的電量限額指標(biāo)62.5kw/日，其次考慮完成與超額完成利潤(rùn)指標(biāo)10百元/日。每日可供給予制水泥8噸。其它有關(guān)數(shù)據(jù)如下表，問(wèn)應(yīng)如何確定A,B的產(chǎn)量。產(chǎn)品耗電量(kw/產(chǎn)品）水泥消耗（噸/產(chǎn)品）利潤(rùn)（百元/產(chǎn)品）A1021B1212第十三頁(yè)，共三十頁(yè)，2022年，8月28日OR214課堂練習(xí)：某工廠生產(chǎn)A、B兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)如下：要求：首先、B產(chǎn)品不超過(guò)10單位；其次，利潤(rùn)不低于1600元，再次，充分利用2車間的生產(chǎn)能力，盡量不加班。請(qǐng)建立該問(wèn)題的模型。

產(chǎn)品資源

AB限量1車間2車間21.5125040單位利潤(rùn)80100第十四頁(yè)，共三十頁(yè)，2022年，8月28日OR215圖解法的基本步驟：（1）先作硬約束與決策變量的非負(fù)約束，同一般線性規(guī)劃作圖法。（2）作目標(biāo)約束，此時(shí)，先讓di-

-di+＝0，然后標(biāo)出di-

及di+的增加方向（實(shí)際上是目標(biāo)值減少與增加的方向）。（3）按優(yōu)先級(jí)的次序，逐級(jí)讓目標(biāo)規(guī)劃的目標(biāo)函數(shù)中極小化偏差變量取0，從而逐步縮小可行域，最后找出問(wèn)題的解。5.2目標(biāo)規(guī)劃的圖解法第十五頁(yè)，共三十頁(yè)，2022年，8月28日OR2165.2目標(biāo)規(guī)劃的圖解法圖解例2:minZ=P1d1+

+P2(d2-+

d2+)

+P3d3-

2x1+x2≤11

x1-x2+d1-

-d1+=0

x1+2x2+d2--d2+

=108x1+10x2+d3--d3+=56x1，x2，di-，di+≥0,i=1,2,3第十六頁(yè)，共三十頁(yè)，2022年，8月28日OR217例4：第十七頁(yè)，共三十頁(yè)，2022年，8月28日OR218考慮目標(biāo)規(guī)劃數(shù)學(xué)模型的一些特點(diǎn)，作以下規(guī)定：1）因目標(biāo)函數(shù)為求最小化，所以要求2）因非基變量檢驗(yàn)數(shù)中含有不同等級(jí)的優(yōu)先因子，即，因p1?p2?…?pk；從每個(gè)檢驗(yàn)數(shù)的整體看：檢驗(yàn)數(shù)的正、負(fù)首先決定于p1的系數(shù)a1j的正負(fù)，若a1j＝0，

則此檢驗(yàn)數(shù)的正、負(fù)就決定于p2的系數(shù)a2j的正負(fù)，依次類推。5.3目標(biāo)規(guī)劃的單純形解法第十八頁(yè)，共三十頁(yè)，2022年，8月28日OR2193)目標(biāo)規(guī)劃使用單純形法求解，di-，di+

視為普通變量。P1>>P2>>…>>PL第十九頁(yè)，共三十頁(yè)，2022年，8月28日OR220求解目標(biāo)規(guī)劃單純形法的步驟：P1051、建立初始單純形表，在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個(gè)數(shù)分別列成K行，置k=1。2、檢查該行中是否存在負(fù)數(shù)，且對(duì)應(yīng)的前k－1行的系數(shù)是零。若有負(fù)數(shù)，取其中最小者對(duì)應(yīng)的變量為換入變量，轉(zhuǎn)（3），若無(wú)負(fù)數(shù)，則轉(zhuǎn)（5）。3、按最小比值規(guī)則確定換出變量，當(dāng)存在兩個(gè)和兩個(gè)以上相同的最小比值時(shí)，選取具有較高優(yōu)先級(jí)別的變量為換出變量。4、按單純形法進(jìn)行基變換運(yùn)算，建立新的計(jì)算表，返回（2）。5、當(dāng)k=K時(shí)，計(jì)算結(jié)束。表中的解即為滿意解。否則置k=k＋1，返回到（2）。第二十頁(yè)，共三十頁(yè)，2022年，8月28日OR221例題5:用單純形法求解下列目標(biāo)規(guī)劃問(wèn)題

minZ=P1d1+

+P2(d2-+

d2+)

+P3d3-

2x1+x2≤11

x1-x2+d1-

-d1+=0

x1+2x2+d2--d2+

=108x1+10x2+d3--d3+=56x1，x2，di-，di+≥0,i=1,2,3第二十一頁(yè)，共三十頁(yè)，2022年，8月28日OR2225.5目標(biāo)規(guī)劃的靈敏度分析例5：已知目標(biāo)規(guī)劃問(wèn)題：目標(biāo)函數(shù)的等級(jí)變化為：試分析原解有什么變化？第二十二頁(yè)，共三十頁(yè)，2022年，8月28日OR223CBXBbx1x22p13p1p2p3x2X1641820100100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2p3解:原問(wèn)題的最優(yōu)單純形表為：第二十三頁(yè)，共三十頁(yè)，2022年，8月28日OR224問(wèn)題1的變化情況為：第二十四頁(yè)，共三十頁(yè)，2022年，8月28日OR225CBXBbx1x22p13p1p2p3x2X1641820101100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2p3p2p3000此時(shí)，檢驗(yàn)數(shù)大于等于零，可見(jiàn)，原解仍是滿意解。p300320－300230－2001010第二十五頁(yè)，共三十頁(yè)，2022年，8月28日OR226CBXBbx1x22p13p1p2p3x2X1641820101100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2p3p12p23p2p1-320300200-230100p1級(jí)的檢驗(yàn)數(shù)不是大于等于零，則p1級(jí)目標(biāo)未實(shí)現(xiàn)，繼續(xù)迭代。過(guò)程見(jiàn)書(shū)第108頁(yè)。第二十六頁(yè)，共三十頁(yè)，2022年，8月28日OR227某單位考慮職工的升級(jí)調(diào)資方案時(shí)，依次遵守得規(guī)定：1、不超過(guò)年工資總額60000元；2、每級(jí)的人數(shù)不超過(guò)定編規(guī)定的人數(shù)；3、二、三級(jí)的升級(jí)面盡可能達(dá)到現(xiàn)有人數(shù)的20％，且無(wú)越級(jí)提升；4、三級(jí)不足編制的人數(shù)可錄用新職工，又一級(jí)的職工中有10％要退休。有關(guān)資料如下，問(wèn)應(yīng)如何擬定一個(gè)滿意的方案。等級(jí)工資額（元/年）現(xiàn)有人數(shù)編制人數(shù)123200015001000101215121515合計(jì)3742第二十七頁(yè)，共三十頁(yè)，2022年，8月28日OR228已知有三個(gè)產(chǎn)地給四個(gè)銷地供應(yīng)某種產(chǎn)品，產(chǎn)銷地之間地供需量和單位運(yùn)費(fèi)見(jiàn)下表，有關(guān)部門在研究調(diào)運(yùn)方案時(shí)依次考慮以下七項(xiàng)目標(biāo)，并規(guī)定其相應(yīng)地優(yōu)先