運(yùn)籌學(xué)課件 ppt 復(fù)習(xí)資料 目標(biāo)規(guī)劃(運(yùn)籌學(xué))

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

GoalProgramming

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

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

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

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

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

d-）

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

minZ=f（d++d-

）（2）要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，即正偏差變量要盡可能地小

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

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

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

P1等級正、負(fù)偏差變量——d1+、d1-

P2等級正、負(fù)偏差變量——d2+、d2-

P3等級正、負(fù)偏差變量——d3+、d3-

x1

、x2

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

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

minZ=P1

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

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

）

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

）

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

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

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

電視機(jī)廠裝配彩色和黑白兩種電視機(jī)，每裝配一臺電視機(jī)需占用裝配線1小時(shí)，裝配線每周計(jì)劃開動(dòng)40小時(shí).預(yù)計(jì)市場每周彩色電視機(jī)的銷量是24臺，每臺可獲利80元；每周黑白電視機(jī)的銷量是30臺，每臺可獲利40元.決策者的目標(biāo)為：

第一優(yōu)先級目標(biāo)：充分利用裝配線每周計(jì)劃開動(dòng)的40小時(shí)；

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

x1

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

x2

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