1、,運籌學基礎及應用 ( Operations Research ),主講：楊啟明,第5章 目標規(guī)劃,目標規(guī)劃問題及其數(shù)學模型,例5.1 某企業(yè)計劃生產甲，乙兩種產品，這些產品分別要在A,B,C,D四種不同設備上加工。按工藝文件規(guī)定，如表所示。,問該企業(yè)應如何安排計劃，使得計劃期內的總利潤收入為最大？,解：設甲、乙產品的產量分別為x1，x2，建立線性規(guī)劃模型：,其最優(yōu)解為x14，x22，z14元,但企業(yè)的經營目標不僅僅是利潤，而且要考慮多個方面，如： 力求使利潤指標不低于12元； 考慮到市場需求，甲、乙兩種產品的生產量需保持1:1的比例； C和D為貴重設備，嚴格禁止超時使用； 設備B必要時可以加

2、班，但加班時間要控制；設備A即要求充分利用，又盡可能不加班。,要考慮上述多方面的目標，需要借助目標規(guī)劃的方法。,線性規(guī)劃模型存在的局限性： 1）要求問題的解必須滿足全部約束條件，實際問題中并非所有約束都需要嚴格滿足。 2）只能處理單目標的優(yōu)化問題。實際問題中，目標和約束可以相互轉化。 3）線性規(guī)劃中各個約束條件都處于同等重要地位，但現(xiàn)實問題中，各目標的重要性即有層次上的差別，同一層次中又可以有權重上的區(qū)分。 4）線性規(guī)劃尋求最優(yōu)解，但很多實際問題中只需找出滿意解就可以。,目標規(guī)劃問題舉例,例1企業(yè)生產:不同企業(yè)的生產目標是不同的。多數(shù)企業(yè)追求最大的經濟效益。但隨著環(huán)境問題的日益突出，可持續(xù)發(fā)展

3、已經成為全社會所必須考慮的問題。因此，企業(yè)生產就不能再如以往那樣只考慮企業(yè)利潤，必須承擔起社會責任，要考慮環(huán)境污染、社會效益、公眾形象等多個方面。兼顧好這幾者關系，企業(yè)才可能保持長期的發(fā)展。 例2商務活動:企業(yè)在進行盈虧平衡預算時，不能只集中在一種產品上，因為某一種產品的投入和產出僅僅是企業(yè)所有投入和產出的一部分。因此，需要用多產品的盈虧分析來解決具有多個盈虧平衡點的決策問題（多產品的盈虧平衡點往往是不一致的）。,例3投資:企業(yè)投資時不僅僅要考慮收益率，還要考慮風險。一般地，風險大的投資其收益率更高。因此，企業(yè)管理者只有在對收益率和風險承受水平有明確的期望值時，才能得到滿意的決策。 例4裁員:

4、同樣的，企業(yè)裁員時要考慮很多可能彼此矛盾的因素。裁員的首要目的是壓縮人員開支，但在人人自危的同時員工的忠誠度就很難保證，此外，員工的心理壓力、工作壓力等都會增加，可能產生負面影響。 例5營銷:營銷方案的策劃和執(zhí)行存在多個目標。既希望能達到立竿見影的效果，又希望營銷的成本控制在某一個范圍內。此外，營銷活動的深入程度也決定了營銷效果的好壞和持續(xù)時間。,目標規(guī)劃問題及其數(shù)學模型,目標規(guī)劃怎樣解決上述線性規(guī)劃模型建模中的局限性？,1. 設置偏差變量，用來表明實際值同目標值之間的差異。,偏差變量用下列符號表示：,d+超出目標的偏差，稱正偏差變量 d-未達到目標的偏差，稱負偏差變量,正負偏差變量兩者必有一

5、個為0。 當實際值超出目標值時： d+0, d-=0; 當實際值未達到目標值時： d+=0, d-0; 當實際值同目標值恰好一致時： d+=0, d-=0; 故恒有d+d-=0,目標規(guī)劃問題及其數(shù)學模型,2. 統(tǒng)一處理目標和約束。,對有嚴格限制的資源使用建立系統(tǒng)約束，數(shù)學形式同線性規(guī)劃中的約束條件。如C和D設備的使用限制。,對不嚴格限制的約束，連同原線性規(guī)劃建模時的目標，均通過目標約束來表達。,1）例如要求甲、乙兩種產品保持1:1的比例，系統(tǒng)約束表達為： x1=x2。由于這個比例允許有偏差， 當x1x2時，出現(xiàn)正偏差d+，即： x1-d+ =x2或x1x2-d+ =0,目標規(guī)劃問題及其數(shù)學模型

6、,正負偏差不可能同時出現(xiàn)，故總有： x1x2+d-d+ =0,若希望甲的產量不低于乙的產量，即不希望d-0,用目標約束可表為:,若希望甲的產量低于乙的產量，即不希望d0,用目標約束可表為:,若希望甲的產量恰好等于乙的產量，即不希望d0,也不希望d-0用目標約束可表為:,目標規(guī)劃問題及其數(shù)學模型,3）設備B必要時可加班及加班時間要控制，目標約束表示為：,2）力求使利潤指標不低于12元，目標約束表示為：,4）設備A既要求充分利用，又盡可能不加班，目標約束表示為：,目標規(guī)劃問題及其數(shù)學模型,3. 目標的優(yōu)先級與權系數(shù),在一個目標規(guī)劃的模型中，為達到某一目標可犧牲其他一些目標，稱這些目標是屬于不同層次

7、的優(yōu)先級。優(yōu)先級層次的高低可分別通過優(yōu)先因子P1,P2,表示。對于同一層次優(yōu)先級的不同目標，按其重要程度可分別乘上不同的權系數(shù)。權系數(shù)是一個個具體數(shù)字，乘上的權系數(shù)越大，表明該目標越重要。,現(xiàn)假定：,第1優(yōu)先級P1企業(yè)利潤； 第2優(yōu)先級P2甲乙產品的產量保持1:1的比例 第3優(yōu)先級P3設備A,B盡量不超負荷工作。其中設備A的重要性比設備B大三倍。,目標規(guī)劃問題及其數(shù)學模型,上述目標規(guī)劃模型可以表示為：,目標規(guī)劃問題及其數(shù)學模型,目標規(guī)劃數(shù)學模型的一般形式,達成函數(shù),目標約束,其中：gk為第k個目標約束的預期目標值， 和 為pl 優(yōu)先因子對應各目標的權系數(shù)。,目標規(guī)劃問題及其數(shù)學模型,用目標規(guī)劃

8、求解問題的過程：,明確問題，列出目標的優(yōu)先級和權系數(shù),構造目標規(guī)劃模型,求出滿意解,滿意否？,分析各項目標完成情況,據(jù)此制定出決策方案,N,Y,目標規(guī)劃的圖解法,例6一位投資商有一筆資金準備購買股票。資金總額為90000元，目前可選的股票有A和B兩種（可以同時投資于兩種股票）。其價格以及年收益率和風險系數(shù)如表1： 從上表可知，A股票的收益率為（320）10015，股票B的收益率為4501008，A的收益率比B大，但同時A的風險也比B大。這也符合高風險高收益的規(guī)律。試求一種投資方案，使得一年的總投資風險不高于700，且投資收益不低于10000元。,目標規(guī)劃的圖解法,顯然，此問題屬于目標規(guī)劃問題。

9、它有兩個目標變量：一是限制風險，一 是確保收益。在求解之前，應首先考慮兩個目標的優(yōu)先權。假設第一個目 標（即限制風險）的優(yōu)先權比第二個目標（確保收益）大，這意味著求解 過程中必須首先滿足第一個目標，然后在此基礎上再盡量滿足第二個目 標。 建立模型： 設x1、x2分別表示投資商所購買的A股票和B股票的數(shù)量。 首先考慮資金總額的約束：總投資額不能高于90000元。即 20 x150 x290000。,目標規(guī)劃的圖解法,約束條件 再來考慮風險約束：總風險不能超過700。投資的總風險為 0.5x10.2x2。引入兩個變量d1+和d1-,建立等式如下： 0.5x1 +0.2x2=700+d1+-d1-

10、其中，d1+表示總風險高于700的部分，d1-表示總風險少于700的 部分，d1+0。 目標規(guī)劃中把d1+、d1-這樣的變量稱為偏差變量。偏差變量的作 用是允許約束條件不被精確滿足。,把等式轉換，可得到 0.5x1 +0.2x2-d1+d1-=700。 再來考慮年收入: 年收入=3x1+4x2 引入變量d2+和d2-，分別表示年收入超過與低于10000的數(shù)量。 于是，第2個目標可以表示為 3x1+4x2-d2+d2-=10000。,有優(yōu)先權的目標函數(shù) 本問題中第一個目標的優(yōu)先權比第二個目標大。即最重要的目標 是滿足風險不超過700。分配給第一個目標較高的優(yōu)先權P1,分配給第 二個目標較低的優(yōu)先

11、權P2。 針對每一個優(yōu)先權，應當建立一個單一目標的線性規(guī)劃模型。首 先建立具有最高優(yōu)先權的目標的線性規(guī)劃模型，求解；然后再按照優(yōu) 先權逐漸降低的順序分別建立單一目標的線性規(guī)劃模型，方法是在原 來模型的基礎上修改目標函數(shù)，并把原來模型求解所得的目標最優(yōu)值 作為一個新的約束條件加入到當前模型中，并求解。,圖解法 針對優(yōu)先權最高的目標建立線性規(guī)劃 建立線性規(guī)劃模型如下： Min d1+ s.t. 20 x150 x290000 0.5x1 +0.2x2-d1+d1-=700 3x1+4x2-d2+d2-=10000 x1,x2,d1+,d1-0,針對優(yōu)先權次高的目標建立線性規(guī)劃 優(yōu)先權次高（P2）的

12、目標是總收益超過10000。 建立線性規(guī)劃如下： Min d2- s.t. 20 x150 x290000 0.5x1 +0.2x2-d1+d1-=700 3x1+4x2-d2+d2-=10000 d1+0 x1,x2,d1+,d1-,d2+,d2-0,目標規(guī)劃的這種求解方法可以表述如下： 1確定解的可行區(qū)域。 2對優(yōu)先權最高的目標求解，如果找不到能滿足該目標的解，則尋找最接近該目標的解。 3對優(yōu)先權次之的目標進行求解。注意：必須保證優(yōu)先權高的目標不變。 4. 重復第3步，直至所有優(yōu)先權的目標求解完。,目標規(guī)劃模型的標準化 例6中對兩個不同優(yōu)先權的目標單獨建立線性規(guī)劃進行求解。為簡 便，把它們

13、用一個模型來表達，如下： Min P1（d1+）+P2（d2-） s.t. 20 x150 x290000 0.5x1 +0.2x2-d1+d1-=700 3x1+4x2-d2+d2-=10000 x1,x2,d1+,d1-,d2+,d2-0,復雜情況下的目標規(guī)劃,例7一工藝品廠商手工生產某兩種工藝品A、B，已知生產一件產品A需要耗費人力2工時，生產一件產品B需要耗費人力3工時。A、B產品的單位利潤分別為250元和125元。為了最大效率地利用人力資源，確定生產的首要任務是保證人員高負荷生產，要求每周總耗費人力資源不能低于600工時，但也不能超過680工時的極限；次要任務是要求每周的利潤超過70

14、000元；在前兩個任務的前提下，為了保證庫存需要，要求每周產品A和B的產量分別不低于200和120件，因為B產品比A產品更重要，不妨假設B完成最低產量120件的重要性是A完成200件的重要性的2倍。 試求如何安排生產？,解：本問題中有3個不同優(yōu)先權的目標，不妨用P1、P2、P3表 示從高至低的優(yōu)先權。 對應P1有兩個目標：每周總耗費人力資源不能低于600工 時,也不能超過680工時； 對應P2有一個目標：每周的利潤超過70000元； 對應P3有兩個目標：每周產品A和B的產量分別不低于200和120件。,采用簡化模式，最終得到目標線性規(guī)劃如下： Min P1(d1+)+ P1(d2)+P2(d3

15、-)+ P3(d4-)+ P3(2d5-) s.t. 2x1+3x2-d1+d1-=680 對應第1個目標 2x1+3x2-d2+d2-=600 對應第2個目標 250 x1+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,使用運籌學軟件求解可得： 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ù)d

16、4-+2d5- =120。 可見，目標1、目標3和目標4達到了，但目標2、目標5都有一些偏差。,加權目標規(guī)劃,加權目標規(guī)劃是另一種解決多目標決策問題的方法，其基本方法是通過 量化的方法分配給每個目標的偏離的嚴重程度一個罰數(shù)權重，然后建立總 的目標函數(shù)，該目標函數(shù)表示的目標是要使每個目標函數(shù)與各自目標的加 權偏差之和最小，假設所有單個的目標函數(shù)及約束條件都符合線性規(guī)劃的 要求，那么，整個問題都可以描述為一個線性規(guī)劃的問題。 如果在例7中我們對每周總耗費的人力資源超過680工時或低于600工時 的每工時罰數(shù)權重定為7；每周利潤低于70000元時，每元的罰數(shù)權重為 5；每周產品A產量低于200件時每件罰數(shù)權重為2，而每周產品B產量