運籌學王莉莉四川農業大學數學系2012年10月學習目標正確理解目標規劃的定義；掌握目標規劃的建模技巧；掌握目標規劃的圖解解法；掌握目標規劃的單純形求解模型.第五章—目標規劃目標規劃

GoalProgramming

目標規劃方法是Charnes和Cooper于1961年提出的，目前已成為一種簡單、實用的處理多目標決策問題的方法，是多目標決策中應用最為廣泛的一種方法。為了學習和初步掌握目標規劃與線性規劃在處理問題的方法上的區別，我們分析如下案例——家具制造問題——王老板遇到的新問題背景材料：王老板一直從事專業家具制造，主要生產桌子、椅子兩種家具，王老板的經營環境主要受到兩種資源——木工和油漆工每天的有效工作時間的限制。王老板過去的經營環境條件如下：1、每天木工和油漆工的總有效工作時間分別為11小時和10小時.2、每生產一把椅子需要2小時的木工、1小時的油漆工.3、每生產一張桌子需要1小時的木工、2小時的油漆工.4、每生產一把椅子和一張桌子分別可獲利潤8元、10元.

求解此線性規劃問題可以得到王老板的最優方案：每天生產椅子4把，桌子3張，獲最大利潤62元.家具制造問題——王老板遇到的新問題王老板過去一直以如何計劃兩種家具的生產量才能獲得最大總利潤為其生產、經營的唯一目標。然而，市場經濟環境下新的問題出現了，它迫使王老板不得不考慮…...（1）首先，根據市場信息，椅子的銷售量已有下降的趨勢，故應果斷決策減少椅子的產量，其產量最好不大于桌子的產量.（2）其次，市場上找不到符合生產質量要求的木工了，因此決不可能考慮增加木工這種資源來增加產量，并且由于某種原因木工決不可能加班.（3）再其次，應盡可能充分利用油漆工的有效工作時間，但油漆工希望最好不加班.（4）最后，王老板考慮最好達到并超過預計利潤指標56元.家具制造問題——王老板遇到的新問題討論——1、王老板現在的生產、經營問題——多個目標的生產問題2、決策變量——椅子、桌子的生產量x1，x2

引入一種新的變量——正、負偏差變量d+、d-，d+、d-≥03、約束條件——

絕對約束、目標約束——硬約束、軟約束4、目標函數——

優先因子（優先等級）P1，P2，…，規定Pk>>Pk+1，k=1,2,…表示Pk比Pk+1有更大的優先權.這意味著當目標與目標之間發生沖突時應按其優先等級來實現.家具制造問題——王老板遇到的新問題目標規劃獨特的目標函數（準則函數）是按各目標約束的正、負偏差變量和賦予相應的優先因子而構造的.當每一目標值確定后，決策者的要求是盡可能縮小偏離目標值.因此，目標規劃的目標函數只能是minZ=f（d+,

d-）

其基本形式有三種：家具制造問題——王老板遇到的新問題（1）要求恰好達到目標值，即正、負偏差變量都要盡可能地小

minZ=f（d++d-

）（2）要求不超過目標值，即允許達不到目標值，即正偏差變量要盡可能地小

minZ=f（d+）（3）要求超過目標值，即超過量不限，但必須是即負偏差變量要盡可能地小

minZ=f（d-）家具制造問題——王老板遇到的新問題歸納上面的分析——王老板應在木工每天的有效工作時間受到嚴格限制的基礎上按順序考慮其他目標的實現.目標優先等級：（1）P1——椅子的產量最好不大于桌子的產量.（2）P2——充分利用油漆工的有效工作時間，但希望不加班.（3）P3——總利潤不小于

56元.家具制造問題——王老板遇到的新問題決策變量：（1）x1——椅子的產量，x2——桌子的產量（2）

P1等級正、負偏差變量——d1+、d1-

P2等級正、負偏差變量——d2+、d2-

P3等級正、負偏差變量——d3+、d3-

x1

、x2

、d1+、d1-、d2+、d2-

、d3+、d3-≥0目標函數：

minZ=P1

d1++P2（d2-+d2+）+P3

d3-家具制造問題——王老板遇到的新問題約束條件：（1）絕對約束——2x1+x2≤11（2）目標約束——x1-x2+d1--d1+=0（P1

）

x1+2x2+d2--d2+=10（P2

）

8x1+10x2+d3--d3+=56（P3

）家具制造問題——王老板遇到的新問題王老板的多目標線性規劃問題——目標規劃問題minZ=P1d1++P2（d2-+d2+）+P3

d3-s.t.2x1+x2≤11x1-x2+d1--d1+=0x1+2x2+d2--d2+=108x1+10x2+d3--d3+=56x1

、x2

、d1+、d1-、d2+、d2-、d3+、d3-≥0目標規劃的一般形式目標規劃VS線性規劃線性規劃只有一個目標.而目標規劃具有多個目標，并有不同的優先級，低優先級目標必須服從高優先級目標的實現.線性規劃尋求單一目標的最優值.而目標規劃尋求所有目標與預計成果的最小差距，差距越小，目標實現的可能性越大.線性規劃只接受最優解，而目標規劃接受滿意解，即如果某些低優先級的約束得不到滿足，將目標規劃的解稱為滿意解.目標規劃的圖解法如何求解多目標線性規劃問題，其方法與求解線性規劃問題的方法相似——目標線性規劃單純形法.但是，對于只有兩個決策變量的目標線性規劃問題同樣可以采用圖解的方法來揭示問題的解的某種特征.在用圖解法解目標規劃時，首先必須滿足所有絕對約束條件.在此基礎上，再按照目標優先級別從高到低的順序，逐個地考慮各個目標約束條件.minZ=P1d1++P2（d2-+d2+）+P3d3-s.t.2x1+x2≤11x1-x2+d1--d1+=0x1+2x2+d2--d2+=108x1+10x2+d3--d3+=56x1

、x2

、d1+、d1-、d2+、d2-、d3+、d3-≥08x1+10x2=56

x1-x2=0

x1+2x2=102x1+x2=11

絕對約束域d2+

d3+

d3-d2-

d1-

d1+

（10/3，10/3）（2，4）目標規劃的圖解法王老板的目標規劃新問題圖解目標規劃的單純形解法

目標規劃的模型實際上是求min型的線性規劃，因此，也可以用單純形法求解.在采用單純形法求解目標規劃時，目標函數是各優先因子的線性組合.因此，在判別各系數的正負及大小時，關鍵是要注意到優先因子的級別.當系數按優先級別從高到低已滿足最優性條件時，且無法進一步優化時，從單純形表上就可以得到目標規劃的最優解或滿意解.minZ=P1d1++P2（d2-+d2+）+P3d3-s.t.2x1+x2≤11x1-x2+d1--d1+=0x1+2x2+d2--d2+=108x1+10x2+d3--d3+=56x1

、x2

、d1+、d1-、d2+、d2-、d3+、d3-≥02x1+x2+xs=11x1-x2+d1--d1+=0x1+2x2+d2--d2+=108x1+10x2+d3--d3+=56x1

、x2

、xs、d1+、d1-、d2+、d2-、d3+、d3-≥0

minZ=P1d1++P2(d2-+d2+)+P3d3-s.t.引入松弛變量列出初始單純形表x1x2xsd1-d2-d3-d1+d2+d3+RHSP1-1P2-1-1P3-102110000001101-10100-100001200100-10100810000100-156為了找到基變量xs、d1-、d2-、d3-，需將其目標函數中所在列的系數化為0.改寫初始單純形表x1x2xsd1-d2-d3-d1+d2+d3+RHSP1-1P212-2P3810-1xs021100000011d1-01-10100-1000d2-01200100-1010d3-0810000100-156按優先級的級別由高到低依次檢驗，方法和單純形法一樣.11---55.6x1x2xsd1-d2-d3-d1+d2+d3+RHSP1-1P212-2P3810-1xs021100000011d1-01-10100-1000d2-01200100-1010d3-0810000100-156從第一級優先P1行開始，由于第一行上系數都非正，故第一級優先P1已得到滿足。x1x2xsd1-d2-d3-d1+d2+d3+RHSP1-1P2-1-1P33-55-1xs03/2010-1/2001/206d1-03/20011/20-1-1/205x201/21001/200-1/205d3-03000-5105-16由于第二行上系數都非正，故第二級優先P2已得到滿足。12/310/3102x1x2xsd1-d2-d3-d1+d2+d3+RHSP1-1P2-1-1P3-1xs000102-1/20-21/23d1-000013-1/2-1-31/22x2001004/3-1/6-4/3-1/21/64x101000-5/31/305/3-1/32由于第三行上系數都非正，故第三級優先P3也已得到滿足。從而此題得滿意解x1=2，x2=4.案例——

電視機廠裝配彩色和黑白兩種電視機，每裝配一臺電視機需占用裝配線1小時，裝配線每周計劃開動40小時.預計市場每周彩色電視機的銷量是24臺，每臺可獲利80元；每周黑白電視機的銷量是30臺，每臺可獲利40元.決策者的目標為：

第一優先級目標：充分利用裝配線每周計劃開動的40小時；

第二優先級目標：允許裝配線加班，但加班時間每周盡量不超過10小時；第三優先級目標：裝配電視機的數量盡量滿足市場需求.因為彩色電視機的利潤更高（是黑白電視機利潤的2倍），取其市場需求滿足權系數為2.目標規劃模型

x1

——彩色電視機的生產量

x2

——黑白電視機的生產量x1+x2+d1--d1+=40x1+x2+d2--d2+=50x1+d3--d3+=24

x2+d4--d4+=30x1

、x2

、d1+、d1-、d2+、d2-、d3+、d3-、d4+、d4-≥0

minZ=P1d1-+P2

d2++P3（2d3-+1d4-）s.t.列出初始單純形表x1x2d1-d2-d3-d4-d1+d2+d3+d4+RHSP1-1P2-1P3-2-1d1-0111000-100040d2-01101000-10050d3-010001000-1024d4-0010001000-130為了找到基變量d1-、d2-、d3-、d4-，需將其目標函數中所在列的系數化為0.改寫初始單純形表x1x2d1-d2-d3-d4-d1+d2+d3+d4+RHSP111-1P2-1P321-2-1d1-0111000-100040d2-01101000-10050d3-010001000-1024d4-0010001000-130按優先級的級別由高到低依次檢驗，方法和單純形法一樣.405024---x1x2d1-d2-d3-d4-d1+d2+d3+d4+RHSP11-1-11P2-1P31-2-1d1-00110-10-101016d2-00101-100-11026x1010001000-1024d4-0010001000-1301626---30至此第一級優先P1、第二級優先P2已得到滿足，但因為第三級優先P3還有數大于0，所以繼續迭代.x1x2d1-d2-d3-d4-d1+d2+d3+d4+RHSP1-1P2-1P3-1-11-1-1x200110-10-101016d2-000-11001-10010x1010001000-1024d4-000-101110-1-114---10---14雖然第三級優先級P3中仍有數大于零，但并不意味著解不是最優的。對于一個最優決策，如果優先級的系數中存在正數，就要看一看在同一列的更高等級水平是否有任何負數。若有，則最優解已達到；若沒有，則繼續求解.x1x2d1-d2-d3-d4-d1+d2+d3+d4+RHSP1-1P2-1P3-1-11-1-1x200101-100-11026d1+000-11001-10010x1010001000-1024d4-00-1-1-12101-2-14故此題得滿意解x1=24，x2=26.目標規劃的靈敏度分析目標規劃的靈敏度分析主要針對優先級別進行，其原因是目標優先級別和權系數的確定往往帶有一定的主觀性.分析的方法主要是通過改變優先級別的順序來觀察解的變化情況.目標規劃的應用某單位領導在考慮本單位職工的升級調資方案時，依次遵守以下規定：(1)不超過年工資總額60000元；(2)每級的人數不超過定編規定的人數；(3)Ⅱ、Ⅲ級的升級面盡可能達到現有人數的20%，且無越級提升；(4)Ⅲ級不足編制的人數可錄用新職工，又Ⅰ級的職工有10%要退休.有關資料匯總見下表，問如何擬定滿意的方案？等級ⅠⅡⅢ工資額(元/年)現有人數編制人數200015001000101215121515解：設x1、x2、x3分別表示提升到Ⅰ、Ⅱ級和錄用到Ⅲ級的新職工人數.對各級目標確定優先因子為：P1——不超過年工資總額60000元；P2——每級的人數不超過定編規定的人數；P3——Ⅱ、Ⅲ級的升級面盡可能達到現有人數的20%建立目標約束2000(10-0.1×10+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1--d1+=6000010-0.1×10+x1+d2--d2+=12目標約束12-x1+x2+d3--d3+=1515-x2+x3+d4--d4+=15x1+d5--d5+=12×0.2X2+d6--d6+=15×0.2目標函數Minz=P1d1++P2(d2++d3++d4+)+P3(d5-+d6-)目標規劃的應用某工廠生產甲、乙兩種型號的微型計算機，他們均需經過兩道工序加工。每臺微機所需的加工時間、銷售利潤及該廠每周最大加工能力如下表工序1工序2利潤甲乙最大加工能力433006245075150工廠經營目標的各級優先級如下：1、每周總利潤不低于10000元；2、合同要求甲型機每周至少生產10臺，乙型機每周至少生產15臺；3、工序1每周生產時間最好為150，工序2生產時間可適當超過其能力.試建立這個問題的數學模型.解：設x1、x2分別表示甲、乙機器的生產臺數目標規劃的應用某市準備在下一年度預算中購置一批救護車，已知每輛救護車購置價為20萬元。救護車用于所屬的兩個郊區縣，各分配xA和xB臺。A縣