1、第四章 目標規(guī)劃,目標規(guī)劃的數學模型,目標規(guī)劃的圖解法,解目標規(guī)劃的單純形法,應用舉例,目標規(guī)劃（Goal Programming，簡記為GP）在線性規(guī)劃 的基礎上，為適應經濟管理中多目標決策的需要而逐步發(fā)展起來的一個運籌學分支，是實行目標管理這種現代化管理技術的一個有效工具.,目標規(guī)劃的有關概念和模型最早在1961年由美國學者查恩斯（A.Charnes）和庫伯（W.W.Coopor）在他們合著的管理模型和性規(guī)劃的工業(yè)應用一書中提出，以后這種模型又先后經尤吉艾吉里（ Yuji.Ijiri）等人的不斷完善改進，1976年伊格尼齊奧（J.P.Ignizio）發(fā)表了目標規(guī)劃及其擴展一書， 系統(tǒng)歸納總

2、結了目標規(guī)劃的理論和方法目前研究較多的有線性目標規(guī)劃、非線性目標規(guī)劃、線性整數目標規(guī)劃和01目標規(guī)劃等.,4.1 目標規(guī)劃問題及其數學模型,一、問題的提出 第一，線性規(guī)劃是在一組線性約束條件下，尋求某一項目標（如產量、利潤或成本等）的最優(yōu)值.而實際問題中往往要考慮多個目標的決策問題.如核電站的設計問題，傳統(tǒng)的單目標規(guī)劃只允許設定一個目標，那么單一目標選擇什么？是使整個電站建設費用為最低，安全運行的可靠性最高，電能輸出最大，還是對周圍環(huán)境的影響最小.顯然，上述目標都很重要，且又可能互相矛盾，若系統(tǒng)設計只選取一個目標，如建設費用最低，這可能很容易達到，但這種選擇的結果將犧牲其它方面條件，如降低運行

3、的安全可靠性或環(huán)境條件的嚴重破壞.這是一個多目標決策問題，普通的線性規(guī)劃是無能為力的；,第二，線性規(guī)劃最優(yōu)解存在的前提條件是可行域為非空集，否則，線性規(guī)劃無解.然而實際問題中，有時可能出現資源條件滿足不了管理目標的要求的情況，此時，僅做無解的結論是沒有意義的； 第三，線性規(guī)劃問題中的約束條件是不分主次、同等對待的，是一律要滿足的“硬約束”，而在實際問題中，多個目標和多個約束條件并不一定是同等重要的，而是有輕重緩急和主次之分的； 第四，線性規(guī)劃的最優(yōu)解可以說是絕對意義下的最優(yōu)，但很多實際只需（或只能）找出滿意解就可以.如對核電站設計問題中的若干目標.,例4.1 某工廠生產兩種產品，受到原材料供應

4、和設備工時的限制.在單件利潤等有關數據已知的條件下，要求制訂一個獲利最大的生產計劃，具體數據見表4-1.,設產品、的產量分別為 ，建立線性規(guī)劃模型,解之得最優(yōu)生產計劃為 件， 件， 利潤為 元.,工廠作決策時可能還需根據市場和工廠實際情況，考慮其它問題，如：（1）由于產品銷售疲軟，故希望產品的產量不超過產品的一半；（2）原材料嚴重短缺，原料數量只有60；（3）最好能節(jié)約4小時設備工時；（4）計劃利潤不少于48元.,二、目標規(guī)劃的基本概念,1、目標值和偏差變量 目標值:決策者對每一個目標都有一個期望值-或稱為理想值. 正偏差變量：表示決策值（實現值）超過目標值的數量，記為 ； 負偏差變量:表示決

5、策值（實現值）未達到目標值的數量，記為 .,2、目標約束和絕對約束絕對約束是指必須嚴格滿足的等式約束和不等式約束.如線性規(guī)劃問題的所有約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束.如原材料短缺;目標約束是目標規(guī)劃特有的，可把約束右端看作要追求的目標值，在達到此目標值時允許發(fā)生正或負偏差；如何寫目標約束：對每個原始目標表達式（或是等式、不等式，其右端為理想值）的左端都加上負偏差變量、減去正偏差變量后，變換為等式，即目標約束.,一個多目標決策問題中，常有多個目標，這些目標是有主次或輕重緩急的不同，根據重要程度賦予優(yōu)先因子 表示 比 有更大的優(yōu)先權， 對相同優(yōu)先因子的兩個目標，賦

6、予它們不同的權系數 優(yōu)先因子和權系數一般根據題目要求而定。,3、優(yōu)先因子（優(yōu)先等級）與權系數,4、目標規(guī)劃的目標函數 目標規(guī)劃的目標函數，是由各目標約束的偏差變量及相應的優(yōu)先因子和權系數構成，當一個目標規(guī)劃確定后決策者的要求是盡可能接近各既定目標值，也就是偏差變量盡可能小， 目標函數一定是極小化的，三種基本表達式. （1）要求恰好達到目標值.這時決策值超過或低于目標值都是不希望的，因此有： （2）要求不超過目標值，即允許達不到目標值，就是正偏差變量要盡可能地小，因此有： （3）要求不低于目標值，即允許超過目標值，就是負偏差變量要盡可能地小，因此有：,5、目標規(guī)劃問題的解-滿意解 目標規(guī)劃問題的

7、求解是分級進行的，首先求滿足 級目標的解，然后在保證 級目標不被破壞的前提下再求滿足 級目標的解. 以此類推. 因此，這樣最后求出的解就不是通常意義下的最優(yōu)解，稱之為滿意解. 因為對于這種解來說，前面的目標是可以保證實現或部分實現的，后面的目標就不一定能保證實現或部分實現，有些可能就不能實現.滿意解這一概念的提出是對最優(yōu)化概念的一個突破.顯然它更切合實際，更便于運用.,三、目標規(guī)劃的數學模型,例4.2 在例4.1中若工廠提出的管理目標按優(yōu)先級排列如下： 級目標：希望產品的產量不超過產品的一半； 級目標：最好能節(jié)約4小時設備工時； 級目標：希望計劃利潤不小于48元； 由于原材料嚴重短缺，故原材料

8、約束作為絕對約束.試建立目標規(guī)劃模型.,解：引入偏差變量 三個目標約束： 按優(yōu)先級確定目標函數， 級目標要求 ； 級目 標要求 ； 級目標要求 . 該問題的目標規(guī)劃模型為： （4.1） 該問題也可以這樣處理，把絕對約束化為目標約束,而把 級目標要求設為 ，其余依次后退優(yōu)先級，得：,例4.3 某計算機制造廠生產A、B、C三種型號的計算機，它們在同一條生產線上裝配，三種產品的工時消耗分別為5小時、8小時、12小時，生產線上每月正常運轉時間是170小時，這三種產品的利潤分別為每臺1000元、1440元、2520元，該廠的經營目標為 ：充分利用現有工時，必要時可以加班； ：A、B、C的最低產量分別為5

9、、5、8臺，并依單位工時的利潤比例確定權系數； ：生產線的加班時間每月不超過20小時； ：A、B、C三種產品的月銷售指標分別定為10、12、10臺，并依單位工時的利潤比例確定權系數.試建立目標規(guī)劃模型.,解：設A、B、C三種產品的產量分別為 ，單位工時的利潤分別為1000/5=200、1440/8=180、2520/12=210，故單位工時的利潤比例為20:18:21，于是得目標規(guī)劃模型為：,綜上分析，可得目標規(guī)劃的一般模型 （4.2 ） s.t. （4.3） （4.4） （4.5） （4.6） 其中，式（4.2）是目標函數有L個目標，根據L個目標的優(yōu)先程度，把它們分成K個優(yōu)先等級，即 ， 是

10、權系數， 是正負偏差變量；式（4.3)是目標約束， 是L個目標的期望值，一般都應同時引入下、 負偏差變量 ，但有時也可根據已知條件只引入單個 或 ；式（4.4）是目標規(guī)劃的絕對約束，通常是人力、物力、財力等資源的約束；式（4.5）、（4.6）是目標規(guī)劃的非負約束.,2 目標規(guī)劃的圖解法,用圖解法解目標規(guī)劃時，先在由決策變量 構成的平面直角坐標系 的第一象限內作各約束條件.絕對約束條件的作圖與線性規(guī)劃相同，作目標約束時，先令 =0，作相應的直線，然后在這直線旁標上 , 增大的方向，在此基礎上，再按照優(yōu)先級從高到低的順序，逐個地考慮各個目標約束.一般地，若優(yōu)先因子 對應的解空間為 ，則優(yōu)先因子 對

11、應的解空間只能在 中考慮，即 若 而 ，則 中的解為目標規(guī)劃的滿意解，它只能保證滿足 級目標，而不保證滿足其后的各級目標.,例4.4 用圖解法解,x2,x1,0,L1,L2,L3,L4,A,B,C,D,E,F,解：CDEF內均為最優(yōu)解，無窮多最優(yōu)解,例4.5 某電視機廠裝配黑白和彩色兩種電視機，每裝配一臺，電視機需占用裝配線1小時，裝配線每周計劃開動40小時，預計市場每周彩色電視機的銷量是24臺，每臺可獲利80元，黑白電視機的銷量是30臺，每臺可獲利40元，該廠確定的目標為：P1：充分利用裝配線每周計劃開動40小時；P2：允許裝配線加班，但加班時間每周盡量不超過10小時；P3：裝配電視機的數量盡量滿足市場需要. 試建立該問題的目標規(guī)劃模型，并用圖解法求解黑白和彩色電視機的產量.,解：設 分別表示黑白和彩色電視機的產量，問題的目標規(guī)劃模型為 ,其中在P3級目標中，因彩色電視機的利潤是黑白電視機利潤的2倍，故取權系數為2.解題過程見圖4-2.,滿足P1,P2目標的解空間R2為四邊形A