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

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

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

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

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

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

、d-；正偏差量d+表示決策值超過目標值的部分；負偏差量d-

表示決策值未達到目標值的部分;

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

、d-

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

Pk>>Pk+1

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

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

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

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

級）；其次是充分利用設備有效臺時，不加班（P2

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

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

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

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

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

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

例：用圖解法求解例2FGJEDCOBAx1x2d1-d1+d2+d2-d3-d3+例3解:假設x1,x2分別表示彩色和黑白電視機的產量：FEGJDCOBAx1x2d1-d1+d2+d2-d3-d3+d4+d4-H3解目標規(guī)劃的單純形法例：用單純形法求解書上例2的目標規(guī)劃數(shù)學模型1.將該目標規(guī)劃中的第四個約束（絕對約束）修正為標準化形式。2.按標準化模型列出單純形表，將檢驗數(shù)行按優(yōu)先因子的個數(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)先級開始檢查每行檢驗數(shù)是否存在負數(shù)，且對應前幾行的系數(shù)為0。若存在，取最小者對應的變量為換入變量進基，然后用最小比原則確定出基變量，得到主元素；若不存在，計算結束。（判斷是否滿意）11/110/256/10cBd1-x1bxBx2xsd2-d1+d3-d2+d3+cjP3P2P1P21121101-11-110121-1568101-1xsd1-

d2-d3-0

0P2P3cj-zjP1P2P3-1-8-2-101214.確定主元素后，按照單純形法進行基變換運算，得到關于新基的計算表（換基迭代）。然后重新計算檢驗數(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ù)進行基變換運算，得到關于新基的計算表，然后計算檢驗數(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所有非基變量的檢驗數(shù)均>=0,已達到滿意。6.由于非基變量d3+

的檢驗數(shù)為0，表明存在多重解。在上表的基礎上以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第一個滿意解為：x1=2,x2=4,對應于圖解法中的G點第二個滿意解為：x1=10/3,x2=10/3;對應于圖解法中的D點。G,D兩點的凸線性組合都是此問題的滿意解。4目標規(guī)劃的靈敏度分析目標規(guī)劃的靈敏度分析方法與線性規(guī)劃相似，但其除了分析各項系數(shù)（b,cj,aij）的變化外，還有優(yōu)先因子的變化問題。例：已知目標規(guī)劃問題其最終滿意表如下所示。cj2p13p1p2p3CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+x2611-1-11x1411-1p2d3-18-33-221-1d4-2-111-1cj-zjp123p23-32-21p31如果目標函數(shù)的優(yōu)先等級發(fā)生變化，試分析原解有什么變化？(1)(2)解：分析式(1)可見，式(1)實際是將原目標函數(shù)中的優(yōu)先因子對換了。這時需將原滿意表的檢驗數(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前兩行檢驗數(shù)都為正，最后一行檢驗數(shù)有負，但對應前兩行有系數(shù)為正，說明仍達到滿意。解：分析式(2)可見，式(2)實際是將原目標函數(shù)中的優(yōu)先因子對換了。這時需將原滿意表的檢驗數(shù)行和cj行的相應位置對換。cj2p23p2p1p3CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+x2611-1-11x1411-1p1d3-18-33-221-1d4-2-111-1cj-zjp13-32-21p223p31第一行檢驗數(shù)有負數(shù)，選擇最小者對應的變量進基，然后用最小比原則確定出基變量，得到主元素。2p23p2P1p3CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+x281-111-1x1411-1p1d3-12-221-1-332p2d1+2-111-1cj-zjp12-213-3p2232p31通過換基迭代，然后計算檢驗數(shù)，并判斷是否達到滿意，如果不滿意，繼續(xù)換基進行運算。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前兩行檢驗數(shù)都為正，最后一行檢驗數(shù)有負，但對應前兩行有系數(shù)為正，說明已達到滿意，x1=4,x2=12。5應用舉例例6某單位領導在考慮本單位職工