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

目標(biāo)規(guī)劃_第10章目標(biāo)規(guī)劃(Goalprogramming)目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟管理中多目標(biāo)決策的需要而逐步發(fā)展起來的一個分支。例一、某廠計劃在下一個生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計劃，使獲得的利潤最大？同時，根據(jù)市場預(yù)測，甲的銷路不是太好，應(yīng)盡可能少生產(chǎn)；乙的銷路較好，可以擴大生產(chǎn)。試建立此問題的數(shù)學(xué)模型。12070單件利潤3000103設(shè)備臺時200054煤炭360049鋼材資源限制乙甲單位產(chǎn)品資源消耗一、目標(biāo)規(guī)劃模型設(shè)：甲產(chǎn)品x1

，乙產(chǎn)品x2

一般有：maxZ=70x1

+120x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000

x1，

x2≥0同時：maxZ1=70x1

+120x2minZ2=x1maxZ3=x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000

x1，

x2≥0顯然，這是一個多目標(biāo)規(guī)劃問題。如何將多目標(biāo)轉(zhuǎn)化為單目標(biāo)如何表示不同目標(biāo)的主次如何求解若在上例中提出下列要求：

1、完成或超額完成利潤指標(biāo)50000元；2、產(chǎn)品甲不超過200件，產(chǎn)品乙不低于250件；3、現(xiàn)有鋼材3600噸必須用完。2、產(chǎn)品甲不超過200件，產(chǎn)品乙不低于250件；3、3600噸鋼材必須用完目標(biāo)值：預(yù)先給定的某個目標(biāo)的一個期望值e。實現(xiàn)值或決策值：當(dāng)決策變量xj

被求出以后，目標(biāo)函數(shù)的對應(yīng)值。偏差變量（事先無法確定的未知數(shù)）：實現(xiàn)值和目標(biāo)值之間的差異,記為d。正偏差變量：實現(xiàn)值超過目標(biāo)值的部分，記為d＋。負偏差變量：實現(xiàn)值未達到目標(biāo)值的部分，記為d－。1、目標(biāo)值和偏差變量通過引入目標(biāo)值和偏差變量，使上述三個要求變成相應(yīng)的約束條件，即目標(biāo)約束。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：d＋≥0,d－＝0當(dāng)未完成規(guī)定的指標(biāo)則表示：d＋＝0,d－≥0當(dāng)恰好完成指標(biāo)時則表示：d＋＝0,d－＝0∴d＋×d－

＝0成立。引入了目標(biāo)值和正、負偏差變量后，就對某一問題有了新的限制，即目標(biāo)約束。在一次決策中，實現(xiàn)值不可能既超過目標(biāo)值又未達到目標(biāo)值，故有d＋×d－

＝0,并規(guī)定d＋≥0,d－≥02、目標(biāo)約束和絕對約束

絕對約束：必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對約束，有一個不滿足就無可行解。所以，絕對約束是硬約束。目標(biāo)約束（軟約束）絕對約束（硬約束）

目標(biāo)函數(shù)是一個使總偏差量為最小的目標(biāo)函數(shù)，記為 minZ=f（d＋、d－）。一般說來，有以下三種情況，但只能出現(xiàn)其中之一：3、目標(biāo)函數(shù)⑴要求恰好達到規(guī)定的目標(biāo)值，即正、負偏差變量要盡可能小，則minZ=f（d＋＋d－）。⑵要求不超過目標(biāo)值，即允許達不到目標(biāo)值，也就是正偏差變量盡可能小，則minZ=f（d＋）。⑶要求不低于目標(biāo)值，即超過量不限，也就是負偏差變量盡可能小，則minZ=f（d－）。對于由絕對約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可。優(yōu)先因子Pk

是將決策目標(biāo)按其重要程度排序并表示出來。P1>>P2>>…>>Pk>>Pk+1>>…>>PK，k=1.2…K。權(quán)系數(shù)ωk區(qū)別具有相同優(yōu)先因子的兩個目標(biāo)的差別，決策者可視具體情況而定。對于這種解來說，前面的目標(biāo)可以保證實現(xiàn)或部分實現(xiàn)，而后面的目標(biāo)就不一定能保證實現(xiàn)或部分實現(xiàn)，有些可能就不能實現(xiàn)。4、優(yōu)先因子（優(yōu)先等級）與優(yōu)先權(quán)系數(shù)5、滿意解（具有層次意義的解）對于上例中的目標(biāo)：1、完成或超額完成利潤指標(biāo)50000元；2、產(chǎn)品甲不超過200件，產(chǎn)品乙不低于250件；3、現(xiàn)有鋼材3600噸必須用完。若實現(xiàn)值沒有達到目標(biāo)，則存在偏差，希望按目標(biāo)先后盡可能使偏差最小。偏差目標(biāo)2有兩個要求，且具有相同的優(yōu)先因子，因此需要確定權(quán)系數(shù)。本題可用單件利潤比作為權(quán)系數(shù)即70:120，化簡為7:12。目標(biāo)規(guī)劃模型為：例：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案。ⅠⅡ限量原材料2111設(shè)備(臺時)1210單件利潤810要求考慮：1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；2、充分利用設(shè)備有效臺時，不加班；3、利潤不小于56元。設(shè)：I、II產(chǎn)品產(chǎn)量分別為x1

，x2

目標(biāo)規(guī)劃模型：目標(biāo)規(guī)劃模型的一般形式目標(biāo)規(guī)劃建模步驟2、根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對約束；5、對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù)。4、給各目標(biāo)賦予相應(yīng)的優(yōu)先因子Pk（k=1.2…K）。3、可根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目標(biāo)約束。這時只需要給絕對約束加上負偏差變量和減去正偏差變量即可。1、假設(shè)決策變量；6、根據(jù)決策者的要求，按下列情況之一構(gòu)造一個由優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的、要求實現(xiàn)極小化的目標(biāo)函數(shù)，即達成函數(shù)。⑴.恰好達到目標(biāo)值，取。⑵.不希望低于目標(biāo)值，取。⑶.不希望超過目標(biāo)值，取。圖解法同樣適用兩個變量的目標(biāo)規(guī)劃問題，但其操作簡單，原理一目了然。同時，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。圖解法解題步驟如下：1、確定各約束條件的可行域，即將所有約束條件（包括目標(biāo)約束和絕對約束，暫不考慮正負偏差變量）在坐標(biāo)平面上表示出來；2、在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負偏差變量值增大的方向；目標(biāo)規(guī)劃的圖解法3、求滿足最高優(yōu)先等級目標(biāo)的解；4、轉(zhuǎn)到下一個優(yōu)先等級的目標(biāo)，再不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解；5、重復(fù)4，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止；6、確定最優(yōu)解或滿意解。例：用圖解法求解目標(biāo)規(guī)劃問題012345678123456⑶⑴x2

x1⑵BC

B(0.6250,4.6875)C(0,5.2083)，B、C線段上的所有點均是該問題的解（無窮多最優(yōu)解）。練習(xí)：用圖解法求解下列目標(biāo)規(guī)劃問題⑷⑴⑶⑵結(jié)論：有無窮多最優(yōu)解。C（2，4）D（10/3，10/3）CD例：已知一個生產(chǎn)計劃的線性規(guī)劃模型為其中目標(biāo)函數(shù)為總利潤，x1,x2為產(chǎn)品A、B產(chǎn)量?，F(xiàn)有下列目標(biāo)：1、要求總利潤必須超過2500元；2、考慮產(chǎn)品受市場影響，為避免積壓，A、B的生產(chǎn)量不超過60件和100件；3、由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并用單純形法求解。P1P3P2目標(biāo)規(guī)劃的單純形法Cj00P100P302.5P20P2CBXBbx1x2P1250030121－1000000014021001－100000601000001－1000100010000001－1σkjP1

-2500－30－1201000000P2

000000002.501P3

00000010000θ=min｛2500/30,140/2,60/1｝=60,故為換出變量。目標(biāo)函數(shù)系數(shù)和檢驗數(shù)豎著排列σ

=2.5P2-（0*P1+0*0-1*0+0*0）=2.5P2,將2.5填P2行。Cj

00P100P302.5P20P2CBXBbx1x2P17000121－100－30300002001001－1－22000x1601000001－1000100010000001－1σkjP1

－7000－12010030－3000P2

000000002.501P3

00000010000θ=min｛700/30,20/2,－,－｝=10,故為換出變量。σ

=2.5P2-（30P1+2*0-1*0+0*0）=2.5P2-30P1Cj

00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000x17011/2001/2-1/200000100010000001-1σkjP1

-400030115-150000P2

-250-5/400-5/45/45/2001P3

00000010000θ=min｛400/15,－,－,－｝=10,故為換出變量。σ

=0-（-15P1+2.5P2/2+1/2*0+0*0）=15P1-2.5P2/2Cj

00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000x1250/312/51/30-1/300000000100010000001－1σkjP1

00010000000P2

-175/30-1-1/121/12002/5001P3

-80/301/5-1/151/15100000θ=min｛－,350/6,1250/6,100/1｝=75,故為換出變量。Cj

00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000x2175/3011/12-1/1200-5/25/2000x160100000-11000125/300-1/121/12005/2-5/21－1σkjP1

00010000000P2

000000005/201P3

-115/300-1/121/12101/2-1/200表中P3行有負檢驗數(shù)，說明P3級目標(biāo)沒有實現(xiàn)，但已無法改進，得到滿意解

x1＝60，x2＝175/3，＝115/3，＝125/3。

結(jié)果分析：計算結(jié)果表明，工廠應(yīng)生產(chǎn)A產(chǎn)品60件，B產(chǎn)品175/3件，2500元的利潤目標(biāo)剛好達到。＝125/3，表明產(chǎn)品B比最高限額少125/3件，滿足要求。＝115/3表明甲資源超過庫存115/3公斤，該目標(biāo)沒有達到。即甲資源多消耗115/3公斤，剛好實現(xiàn)2500元的利潤目標(biāo)。而按現(xiàn)有消耗水平和資源庫存量，無法實現(xiàn)利潤目標(biāo)?？煽紤]如下措施：降低A、B產(chǎn)品對甲資源的消耗量，以滿足現(xiàn)有甲資源庫存量的目標(biāo)；或改變P3級目標(biāo)值，增加甲資源115/3公斤。若很難實現(xiàn)上述措施，則需改變現(xiàn)有目標(biāo)的優(yōu)先等級，以取得可行的滿意解果。1、要求總利潤必須超過2500元；2、考慮產(chǎn)品受市場影響，為避免積壓，A、B的生產(chǎn)量不超過60件和100件；3、由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140。1、建立初始單純形表。一般假定初始解在原點，即以約束條件中的所有負偏差變量或松弛變量為初始基變量，按目標(biāo)優(yōu)先等級從左至右分別計算出各列的檢驗數(shù)，填入表的下半部。2、檢驗是否為滿意解。判別準(zhǔn)則如下：⑴.首先檢查b列中的αk

(k=1.2…K)是否全部為零？如果全部為零，則表示目標(biāo)均已全部達到，獲得滿意解，停止計算轉(zhuǎn)到第6步；否則轉(zhuǎn)入⑵。

（二）、單純形法的計算步驟⑵.如果某一個αk

>0。說明第k個優(yōu)先等級的目標(biāo)尚未達到,必須檢查Pk行的檢驗數(shù)σkj(j=1.2…n+2m).若Pk這一行某些負檢驗數(shù)的同列上面（較高優(yōu)先等級）沒有正檢驗數(shù)，說明未得到滿意解，應(yīng)繼續(xù)改進，轉(zhuǎn)到第3步；若Pk這一行全部負檢驗數(shù)的同列上面（較高優(yōu)先等級）都有正檢驗數(shù)，說明目標(biāo)雖沒達到，但已不能改進，故得滿意解，轉(zhuǎn)到第6步。3、確定進基變量。在Pk行，從那些上面沒有正檢驗數(shù)的負檢驗數(shù)中，選絕對值最大者，對應(yīng)的變量xs就是進基變量。若Pk行中有幾個相同的絕對值最大者，則依次比較它們各列下部的檢驗數(shù)，取其絕對值最大的負檢驗數(shù)的所在列的xs為進基變量。假如仍無法確定，則選最左邊的變量（變量下標(biāo)小者）為進基變量。4、確定出基變量其方法同線性規(guī)劃，即依據(jù)最小比值法則故確定xr為出基變量，ers為主元素。若有幾個相同的行可供選擇時，選最上面那一行所對應(yīng)得變量為xr。5、旋轉(zhuǎn)變換（變量迭代）。以主元素進行變換，得到新的單純形表，獲得一組新解，返回到第2步。6、對求得的解進行分析若計算結(jié)果滿意，停止運算；若不滿意，需修改模型，即調(diào)整目標(biāo)優(yōu)先等級和權(quán)系數(shù)，或者改變目標(biāo)值，重新進行第1步。練習(xí)：用單純形法求解下列目標(biāo)規(guī)劃問題Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

001－11－100000P21012001－1000P3

5681000001－100

x3

11210000001σkjP1

0000100000P2

－10－1－20002000P3

－56－8－100000010θ=min｛－,10/2,56/10,11/1｝=5,故為換出變量。Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

023/201－11/2-1/20000x251/21001/2-1/2000P3

63000-551－100

x3

63/2000-1/21/2001σkjP1

0000100000P2

0000011000P3

－6－30005-5010θ=min｛4/3,10,6/3,12/3｝=2,故為換出變量。Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

02001－13-3-1/21/200x2401004/3-4/3-1/61/600x121000-5/35/31/3-1/300

x3

300002-2-1/21/21σ