第四章目標規劃OperationalResearch(OR)本章內容目標規劃問題及其數學模型目標規劃的圖解法解目標規劃的單純形法目標規劃的靈敏度分析目標規劃應用舉例目標規劃問題的導出例4-1

某工廠生產兩種產品，受到原材料供應和設備工時的限制。在單件利潤等有關數據已知上網條件下，要求制訂一個獲利最大的生產計劃。具體數據如下：產品ⅠⅡ限量原材料（kg/件）51060設備工時（h/件）4440利潤（元/件）68解得，最優解x1=8，x2=2，maxz=64（元）目標規劃問題的導出一般來說，一個計劃問題可能要滿足多方面得要求。線性規劃有最優解的必要條件是其可行解集非空，即各約束條件彼此相容。但實際問題有時不能滿足這樣的要求。線性規劃解得可行性和最優性具有十分明確的意義，但那都是針對特定數學模型而言的。實際中，決策者需要計劃人員提供的不是嚴格的數學上的最優解，而是可以幫助作出最優決策的參考性計劃，或是提供多種計劃方案，供最終決策時選擇。例4-2假設計劃人員被要求考慮如下意見：(1)由于產品Ⅱ銷售疲軟，故希望產品Ⅱ的產量不超過產品Ⅰ的一半；(2)原材料嚴重短缺，生產中應避免過量消耗；(3)最好能節約4h設備工時；(4)計劃利潤不少于48元。計劃人員需要會同有關各方作進一步的協調，最后達成了一致意見：原材料使用限額不得突破；產品Ⅱ產量要求必須優先考慮；設備工時問題其次考慮；最后考慮計劃利潤的要求。類似這樣的多目標決策問題是典型的目標規劃問題。目標規劃問題的導出目標規劃的數學模型基本概念（1）偏差變量d+≥0，d-≥0，d+·d-=0（2）絕對約束和目標約束（3）優先因子和權系數（4）目標規劃的目標函數三種基本表達式：

①要求恰好達到目標值min{f(d++d-)}②要求不超過目標值，但允許不足目標值min{f(d+)}③要求不低于目標值，但允許超過目標值min{f(d-)}目標規劃的數學模型例4-1的目標規劃表達式為：min{P1d1-,P2d2+,P3d3-}絕對約束目標約束P1為兩種產品產量要求的優先因子；P2為節約工時要求的優先因子；P3為計劃利潤要求的優先因子，它們應滿足P1》P2》P3目標規劃的數學模型目標規劃數學模型的一般形式：gk為第k個目標約束的預期目標值，Wlk-和Wlk+為Pl優先因子對應各目標的權系數。目標規劃目標規劃問題及其數學模型目標規劃的圖解法解目標規劃的單純形法目標規劃的靈敏度分析目標規劃應用舉例目標規劃的圖解法對于只有兩個決策變量的目標規劃問題，可以用圖解方法來求解。在用圖解法解目標規劃時，首先必須滿足所有絕對約束。在此基礎上，再按照優先級從高到低的順序，逐個地考慮各個目標約束。一般地，若優先因子Pj對應的解空間為Rj，則優先因子Pj+1對應的解空間只能在Rj中考慮，即Rj+1屬于Rj。若Rj不空，而Rj+1為空集，則Rj中的解為目標規劃的滿意解，它只能保證滿足P1,P2,…,Pj級目標，而不保證滿足其后的各級目標。目標規劃的圖解法例4-3

用圖解法解例4-2。R1R2△OAB區域是滿足絕對約束和非負條件的解空間。對于所有目標約束，去掉偏差變量，畫出相應直線，然后標出偏差變量變化時直線平移方向，見圖所示。首先考慮P1，此時要求mind-1，因而解空間R1為△OAC區域；再考慮P2，此時要求mind2+，因而解空間R2為△ODC區域；最后考慮P3，此時要求mind3-，因而解空間R3為四邊形EDCF區域。容易求得E，D，C，F四點的坐標分別為(8,0)、(9,0)、(6,3)、(4.8,2.4)，故問題的解可表示為：α1(8,0)+α2(9,0)+α3(6,3)+α4(4.8,2.4)=(8α1+9α2+6α3+4.8α4,3α3+2.4α4)其中，α1，α2，α3，α4≥0，

α1+α2+α3+α4=1目標規劃的圖解法例4-3最后一級目標的解空間非空。這時得到的解能滿足所有目標的要求。當解不惟一時(如例4-3，R3為四邊形EDCF區域)，決策者在作實際決策時究竟選擇哪一個解，完全取決于決策者自身的考慮。目標規劃的圖解法例4-4

用圖解法解下面的目標規劃min{P1d1-,P2d2+,P3(5d3-+3d4-),P4d1+}目標規劃的圖解法所以滿意解為：x1=6.5，x2=1.25目標規劃的圖解法例4-4得到的解不能滿足所有目標。這時，我們要做的是尋找滿意解，使它盡可能滿足高級別的目標，同時又使它對那些不能滿足的較低級別目標的偏離程度盡可能的小。必須注意的是，在考慮低級別目標時，不能破壞已經滿足的高級別目標，這是目標規劃的基本原則。但是，也不能因此而以為，當高級別目標不能滿足時，其后的低級別目標也一定不能被滿足。事實上，在有些目標規劃中，當某一優先級的目標不能滿足時，其后的某些低級別目標仍有可能被滿足。目標規劃目標規劃問題及其數學模型目標規劃的圖解法解目標規劃的單純形法目標規劃的靈敏度分析目標規劃應用舉例解目標規劃的單純形法目標規劃的數學模型實際上是最小化形的線性規劃，可以用單純形法求解。在用單純形法解目標規劃時，檢驗數是各優先因子的線性組合。因此，在判別各檢驗數的正負及大小時，必須注意P1?P2?P3?…。當所有檢驗數都已滿足最優性條件(cj-zj≥0)時，從最終單純形表上就可以得到目標規劃的解。解目標規劃的單純形法例4-5

用單純形法解例4-4。引入松弛變量x3，

min{P1d1-,P2d2+,P3d3-}cj→000P100P2P30CBxBbx1x2x3d1-d1+d2-d2+d3-d3+0x3605101000000P1d1-0[1]-201-100000d2-36440001-100P3d3-4868000001-1zj-cjP1-120010000P2000000100P3-6-800000010x3600201-5500000x101-201-100000d2-360120-441-100P3d3-480[20]0-66001-1zj-cjP1000100000P2000000100P30-2006-600010x3120011-100-110x124/51002/5-2/5001/10-1/100d2-36/5000-2/52/51-1-3/53/5P3x212/5010-3/103/10001/20-1/20zj-cjP1000100000P2000000100P3000000010解目標規劃的單純形法在單純形表Ⅲ中，由于非基變量d1+和d3+的檢驗數都是零，故知例4-4有多重最優解(滿意解)。以d1+為換入變量繼續迭代，可得如下單純形表Ⅳcj→000P100P2P30CBxBbx1x2x3d1-d1+d2-d2+d3-d3+0x320010/310000-5/65/6P1x1814/3000001/6-1/60d2-40-4/30001-1-2/32/3P3d1+8010/30-11001/6-1/6cj-zjP1000100000P2000000100P3000000010Ⅳ解目標規劃的單純形法以d3+為換入變量繼續迭代，可得如下單純形表Ⅴcj→000P100P2P30CBCBbx1x2x3d1-d1+d2-d2+d3-d3+0d3+120011-100-11P1x16101/101/2-1/200000d2-000-3/5-111-100P3x23011/20-1/41/40000cj-zjP1000100000P2000000100P3000000010解目標規劃的單純形法解目標規劃的單純形法結論：

例4-5的解為以上四個滿意解(即C，D，E，F四點)的凸組合。而且，從單純形表Ⅲ，Ⅳ，Ⅴ，Ⅵ中可知，各非基變量檢驗數中三個優先因子的系數全部非負，這表示任何一個滿意解都能滿足所有目標的要求。單純形法和圖解法的解題結果完全一致。目標規劃目標規劃問題及其數學模型目標規劃的圖解法解目標規劃的單純形法目標規劃的靈敏度分析目標規劃應用舉例目標規劃的靈敏度分析在目標規劃建模時，目標優先級和權系數的確定往往帶有一定的主觀性，因此，對它們的靈敏度分析是目標規劃靈敏度分析的主要內容。目標規劃靈敏度分析的方法、原理同線性規劃的靈敏度分析本質上相同。

例4-6

對例4-4的目標規劃問題，已求得滿意解為x1=13/2,x2=5/4。現決策者想知道，目標函數中各目標的優先因子和權系數對最終解的影響。為此，提出了下面兩個靈敏度分析問題，即目標函數分別變為：(1)min{P1d1-,P2d2+,P3d1+,P4(5d3-+3d4-)}(2)min{P1d1-,P2d2+,P3(W1d3-+W2d4-),P4d1+}(W1,W2>0)目標規劃的靈敏度分析解目標函數的變化僅影響原解的最優性，即各變量的檢驗數。因此，應當先考察檢驗數的變化，然后再作適當的處理。1.當目標函數變為（1），就是要了解交換第三和第四優先級目標對原解的影響。此時，單純形表變為下表：cj→00P1P30P25P403P40CBxBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0x113/210001/2-1/21/2-1/200P3d1+300-111-100003P4d4-3/40000-1/41/41/4-1/41-10x25/401001/4-1/4-1/41/400cj-zjP10010000000P20000000000P30010-110000P400003/4-3/417/43/403目標規劃的靈敏度分析可見，原解最優性已被破壞(d2-的檢驗數-P3+3/4P4<0)，故應用單純形法繼續求解。目標規劃的靈敏度分析cj→00P1P30P25P403P40CBxBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0x15101/2-1/2001/2-1/2000d2-300-111-100003P4d4-3/200-1/41/4001/4-1/41-10x21/2011/4-1/400-1/41/400cj-zjP10010000000P20000000000P30001010000P4003/4-3/40017/43/403可知，第三和第四優先級目標交換后，原滿意解已失去了最優性。新的滿意解為x1=5,x2=1/2當目標函數變為(2)，就是要了解第三優先級中兩目標權系數取值對原解的影響。此時，單純形表變為:目標規劃的靈敏度分析cj→00P1P40P2W1P30W2P30CBxBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0x113/210001/2-1/21/2-1/200P4d1+300-111-10000W2P3d4-3/40000-1/41/41/4-1/41-10x25/401001/4-1/4-1/41/400cj-zjP10010000000P20000010000P30000W2/4-W2/4-W2/4W2/40W2P40010-1117/43/403可知，原解是否改變取決于d3-的檢驗數W1-W2/4。因此：當W1-W2/4>0，即W1/W2>1/4時，原解不變，仍為x1=13/2,x2=5/4當W1/W2<1/4時，原解改變。用單純形法繼續求解，可得新的滿意解x1=5,x2=2(此時，d3-=3,d4-=0)

當W1/W2=1/4時，兩個解均為滿意解。目標規劃的靈敏度分析第三優先級兩目標權系數的改變有可能會影響所得的滿意解。解的變化取決于兩目標權系數的比值W1/W2，其臨界點為1/4。事實上，在前兩優先級目標均已被滿足的條件下，如滿足d3-=0，則使d4-=3/4；如滿足d4-=0，則使d3-=3。d4-/d3-=1/4。如將W1/W2看作同一優先級下兩目標重要程度的比較，而將d4-/d3-看作因此而引起的不滿足程度的比較，則兩者的一致恰好說明了目標規劃中權系數的作用和意義。目標規劃目標規劃問題及其數學模型目標規劃的圖解法解目標規劃的單純形法目標規劃的靈敏度分析目標規劃應用舉例目標規劃應用舉例例8

有三個產地向四個銷地供應物資。產地Ai(i=1,2,3)的供應量ai、銷地Bj(j=1,2,3,4)的需要量bj、各產銷地之間的單位物資運費cij見表。表中，ai和bj的單位為t，cij的單位為元／t。編制調運方案時要求按照相應的優先級依次考慮下列7項目標：P1:B4是重點保證單位，其需要量應盡可能全部滿足；P2:A3向B1提供的物資不少于100t；P3:每個銷地得到的物資數量不少于其需要量的80%；P4:實際的總運費不超過當不考慮P1至P6各目標時的最小總運費的110%；P5:因路況原因，盡量避免安排A2的物資運往B4；P6:對B1和B3的供應率要盡可能相同；P7:力求使總運費最省。試求滿意的調運方案。目標規劃應用舉例B1B2B3B4aiA15267300A23546200A34523400bj200100450250解用表上作業法可以求得不考慮P1至P6各目標時的最小運費調運方案，相應的最小運費為2950元。現在建立問題的目標