運籌學課件 ppt 復習資料 目標規(guī)劃(運籌學)

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

GoalProgramming

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

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

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

絕對約束、目標約束——硬約束、軟約束4、目標函數(shù)——

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

d-）

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

minZ=f（d++d-

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

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

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

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

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

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

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

x1

、x2

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

、d3+、d3-≥0目標函數(shù)：

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

）家具制造問題——王老板遇到的新問題王老板的多目標線性規(guī)劃問題——目標規(guī)劃問題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目標規(guī)劃的一般形式目標規(guī)劃VS線性規(guī)劃線性規(guī)劃只有一個目標.而目標規(guī)劃具有多個目標，并有不同的優(yōu)先級，低優(yōu)先級目標必須服從高優(yōu)先級目標的實現(xiàn).線性規(guī)劃尋求單一目標的最優(yōu)值.而目標規(guī)劃尋求所有目標與預計成果的最小差距，差距越小，目標實現(xiàn)的可能性越大.線性規(guī)劃只接受最優(yōu)解，而目標規(guī)劃接受滿意解，即如果某些低優(yōu)先級的約束得不到滿足，將目標規(guī)劃的解稱為滿意解.目標規(guī)劃的圖解法如何求解多目標線性規(guī)劃問題，其方法與求解線性規(guī)劃問題的方法相似——目標線性規(guī)劃單純形法.但是，對于只有兩個決策變量的目標線性規(guī)劃問題同樣可以采用圖解的方法來揭示問題的解的某種特征.在用圖解法解目標規(guī)劃時，首先必須滿足所有絕對約束條件.在此基礎上，再按照目標優(yōu)先級別從高到低的順序，逐個地考慮各個目標約束條件.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）目標規(guī)劃的圖解法王老板的目標規(guī)劃新問題圖解目標規(guī)劃的單純形解法

目標規(guī)劃的模型實際上是求min型的線性規(guī)劃，因此，也可以用單純形法求解.在采用單純形法求解目標規(guī)劃時，目標函數(shù)是各優(yōu)先因子的線性組合.因此，在判別各系數(shù)的正負及大小時，關鍵是要注意到優(yōu)先因子的級別.當系數(shù)按優(yōu)先級別從高到低已滿足最優(yōu)性條件時，且無法進一步優(yōu)化時，從單純形表上就可以得到目標規(guī)劃的最優(yōu)解或滿意解.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-，需將其目標函數(shù)中所在列的系數(shù)化為0.改寫初始單純形表x1x2xsd1-d2-d3-d1+d2+d3+RHSP1-1P212-2P3810-1xs021100000011d1-01-10100-1000d2-01200100-1010d3-0810000100-156按優(yōu)先級的級別由高到低依次檢驗，方法和單純形法一樣.11---55.6x1x2xsd1-d2-d3-d1+d2+d3+RHSP1-1P212-2P3810-1xs021100000011d1-01-10100-1000d2-01200100-1010d3-0810000100-156從第一級優(yōu)先P1行開始，由于第一行上系數(shù)都非正，故第一級優(yōu)先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由于第二行上系數(shù)都非正，故第二級優(yōu)先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由于第三行上系數(shù)都非正，故第三級優(yōu)先P3也已得到滿足。從而此題得滿意解x1=2，x2=4.案例——

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

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

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

x1

——彩色電視機的生產(chǎn)量

x2

——黑白電視機的生產(chǎn)量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-，需將其目標函數(shù)中所在列的系數(shù)化為0.改寫初始單純形表x1x2d1-d2-d3-d4-d1+d2+d3+d4+RHSP111-1P2-1P321-2-1d1-0111000-100040d2-01101000-10050d3-010001000-1024d4-0010001000-130按優(yōu)先級的級別由高到低依次檢驗，方法和單純形法一樣.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至此第一級優(yōu)先P1、第二級優(yōu)先P2已得到滿足，但因為第三級優(yōu)先P3還有數(shù)大于0，所以繼續(xù)迭代.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雖然第三級優(yōu)先級P3中仍有數(shù)大于零，但并不意味著解不是最優(yōu)的。對于一個最優(yōu)決策，如果優(yōu)先級的系數(shù)中存在正數(shù)，就要看一看在同一列的更高等級水平是否有任何負數(shù)。若有，則最優(yōu)解已達到；若沒有，則繼續(xù)求解.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.目標規(guī)劃的靈敏度分析目標規(guī)劃的靈敏度分析主要針對優(yōu)先級別進行，其原因是目標優(yōu)先級別和權系數(shù)的確定往往帶有一定的主觀性.分析的方法主要是通過改變優(yōu)先級別的順序來觀察解的變化情況.目標規(guī)劃的應用某單位領導在考慮本單位職工的升級調(diào)資方案時，依次遵守以下規(guī)定：(1)不超過年工資總額60000元；(2)每級的人數(shù)不超過定編規(guī)定的人數(shù)；(3)Ⅱ、Ⅲ級的升級面盡可能達到現(xiàn)有人數(shù)的20%，且無越級提升；(4)Ⅲ級不足編制的人數(shù)可錄用新職工，又Ⅰ級的職工有10%要退休.有關資料匯總見下表，問如何擬定滿意的方案？等級ⅠⅡⅢ工資額(元/年)現(xiàn)有人數(shù)編制人數(shù)200015001000101215121515解：設x1、x2、x3分別表示提升到Ⅰ、Ⅱ級和錄用到Ⅲ級的新職工人數(shù).對各級目標確定優(yōu)先因子為：P1——不超過年工資總額60000元；P2——每級的人數(shù)不超過定編規(guī)定的人數(shù)；P3——Ⅱ、Ⅲ級的升級面盡可能達到現(xiàn)有人數(shù)的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目標函數(shù)Minz=P1d1++P2(d2++d3++d4+)+P3(d5-+d6-)目標規(guī)劃的應用某工廠生產(chǎn)甲、乙兩種型號的微型計算機，他們均需經(jīng)過兩道工序加工。每臺微機所需的加工時間、銷售利潤及該廠每周最大加工能力如下表工序1工序2利潤甲乙最大加工能力433006245075150工廠經(jīng)營目標的各級優(yōu)先級如下：1、每周總利潤不低于10000元；2、合同要求甲型機每周至少生產(chǎn)10臺，乙型機每周至少生產(chǎn)15臺；3、工序1每周生產(chǎn)時間最好為150，工序2生產(chǎn)時間可適當超過其能力.試建立這個問題的數(shù)學模型.解：設x1、x2分別表示甲、乙機器的生產(chǎn)臺數(shù)目標規(guī)劃的應用某市準備在下一年度預算中購置一批救護車，已知每輛救護車購置價為20萬元。救護車用于所屬的兩個郊區(qū)縣，各分配xA和xB臺。A縣