目標規(guī)劃hppt課件

1、第五章目標規(guī)劃Objective Programming本章知識點本章知識點l了解與現(xiàn)行規(guī)劃相比較，目標規(guī)劃的特點；l理解目標規(guī)劃中正負偏差的含義，掌握根據(jù)實際問題設定正負偏差；l理解目標的優(yōu)先級與權系數(shù)的含義，掌握根據(jù)實際問題設定優(yōu)先級與權系數(shù)；l掌握目標繪畫圖解法；l掌握根據(jù)實際問題建立目標規(guī)劃數(shù)學模型。主要內(nèi)容l問題的提出問題的提出l目標規(guī)劃的數(shù)學模型目標規(guī)劃的數(shù)學模型l目標規(guī)劃的圖解分析目標規(guī)劃的圖解分析l應用舉例應用舉例問題的提出例1l某企業(yè)計劃生產(chǎn)、兩種產(chǎn)品，這些產(chǎn)品分別要在A、B、C、D四種不同設備上加工。l按工藝文件規(guī)定，每生產(chǎn)一件產(chǎn)品占用各設備分別為2h、1h、4h、0h，每

2、生產(chǎn)一件產(chǎn)品分別占用各設備2h、2h、0h、4h。l已知各設備在計劃期內(nèi)的能力分別為12h、8h、16h、12 h，l又知每生產(chǎn)一件產(chǎn)品，利潤收入為2元，生產(chǎn)一件產(chǎn)品，利潤收入為3元。l問該企業(yè)應如何安排計劃，使在計劃期內(nèi)的總利潤收入為最大? l設、產(chǎn)品的產(chǎn)量分別為x1、x2，可以建立這個問題的線性規(guī)劃模型如下： 2132maxxxz0,12416482122221212121xxxxxxxx最優(yōu)解為 , , 元.41x22x14*z l如果企業(yè)的經(jīng)營目標包括多個方面，如：l 力求使利潤指標不低于12元；l 考慮到市場需求，、兩種產(chǎn)品的生產(chǎn)量需保持1：1的比例；l C和D為貴重設備，嚴格禁止超

3、時使用；l 設備B必要時可以加班，但加班時間要控制；設備A既要求充分利用，又盡可能不加班。1.如何綜合考慮上述多方面的目標，制定生產(chǎn)計劃？l線性規(guī)劃歸根結(jié)底是研究資源的有效分配和利用；l模型的特點是：l在滿足一組約束條件的情況下，尋求某一個目標(如產(chǎn)量、利潤、成本等)的最大值或最小值。 線性規(guī)劃模型存在的局限性(1)l 它要求問題的解必須滿足全部約束條件，但實際問題中并非所有約束都需嚴格滿足嚴格滿足，對某些約束有一定程度的違背是允許的。l 只能處理單目標單目標的優(yōu)化問題，因此線性規(guī)劃模型中人為地將一些次要目標轉(zhuǎn)為約束。而實際問題中，目標和約束可以互相轉(zhuǎn)化，處理時不一定要嚴格區(qū)分。例如在給定資源

4、條件下，使產(chǎn)量盡可能多，這里資源是約束，產(chǎn)量是目標。但如果規(guī)定需完成的產(chǎn)量條件下，使資源的耗費最小，則成了產(chǎn)量是約束，資源耗費是目標。線性規(guī)劃模型存在的局限性(2)l線性規(guī)劃中各個約束條件(實際上也可看作目標)都處于同等重要同等重要地位，但現(xiàn)實問題中，各目標的重要性既有層次上的差別，同一層次中又可以有權重上的區(qū)分；l線性規(guī)劃尋求最優(yōu)解，但很多實際問題中只需找出滿意解滿意解就可以。目標規(guī)劃的特點l目標規(guī)劃是實行目標管理的有效工具，它根據(jù)企業(yè)制訂的經(jīng)營目標以及這些目標的輕重緩急次序，考慮現(xiàn)有資源情況，分析l如何達到規(guī)定目標或從總體上離規(guī)定目標如何達到規(guī)定目標或從總體上離規(guī)定目標的差距為最小的差距為

5、最小。 目標規(guī)劃解決線性規(guī)劃建模中局限性的方法 l 設置偏差變量 l 統(tǒng)一處理目標和約束 l 設定目標的優(yōu)先級與權系數(shù) 1.設置偏差變量l偏差變量：表明實際值同目標值之間的差異l偏差變量用下列符號表示：ld+超出目標的差值，正偏差變量ld-未達到目標的差值，負偏差變量ld+與d-兩者中必有一個為零。l當實際值超出目標值時，有d-=0，d+0；l當實際值未達到目標值時，有d+=0，d-0；l當實際值同目標值恰好一致時，d+=d-=0，故恒有d+d-=0。 2.統(tǒng)一處理目標和約束-1l只對資源使用上有嚴格限制的建立系統(tǒng)約系統(tǒng)約束束，數(shù)學形式上為嚴格的等式或不等式，同線性規(guī)劃中的約束條件；如：）嚴格

6、限制超過資源）嚴格限制超過資源12hD( 12416hC( 16421xx2.統(tǒng)一處理目標和約束-2l對不嚴格限定的約束，連同原線性規(guī)劃建模時的目標，均通過目標約束目標約束來表達。l目標約束是一種將約束同目標結(jié)合在一起的表達式。l例如要求、兩種產(chǎn)品保持1:1的比例，當作一個約束，可以寫為： 1/21xx0 21 xx或系統(tǒng)約束系統(tǒng)約束/剛性約束剛性約束l由于對“要求要求、兩種產(chǎn)品保持兩種產(chǎn)品保持1:1的比的比例例”允許有偏差，當產(chǎn)品產(chǎn)量小于產(chǎn)品產(chǎn)量，有x1x2 ，即出現(xiàn)正偏差量d+，若將x1減去這個正偏差量有l(wèi)因正負偏差不可能同時出現(xiàn)，故總有21xdx0 21dxx或21xdx0 21dxx或

7、021ddxxl假如希望的產(chǎn)量不低于的產(chǎn)量，l即不希望 中d-0，用目標約束可表為：l假如希望的產(chǎn)量低于的產(chǎn)量，即不希望出現(xiàn)d+0，用目標約束可表為： 21xdx021ddxx 0min21ddxxd 0min21ddxxdl假如希望的產(chǎn)量恰好等于的產(chǎn)量，即不希望出現(xiàn)d-0，又不希望出現(xiàn)d+0，用目標約束可表為：0min21ddxxddl例1中力求使利潤指標不低于12元，可表達為 1232min21ddxxdl設備B必要時可以加班及加班時間要控制可表達為 82min21ddxxdl設備A既要求充分利用，又盡可能不加班可表達為 1222min21ddxxdd3.目標的優(yōu)先級與權系數(shù) l在一個目標

8、規(guī)劃的模型中，如果兩個不同目標重要程度相差懸殊，為達到某一目標可犧牲其它一些目標，稱這些目標是屬于不同層次的優(yōu)不同層次的優(yōu)先級先級。l優(yōu)先級層次的高低可分別通過優(yōu)先因子P1，P2，表示，并規(guī)定， 即不同優(yōu)先級之間的差別無法用數(shù)字大小衡量。l對屬于同一層次優(yōu)先級的不同目標，按其重要程度可分別乘上不同的權系數(shù)。l權系數(shù)是一個個具體數(shù)字，乘上的權系數(shù)越大，表明該目標越重要。 1kkPPl假定：l例中企業(yè)最重要目標是利潤，列為第一優(yōu)先級；l其次目標是、產(chǎn)品的產(chǎn)量盡可能保持1：1的比例，列為第二優(yōu)先級；l再次是設備A、B盡量不超負荷工作，列為第三優(yōu)先級。l在第三優(yōu)先級中，設備A的重要性比設備B大三倍，因

9、此目標函數(shù)中在設備A的偏差變量前冠以權系數(shù)3。l這樣對各目標約束中的正負偏差變量按序編號后，上述問題的目標規(guī)劃模型可以寫為： 由于目標函數(shù)中劃分優(yōu)先級并有權系數(shù)大小，使企業(yè)可根據(jù)外界條件變化，通過調(diào)整目標優(yōu)先級和權系數(shù)，求出不同方案以供選擇。 2132maxxxz0,12416482122221212121xxxxxxxx目標規(guī)劃比起線性規(guī)劃來適應面要靈活得多。目標規(guī)劃適用于多個目標并且還可以帶有從屬目標的規(guī)劃問題，而且目標的計量單位可以多種多樣。目標規(guī)劃中約束的柔性，給決策方案的選擇帶來很大的靈活性。 4333322211)(3)(mindPddPddPdPz)4, 1(0,82122201

10、23212416421442133212221112121iddxxddxxddxxddxxddxxxxii、的產(chǎn)量盡可的產(chǎn)量盡可能保持能保持1：1的比例的比例設備設備A的重要性的重要性比設備比設備B大三倍大三倍A既要求充分利用既要求充分利用又盡可能不加班又盡可能不加班利潤目標利潤目標B必要時可以加班必要時可以加班及加班時間要控制及加班時間要控制目標規(guī)劃的一般數(shù)學模型 (5.2a) )(min11KkLllkllklkdwdwPz(5.2e), 1(0,(5.2d), 1(5.2c), 1(;(5.2b), 1(),(1)(1Llddnj0 xLlgddxcmibxalljnjllljlinj

11、jijPk：第k級優(yōu)先因子，k=1，K；wkl-，wkl+：分別賦予第l個目標約束的正負偏差變量的權系數(shù)；gl：第l個目標的預期目標值，l=1，L。(5.2c)為目標約束，(5.2b)為系統(tǒng)約束。 目標規(guī)劃來解決問題時的難點l構造模型時需事先擬定目標值、優(yōu)先級和權系數(shù)。而這些信息來自人的主觀判斷，往往帶有模糊性，很難定出一個絕對的數(shù)值。目標規(guī)劃求解問題過程 明確問題，列出（或修改）目標的優(yōu)先級和權系數(shù)構造目標規(guī)劃的數(shù)學模型求出滿意解分析各項目標完成情況滿意？據(jù)此制定出決策方案YN目標規(guī)劃的圖解分析法 l第一步：先以x1、x2為軸，畫出平面直角坐標系，在確定坐標的長度單位后，將代表各目標約束的直

12、線方程分別標示在坐標平面內(nèi)。)4, 1(0,(6) 82(5) 1222(4) 0(3) 1232(2) 124(1) 16421442133212221112121iddxxddxxddxxddxxddxxxxii4333322211)(3)(mindPddPddPdPz約束條件 是系統(tǒng)約束，因此只有在四邊形OABC范圍內(nèi)的點才滿足要求。 12416421xx第二步：按目標的優(yōu)先級別依次分析。l圖中直線代表2xl+3x2=12。直線上的所有點有l(wèi)dl-=d1+=0，l其左下方點滿足2xl+3x20，l直線右上方的點有2xl+3x212，故d1+0。l目標函數(shù)中的優(yōu)先因子Pl要求d1-=0，l

13、故應取直線右上方的點，使問題解的范圍縮小為BED。 4333322211)(3)(mindPddPddPdPzl優(yōu)先因子P2對應的是偏差變量d2-、d2+，由于要求有d2+=d2-=0，使問題解的范圍又縮減為線段FG。 G4333322211)(3)(mindPddPddPdPzGl對優(yōu)先因子P3，考慮d3+d3-=0時應選F點，l考慮d4+= 0時應選線段GH。l由于(d3+d3-)的權系數(shù)3倍于d4+，故取F點。lF點是直線的交點，故可求解聯(lián)立方程l得問題的滿意解為x1=3，x2=3。這時企業(yè)的利潤值為15元。)5( 1222(4) 02121xxxx4333322211)(3)(mind

14、PddPddPdPz例2l假定上例中各有關數(shù)據(jù)不變，但根據(jù)外界條件變化，企業(yè)重新調(diào)整經(jīng)營目標的優(yōu)先級次序和有關的權系數(shù)如下：l第一，產(chǎn)品 、的產(chǎn)量應盡量滿足4：3；l第二，利潤額不低于12元；l第三，設備A充分利用并不超負荷，設備B允許加班，但又盡量少加班，但權系數(shù)改為設備A為1，設備B為3。l問：如何安排生產(chǎn)計劃？ 該問題目標規(guī)劃數(shù)學模型43333122213)()(mindPddPdPddPz)4, 1(0,821222043123212416421442133212221112121iddxxddxxddxxddxxddxxxxii產(chǎn)品產(chǎn)品I、的產(chǎn)量應盡量滿足的產(chǎn)量應盡量滿足4：3利潤額

15、不低于利潤額不低于12元元設備設備A充分利用并不超負荷充分利用并不超負荷設備設備B允許加班，但又盡量少加班允許加班，但又盡量少加班43333122213)()(mindPddPdPddPz 圖解)4, 1(0,821222043123212416421442133212221112121iddxxddxxddxxddxxddxxxxii由于設備B權系數(shù)比A大，又考慮利潤盡可能大，取M點。M點坐標為x1=16/5，x2=12/5，這時企業(yè)的利潤值為68/5元。 考慮系統(tǒng)約束，解的范圍為四邊形O ABC?？紤]優(yōu)先級P1，使解的范圍縮減為線段O B。再考慮優(yōu)先級P2，解的范圍進一步縮減為線段KB。最

16、后考慮優(yōu)先級P3，如果滿足設備A要求，使d3+d3-=0，應取L點；如果滿足設備B要求，使d4+=0，應取KM段。目標規(guī)劃應用舉例l生產(chǎn)計劃l財務分析l市場研究l行政教育l人力和資源分配 等l比較線性規(guī)劃來的優(yōu)點優(yōu)點：更靈活，并適用于多目標問題的優(yōu)化；l不足不足：是優(yōu)先級的層次統(tǒng)治關系過于絕對化、軟件的開發(fā)相對滯后。應用舉例1l某電子廠生產(chǎn)錄音機和電視機兩種產(chǎn)品，分別經(jīng)由甲、乙兩個車間生產(chǎn)。已知除外購件外，生產(chǎn)一臺錄音機需甲車間加工2h，乙車間裝配1h；生產(chǎn)一臺電視機需甲車間加工1h，乙車間裝配3h。這兩種產(chǎn)品生產(chǎn)出來后均需經(jīng)檢驗、銷售等環(huán)節(jié)。已知每臺錄音機檢驗銷售費用需50元，每臺電視機檢驗

17、銷售費用需30元。又甲車間每月可用的生產(chǎn)工時為120h，車間管理費用為80元/h；乙車間每月可用的生產(chǎn)工時為150h，車間管理費用為20元/h。估計每臺錄音機利潤為100元，每臺電視機利潤為75元，又估計下年度內(nèi)平均每月可銷售錄音機50臺，電視機80臺。 加工時間（小時）車間管理費(元/月)檢驗銷售費用利潤(元/)臺銷量(臺/月)甲車間 乙車間 甲車間 乙車間錄音機2180元/h20元/h5010050電視機13307580總量/月120150l工廠確定制訂月度計劃的目標如下：l第一優(yōu)先級：檢驗和銷售費每月不超過4600元l第二優(yōu)先級：每月售出錄音機不少于50臺l第三優(yōu)先級：甲、乙兩車間的生產(chǎn)

18、工時得到充分利用(重要性權系數(shù)按兩個車間每小時費用的比例確定)l第四優(yōu)先級：甲車間加班不超過20小時l第五優(yōu)先級：每月銷售電視機不少于80臺l第六優(yōu)先級：兩個車間加班總時間要有控制(權系數(shù)分配與第三優(yōu)先級相同) l試確定該廠為達到以上目標的最優(yōu)月度計劃生產(chǎn)數(shù)字。 解題：解題：設x1為每月生產(chǎn)錄音機的臺數(shù)，x2為每月生產(chǎn)電視機的臺數(shù)。有約束情況如下(1)甲、乙車間可用工時約束 )(1503)(120222211121乙車間甲車間ddxxddxx(2)檢驗和銷售費用的限制 460030503321ddxx(3)每月銷售量要求 )(80)(50552441電視機錄音機ddxddx(4)對甲車間加班的

19、限制 20661ddd考慮甲、乙車間管理費用分別為80元/h和20元/h，其權重比為4:l。可得目標規(guī)劃模型為：)4()4(min21655642134231ddPdPdPddPdPdPz)6, 1(0,208050460030501503120221661552441332122211121iddxxdddddxddxddxxddxxddxxii甲車間可用工時約束甲車間可用工時約束乙車間可用工時約束乙車間可用工時約束檢驗和銷售費用的限制檢驗和銷售費用的限制錄音機每月銷售量要求錄音機每月銷售量要求電視機每月銷售量要求電視機每月銷售量要求甲車間加班的限制甲車間加班的限制檢驗和銷售檢驗和銷售費每月

20、不超費每月不超過過4600元元每月售出錄音每月售出錄音機不少于機不少于50臺臺兩車間的生產(chǎn)工兩車間的生產(chǎn)工時得到充分利用時得到充分利用甲車間加班不超過甲車間加班不超過20小時小時每月銷售電視每月銷售電視機不少于機不少于80臺臺兩個車間加班總兩個車間加班總時間要有控制時間要有控制最優(yōu)解501x402x201d202d9003d405d066544321dddddddd 每月生產(chǎn)50臺錄音機每月生產(chǎn)40臺電視機甲車間每月加班20小時乙車間每月加班20小時甲乙兩車間每月檢驗銷售費用4600-900=3500元每月銷售電視機離目標80臺還差40臺每月生產(chǎn)錄音機每月生產(chǎn)錄音機50臺，電視機臺，電視機40

21、臺，利潤額可達臺，利潤額可達8000元。元。 兩車間的生產(chǎn)工兩車間的生產(chǎn)工時得到充分利用時得到充分利用每月檢驗銷每月檢驗銷售費無超出售費無超出每月剛好完成錄每月剛好完成錄音機銷售任務音機銷售任務每月未超額完成每月未超額完成電視機銷售任務電視機銷售任務每月甲車間加班每月甲車間加班未超過限制的未超過限制的20h應用舉例2l已知三個工廠生產(chǎn)的產(chǎn)品供應四個用戶需要，各工廠生產(chǎn)量、用戶需求量及從各工廠到用戶的單位產(chǎn)品的運輸費用如表所示 工廠工廠用戶用戶1234生產(chǎn)量生產(chǎn)量152673002354620034523400需求量需求量200100450250l用表上作業(yè)法求得最優(yōu)調(diào)配方案如下表，總運費為29

22、50元。l但上述方案只考慮了運費為最少，沒有考慮到很多具體情況和條件。 工廠 用戶1234生產(chǎn)量1200100300202003003250150400虛設100100需求量200100450250故上級部門研究后確定了制訂調(diào)配方案時要考慮的七項目標，并規(guī)定重要性次序為 ：l第一目標：第4用戶為重要部門，需要量必須全部滿足 l第二目標：供應用戶1的產(chǎn)品中，工廠3的產(chǎn)品不少于100單位l第三目標：為兼顧一般，每個用戶滿足率不低于80l第四目標：新方案總運費不超過原方案的10l第五目標：因道路限制，從工廠2到用戶4的路線應盡量避免分配運輸任務l第六目標：用戶1和用戶3的滿足率應盡量保持平衡l第七目

23、標：力求減少總運費解題l設xij為i工廠調(diào)配給j用戶的數(shù)量(1)供需約束 供應約束供應約束 需求約束需求約束 400200300343332312423222114131211xxxxxxxxxxxx2504501002004342414333231323222121312111dxxxdxxxdxxxdxxx(2)用戶1需要量中工廠3的產(chǎn)品不少于100單位1005531ddx(3)各用戶滿足率不低于80 2003608016099342414883323137732221266312111ddxxxddxxxddxxxddxxx200100450250(4)運費上限制(原方案總運費為2950

24、元) 324510103141ddxcijijij2950 x1.1(5)道路通過的限制(工廠2到用戶4盡量避免分配運輸任務)01124dx(6)用戶1和用戶3的滿足率保持平衡 0)(450200)(1212332313312111ddxxxxxx(7)力求減少總的運費2950133141dxcijijij目標函數(shù)為 13712126115104987635241dP )dd(P dP dP )dddd(P dP dP min Z第第4用戶需要量必須全部滿足用戶需要量必須全部滿足工廠工廠3供應用戶供應用戶1的產(chǎn)品不少于的產(chǎn)品不少于100單位單位每個用戶滿足率不低于每個用戶滿足率不低于80新方案總運費不超過原方案的新方案總運費不超過原方案的10工廠工廠2到用戶到用戶4盡量避免分配運輸任務盡量避免分配運輸任務用戶用戶1和用戶和用戶3的滿足率應盡量保持平衡的滿足率應盡量保持平衡力求減少總運費力求減少總運費計算結(jié)果為： 0,200,50,250,110,100,100,9014343323123121ijxxxxxxxx其