目標(biāo)規(guī)劃-第四章

目標(biāo)規(guī)劃-第四章第四章目標(biāo)規(guī)劃目標(biāo)規(guī)劃的數(shù)學(xué)模型解目標(biāo)規(guī)劃的圖解法解目標(biāo)規(guī)劃的單純形法靈敏度分析例1：某工廠生產(chǎn)Ⅰ，Ⅱ兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)見下表。試求獲利最大生產(chǎn)方案。ⅠⅡ擁有量原材料Kg2111設(shè)備hr1210利潤元/件810目標(biāo)規(guī)劃的數(shù)學(xué)模型問題是，在實(shí)際生產(chǎn)時(shí)的考慮如下：（1）根據(jù)市場信息，產(chǎn)品Ⅰ的銷量有下降的趨勢，故產(chǎn)品Ⅰ的產(chǎn)量不大于產(chǎn)品Ⅱ的產(chǎn)量；（2）超過計(jì)劃供應(yīng)的原材料時(shí)，需用高價(jià)采購，這就使得成本增加；（3）應(yīng)盡可能充分利用設(shè)備，但不希望加班。（4）應(yīng)盡可能達(dá)到并超過計(jì)劃利潤指標(biāo)56元。顯然，這個(gè)決策問題有多個(gè)目標(biāo)需要滿足。應(yīng)該怎樣建立目標(biāo)規(guī)劃的數(shù)學(xué)模型？它和前面所講的線性規(guī)劃的數(shù)學(xué)模型有何異同？

線性規(guī)劃的數(shù)學(xué)模型：

用一組未知變量表示要求的方案，這組未知變量稱為決策變量；存在一定的約束條件，且為線性表達(dá)式；有一個(gè)目標(biāo)要求（最大化，當(dāng)然也可以是最小化），目標(biāo)表示為未知變量的線性表達(dá)式，稱之為目標(biāo)函數(shù)；對決策變量有非負(fù)要求。目標(biāo)規(guī)劃數(shù)學(xué)模型的相關(guān)概念？用一組未知變量xi表示決策變量，此外，引進(jìn)正、負(fù)偏差變量d+

、d-；存在一定的約束條件，包含絕對約束和目標(biāo)約束；各目標(biāo)具有不同的優(yōu)先因子Pk或權(quán)系數(shù)wj；目標(biāo)函數(shù)由各目標(biāo)約束的正、負(fù)偏差變量d+

、d-和賦予其的優(yōu)先因子及權(quán)系數(shù)構(gòu)造；對決策變量和正、負(fù)偏差變量有非負(fù)要求。用一組未知變量xi表示決策變量，此外，引進(jìn)正、負(fù)偏差變量d+

、d-；正偏差量d+表示決策值超過目標(biāo)值的部分；負(fù)偏差量d-

表示決策值未達(dá)到目標(biāo)值的部分;

因?yàn)闆Q策值不可能既超過目標(biāo)值同時(shí)又未達(dá)到目標(biāo)值，則恒有d+×d-＝0。存在一定的約束條件，包含絕對約束和目標(biāo)約束；絕對約束是指必須嚴(yán)格滿足的約束條件，如線性規(guī)劃中的約束條件都是絕對約束；目標(biāo)約束是目標(biāo)規(guī)劃特有的。目標(biāo)約束的右端是所要追求的目標(biāo)值，允許該值發(fā)生正負(fù)偏差，因此在此約束的左端加入正、負(fù)偏差量d+

、d-

。各目標(biāo)具有不同的優(yōu)先因子或權(quán)系數(shù)；決策者對于不同的目標(biāo)要求，有主次輕重之分。要求第一位達(dá)到的目標(biāo)賦予優(yōu)先因子P1，次位的目標(biāo)賦予優(yōu)先因子P2，依次類推，并規(guī)定

Pk>>Pk+1

。若要區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，可分別賦予它們不同的權(quán)系數(shù)wj。注：目標(biāo)的主次輕重之分由決策者確定。目標(biāo)函數(shù)由各目標(biāo)約束的正負(fù)偏差量和各目標(biāo)相應(yīng)的優(yōu)先因子及權(quán)系數(shù)構(gòu)造。

當(dāng)某一目標(biāo)值確定后，決策者的要求是盡可能地縮小與目標(biāo)值的偏離。因此目標(biāo)規(guī)劃的目標(biāo)函數(shù)形式為minz=f(d+,d-)，其基本形式有三種：

1）要求恰好達(dá)到目標(biāo)值，即正負(fù)偏差都要盡可能的小，這時(shí)要求minz=f(d++d-)

2）要求不超過目標(biāo)值，也就是允許達(dá)不到目標(biāo)值，而正偏差量要盡可能的小，即minz=f(d+)3）要求不低于目標(biāo)值，也就是允許超過目標(biāo)值，而負(fù)偏差量要盡可能的小，即minz=f(d-)例2對于例1中需要考慮的多個(gè)目標(biāo)，試給出合適的目標(biāo)規(guī)劃數(shù)學(xué)模型。解：1）設(shè)定決策變量xi;2）確定所需考慮的各個(gè)目標(biāo)的優(yōu)先級及權(quán)系數(shù)。★假定決策者在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上考慮：首先是產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量（P1

級）；其次是充分利用設(shè)備有效臺(tái)時(shí)，不加班（P2

級）；再次是利潤不小于56元（P3

級）。★原材料供應(yīng)受嚴(yán)格限制－－絕對約束★首先是產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量－－優(yōu)先級為P1的目標(biāo)約束★其次是充分利用設(shè)備有效臺(tái)時(shí)，不加班－－優(yōu)先級為P2的目標(biāo)約束★再次是利潤不小于56元－－優(yōu)先級為P3的目標(biāo)約束3）將各個(gè)目標(biāo)寫入目標(biāo)規(guī)劃的約束條件，包括絕對約束和目標(biāo)約束。4）確定各個(gè)目標(biāo)約束對于各自正負(fù)偏差量的的要求?！锸紫仁钱a(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量，也就是要求x1-x2不超過目標(biāo)值0，即盡量小?！锲浯问浅浞掷迷O(shè)備有效臺(tái)時(shí)，不加班，也就是要求x1+2x2最好恰好為10，即盡量小?！镌俅问抢麧櫜恍∮?6元，也就是要求8x1+10x2不小于目標(biāo)值56，即盡量小。5）用各目標(biāo)約束的優(yōu)先因子及權(quán)系數(shù)與其自身偏差量要求的乘積的加和構(gòu)造目標(biāo)函數(shù)。6）給出各決策變量和偏差變量的非負(fù)要求將上述步驟加以整理，得例2的數(shù)學(xué)模型為：目標(biāo)規(guī)劃的一般數(shù)學(xué)模型：目標(biāo)規(guī)劃vs線性規(guī)劃

1）線性規(guī)劃只有一個(gè)目標(biāo)。而目標(biāo)規(guī)劃具有多個(gè)目標(biāo)，并有不同的優(yōu)先級，低優(yōu)先級目標(biāo)必須服從高優(yōu)先級目標(biāo)的實(shí)現(xiàn)。

2）線性規(guī)劃尋求單一目標(biāo)的最優(yōu)值。而目標(biāo)規(guī)劃尋求所有目標(biāo)與預(yù)計(jì)成果的最小差距，差距越小，目標(biāo)實(shí)現(xiàn)的可能性越大。

3）線性規(guī)劃只接受最優(yōu)解，而目標(biāo)規(guī)劃接受滿意解，即如果某些低優(yōu)先級的約束得不到滿足，將目標(biāo)規(guī)劃問題的解稱為滿意解。2.解目標(biāo)規(guī)劃的圖解法

求解思路：（1）在平面直角系的第一象限，做出滿足絕對約束條件的可行域。（2）令，做出相應(yīng)的目標(biāo)約束線，并確定正負(fù)偏差量的方向。（3）根據(jù)目標(biāo)函數(shù)中各目標(biāo)偏差量的優(yōu)先等級依次分析求解。

例：用圖解法求解例2FGJEDCOBAx1x2d1-d1+d2+d2-d3-d3+例3解:假設(shè)x1,x2分別表示彩色和黑白電視機(jī)的產(chǎn)量：FEGJDCOBAx1x2d1-d1+d2+d2-d3-d3+d4+d4-H3解目標(biāo)規(guī)劃的單純形法例：用單純形法求解書上例2的目標(biāo)規(guī)劃數(shù)學(xué)模型1.將該目標(biāo)規(guī)劃中的第四個(gè)約束（絕對約束）修正為標(biāo)準(zhǔn)化形式。2.按標(biāo)準(zhǔn)化模型列出單純形表，將檢驗(yàn)數(shù)行按優(yōu)先因子的個(gè)數(shù)排成K行，見下表。（確定初始解）11/110/256/10cBd1-x1bxBx2xsd2-d1+d3-d2+d3+cjP3P2P1P21121101-11-110121-1568101-1xsd1-

d2-d3-0

0P2P3cj-zjP1P2P3-1-8-2-101213.由高優(yōu)先級開始檢查每行檢驗(yàn)數(shù)是否存在負(fù)數(shù)，且對應(yīng)前幾行的系數(shù)為0。若存在，取最小者對應(yīng)的變量為換入變量進(jìn)基，然后用最小比原則確定出基變量，得到主元素；若不存在，計(jì)算結(jié)束。（判斷是否滿意）11/110/256/10cBd1-x1bxBx2xsd2-d1+d3-d2+d3+cjP3P2P1P21121101-11-110121-1568101-1xsd1-

d2-d3-0

0P2P3cj-zjP1P2P3-1-8-2-101214.確定主元素后，按照單純形法進(jìn)行基變換運(yùn)算，得到關(guān)于新基的計(jì)算表（換基迭代）。然后重新計(jì)算檢驗(yàn)數(shù)(第2步)，并判斷是否最優(yōu)(第三步)。410/3106/3cBd1-x1bxBx2xsd2-d1+d3-d2+d3+cjP3P2P1P263/21-1/21/253/21-1-1/21/251/211/2

-1/2

63－551－1xsd1-

x2d3-0

00P3cj-zjP1P2P3-31151-31-55.繼續(xù)進(jìn)行基變換運(yùn)算，得到關(guān)于新基的計(jì)算表，然后計(jì)算檢驗(yàn)數(shù)，判斷是否滿意。11/110/256/10cBd1-x1bxBx2xsd2-d1+d3-d2+d3+cjP3P2P1P2312-2-1/21/221-13-3-1/21/2414/3-4/3-1/61/621-5/35/31/3-1/3xsd1-

x2x10

000cj-zjP1P2P31111所有非基變量的檢驗(yàn)數(shù)均>=0,已達(dá)到滿意。6.由于非基變量d3+

的檢驗(yàn)數(shù)為0，表明存在多重解。在上表的基礎(chǔ)上以d3+作為換入變量，繼續(xù)迭代。6424cBd1-x1bxBx2xsd2-d1+d3-d2+d3+cjP3P2P1P2312-2-1/21/221-13-3-1/21/2414/3-4/3-1/61/621-5/35/31/3-1/3xsd1-

x2x10

000cj-zjP1P2P31111Cjp1p2p2p3θCBXBbx1x2xSd1-d1+d2-d2+d3-d3+xS11-11-11d3-42-26-6-11x210/31-1/31/31/3-1/3x110/312/3-2/31/3-1/3cj-zjp11p211p31第一個(gè)滿意解為：x1=2,x2=4,對應(yīng)于圖解法中的G點(diǎn)第二個(gè)滿意解為：x1=10/3,x2=10/3;對應(yīng)于圖解法中的D點(diǎn)。G,D兩點(diǎn)的凸線性組合都是此問題的滿意解。4目標(biāo)規(guī)劃的靈敏度分析目標(biāo)規(guī)劃的靈敏度分析方法與線性規(guī)劃相似，但其除了分析各項(xiàng)系數(shù)（b,cj,aij）的變化外，還有優(yōu)先因子的變化問題。例：已知目標(biāo)規(guī)劃問題其最終滿意表如下所示。cj2p13p1p2p3CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+x2611-1-11x1411-1p2d3-18-33-221-1d4-2-111-1cj-zjp123p23-32-21p31如果目標(biāo)函數(shù)的優(yōu)先等級發(fā)生變化，試分析原解有什么變化？(1)(2)解：分析式(1)可見，式(1)實(shí)際是將原目標(biāo)函數(shù)中的優(yōu)先因子對換了。這時(shí)需將原滿意表的檢驗(yàn)數(shù)的P2,P3行和cj行的P2,P3對換即可。cj2p13p1p3p2CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+x2611-1-11x1411-1p3d3-18-33-221-1d4-2-111-1cj-zjp123p21p33-32-21前兩行檢驗(yàn)數(shù)都為正，最后一行檢驗(yàn)數(shù)有負(fù)，但對應(yīng)前兩行有系數(shù)為正，說明仍達(dá)到滿意。解：分析式(2)可見，式(2)實(shí)際是將原目標(biāo)函數(shù)中的優(yōu)先因子對換了。這時(shí)需將原滿意表的檢驗(yàn)數(shù)行和cj行的相應(yīng)位置對換。cj2p23p2p1p3CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+x2611-1-11x1411-1p1d3-18-33-221-1d4-2-111-1cj-zjp13-32-21p223p31第一行檢驗(yàn)數(shù)有負(fù)數(shù)，選擇最小者對應(yīng)的變量進(jìn)基，然后用最小比原則確定出基變量，得到主元素。2p23p2P1p3CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+x281-111-1x1411-1p1d3-12-221-1-332p2d1+2-111-1cj-zjp12-213-3p2232p31通過換基迭代，然后計(jì)算檢驗(yàn)數(shù)，并判斷是否達(dá)到滿意，如果不滿意，繼續(xù)換基進(jìn)行運(yùn)算。cj2p23p2p1p3CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+x2121-5/35/31/3-1/3x1411-1p3d4+4-2/32/31/3-1/3-112p2d1+6-11-2/32/31/3-1/3cj-zjp11p204/35/3-2/32/3p32/3-2/3-1/31/31前兩行檢驗(yàn)數(shù)都為正，最后一行檢驗(yàn)數(shù)有負(fù)，但對應(yīng)前兩行有系數(shù)為正，說明已達(dá)到滿意，x1=4,x2=12。5應(yīng)用舉例例6某單位領(lǐng)導(dǎo)在考慮本單位職工