研目標(biāo)規(guī)劃ppt課件

1、目 標(biāo) 規(guī) 劃(Goal programming)目的規(guī)劃的數(shù)學(xué)模型目的規(guī)劃的圖解法目的規(guī)劃的單純形法目的規(guī)劃概述導(dǎo)入案例產(chǎn)品組合問(wèn)題產(chǎn)品I產(chǎn)品II設(shè)備A設(shè)備B設(shè)備C240205121615單位利潤(rùn)23現(xiàn)添加如下思索：1力求使利潤(rùn)目的不低于15元；2據(jù)市場(chǎng)預(yù)測(cè)，I、II兩種產(chǎn)品需求量的比例大致是1:2；3A為貴重設(shè)備，嚴(yán)厲制止超時(shí)運(yùn)用；4設(shè)備C可以適當(dāng)加班，但要控制；設(shè)備B既要求充分利用，又盡能夠不加班，在重要性上設(shè)備B是C的3倍。綜合思索上述要素，企業(yè)應(yīng)如何決策？這里本章所要討論的問(wèn)題。最優(yōu)解：x1=3x2=3z=15假設(shè)僅思索利潤(rùn)目的，其LP模型為： 目的規(guī)劃經(jīng)過(guò)引入目的值和偏向變量，可以

2、將目的函數(shù)轉(zhuǎn)化為目的約束。 目的值：是指預(yù)先給定的某個(gè)目的的一個(gè)期望值。 實(shí)現(xiàn)值或決策值：是指當(dāng)決策變量xj 選定以后，目的函數(shù)的對(duì)應(yīng)值。 偏向變量事先無(wú)法確定的未知數(shù)：是指實(shí)現(xiàn)值和目的值之間的差別,記為 d 。 正偏向變量：表示實(shí)現(xiàn)值超越目的值的部分，記為 d。 負(fù)偏向變量：表示實(shí)現(xiàn)值未到達(dá)目的值的部分，記為 d。1、目的值和偏向變量 當(dāng)完成或超額完成規(guī)定的目的那么表示：d0, d0 當(dāng)未完成規(guī)定的目的那么表示： d0, d0 當(dāng)恰好完成目的時(shí)那么表示： d0, d0 d d 0 成立。 引入了目的值和正、負(fù)偏向變量后，就對(duì)某一問(wèn)題有了新的限制，既目的約束。 目的約束即可對(duì)原目的函數(shù)起作用，

3、也可對(duì)原約束起作用。目的約束是目的規(guī)劃中特有的，是軟約束。在一次決策中，實(shí)現(xiàn)值不能夠既超越目的值又未到達(dá)目的值，故有 d d 0,并規(guī)定d0, d02、目的約束和絕對(duì)約束絕對(duì)約束系統(tǒng)約束是指必需嚴(yán)厲滿足的等式或不等式約束。如線性規(guī)劃中的一切約束條件都是絕對(duì)約束，否那么無(wú)可行解。所以，絕對(duì)約束是硬約束。目的規(guī)劃處置問(wèn)題的方法是將多目的轉(zhuǎn)化為多個(gè)目的約束。如目的利潤(rùn)的約束：甲產(chǎn)品單位利潤(rùn)2元，乙產(chǎn)品單位利潤(rùn)3元，目的要求利潤(rùn)不小于15元，即有目的約束不等式： 添加正負(fù)偏向變量，將其變?yōu)榈仁剑寒?dāng) 時(shí)，闡明 ，到達(dá)了目的；當(dāng) 時(shí)，闡明 ，未到達(dá)目的，此種情況一但發(fā)生，希望越小越好，即目的要求為：同理有

4、其他目的約束：產(chǎn)品比例設(shè)備B利用與加班設(shè)備C的加班 達(dá)成函數(shù)是一個(gè)使總偏向量為最小的目的函數(shù)，記為 minZ = fd、d。 普通說(shuō)來(lái)，有以下三種情況，但只能出現(xiàn)其中之一： .要求恰好到達(dá)規(guī)定的目的值，即正、負(fù)偏向變量要盡能夠小，那么minZ = fd d。 .要求不超越目的值，即允許達(dá)不到目的值，也就是正偏向變量盡能夠小，那么minZ = fd。 .要求超越目的值，即超越量不限，但不低于目的值，也就是負(fù)偏向變量盡能夠小，那么minZ = fd。 對(duì)于由絕對(duì)約束轉(zhuǎn)化而來(lái)的目的函數(shù)，也照上述處置即可。3、達(dá)成函數(shù)即目的規(guī)劃中的目的函數(shù) 優(yōu)先因子Pk 是將決策目的按其重要程度排序并表示出來(lái)。P1P

5、2PkPk+1PK ，k=1.2K。 權(quán)系數(shù)k 區(qū)別具有一樣優(yōu)先因子的兩個(gè)目的的差別，決策者可視詳細(xì)情況而定。 對(duì)于這種解來(lái)說(shuō)，前面的目的可以保證明現(xiàn)或部分實(shí)現(xiàn)，而后面的目的就不一定能保證明現(xiàn)或部分實(shí)現(xiàn)，有些能夠就不能實(shí)現(xiàn)。4、優(yōu)先因子優(yōu)先等級(jí)與優(yōu)先權(quán)系數(shù) 5、稱心解具有層次意義的解導(dǎo)入案例產(chǎn)品組合問(wèn)題產(chǎn)品I產(chǎn)品II設(shè)備A設(shè)備B設(shè)備C240205121615單位利潤(rùn)23現(xiàn)添加如下思索：1力求使利潤(rùn)目的不低于15元；2據(jù)市場(chǎng)預(yù)測(cè)，I、II兩種產(chǎn)品需求量的比例大致是1:2；3A為貴重設(shè)備，嚴(yán)厲制止超時(shí)運(yùn)用；4設(shè)備C可以適當(dāng)加班，但要控制；設(shè)備B既要求充分利用，又盡能夠不加班，在重要性上設(shè)備B是C的

6、3倍。綜合思索上述要素，企業(yè)應(yīng)如何決策？這里本章所要討論的問(wèn)題。最優(yōu)解：x1=3x2=3z=15假設(shè)僅思索利潤(rùn)目的，其LP模型為：將上述目的規(guī)劃的目的約束、目的函數(shù)再加上系統(tǒng)約束和變量非負(fù)約束，即構(gòu)成了引例中的目的規(guī)劃數(shù)學(xué)模型如下： 目的規(guī)劃是在線性規(guī)劃的根底上，為順應(yīng)經(jīng)濟(jì)管理中多目的決策的需求而逐漸開展起來(lái)的一個(gè)分支。 2、線性規(guī)劃求最優(yōu)解；目的規(guī)劃是找到一個(gè)稱心解。 1、線性規(guī)劃只討論一個(gè)線性目的函數(shù)在一組線性約束條件下的極值問(wèn)題；而目的規(guī)劃是多個(gè)目的決策，可求得更切合實(shí)踐的解。目的規(guī)劃概述一、目的規(guī)劃與線性規(guī)劃的比較 4、線性規(guī)劃的最優(yōu)解是絕對(duì)意義下的最優(yōu)，但需花去大量的人力、物力、財(cái)力

7、才干得到；實(shí)踐過(guò)程中，只需求得稱心解，就能滿足需求或更能滿足需求。 3、線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目的規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。目前，曾經(jīng)在經(jīng)濟(jì)方案、消費(fèi)管理、運(yùn)營(yíng)管理、市場(chǎng)分析、財(cái)務(wù)管理等方面得到了廣泛的運(yùn)用。目的規(guī)劃的數(shù)學(xué)模型目的規(guī)劃數(shù)學(xué)模型的普通方式： 優(yōu)先因子正偏向權(quán)系數(shù)負(fù)偏向權(quán)系數(shù)目的約束系統(tǒng)約束變量非負(fù)建模的步驟 1、根據(jù)要研討的問(wèn)題所提出的各目的與條件，確定目的值，列出目的約束與絕對(duì)約束； 4、對(duì)同一優(yōu)先等級(jí)中的各偏向變量，假設(shè)需求可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù) 。 3、給各目的賦予相應(yīng)的優(yōu)先因子 Pkk=1.2K。 2、可根據(jù)決策者的需

8、求，將某些或全部絕對(duì)約束轉(zhuǎn)化為目的約束。這時(shí)只需求給絕對(duì)約束加上負(fù)偏向變量和減去正偏向變量即可。 5、根據(jù)決策者的要求，按以下情況之一構(gòu)造 優(yōu)先因子和權(quán)系數(shù)相對(duì)應(yīng)的偏向變量組成的，要?jiǎng)?wù)虛現(xiàn)極小化的目的函數(shù)，即達(dá)成函數(shù)。.恰好到達(dá)目的值，取 。.允許超越目的值，取 。.不允許超越目的值，取 。 例、某廠方案在下一個(gè)消費(fèi)周期內(nèi)消費(fèi)甲、乙兩種產(chǎn)品，知資料如表所示。試制定消費(fèi)方案，使獲得的利潤(rùn)最大？同時(shí)，根據(jù)市場(chǎng)預(yù)測(cè)，甲的銷路不是太好，應(yīng)盡能夠少消費(fèi)；乙的銷路較好，可以擴(kuò)展消費(fèi)。試建立此問(wèn)題的數(shù)學(xué)模型。12070單件利潤(rùn)3000103設(shè)備臺(tái)時(shí)200054煤炭360049鋼材資源限制乙甲 單位 產(chǎn)品資源

9、 耗費(fèi) 另外提出以下要求： 1、完成或超額完成利潤(rùn)目的 50000元； 2、產(chǎn)品甲不超越 200件，產(chǎn)品乙不低于 250件； 3、現(xiàn)有鋼材 3600噸必需用完。試建立目的規(guī)劃模型。 分析：標(biāo)題有三個(gè)目的層次，包含四個(gè)目的值。 第一目的： 第二目的：有兩個(gè)要求即甲 ，乙 ，但兩個(gè)具有一樣的優(yōu)先因子，因此需求確定權(quán)系數(shù)。此題可用單件利潤(rùn)比作為權(quán)系數(shù)即 70 :120，化簡(jiǎn)為7:12。第三目的：目的規(guī)劃模型為： 某廠消費(fèi)、兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的消費(fèi)方案？擁有量原材料2111設(shè)備(臺(tái)時(shí))1210單件利潤(rùn)810 在此根底上思索： 1、產(chǎn)品的產(chǎn)量不低于產(chǎn)品的產(chǎn)量； 2、充分利用設(shè)備有效

10、臺(tái)時(shí)，不加班； 3、利潤(rùn)不小于 56 元。解: 分析 第一目的： 即產(chǎn)品的產(chǎn)量不大于的產(chǎn)量。 第二目的：例三：第三目的：規(guī)劃模型：三、小結(jié)線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min , max系數(shù)可正負(fù)min , 偏差變量系數(shù)0變量xi, xs xa xi xs xa d約束條件系統(tǒng)約束（絕對(duì)約束）目標(biāo)約束系統(tǒng)約束解最優(yōu)最滿意 圖解法同樣適用兩個(gè)變量的目的規(guī)劃問(wèn)題，但其操作簡(jiǎn)單，原理一目了然。同時(shí)，也有助于了解普通目的規(guī)劃的求解原理和過(guò)程。 圖解法解題步驟如下： 1、確定各約束條件的可行域，即將一切約束條件包括目的約束和絕對(duì)約束，暫不思索正負(fù)偏向變量在坐標(biāo)平面上表示出來(lái)； 2、在目的約束所代表的邊

11、境限上，用箭頭標(biāo)出正、負(fù)偏向變量值增大的方向；三、目的規(guī)劃的圖解法 3、求滿足最高優(yōu)先等級(jí)目的的解； 4、轉(zhuǎn)到下一個(gè)優(yōu)先等級(jí)的目的，在不破壞一切較高優(yōu)先等級(jí)目的的前提下，求出該優(yōu)先等級(jí)目的的解； 5、反復(fù)4，直到一切優(yōu)先等級(jí)的目的都已審查終了為止； 6、確定最優(yōu)解和稱心解。例一、用圖解法求解目的規(guī)劃問(wèn)題01 2 3 4 5 6 7 8 1 2 3 4 5 6 Ax2 x1BC B (0.6250 , 4.6875) C (0 , 5.2083) ， B、C 線段上的一切點(diǎn)均是該問(wèn)題的解無(wú)窮多最優(yōu)解。圖解法x1x2o662x1+2x2=122x1+3x2=157.552x1-x2=04x1=16

12、5x2=151繪出直角坐標(biāo)2圖示系統(tǒng)約束，確定可行域3按優(yōu)先級(jí)高低，依次圖示目的約束，減少稱心解范圍。 例二、知一個(gè)消費(fèi)方案的線性規(guī)劃模型為 其中目的函數(shù)為總利潤(rùn)，x1,x2 為產(chǎn)品A、B產(chǎn)量。現(xiàn)有以下目的： 1、要求總利潤(rùn)必需超越 2500 元； 2、思索產(chǎn)品受市場(chǎng)影響，為防止積壓，A、B的消費(fèi)量不超越 60 件和 100 件； 3、由于甲資源供應(yīng)比較緊張，不要超越現(xiàn)有量140。試建立目的規(guī)劃模型，并用圖解法求解。 解：以產(chǎn)品 A、B 的單件利潤(rùn)比 2.5 ：1 為權(quán)系數(shù)，模型如下：0 x2 0 x11401201008060402020 40 60 80 100ABCD 結(jié)論：C(60 ,

13、58.3)為所求的稱心解。作圖： 檢驗(yàn)：將上述結(jié)果帶入模型，因 0； 0； 0， 存在； 0， 存在。所以，有下式： minZ=P3 將 x160， x2 58.3 帶入約束條件，得30601258.32499.62500；260+58.3=178.3 140；16060158.358.3 0。闡明第k個(gè)優(yōu)先等級(jí)的目的尚未到達(dá),必需檢查Pk這一的檢驗(yàn)數(shù)kj(j=1.2n+2m).假設(shè)Pk這一行某些負(fù)檢驗(yàn)數(shù)的同列上面較高優(yōu)先等級(jí)沒(méi)有正檢驗(yàn)數(shù)，闡明未得到稱心解，應(yīng)繼續(xù)改良，轉(zhuǎn)到第3步；假設(shè)Pk這一行全部負(fù)檢驗(yàn)數(shù)的同列上面較高優(yōu)先等級(jí)都有正檢驗(yàn)數(shù)，闡明目的雖沒(méi)到達(dá)，但已不能改良，故得稱心解，轉(zhuǎn)到第6

14、步。 3、確定進(jìn)基變量。 在Pk行，從那些上面沒(méi)有正檢驗(yàn)數(shù)的負(fù)檢驗(yàn)數(shù)中，選絕對(duì)值最大者，對(duì)應(yīng)的變量xs就是進(jìn)基變量。假設(shè)Pk行中有幾個(gè)一樣的絕對(duì)值最大者，那么依次比較它們各列下部的檢驗(yàn)數(shù)，取其絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)的所在列的xs為進(jìn)基變量。假設(shè)仍無(wú)法確定，那么選最左邊的變量變量下標(biāo)小者為進(jìn)基變量。 4、確定出基變量 其方法同線性規(guī)劃，即根據(jù)最小比值法那么故確定xr為出基變量，ers為主元素。假設(shè)有幾個(gè)一樣的行可供選擇時(shí)，選最上面那一行所對(duì)應(yīng)得變量為xr 。 5、旋轉(zhuǎn)變換變量迭代。 以為主元素進(jìn)展變換，得到新的單純形表，獲得一組新解，前往到第2步。 6、對(duì)求得的解進(jìn)展分析 假設(shè)計(jì)算結(jié)果稱心，停頓運(yùn)

15、算；假設(shè)不稱心，需修正模型，即調(diào)整目的優(yōu)先等級(jí)和權(quán)系數(shù)，或者改動(dòng)目的值，重新進(jìn)展第1步。單純形法步驟：第1步 列出初始單純形表1由于目的函數(shù)均為負(fù)值，為方便起見，不轉(zhuǎn)換為極大；2以系統(tǒng)約束的松馳變量、人工變量、目的約束的負(fù)偏向變量為初始基變量；3檢驗(yàn)數(shù)行按優(yōu)先因子分別列出。第2步 計(jì)算檢驗(yàn)數(shù)，確定換入變量1從第一級(jí)優(yōu)級(jí)開場(chǎng)，假設(shè)檢驗(yàn)數(shù)存在負(fù)數(shù)，最小檢驗(yàn)數(shù)所對(duì)應(yīng)的變量為換入變量。當(dāng)高級(jí)優(yōu)先級(jí)得到優(yōu)化，轉(zhuǎn)向下一級(jí)；2在第k優(yōu)先級(jí)優(yōu)化過(guò)程中，假設(shè)破壞了上級(jí)優(yōu)化結(jié)果，那么迭代停頓，k-1以上級(jí)目的得到優(yōu)化，k級(jí)以下未得到優(yōu)化，所得結(jié)果為稱心解；3假設(shè)一切檢驗(yàn)數(shù)均非負(fù)，一切目的均得到優(yōu)化，所得結(jié)果可稱為

16、最優(yōu)解。第3步 用最小比值原那么確定換出變量第4步 用換入變量交換換出變量，用行初等變換方法列出新的單純形表，前往第2步。用單純形法求目的規(guī)劃稱心解稱心解例一、用單純形法求解以下目的規(guī)劃問(wèn)題Cj00P1000000000000002.5P20P200000P30000CBXBbx1x2P1250030121100000001402100110000060100000110001000100000011kjP1 -2500301201000000P2 000000002.501P3 00000010000= min2500/30,140/2,60/1=60 ,故 為換出變量。Cj 00P100P

17、302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x160100000110001000100000011kjP1 7000120100303000P2 000000002.501P3 00000010000= min700/30,20/2, =10 ,故 為換出變量。Cj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000 x17011/2001/2-1/200000100010000001-1kjP1 -400030115-150000P2 -

18、250-5/400-5/45/45/2001P3 00000010000= min400/15, =10 ,故 為換出變量。Cj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/3000000001000100000011kjP1 00010000000P2 -175/30-1-1/121/12002/5001P3 -80/301/5-1/151/15100000= min,350/6,1250/6,100/1=75 ,故 為換出變量。Cj

19、 00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000 x2175/3011/12-1/1200-5/25/2000 x160100000-11000125/300-1/121/12005/2-5/211kjP1 00010000000P2 000000005/201P3 -115/300-1/121/12101/2-1/200表中P3115/30，闡明P3 優(yōu)先等級(jí)目的沒(méi)有實(shí)現(xiàn)，但已無(wú)法改良，得到稱心解 x1 60， x2 175/3， 115/3， 125/3。 結(jié)果分析：計(jì)算結(jié)果闡明，工廠應(yīng)消費(fèi)A產(chǎn)品60件，B產(chǎn)品175/3件

20、，2500元的利潤(rùn)目的剛好到達(dá)。 125/3，闡明產(chǎn)品比最高限額少125/3件，滿足要求。 115/3 闡明甲資源超越庫(kù)存115/3公斤，該目的沒(méi)有到達(dá)。 從表中還可以看到，P3 的檢驗(yàn)數(shù)還有負(fù)數(shù)，但其高等級(jí)的檢驗(yàn)數(shù)卻是正數(shù)，要保證 P1目的實(shí)現(xiàn)，P3等級(jí)目的那么無(wú)法實(shí)現(xiàn)。所以，按現(xiàn)有耗費(fèi)程度和資源庫(kù)存量，無(wú)法實(shí)現(xiàn)2500元的利潤(rùn)目的。 可思索如下措施：降低A、B產(chǎn)品對(duì)甲資源的耗費(fèi)量，以滿足現(xiàn)有甲資源庫(kù)存量的目的；或改動(dòng)P3等級(jí)目的的目的值，添加甲資源115/3公斤。 假設(shè)很難實(shí)現(xiàn)上述措施，那么需改動(dòng)現(xiàn)有目的的優(yōu)先等級(jí)，以獲得可行的稱心解果。練習(xí)：用單純形法求解以下目的規(guī)劃問(wèn)題Cj 000P1

21、 P2 P2P3 00CBXBbx1x2 x3 00111100000P210120011000 P3 5681000001100 x3 11210000001kjP1 0000100000P2 10120002000P3 568100000010= min,10/2,56/10,11/1= 5,故 為換出變量。Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 023/20111/2-1/20000 x251/21001/2-1/2000 P3 63000-551100 x3 63/2000-1/21/2001kjP1 0000100000P2 0000011000P3 6300

22、05-5010= min10/3,10,6/3,12/3= 2,故 為換出變量。Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 0200113-3-1/21/200 x2401004/3-4/3-1/61/600 x121000-5/35/31/3-1/300 x3 300002-2-1/21/21kjP1 0000100000P2 0000011000P3 0000000100 最優(yōu)解為x12， x2 4。 但非基變量 的檢驗(yàn)數(shù)為零，故此題有無(wú)窮多最優(yōu)解。= min4 , 24 , 6= 4,故 為換出變量。Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 04

23、002-26-6-1100 x210/301-1/31/31/3-1/30000 x110/3102/3-2/31/3-1/30000 x3 100-11-11001kjP1 0000100000P2 0000011000P3 0000000100 最優(yōu)解為x110/3,，x2 =10/3。 1、某廠消費(fèi)A、B、C三種產(chǎn)品，裝配任務(wù)在同一消費(fèi)線上完成，三種產(chǎn)品時(shí)的工時(shí)耗費(fèi)分別為6、8、10小時(shí)，消費(fèi)線每月正常任務(wù)時(shí)間為200小時(shí)；三種產(chǎn)品銷售后，每臺(tái)可獲利分別為500、650和800元；每月銷售量估計(jì)為12、10和6臺(tái)。 該廠運(yùn)營(yíng)目的如下：1、利潤(rùn)目的為每月16000元，爭(zhēng)取超額完成；2、充分利用現(xiàn)有消費(fèi)才干；3、可以適當(dāng)加班，但加班時(shí)間不得超越24小時(shí)；4、產(chǎn)量以估計(jì)銷售量為準(zhǔn)。試建立目的規(guī)劃模型。 作業(yè)：2、用圖解法求解以下目的規(guī)劃問(wèn)題：稱心解為由x1 =3， 3, x2 =3.5，1.5 所連線段。 3、用圖解法解以下目的規(guī)劃模