1、 3 3 目標規劃方法目標規劃方法 目標規劃模型目標規劃模型 求解目標規劃的單純形方法求解目標規劃的單純形方法 通過上節的介紹和討論，我們知道，目標通過上節的介紹和討論，我們知道，目標規劃方法是解決多目標規劃問題的重要技術之規劃方法是解決多目標規劃問題的重要技術之一。一。 這一方法是美國學者查恩斯（這一方法是美國學者查恩斯（A.Charnes）和庫伯（和庫伯（W.W.Cooper）于）于1961年在線性規劃年在線性規劃的基礎上提出來的。后來，查斯基萊恩的基礎上提出來的。后來，查斯基萊恩（U.Jaashelainen）和李（）和李（S.Lee）等人，進一）等人，進一步給出了求解目標規劃問題的一般

2、性方法步給出了求解目標規劃問題的一般性方法單純形方法。單純形方法。 一、目標規劃模型一、目標規劃模型 給定若干目標以及實現這些目標的優給定若干目標以及實現這些目標的優先順序，在有限的資源條件下，使總的偏先順序，在有限的資源條件下，使總的偏離目標值的偏差最小。離目標值的偏差最小。（一）基本思想（一）基本思想例例1：某一個企業利用某種原材料和現有設：某一個企業利用某種原材料和現有設備可生產甲、乙兩種產品，其中，甲、乙兩備可生產甲、乙兩種產品，其中，甲、乙兩種產品的單價分別為種產品的單價分別為8元和元和10元；生產單位元；生產單位甲、乙兩種產品需要消耗的原材料分別為甲、乙兩種產品需要消耗的原材料分別

3、為2個單位和個單位和1個單位，需要占用的設備分別為個單位，需要占用的設備分別為1臺時和臺時和2臺時；原材料擁有量為臺時；原材料擁有量為11個單位；個單位；可利用的設備總臺時為可利用的設備總臺時為10臺時。試問：如何臺時。試問：如何確定其生產方案？確定其生產方案？（二）目標規劃的有關概念（二）目標規劃的有關概念 如果決策者所追求的唯一目標是使總如果決策者所追求的唯一目標是使總產值達到最大，則這個企業的生產方案可產值達到最大，則這個企業的生產方案可以由如下線性規劃模型給出：求以由如下線性規劃模型給出：求 ， ，使使 1x2x21108maxxxz（3.13.1） 而且滿足而且滿足 )4 . 3(0

4、,)3 . 3(102)2 . 3(112212121xxxxxx 將上述問題化為標準后，求解可得最佳決將上述問題化為標準后，求解可得最佳決策方案為策方案為 （萬元）。（萬元）。 62, 3, 421Zxx 但是，在實際決策時，企業領導者必須考慮但是，在實際決策時，企業領導者必須考慮市場等一系列其他條件，如：市場等一系列其他條件，如： 根據市場信息，甲種產品的需求量有下降根據市場信息，甲種產品的需求量有下降的趨勢，因此甲種產品的產量不應大于乙種產品的趨勢，因此甲種產品的產量不應大于乙種產品的產量。的產量。 超過計劃供應的原材料，需用高價采購，這超過計劃供應的原材料，需用高價采購，這就會使生產成

5、本增加。就會使生產成本增加。 應盡可能地充分利用設備的有效臺時，但不應盡可能地充分利用設備的有效臺時，但不希望加班。希望加班。 應盡可能達到并超過計劃產值指標應盡可能達到并超過計劃產值指標56萬元。萬元。 這樣，該企業生產方案的確定，便成為一個多這樣，該企業生產方案的確定，便成為一個多目標決策問題，這一問題可以運用目標規劃方法進目標決策問題，這一問題可以運用目標規劃方法進行求解。行求解。 為了建立目標規劃數學模型，下面引入有為了建立目標規劃數學模型，下面引入有關概念。關概念。 n偏差變量偏差變量 在目標規劃模型中，除了決策變量外，還在目標規劃模型中，除了決策變量外，還 需要引入正、負偏差變量需

6、要引入正、負偏差變量 、 。其中，正偏。其中，正偏差變量表示決策值差變量表示決策值超過目標值的部分超過目標值的部分，負偏差，負偏差變量表示決策值變量表示決策值未達到目標值的部分未達到目標值的部分。 因為決策值不可能既超過目標值同時又未因為決策值不可能既超過目標值同時又未達到目標值，故有達到目標值，故有 成立。成立。dd0dd絕對約束和目標約束絕對約束和目標約束 絕對約束絕對約束，必須嚴格滿足的等式約束，必須嚴格滿足的等式約束和不等式約束，譬如，線性規劃問題的所和不等式約束，譬如，線性規劃問題的所有約束條件都是絕對約束，不能滿足這些有約束條件都是絕對約束，不能滿足這些約束條件的解稱為非可行解，所

7、以它們是約束條件的解稱為非可行解，所以它們是硬約束硬約束。 目標約束目標約束，目標規劃所特有的，可以，目標規劃所特有的，可以將約束方程右端項看做是追求的目標值，將約束方程右端項看做是追求的目標值，在達到此目標值時允許發生正的或負的偏在達到此目標值時允許發生正的或負的偏差差 ，可加入正負偏差變量，是，可加入正負偏差變量，是軟約束軟約束。 線性規劃問題的線性規劃問題的目標函數目標函數，在給定目，在給定目標值和加入正、負偏差變量后可以標值和加入正、負偏差變量后可以轉化轉化為為目標約束目標約束，也可以根據問題的需要將絕對，也可以根據問題的需要將絕對約束轉化為目標約束。約束轉化為目標約束。 n優先因子（

8、優先等級）與權系數優先因子（優先等級）與權系數 一個規劃問題一個規劃問題, ,常常有若干個目標，決常常有若干個目標，決策者對策者對各個目標各個目標的考慮的考慮, ,往往是有往往是有主次主次或或輕輕重緩急重緩急的。凡要求第一位達到的目標賦予優的。凡要求第一位達到的目標賦予優先因子先因子 ，次位的目標賦予優先因子，次位的目標賦予優先因子 ，并規定并規定 表示表示 比比 有更大的優先權。這就是說，首先保證有更大的優先權。這就是說，首先保證 級目標的實現，這時可以不考慮次級目級目標的實現，這時可以不考慮次級目標；而標；而 級目標是在實現級目標是在實現 級目標的基礎上級目標的基礎上考慮的；依此類推。考慮

9、的；依此類推。1p2p), 2 , 1(1Llppll1lp1p2p1plp， 若要區別具有若要區別具有相同優先因子相同優先因子 的目標的目標的的差別差別，就可以分別賦予它們，就可以分別賦予它們不同的權不同的權系數系數 。這些優先因子和權。這些優先因子和權系數都由決策者按照具體情況而定。系數都由決策者按照具體情況而定。 lp), 2 , 1(Kklk n目標函數目標函數 目標規劃的目標函數（準則函數）是目標規劃的目標函數（準則函數）是按照各目標約束的正、負偏差變量和賦予按照各目標約束的正、負偏差變量和賦予相應的優先因子而構造的。當每一目標確相應的優先因子而構造的。當每一目標確定后，盡可能定后，

10、盡可能縮小與目標值縮小與目標值的的偏離偏離。因此，。因此，目標規劃的目標函數只能是目標規劃的目標函數只能是基本形式有基本形式有3種：種： ),(minddfZ (3.5 (3.5） 要求要求恰好達到目標值恰好達到目標值，就是，就是正、負偏正、負偏差差變量都要盡可能變量都要盡可能小小, ,即即 ),(minddfZ（3.63.6） 要求要求不超過目標值不超過目標值，即允許達不到，即允許達不到目標值，就是目標值，就是正偏差正偏差變量要盡可能變量要盡可能小小，即，即)(mindfZ（3.73.7） 要求要求超過目標超過目標值，也就是超過值，也就是超過量不限，但量不限，但負偏差負偏差變量要盡可能變量要

11、盡可能小小，即即 )(mindfZ（3.83.8） 在實際問題中，可以根據決策者在實際問題中，可以根據決策者的要求，引入正、負偏差變量和目標的要求，引入正、負偏差變量和目標約束，并給不同目標賦予相應的優先約束，并給不同目標賦予相應的優先因子和權系數，構造目標函數，建立因子和權系數，構造目標函數，建立模型。模型。 例例2 2：在例：在例1 1中，如果決策者在原材料供應受中，如果決策者在原材料供應受嚴格控制的基礎上考慮：首先是甲種產品的嚴格控制的基礎上考慮：首先是甲種產品的產量不超過乙種產品的產量；其次是充分利產量不超過乙種產品的產量；其次是充分利用設備的有限臺時，不加班；再次是產值不用設備的有限

12、臺時，不加班；再次是產值不小于小于5656萬元。并分別賦予這萬元。并分別賦予這3 3個目標優先因個目標優先因子子 。試建立該問題的目標規劃模型。試建立該問題的目標規劃模型。321,PPP21108maxxxz121212211(3.2)210(3.3),0(3.4)xxxxx x設備原料非負原模型原模型解：根據題意，這一決策問題的目解：根據題意，這一決策問題的目標規劃模型是標規劃模型是3322211)(mindpddpdpZ11221 xx01121ddxx1022221ddxx561083321ddxx)3 , 2 , 1(0,21iddxxii（3.93.9）（3.103.10）（3.11

13、3.11）（3.123.12）（3.133.13）（3.143.14） 假定有假定有L個目標，個目標，K個優先級個優先級( (KL) )，n個個變量。在同一優先級變量。在同一優先級 中不同目標的正、負偏中不同目標的正、負偏差變量的權系數分別為差變量的權系數分別為 、 ，則多目標規劃，則多目標規劃問題可以表示為問題可以表示為kPkl kl KkLllkllklkddPZ11)(min njllljljLlgddxc1)(), 2 , 1(njijijmibxa1), 2 , 1(),(), 2 , 1(0njxj), 2 , 1(0,Llddll（三）目標規劃模型的一般形式（三）目標規劃模型的一

14、般形式 （3.153.15）（3.163.16）（3.173.17）（3.183.18）（3.193.19）在以上各式中在以上各式中： 、 分別為賦予分別為賦予 優先因子的第優先因子的第 個目標個目標的正、負偏差變量的權系數的正、負偏差變量的權系數； 為第為第 個目標的預期值個目標的預期值； 為決策變量為決策變量； 、 分別為第分別為第 個目標的正、負偏差變量個目標的正、負偏差變量。lk lk lpkkgkjxkdkdk（3.15）式為目標函數）式為目標函數;（3.16）式為目標約束）式為目標約束;（3.17）式為絕對約束）式為絕對約束;（3.18）式和（）式和（3.19）式為非負約束）式為非

15、負約束; 、 、 分別為目標約束和絕對約束中分別為目標約束和絕對約束中決策變量的系數及約束值。其中決策變量的系數及約束值。其中： ； ； ； 。 )(kjcijaibmi, 2 , 1nj, 2 , 1Ll, 2 , 1Kk, 2 , 1二、求解目標規則的單純形方法二、求解目標規則的單純形方法 目標規劃模型仍可以用單純形方法求目標規劃模型仍可以用單純形方法求解解 ，在求解時作以下規定：，在求解時作以下規定： 因為目標函數都是求最小值，所以，因為目標函數都是求最小值，所以，最優判別檢驗數最優判別檢驗數為為 因為非基變量的檢驗數中含有不同等因為非基變量的檢驗數中含有不同等級的優先因子級的優先因子

16、), 2 , 1(0njzcjjKPPP21KkkkjjjPazc1),2 , 1,2 , 1(Kknj； 所以檢驗數的正、負首先決定于所以檢驗數的正、負首先決定于 的系的系數數 的正、負，若的正、負，若 ，則檢驗數的正、，則檢驗數的正、負就決定于負就決定于 的系數的系數 的正、負，下面可的正、負，下面可依此類推。依此類推。1pj1 01j 2pj2 據此，我們可以總結出求解目標規劃據此，我們可以總結出求解目標規劃問題的單純形方法的計算步驟如下：問題的單純形方法的計算步驟如下： 建立初始單純形表，在表中將檢驗建立初始單純形表，在表中將檢驗數 行 按 優 先 因 子 個 數 分 別 排 成數 行

17、 按 優 先 因 子 個 數 分 別 排 成 L 行 ，行 ，置置 。 1l 檢查該行中是否存在負數，且對應的前檢查該行中是否存在負數，且對應的前L L- -1 1行的系數是零。若有，取其中最小者對應的變行的系數是零。若有，取其中最小者對應的變量為換入變量，轉量為換入變量，轉。若無負數，則轉。若無負數，則轉。 按最小比值規則（按最小比值規則（ 規則）確定換出變量，規則）確定換出變量，當存在兩個和兩個以上相同的最小比值時，選取當存在兩個和兩個以上相同的最小比值時，選取具有較高優先級別的變量為換出變量。具有較高優先級別的變量為換出變量。 按單純形法進行基變換運算，建立新的計按單純形法進行基變換運算

18、，建立新的計算表，返回算表，返回。 當當l= =L時，計算結束，表中的解即為滿意時，計算結束，表中的解即為滿意解。否則置解。否則置l= =l+1+1，返回，返回 。 例例3 3：試用單純形法求解例：試用單純形法求解例2 2所描述的目標所描述的目標規劃問題規劃問題解：首先將這一問題化為如下標準形式解：首先將這一問題化為如下標準形式 3322211)(mindpddpdpZ112321xxx01121ddxx1022221ddxx561083321ddxx)3 , 2 , 1(0,iddxiii (1) (1)取取 , , , , , , ,為初始基變量，列為初始基變量，列出初始單純形表出初始單純形表。表表3.13.13x1d2d3d (2)取取 ，檢查檢驗數的，檢查檢驗數的 行，因該行無行，因該行無負檢驗數，故轉負檢驗數，故轉(5) 。 (5) 因為因為 ，置，置 ，返回，返回(2)。 (2) 檢查發現檢驗數檢查發現檢驗數 行中有行中有 ， ，因為，因為有有 ，所以，所以 為換入變量，轉入為換入變量，轉入(3)。 1l1p31Ll21 ll2p1222, 1min2x (3 (3按按 規則計算：規則計算： ，所以所以 為換出變量，轉入為換出變量，轉入(4)(4)。 (4)(4)進行換基運算，得到表進行換基運算，得到表3.23.2。以此類。以此類推，直至得到最終單純形表為止，如表