管理運籌學目標規(guī)劃.ppt

1,第九章 目標規(guī)劃,1 目標規(guī)劃問題舉例 2 目標規(guī)劃的圖解法 3 復雜情況下的目標規(guī)劃 4 加權目標規(guī)劃 5 目標規(guī)劃的單純型法,2,1 目標規(guī)劃問題舉例,線性規(guī)劃模型的特征是在滿足一組約束條件下，尋求一個目標的最優(yōu)解（最大值或最小值）。 而在現(xiàn)實生活中最優(yōu)只是相對的，或者說沒有絕對意義下的最優(yōu)，只有相對意義下的滿意。 1978年諾貝爾經(jīng)濟學獎獲得者.西蒙(H.A.Simon-美國卡內(nèi)基-梅隆大學,1916-)教授提出“滿意行為模型要比最大化行為模型豐富得多”，否定了企業(yè)的決策者是“經(jīng)濟人”概念和“最大化”行為準則，提出了“管理人”的概念和“令人滿意”的行為準則，對現(xiàn)代企業(yè)管理的決策科學進行了開創(chuàng)性的研究,3,1 目標規(guī)劃問題舉例,例1企業(yè)生產(chǎn) 不同企業(yè)的生產(chǎn)目標是不同的。多數(shù)企業(yè)追求最大的經(jīng)濟效益。但隨著環(huán)境問題的日益突出，可持續(xù)發(fā)展已經(jīng)成為全社會所必須考慮的問題。因此，企業(yè)生產(chǎn)就不能再如以往那樣只考慮企業(yè)利潤，必須承擔起社會責任，要考慮環(huán)境污染、社會效益、公眾形象等多個方面。兼顧好這幾者關系，企業(yè)才可能保持長期的發(fā)展。 例2商務活動 企業(yè)在進行盈虧平衡預算時，不能只集中在一種產(chǎn)品上，因為某一種產(chǎn)品的投入和產(chǎn)出僅僅是企業(yè)所有投入和產(chǎn)出的一部分。因此，需要用多產(chǎn)品的盈虧分析來解決具有多個盈虧平衡點的決策問題（多產(chǎn)品的盈虧平衡點往往是不一致的）。,4,1 目標規(guī)劃問題舉例,例3投資 企業(yè)投資時不僅僅要考慮收益率，還要考慮風險。一般地，風險大的投資其收益率更高。因此，企業(yè)管理者只有在對收益率和風險承受水平有明確的期望值時，才能得到滿意的決策。 例4裁員 同樣的，企業(yè)裁員時要考慮很多可能彼此矛盾的因素。裁員的首要目的是壓縮人員開支，但在人人自危的同時員工的忠誠度就很難保證，此外，員工的心理壓力、工作壓力等都會增加，可能產(chǎn)生負面影響。 例5營銷 營銷方案的策劃和執(zhí)行存在多個目標。既希望能達到立竿見影的效果，又希望營銷的成本控制在某一個范圍內(nèi)。此外，營銷活動的深入程度也決定了營銷效果的好壞和持續(xù)時間。,5,1 目標規(guī)劃問題舉例,【例1.】考慮例1.1資源消耗如表9-1所示。x1、x2、x3分別為甲、乙、丙的產(chǎn)量。,使企業(yè)在計劃期內(nèi)總利潤最大的線性規(guī)劃模型為：,表9-1,1.1 引例,6,1 目標規(guī)劃問題舉例,最優(yōu)解X（50，30，10），Z3400,7,1 目標規(guī)劃問題舉例,現(xiàn)在決策者根據(jù)企業(yè)的實際情況和市場需求，需要重新制定經(jīng)營目標，其目標的優(yōu)先順序是： （1）利潤不少于3200元 （2）產(chǎn)品甲與產(chǎn)品乙的產(chǎn)量比例盡量不超過1.5 （3）提高產(chǎn)品丙的產(chǎn)量使之達到30件 （4）設備加工能力不足可以加班解決，能不加班最好不加班 （5）受到資金的限制，只能使用現(xiàn)有材料不能再購進,【解】 設甲、乙、丙產(chǎn)品的產(chǎn)量分別為x1、x2、x3。如果按線性規(guī)劃建模思路，最優(yōu)解實質(zhì)是求下列一組不等式的解,8,1 目標規(guī)劃問題舉例,通過計算不等式無解，即使設備加班10小時仍然無解在實際生產(chǎn)過程中生產(chǎn)方案總是存在的，無解只能說明在現(xiàn)有資源條件下，不可能完全滿足所有經(jīng)營目標,這種情形是按事先制定的目標順序逐項檢查，盡可能使得結果達到預定目標，即使不能達到目標也使得離目標的差距最小，這就是目標規(guī)劃的求解思路，對應的解稱為滿意解下面建立例1.1的目標規(guī)劃數(shù)學模型,9,1 目標規(guī)劃問題舉例,設d為未達到目標值的差值，稱為負偏差變量（negative deviation variable） d+為超過目標值的差值，稱為正偏差變量（positive deviation variable）, d0、d0,設d1-未達到利潤目標的差值, d1+ 為超過目標的差值,當利潤小于3200時,d1且d10,有 40x1+30x2+50x3+d1=3200成立 當利潤大于3200時，d1且d1，有 40x1+30x2+50x3-d1+=3200成立 當利潤恰好等于3200時，d1=且d1+=0,有 40x1+30x2+50x3=3200成立 實際利潤只有上述三種情形之一發(fā)生，因而可以將三個等式寫成一個等式,40x1+30x2+50x3+d1d1+=3200,10,1 目標規(guī)劃問題舉例,（2）設 分別為未達到和超過產(chǎn)品比例要求的偏差變量,則產(chǎn)量比例盡 量不超過1.5的數(shù)學表達式為：,（3）設d3、d分別為品丙的產(chǎn)量未達到和超過30件的偏差變量，則產(chǎn)量丙的產(chǎn)量盡可能達到30件的數(shù)學表達式為：,利潤不少于3200理解為達到或超過3200，即使不能達到也要盡可能接近3200,可以表達成目標函數(shù)d1取最小值，則有,11,1 目標規(guī)劃問題舉例,（4） 設d4 、d4+為設備A的使用時間偏差變量, d5、d5+為設備B的使用時間偏差變量，最好不加班的含義是 d4+ 和d5+同時取最小值，等價 于d4+ + d5+取最小值，則設備的目標函數(shù)和約束為：,（5）材料不能購進表示不允許有正偏差，約束條件為小于等于約束,由于目標是有序的并且四個目標函數(shù)非負，因此目標函數(shù)可以表達成一個函數(shù)：,12,1 目標規(guī)劃問題舉例,式中：Pj（j=1,2,3,4）稱為目標的優(yōu)先因子，第一目標優(yōu)于第二目標，第二目標優(yōu)于第三目標等等，其含義是按P1、P2、的次序分別求后面函數(shù)的最小值.則問題的目標規(guī)劃數(shù)學模型為：,13,2 目標規(guī)劃的圖解法,例6一位投資商有一筆資金準備購買股票。資金總額為90000元，目前可選的股票有A和B兩種（可以同時投資于兩種股票）。其價格以及年收益率和風險系數(shù)如表1： 從上表可知，A股票的收益率為（320）10015，股票B的收益率為4501008，A的收益率比B大，但同時A的風險也比B大。這也符合高風險高收益的規(guī)律。 試求一種投資方案，使得一年的總投資風險不高于700，且投資收益不低于10000元。用來全部投資一個股票兩個目標不能同時達到.,14,2 目標規(guī)劃的圖解法,顯然，此問題屬于目標規(guī)劃問題。它有兩個目標變量：一是限制風險，一是確保收益。在求解之前，應首先考慮兩個目標的優(yōu)先權。 假設第一個目標（即限制風險）的優(yōu)先權比第二個目標（確保收益）大，這意味著求解過程中必須首先滿足第一個目標，然后在此基礎上再盡量滿足第二個目標。 建立模型： 設x1、x2分別表示投資商所購買的A股票和B股票的數(shù)量。 首先考慮資金總額的約束：總投資額不能高于90000元。即 20x150x290000。,15,2 目標規(guī)劃的圖解法,一、約束條件 再來考慮風險約束：總風險不能超過700。投資的總風險為 0.5x10.2x2。引入兩個變量d1+和d1-,建立等式如下： 0.5x1 +0.2x2=700+d1+-d1- 其中，d1+表示總風險高于700的部分，d1-表示總風險少于700的 部分，d1+0。 目標規(guī)劃中把d1+、d1-這樣的變量稱為偏差變量。偏差變量的作 用是允許約束條件不被精確滿足。,16,2 目標規(guī)劃的圖解法,把等式轉換，可得到 0.5x1 +0.2x2-d1+d1-=700。 再來考慮年收入: 年收入=3x1+4x2 引入變量d2+和d2-，分別表示年收入超過與低于10000的數(shù)量。 于是，第2個目標可以表示為 3x1+4x2-d2+d2-=10000。,17,2 目標規(guī)劃的圖解法,二、有優(yōu)先權的目標函數(shù) 本問題中第一個目標的優(yōu)先權比第二個目標大。即最重要的目標是滿足風險不超過700。分配給第一個目標較高的優(yōu)先權P1,分配給第二個目標較低的優(yōu)先權P2。 針對每一個優(yōu)先權，應當建立一個單一目標的線性規(guī)劃模型。首先建立具有最高優(yōu)先權的目標的線性規(guī)劃模型，求解；然后再按照優(yōu)先權逐漸降低的順序分別建立單一目標的線性規(guī)劃模型，方法是在原來模型的基礎上修改目標函數(shù)，并把原來模型求解所得的目標最優(yōu)值作為一個新的約束條件加入到當前模型中，并求解。,18,2 目標規(guī)劃的數(shù)學模型,（1）目標規(guī)劃數(shù)學模型的形式有：線性模型、非線性模型、整數(shù)模型、交互作用模型等 （2）一個目標中的兩個偏差變量di-、 di+至少一個等于零，偏差變量向量的叉積等于零：dd=0,（3）一般目標規(guī)劃是將多個目標函數(shù)寫成一個由偏差變量構成的函數(shù)求最小值，按多個目標的重要性，確定優(yōu)先等級，順序求最小值,（4）按決策者的意愿，事先給定所要達到的目標值 當期望結果不超過目標值時，目標函數(shù)求正偏差變量最小; 當期望結果不低于目標值時，目標函數(shù)求負偏差變量最小; 當期望結果恰好等于目標值時，目標函數(shù)求正負偏差變量之和最小,9.2 數(shù)學模型,19,2 目標規(guī)劃的數(shù)學模型,（5）由目標構成的約束稱為目標約束，目標約束具有更大的彈性，允許結果與所制定的目標值存在正或負的偏差，如例1.1中的5個等式約束；如果決策者要求結果一定不能有正或負的偏差，這種約束稱為系統(tǒng)約束，如例1.1的材料約束；,（6）目標的排序問題。多個目標之間有相互沖突時，決策者首先必須對目標排序。排序的方法有兩兩比較法、專家評分等方法，構造各目標的權系數(shù)，依據(jù)權系數(shù)的大小確定目標順序；,（7）合理的確定目標數(shù)。目標規(guī)劃的目標函數(shù)中包含了多個目標，決策者對于具有相同重要性的目標可以合并為一個目標，如果同一目標中還想分出先后次序，可以賦予不同的權系數(shù)，按系數(shù)大小再排序。例如，在例1.1中要求設備B的加班時間不超過設備A的時間，目標函數(shù)可以表達為 ,表示在 中先求 最小再求 最小。,20,2 目標規(guī)劃的數(shù)學模型,（8）目標規(guī)劃的一般模型設xj（j=1,2,n）為決策變量,式中p k 為第k 級優(yōu)先因子, k=1 、2、 K；wkl- 、wkl+，為分別賦予第l個目標約束的正負偏差變量的權系數(shù)；gl為目標的預期目標值，l=1,L (4.1b)為系統(tǒng)約束,（4.1c）為目標約束,21,2 目標規(guī)劃的數(shù)學模型,【例1.2】某企業(yè)集團計劃用1000萬元對下屬5個企業(yè)進行技術改造，各企業(yè)單位的投資額已知，考慮2種市場需求變化、現(xiàn)有競爭對手、替代品的威脅等影響收益的4個因素，技術改造完成后預測單位投資收益率(（單位投資獲得利潤/單位投資額）100)如表12所示,集團制定的目標是： （1）希望完成總投資額又不超過預算； （2）總期望收益率達到總投資的30%； （3）投資風險盡可能最小； （4）保證企業(yè)5的投資額占20%左右 集團應如何作出投資決策,22,2 目標規(guī)劃的數(shù)學模型,表12,23,2 目標規(guī)劃的數(shù)學模型,【解】設xj（j=1,2,5）為集團對第 j 個企業(yè)投資的單位數(shù),（1）總投資約束：,（2）期望利潤率約束：,整理得,24,2 目標規(guī)劃的數(shù)學模型,(3）投資風險約束投資風險值的大小一般用期望收益率的方差表示，但方差是x的非線性函數(shù)這里用離差（rijE(rj)）近似表示風險值，例如，集團投資5個企業(yè)后對于市場需求變化第一情形的風險是： 則4種因素風險最小的目標函數(shù)為： ，約束條件為,25,2 目標規(guī)劃的數(shù)學模型,根據(jù)目標重要性依次寫出目標函數(shù)，整理后得到投資決策的目標規(guī)劃數(shù)學模型：,26,2 目標規(guī)劃的數(shù)學模型,【例1.3】車間計劃生產(chǎn)I、II 兩種產(chǎn)品，每種產(chǎn)品均需經(jīng)過A、B兩道工序加工工藝資料如表43所示,（1）車間如何安排生產(chǎn)計劃，使產(chǎn)值和利潤都盡可能高 （2）如果認為利潤比產(chǎn)值重要，怎樣決策,表13,27,2 目標規(guī)劃的數(shù)學模型,【解】設x1、x2分別為產(chǎn)品甲和產(chǎn)品乙的日產(chǎn)量，得到線性多目標規(guī)劃模型：,28,2 目標規(guī)劃的數(shù)學模型,（1）將模型化為目標規(guī)劃問題首先，通過分別求產(chǎn)值最大和利潤最大的線性規(guī)劃最優(yōu)解 產(chǎn)值最大的最優(yōu)解：X(1)（20，40），Z13800 利潤最大的最優(yōu)解：X (2) （30，30），Z2540 目標確定為產(chǎn)值和利潤盡可能達到3800和540，得到目標規(guī)劃數(shù)學模型：,29,2 目標規(guī)劃的圖解法,三、圖解法 1針對優(yōu)先權最高的目標建立線性規(guī)劃 建立線性規(guī)劃模型如下： Min d1+ s.t. 20x150x290000 0.5x1 +0.2x2-d1+d1-=700 3x1+4x2-d2+d2-=10000 x1,x2,d1+,d1-0,30,2 目標規(guī)劃的圖解法,31,2 目標規(guī)劃的圖解法,2針對優(yōu)先權次高的目標建立線性規(guī)劃 優(yōu)先權次高（P2）的目標是總收益超過10000。 建立線性規(guī)劃如下： Min d2- s.t. 20x150x290000 0.5x1 +0.2x2-d1+d1-=700 3x1+4x2-d2+d2-=10000 d1+0 x1,x2,d1+,d1-,d2+,d2-0,32,2 目標規(guī)劃的圖解法,33,2 目標規(guī)劃的圖解法,目標規(guī)劃的這種求解方法可以表述如下： 1確定解的可行區(qū)域。 2對優(yōu)先權最高的目標求解，如果找不到能滿足該目標的解，則尋找最接近該目標的解。 3對優(yōu)先權次之的目標進行求解。注意：必須保證優(yōu)先權高的目標不變。 4. 重復第3步，直至所有優(yōu)先權的目標求解完。,34,2 目標規(guī)劃的圖解法,四、目標規(guī)劃模型的標準化 例6中對兩個不同優(yōu)先權的目標單獨建立線性規(guī)劃進行求解。為簡 便，把它們用一個模型來表達，如下： Min P1（d1+）+P2（d2-） s.t. 20x150x290000 0.5x1 +0.2x2-d1+d1-=700 3x1+4x2-d2+d2-=10000 x1,x2,d1+,d1-,d2+,d2-0,35,2 目標規(guī)劃的圖解法,【例】企業(yè)計劃生產(chǎn)I 、 II 兩種產(chǎn)品，這些產(chǎn)品需要使用兩種材料，要在兩種不同設備上加工工藝資料如表44所示,表44,36,2 目標規(guī)劃的圖解法,【解】設x1、x2分別為產(chǎn)品甲和產(chǎn)品乙的產(chǎn)量，目標規(guī)劃數(shù)學模型為：,企業(yè)怎樣安排生產(chǎn)計劃，盡可能滿足下列目標： (1)力求使利潤指標不低于80元 (2)考慮到市場需求,、II兩種產(chǎn)品的生產(chǎn)量需保持1:1的比例 (3)設備A既要求充分利用，又盡可能不加班 (4) 設備B必要時可以加班，但加班時間盡可能少 (5)材料不能超用。,37,(2),(1),(3),(4 ),x2,x1,(6),(5),o,4,6,4,6,2,2,圖41,A,B,C,滿意解C(3,3),滿意解X(3,3),38,2 目標規(guī)劃的圖解法,(3),x1,x2,20,40,60,80,100,20,40,60,80,100,(2),(1),(4),B,C,滿意解是線段 上任意點，端點的解是 B(100/3，80/3)，C(60，0) 決策者根據(jù)實際情形進行二次選擇,A,39,2 目標規(guī)劃的圖解法,(3),x1,x2,20,40,60,80,100,20,40,60,80,100,(2),(1),(4),圖53,B,C,滿意解是點 B，X=(100/3，80/3),A,40,(3),x1,x2,20,40,60,80,100,20,40,60,80,100,(2),(1),(4),滿意解是點 A，X=(20，40),A(20,40),D(80/9,560/9),注：線段DA是第二目標函數(shù)的組合， 點A對應的偏差：d2-=100, d3=0 點D對應的偏差： d2-=0, 2d3=2200/9=400/9,41,3 復雜情況下的目標規(guī)劃,例7一工藝品廠商手工生產(chǎn)某兩種工藝品A、B，已知生產(chǎn)一件產(chǎn)品A需要耗費人力2工時，生產(chǎn)一件產(chǎn)品B需要耗費人力3工時。A、B產(chǎn)品的單位利潤分別為250元和125元。為了最大效率地利用人力資源，確定生產(chǎn)的首要任務是保證人員高負荷生產(chǎn)，要求每周總耗費人力資源不能低于600工時，但也不能超過680工時的極限；次要任務是要求每周的利潤超過70000元；在前兩個任務的前提下，為了保證庫存需要，要求每周產(chǎn)品A和B的產(chǎn)量分別不低于200和120件，因為B產(chǎn)品比A產(chǎn)品更重要，不妨假設B完成最低產(chǎn)量120件的重要性是A完成200件的重要性的1倍。 試求如何安排生產(chǎn)？,42,3 復雜情況下的目標規(guī)劃,解： 本問題中有3個不同優(yōu)先權的目標，不妨用P1、P2、P3表示從高至低的優(yōu)先權。 對應P1有兩個目標：每周總耗費人力資源不能低于600工時,也不能超過680工時； 對應P2有一個目標：每周的利潤超過70000元； 對應P3有兩個目標：每周產(chǎn)品A和B的產(chǎn)量分別不低于200和120件。,43,3 復雜情況下的目標規(guī)劃,采用簡化模式，最終得到目標線性規(guī)劃如下： Min P1(d1+)+ P1(d2)+P2(d3-)+ P3(d4-)+ P3(2d5-) s.t. 2x1+3x2-d1+d1-=680 對應第1個目標 2x1+3x2-d2+d2-=600 對應第2個目標 250x1+125x2-d3-+d3+70000 對應第3個目標 x1-d4+d4-=200 對應第4個目標 x2-d5+d5-=120 對應第5個目標 x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-0,44,3 復雜情況下的目標規(guī)劃,使用運籌學軟件求解可得： x1=250；x2=60；d1+=0；d1-=0；d2+=80；d2-=0；d3+=0；d3-=0； d4+=50；d4-=0；d5+=0；d5-=60，目標函數(shù)d4-+2d5- =120。 可見，目標1、目標3和目標4達到了，但目標2、目標5都有一些偏差。,45,4 加權目標規(guī)劃,加權目標規(guī)劃是另一種解決多目標決策問題的方法，其基本方法是通過量化的方法分配給每個目標的偏離的嚴重程度一個罰數(shù)權重，然后建立總的目標函數(shù)，該目標函數(shù)表示的目標是要使每個目標函數(shù)與各自目標的加權偏差之和最小，假設所有單個的目標函數(shù)及約束條件都符合線性規(guī)劃的要求，那么，整個問題都可以描述為一個線性規(guī)劃的問題。 如果在例7中我們對每周總耗費的人力資源超過680工時或低于600工時的每工時罰數(shù)權重定為7；每周利潤低于70000元時，每元的罰數(shù)權重為5；每周產(chǎn)品A產(chǎn)量低于200件時每件罰數(shù)權重為2，而每周產(chǎn)品B產(chǎn)量低于120件時每件罰數(shù)權重為4。,46,4 加權目標規(guī)劃,則其目標函數(shù)化為： min7d1+7d2-+5d3-+2d4-+4d5- 這就變成了一個普通的單一目標的線性規(guī)劃問題 min7d1+7d2-+5d3-+2d4-+4d5- s.t. 2x1+3x2-d1+d1