運籌學-目標規(guī)劃課件

OPERATIONSRESEARCH

運籌學徐玲OR21OPERATIONSRESEARCH

運籌學OR21第五章目標規(guī)劃要求1、理解概念2、掌握建模3、掌握圖解法和單純形解法4、理解目標規(guī)劃的靈敏度分析OR22第五章目標規(guī)劃要求OR225.1目標規(guī)劃的概念及數(shù)學模型1多目標問題多目標線性規(guī)劃例1產(chǎn)品資源

AB限量原材料（kg)設(shè)備（臺時）21121110單位利潤810求利潤最大的生產(chǎn)方案。OR235.1目標規(guī)劃的概念及數(shù)學模型1多目標問題產(chǎn)品原材例2：例1的要求多元化：決策者在原材料供應(yīng)受嚴格限制的基礎(chǔ)上：1、首先是產(chǎn)品A的產(chǎn)量不大于產(chǎn)品B的產(chǎn)量。2、其次是充分利用設(shè)備的有效臺時，不加班。

3、再次是使利潤額盡可能達到并超過計劃利潤指標56元。此問題即為多目標決策問題，目標規(guī)劃就是解這類問題的方法。

AB限量原材料（kg)設(shè)備（臺時）21121110單位利潤810minZ=P1d1++P2(d2-+d2+)+P3d3-OR24例2：例1的要求多元化：決策者在原材料供應(yīng)受嚴格限制的基礎(chǔ)上例2的解法解：問題分析：找差別、定概念（與單目標規(guī)劃相比）1）絕對約束：必須嚴格滿足的等式約束和不等式約束，稱之為絕對約束。2x1+1.5x2≤50(1)

x1+2x2

＝40(2)2）目標約束：那些不必嚴格滿足的等式約束和不等式約束，稱之為目標約束（軟約束）。目標約束是目標規(guī)劃特有的，這些約束不一定要求嚴格完全滿足，允許發(fā)生正或負偏差，因此在這些約束中可以加入正負偏差變量。OR25例2的解法解：問題分析：找差別、定概念（與單目標規(guī)劃相比）O3）偏差變量：目標約束不是剛性的，而是彈性的，允許在一定范圍內(nèi)有偏差，這更接近于實際。為表達這種靈活性，便引入了偏差變量的概念，偏差變量有正負之分，正偏差變量表示為：d+，d+表示超過目標值的部分；負偏差變量表示為：d-，

d-表示不足目標值的部分.顯然有d-·

d+=0（？）OR263）偏差變量：目標約束不是剛性的，而是彈性的，允許在一定范圍4）目標（期望）值：是指預(yù)先給定的某個目標的期望值。5）實際值：是指當決策變量選定以后，目標函數(shù)的對應(yīng)值。顯然：d+＝實際值－目標值≥0d-＝目標值－實際值≥0盡可能達到并超過計劃利潤指標56元，此處的56元即為目標值OR274）目標（期望）值：是指預(yù)先給定的某個目標的期望值。盡可能達6）目標函數(shù)的優(yōu)先級與權(quán)系數(shù):目標的重要程度不同，因此目標的滿足有先有后，即有優(yōu)先級別。設(shè)最重要的為P1級，次之者為P2級……P看成實數(shù)，且有P1>>P2注：目標的優(yōu)先級是一個定性概念，不同的優(yōu)先級之間無法用數(shù)量衡量，僅僅表示優(yōu)化過程中的目標考慮的先后次序。對于同一優(yōu)先級的不同目標，按其重要程度可分別賦予不同的權(quán)系數(shù)。權(quán)系數(shù)是一種可以用數(shù)量表示的指數(shù)，因此，對于一個具體的目標規(guī)劃問題，它是一個數(shù)字。OR286）目標函數(shù)的優(yōu)先級與權(quán)系數(shù):目標的重要程度不同，因此目標的7）目標規(guī)劃的目標函數(shù)：目標規(guī)劃的目標函數(shù)是按各約束的正、負偏差變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)造的。目標函數(shù)的基本形式有三種：1、要求恰好達到目標值，即正負偏差變量都要盡可能地小，這時，minZ＝f(d+＋d-).2、要求不超過目標值，即允許達不到目標值但正偏差變量要盡可能地小，這時，minZ＝f(d+).3、要求超過目標值，即超過量不限但負偏差變量要盡可能的小，這時，minZ＝f(d-)顯然，本題目標函數(shù)表示為：minZ=P1d1+

+P2(d2-+

d2+)

+P3d3-

OR297）目標規(guī)劃的目標函數(shù)：OR29綜上所述，本題的數(shù)學模型為：

minZ=P1d1+

+P2(d2-+

d2+)

+P3d3-

2x1+x2≤11

x1-x2+d1-

-d1+=0

x1+2x2+d2--d2+

=108x1+10x2+d3--d3+=56x1，x2，di-，di+≥0,i=1,2,3OR210綜上所述，本題的數(shù)學模型為：OR210幾點說明：1）有時絕對約束轉(zhuǎn)化為目標約束，則不再表示為絕對約束。2）有時同級別的目標中，其重要程度又有差別，則設(shè)置不同的權(quán)重。OR211幾點說明：1）有時絕對約束轉(zhuǎn)化為目標約束，則不再表示為絕對約目標規(guī)劃問題的特點：1）問題的目標函數(shù)是關(guān)于優(yōu)先等級、權(quán)系數(shù)和偏差變量的極小化函數(shù)；2）約束條件由絕對約束或目標約束構(gòu)成；3）所有決策變量和偏差變量都受到非負約束。OR212目標規(guī)劃問題的特點：1）問題的目標函數(shù)是關(guān)于優(yōu)先等級、權(quán)系數(shù)例3：請建立以下問題的數(shù)學模型某建筑施工單位計劃生產(chǎn)A,B兩種預(yù)制構(gòu)件。決策者首先考慮要充分利用供電部門分配的電量限額指標62.5kw/日，其次考慮完成與超額完成利潤指標10百元/日。每日可供給予制水泥8噸。其它有關(guān)數(shù)據(jù)如下表，問應(yīng)如何確定A,B的產(chǎn)量。產(chǎn)品耗電量(kw/產(chǎn)品）水泥消耗（噸/產(chǎn)品）利潤（百元/產(chǎn)品）A1021B1212OR213例3：請建立以下問題的數(shù)學模型某建筑施工單位計劃生產(chǎn)A,B兩課堂練習：某工廠生產(chǎn)A、B兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)如下：要求：首先、B產(chǎn)品不超過10單位；其次，利潤不低于1600元，再次，充分利用2車間的生產(chǎn)能力，盡量不加班。請建立該問題的模型。

產(chǎn)品資源

AB限量1車間2車間21.5125040單位利潤80100OR214課堂練習：某工廠生產(chǎn)A、B兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)如下：圖解法的基本步驟：（1）先作硬約束與決策變量的非負約束，同一般線性規(guī)劃作圖法。（2）作目標約束，此時，先讓di-

-di+＝0，然后標出di-

及di+的增加方向（實際上是目標值減少與增加的方向）。（3）按優(yōu)先級的次序，逐級讓目標規(guī)劃的目標函數(shù)中極小化偏差變量取0，從而逐步縮小可行域，最后找出問題的解。5.2目標規(guī)劃的圖解法OR215圖解法的基本步驟：5.2目標規(guī)劃的圖解法OR2155.2目標規(guī)劃的圖解法圖解例2:minZ=P1d1+

+P2(d2-+

d2+)

+P3d3-

2x1+x2≤11

x1-x2+d1-

-d1+=0

x1+2x2+d2--d2+

=108x1+10x2+d3--d3+=56x1，x2，di-，di+≥0,i=1,2,3OR2165.2目標規(guī)劃的圖解法圖解例2:minZ=P1d1++P例4：OR217例4：OR217考慮目標規(guī)劃數(shù)學模型的一些特點，作以下規(guī)定：1）因目標函數(shù)為求最小化，所以要求2）因非基變量檢驗數(shù)中含有不同等級的優(yōu)先因子，即，因p1?p2?…?pk；從每個檢驗數(shù)的整體看：檢驗數(shù)的正、負首先決定于p1的系數(shù)a1j的正負，若a1j＝0，

則此檢驗數(shù)的正、負就決定于p2的系數(shù)a2j的正負，依次類推。5.3目標規(guī)劃的單純形解法OR218考慮目標規(guī)劃數(shù)學模型的一些特點，作以下規(guī)定：5.3目標規(guī)3)目標規(guī)劃使用單純形法求解，di-，di+

視為普通變量。P1>>P2

>>…>>

PLOR2193)目標規(guī)劃使用單純形法求解，di-，di+視為普通變量求解目標規(guī)劃單純形法的步驟：P1051、建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行，置k=1。2、檢查該行中是否存在負數(shù)，且對應(yīng)的前k－1行的系數(shù)是零。若有負數(shù)，取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)（3），若無負數(shù)，則轉(zhuǎn)（5）。3、按最小比值規(guī)則確定換出變量，當存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。4、按單純形法進行基變換運算，建立新的計算表，返回（2）。5、當k=K時，計算結(jié)束。表中的解即為滿意解。否則置k=k＋1，返回到（2）。OR220求解目標規(guī)劃單純形法的步驟：P1051、建立初始單純形表，在例題5:用單純形法求解下列目標規(guī)劃問題

minZ=P1d1+

+P2(d2-+

d2+)

+P3d3-

2x1+x2≤11

x1-x2+d1-

-d1+=0

x1+2x2+d2--d2+

=108x1+10x2+d3--d3+=56x1，x2，di-，di+≥0,i=1,2,3OR221例題5:用單純形法求解下列目標規(guī)劃問題minZ=P1d5.5目標規(guī)劃的靈敏度分析例5：已知目標規(guī)劃問題：目標函數(shù)的等級變化為：試分析原解有什么變化？OR2225.5目標規(guī)劃的靈敏度分析例5：已知目標規(guī)劃問題：目標函CBXBbx1x22p13p1p2p3x2X1641820100100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2p3解:原問題的最優(yōu)單純形表為：OR223CBXBbx1x22p13p1p2p3x26011-1-11問題1的變化情況為：OR224問題1的變化情況為：OR224CBXBbx1x22p13p1p2p3x2X1641820101100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2p3p2p3000此時，檢驗數(shù)大于等于零，可見，原解仍是滿意解。p300320－300230－2001010OR225CBXBbx1x22p13p1p2p3x26011-1-11CBXBbx1x22p13p1p2p3x2X1641820101100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2p3p12p23p2p1-320300200-230100p1級的檢驗數(shù)不是大于等于零，則p1級目標未實現(xiàn)，繼續(xù)迭代。過程見書第108頁。OR226CBXBbx1x22p13p1p2p3x26011-1-11某單位考慮職工的升級調(diào)資方案時，依次遵守得規(guī)定：1、不超過年工資總額60000元；2、每級的人數(shù)不超過定編規(guī)定的人數(shù)；3、二、三級的升級面盡可能達到現(xiàn)有人數(shù)的20％，且無越級提升；4、三級不足編制的人數(shù)可錄用新職工，又一級的職工中有10％要退休。有關(guān)資料如下，問應(yīng)如何擬定一個滿意的方案。等級工資額（元/年）現(xiàn)有人數(shù)編制人數(shù)123200015001000101215121515合計3742OR227某單位考慮職工的升級調(diào)資方案時，依次遵守得規(guī)定：等級工資額（已知有三個產(chǎn)地給四個銷地供應(yīng)某種產(chǎn)品，產(chǎn)銷地之間地供需量和單位運費見下表，有關(guān)部門在研究調(diào)運方案時依次考慮以下七項目標，并規(guī)定其相應(yīng)地優(yōu)先等級：P1：B4是重點保證單位，必須全部滿足其需要；P2：A3向B1提供地產(chǎn)量不少于100；P3：每個銷地地供應(yīng)量不小于其需求量地80％；P4：所定調(diào)運方案的總運費不超過最小運費調(diào)運方案的10％。P5：因路段的問題，盡量避免安排將A2的產(chǎn)品往B4；P6：給B1和B3的供應(yīng)率要相同；P7：力求總運費最省。試求滿意的調(diào)運方案。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3534255642763300200400銷量200100450250900/1000其它條件不考慮，用表上作業(yè)法得最小運費為2950。OR228已知有三個產(chǎn)地給四個銷地供應(yīng)某種產(chǎn)品，產(chǎn)銷地之間地供需量和單習題：某工廠計劃期內(nèi)要安排生產(chǎn)A,B兩種產(chǎn)品。已知生產(chǎn)單位產(chǎn)品的利潤與所需資源消耗如下表：產(chǎn)品A產(chǎn)品B資源限量原材料1原材料2設(shè)備1030224128利潤元/kg35OR229習題：某工廠計劃期內(nèi)要安排生產(chǎn)A,B兩種產(chǎn)品。已知生產(chǎn)單位問題：（1）請建立該問題的線性規(guī)劃模型；（5分）（2）請將該問題的數(shù)學模型轉(zhuǎn)變?yōu)闃藴市?，并用單純形法求解該線性規(guī)劃問題。（10分）（3）請寫出該問題的對偶規(guī)劃模型，并指出對偶問題的解。（5分）（4）請指出該問題的影子價格對該工廠有什么指導意義？（5分）

OR230問題：OR230OPERATIONSRESEARCH

運籌學徐玲OR231OPERATIONSRESEARCH

運籌學OR21第五章目標規(guī)劃要求1、理解概念2、掌握建模3、掌握圖解法和單純形解法4、理解目標規(guī)劃的靈敏度分析OR232第五章目標規(guī)劃要求OR225.1目標規(guī)劃的概念及數(shù)學模型1多目標問題多目標線性規(guī)劃例1產(chǎn)品資源

AB限量原材料（kg)設(shè)備（臺時）21121110單位利潤810求利潤最大的生產(chǎn)方案。OR2335.1目標規(guī)劃的概念及數(shù)學模型1多目標問題產(chǎn)品原材例2：例1的要求多元化：決策者在原材料供應(yīng)受嚴格限制的基礎(chǔ)上：1、首先是產(chǎn)品A的產(chǎn)量不大于產(chǎn)品B的產(chǎn)量。2、其次是充分利用設(shè)備的有效臺時，不加班。

3、再次是使利潤額盡可能達到并超過計劃利潤指標56元。此問題即為多目標決策問題，目標規(guī)劃就是解這類問題的方法。

AB限量原材料（kg)設(shè)備（臺時）21121110單位利潤810minZ=P1d1++P2(d2-+d2+)+P3d3-OR234例2：例1的要求多元化：決策者在原材料供應(yīng)受嚴格限制的基礎(chǔ)上例2的解法解：問題分析：找差別、定概念（與單目標規(guī)劃相比）1）絕對約束：必須嚴格滿足的等式約束和不等式約束，稱之為絕對約束。2x1+1.5x2≤50(1)

x1+2x2

＝40(2)2）目標約束：那些不必嚴格滿足的等式約束和不等式約束，稱之為目標約束（軟約束）。目標約束是目標規(guī)劃特有的，這些約束不一定要求嚴格完全滿足，允許發(fā)生正或負偏差，因此在這些約束中可以加入正負偏差變量。OR235例2的解法解：問題分析：找差別、定概念（與單目標規(guī)劃相比）O3）偏差變量：目標約束不是剛性的，而是彈性的，允許在一定范圍內(nèi)有偏差，這更接近于實際。為表達這種靈活性，便引入了偏差變量的概念，偏差變量有正負之分，正偏差變量表示為：d+，d+表示超過目標值的部分；負偏差變量表示為：d-，

d-表示不足目標值的部分.顯然有d-·

d+=0（？）OR2363）偏差變量：目標約束不是剛性的，而是彈性的，允許在一定范圍4）目標（期望）值：是指預(yù)先給定的某個目標的期望值。5）實際值：是指當決策變量選定以后，目標函數(shù)的對應(yīng)值。顯然：d+＝實際值－目標值≥0d-＝目標值－實際值≥0盡可能達到并超過計劃利潤指標56元，此處的56元即為目標值OR2374）目標（期望）值：是指預(yù)先給定的某個目標的期望值。盡可能達6）目標函數(shù)的優(yōu)先級與權(quán)系數(shù):目標的重要程度不同，因此目標的滿足有先有后，即有優(yōu)先級別。設(shè)最重要的為P1級，次之者為P2級……P看成實數(shù)，且有P1>>P2注：目標的優(yōu)先級是一個定性概念，不同的優(yōu)先級之間無法用數(shù)量衡量，僅僅表示優(yōu)化過程中的目標考慮的先后次序。對于同一優(yōu)先級的不同目標，按其重要程度可分別賦予不同的權(quán)系數(shù)。權(quán)系數(shù)是一種可以用數(shù)量表示的指數(shù)，因此，對于一個具體的目標規(guī)劃問題，它是一個數(shù)字。OR2386）目標函數(shù)的優(yōu)先級與權(quán)系數(shù):目標的重要程度不同，因此目標的7）目標規(guī)劃的目標函數(shù)：目標規(guī)劃的目標函數(shù)是按各約束的正、負偏差變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)造的。目標函數(shù)的基本形式有三種：1、要求恰好達到目標值，即正負偏差變量都要盡可能地小，這時，minZ＝f(d+＋d-).2、要求不超過目標值，即允許達不到目標值但正偏差變量要盡可能地小，這時，minZ＝f(d+).3、要求超過目標值，即超過量不限但負偏差變量要盡可能的小，這時，minZ＝f(d-)顯然，本題目標函數(shù)表示為：minZ=P1d1+

+P2(d2-+

d2+)

+P3d3-

OR2397）目標規(guī)劃的目標函數(shù)：OR29綜上所述，本題的數(shù)學模型為：

minZ=P1d1+

+P2(d2-+

d2+)

+P3d3-

2x1+x2≤11

x1-x2+d1-

-d1+=0

x1+2x2+d2--d2+

=108x1+10x2+d3--d3+=56x1，x2，di-，di+≥0,i=1,2,3OR240綜上所述，本題的數(shù)學模型為：OR210幾點說明：1）有時絕對約束轉(zhuǎn)化為目標約束，則不再表示為絕對約束。2）有時同級別的目標中，其重要程度又有差別，則設(shè)置不同的權(quán)重。OR241幾點說明：1）有時絕對約束轉(zhuǎn)化為目標約束，則不再表示為絕對約目標規(guī)劃問題的特點：1）問題的目標函數(shù)是關(guān)于優(yōu)先等級、權(quán)系數(shù)和偏差變量的極小化函數(shù)；2）約束條件由絕對約束或目標約束構(gòu)成；3）所有決策變量和偏差變量都受到非負約束。OR242目標規(guī)劃問題的特點：1）問題的目標函數(shù)是關(guān)于優(yōu)先等級、權(quán)系數(shù)例3：請建立以下問題的數(shù)學模型某建筑施工單位計劃生產(chǎn)A,B兩種預(yù)制構(gòu)件。決策者首先考慮要充分利用供電部門分配的電量限額指標62.5kw/日，其次考慮完成與超額完成利潤指標10百元/日。每日可供給予制水泥8噸。其它有關(guān)數(shù)據(jù)如下表，問應(yīng)如何確定A,B的產(chǎn)量。產(chǎn)品耗電量(kw/產(chǎn)品）水泥消耗（噸/產(chǎn)品）利潤（百元/產(chǎn)品）A1021B1212OR243例3：請建立以下問題的數(shù)學模型某建筑施工單位計劃生產(chǎn)A,B兩課堂練習：某工廠生產(chǎn)A、B兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)如下：要求：首先、B產(chǎn)品不超過10單位；其次，利潤不低于1600元，再次，充分利用2車間的生產(chǎn)能力，盡量不加班。請建立該問題的模型。

產(chǎn)品資源

AB限量1車間2車間21.5125040單位利潤80100OR244課堂練習：某工廠生產(chǎn)A、B兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)如下：圖解法的基本步驟：（1）先作硬約束與決策變量的非負約束，同一般線性規(guī)劃作圖法。（2）作目標約束，此時，先讓di-

-di+＝0，然后標出di-

及di+的增加方向（實際上是目標值減少與增加的方向）。（3）按優(yōu)先級的次序，逐級讓目標規(guī)劃的目標函數(shù)中極小化偏差變量取0，從而逐步縮小可行域，最后找出問題的解。5.2目標規(guī)劃的圖解法OR245圖解法的基本步驟：5.2目標規(guī)劃的圖解法OR2155.2目標規(guī)劃的圖解法圖解例2:minZ=P1d1+

+P2(d2-+

d2+)

+P3d3-

2x1+x2≤11

x1-x2+d1-

-d1+=0

x1+2x2+d2--d2+

=108x1+10x2+d3--d3+=56x1，x2，di-，di+≥0,i=1,2,3OR2465.2目標規(guī)劃的圖解法圖解例2:minZ=P1d1++P例4：OR247例4：OR217考慮目標規(guī)劃數(shù)學模型的一些特點，作以下規(guī)定：1）因目標函數(shù)為求最小化，所以要求2）因非基變量檢驗數(shù)中含有不同等級的優(yōu)先因子，即，因p1?p2?…?pk；從每個檢驗數(shù)的整體看：檢驗數(shù)的正、負首先決定于p1的系數(shù)a1j的正負，若a1j＝0，

則此檢驗數(shù)的正、負就決定于p2的系數(shù)a2j的正負，依次類推。5.3目標規(guī)劃的單純形解法OR248考慮目標規(guī)劃數(shù)學模型的一些特點，作以下規(guī)定：5.3目標規(guī)3)目標規(guī)劃使用單純形法求解，di-，di+

視為普通變量。P1>>P2

>>…>>

PLOR2493)目標規(guī)劃使用單純形法求解，di-，di+視為普通變量求解目標規(guī)劃單純形法的步驟：P1051、建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行，置k=1。2、檢查該行中是否存在負數(shù)，且對應(yīng)的前k－1行的系數(shù)是零。若有負數(shù)，取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)（3），若無負數(shù)，則轉(zhuǎn)（5）。3、按最小比值規(guī)則確定換出變量，當存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。4、按單純形法進行基變換運算，建立新的計算表，返回（2）。5、當k=K時，計算結(jié)束。表中的解即為滿意解。否則置k=k＋1，返回到（2）。OR250求解目標規(guī)劃單純形法的步驟：P1051、建立初始單純形表，在例題5:用單純形法求解下列目標規(guī)劃問題

minZ=P1d1+

+P2(d2-+

d2+)

+P3d3-

2x1+x2≤11

x1-x2+d1-

-d1+=0

x1+2x2+d2--d2+

=108x1+10x2+d3--d3+=56x1，x2，di-，di+≥0,i=1,2,3OR251例題5:用單純形法求解下列目標規(guī)劃問題minZ=P1d5.5目標規(guī)劃的靈敏度分析例5：已知目標規(guī)劃問題：目標函數(shù)的等級變化為：試分析原解有什么變化？OR2525.5目標規(guī)劃的靈敏度分析例5：已知目標規(guī)劃問題：目標函CBXBbx1x22p13p1p2p3x2X1641820100100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2p3解:原問題的最優(yōu)單純形表為：OR253CBXBbx1x22p13p1p2p3x26011-1-11問題1的變化情況為：OR254問題1的變化情況為：OR224CBXBbx1x22p13p1p2p3x2X1641820101100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2p3p2p3000此時，檢驗數(shù)大于等于零，可見，原解仍是滿意解。p300320－300230－2001010OR255CBXBbx1x22p13p1p2p3x26011-1-11CBXBbx1x2