運(yùn)籌學(xué)OP1-目標(biāo)規(guī)劃ppt課件

1、第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃第一節(jié)第一節(jié) 基本概念及模型的建立基本概念及模型的建立一、單一目標(biāo)問(wèn)題一、單一目標(biāo)問(wèn)題 材料材料 消耗消耗 Kg/件件 A B材料庫(kù)存材料庫(kù)存 Kg材材料料不銹鋼不銹鋼鋼鋼 材材鋁鋁 材材 2 3 2 1 0 1 120 80 30 利利 潤(rùn)潤(rùn) 元元/件件 60 70（該企業(yè)應(yīng)如何安排，能使企業(yè)獲利最大？）（該企業(yè)應(yīng)如何安排，能使企業(yè)獲利最大？）0,x 30 802 12032 s.t 7060max213222112121xlx lxxlxxxxz現(xiàn)企業(yè)要求實(shí)現(xiàn)現(xiàn)企業(yè)要求實(shí)現(xiàn)3000元的利潤(rùn)指標(biāo)，該如何生產(chǎn)？元的利潤(rùn)指標(biāo)，該如何生產(chǎn)？（一偏差變量（一偏差變量0

2、1-dd值的偏差量可能實(shí)現(xiàn)值未達(dá)到指標(biāo)、負(fù)偏差變量0 2dd標(biāo)值的數(shù)量可能實(shí)現(xiàn)值超過(guò)規(guī)定指、正偏差變量3、三種情況、三種情況 超額完成指標(biāo)超額完成指標(biāo)0, 0dd 未完成指標(biāo)未完成指標(biāo)0, 0dd 恰好完成指標(biāo)恰好完成指標(biāo)0, 0dd前例，引入目標(biāo)約束：前例，引入目標(biāo)約束：3000706021ddxx（二目標(biāo)約束與絕對(duì)約束（二目標(biāo)約束與絕對(duì)約束）為絕對(duì)約束（系統(tǒng)約束321,lll（三目標(biāo)函數(shù)（三目標(biāo)函數(shù) 恰好完成規(guī)定指標(biāo)恰好完成規(guī)定指標(biāo)ddzmin 超額完成規(guī)定指標(biāo)超額完成規(guī)定指標(biāo) dzmin 不超過(guò)目標(biāo)值不超過(guò)目標(biāo)值 dzmin前例，要求恰好完成前例，要求恰好完成3000元的利潤(rùn)指標(biāo)。元的利

3、潤(rùn)指標(biāo)。ddzmin 30 80 2 120 32 s.t 22121x xxxx3000706021ddxx0,21ddxx二、多目標(biāo)問(wèn)題二、多目標(biāo)問(wèn)題上例中，除要求完成上例中，除要求完成3000元利潤(rùn)外，還要求盡可能將元利潤(rùn)外，還要求盡可能將30Kg的鋁材用完。的鋁材用完。30302222ddxx300070601121ddxx（一優(yōu)先因子（一優(yōu)先因子kPPPP.321。恰好用完鋁材：元；：超額完成利潤(rùn)指標(biāo)前例，30Kg 300021PP)(min22211ddPdPz 80 2 120 32 s.t 2121 xxxx300070601121ddxx30222ddx2 , 1 0,21i

4、ddxxii（二模型（二模型三、一般目標(biāo)規(guī)劃模型三、一般目標(biāo)規(guī)劃模型為權(quán)系數(shù)）（可表示為：）的目標(biāo)規(guī)劃模型個(gè)優(yōu)先等級(jí)（個(gè)目標(biāo)，若有kll-ljlllnjjljinjjijlkllLlklKkk,.,L) (l,d d,.,n) (jx,.,Llgddxc,.,mibxaddPzLKKL, 101 0 )1( )1( ),( )(min -kl1111 練習(xí)題練習(xí)題某彩電組裝廠，生產(chǎn)某彩電組裝廠，生產(chǎn)A、B、C三種規(guī)格電視機(jī)，裝配工作在三種規(guī)格電視機(jī)，裝配工作在同一生產(chǎn)線上完成。三種產(chǎn)品裝配時(shí)的工時(shí)消耗分別為同一生產(chǎn)線上完成。三種產(chǎn)品裝配時(shí)的工時(shí)消耗分別為6小時(shí)、小時(shí)、8小時(shí)和小時(shí)和10小時(shí)。生

5、產(chǎn)線每月正常工作時(shí)間為小時(shí)。生產(chǎn)線每月正常工作時(shí)間為200小時(shí)，三種小時(shí)，三種產(chǎn)品銷(xiāo)售后，每臺(tái)可獲利分別為產(chǎn)品銷(xiāo)售后，每臺(tái)可獲利分別為500元，元，650元和元和800元，每月元，每月銷(xiāo)售量預(yù)計(jì)為銷(xiāo)售量預(yù)計(jì)為12臺(tái)、臺(tái)、10臺(tái)、臺(tái)、6臺(tái)。該廠經(jīng)營(yíng)目標(biāo)如下：臺(tái)。該廠經(jīng)營(yíng)目標(biāo)如下：P1：利潤(rùn)指標(biāo)為每月：利潤(rùn)指標(biāo)為每月16000元；元；P2：充分利用生產(chǎn)能力；：充分利用生產(chǎn)能力；P3：加班時(shí)間不超過(guò)：加班時(shí)間不超過(guò)24小時(shí)；小時(shí)；P4；產(chǎn)量以預(yù)計(jì)銷(xiāo)量為標(biāo)準(zhǔn)；產(chǎn)量以預(yù)計(jì)銷(xiāo)量為標(biāo)準(zhǔn)；為確定生產(chǎn)計(jì)劃，請(qǐng)建立該問(wèn)題的為確定生產(chǎn)計(jì)劃，請(qǐng)建立該問(wèn)題的OP模型。模型。1600080065050011321ddxx

6、x產(chǎn)品的數(shù)量、分別為計(jì)劃生產(chǎn)設(shè)CBAxxx321,200108622321ddxxx224108633321ddxxx61012663552441ddxddxddx11mindPz22dP33dP)(6655444ddddddP1,2,.,6)0 ) 3 , 21( 0 (i,dd,jxi-ij 某企業(yè)生產(chǎn)兩種產(chǎn)品，每件產(chǎn)品某企業(yè)生產(chǎn)兩種產(chǎn)品，每件產(chǎn)品1可獲利可獲利10元，每件產(chǎn)品元，每件產(chǎn)品2可獲利可獲利8元，每生產(chǎn)一件產(chǎn)元，每生產(chǎn)一件產(chǎn)品品1，需要，需要3小時(shí)，每生產(chǎn)一件產(chǎn)品小時(shí)，每生產(chǎn)一件產(chǎn)品2，需要，需要2.5小時(shí)，每周總有效為小時(shí)，每周總有效為120小時(shí)，若加班小時(shí)，若加班生產(chǎn)，每件

7、產(chǎn)品生產(chǎn)，每件產(chǎn)品1的利潤(rùn)下降的利潤(rùn)下降1.5元，每件元，每件產(chǎn)品產(chǎn)品2的利潤(rùn)下降的利潤(rùn)下降1元，決策者希望在允許元，決策者希望在允許的工作和加班時(shí)間內(nèi)獲取最大利潤(rùn)，試建的工作和加班時(shí)間內(nèi)獲取最大利潤(rùn)，試建立該問(wèn)題的目標(biāo)規(guī)劃模型。立該問(wèn)題的目標(biāo)規(guī)劃模型。產(chǎn)品工時(shí)利潤(rùn)1利潤(rùn)213108.522.587總有效工時(shí)：120小時(shí)設(shè)x1,x2分別為計(jì)劃生產(chǎn)產(chǎn)品1和產(chǎn)品2的數(shù)量。0,x 1205 . 23 810max ) 1 (212121xxxs.t xxz400 0 ,40*T zX(2) P1： 利潤(rùn)不低于400元)247( 1685 . 2321xx40075 . 81121ddxx1mindz

8、0,1121ddxx第二節(jié)第二節(jié) 目標(biāo)規(guī)劃的求解方法目標(biāo)規(guī)劃的求解方法一、圖解法一、圖解法210100012100180512 30032 )(min 121422213112122112122111, i,d,d,x x lddxx l ddxx l x.x lxx s.t dPddPzii：例x1x2l1l2OCBAl31d1dDl41、l1與與l2形成的可行域形成的可行域OABC2、先滿足、先滿足P1，OD線段線段2d2dE3、再滿足、再滿足P2，ED線段滿意解）線段滿意解）E (500/11,500/11) , D (360/7,360/7) ,7/922d, 0211ddd15050

9、1005010015002211dddd210120012100180512 30032 )(min 221422213112122112111221, i,d,d,x x lddxx l ddxx l x.x lxx s.t ddPdPzii：例x1x2l1l2OCBAl31d1dD2d2dEFl41、絕對(duì)約束，可行域、絕對(duì)約束，可行域OABD2、滿足、滿足P1，三角形，三角形ABF3、考慮、考慮P2，ABF與與OD 的最接的最接 近點(diǎn)近點(diǎn)F滿意解）滿意解）F （40，200/3）3/80, 01221dddd5010015050100150 x1x2O246810246810l1l2l3A

10、BP112/4.3(1)1、絕對(duì)約束：、絕對(duì)約束：ABO1d1d2d2dCD2、P1：線段：線段CDE3、P2：線段：線段CE滿意解：滿意解：CE線段線段 C(0,5.2)02211ddddE(0.6,4.7)4 . 0, 01221dddd二、單純形法二、單純形法：剩余變量。：松弛變量，數(shù)：不同數(shù)量級(jí)的很大的ddPk, cj P1 P1 P2bcBxB x1 x2 x3 x4 0 0P1P2x3x4 2 3 1 2 1.5 1 1 -1 1 -110 12 1 -1 300 180 01000jP1P22211 d ddd-1-101-12 21 d d-21 cj P1 P1 P2bcBx

11、B x1 x2 x3 x4 0 0P1P2x3x4 2 3 1 2 1.5 1 1 -1 1 -110 12 1 -1 300 180 01000jP1P22211 d ddd-1-101-12 21 d d-21 0 0 0P2x3x4x1 5 1 -2 2 3.5 1 -2 2 1 -1 1 -1 22 -10 10 1 -1 300 180 01000jP1P22d-221101-101 cj P1 P1 P2bcBxB x1 x2 x3 x4 0 0 0 0 x3x4x1x2 1 3/11 -3/11 -5/22 5/22 1 -9/22 9/22 -7/44 7/44 1 6/11

12、-6/11 1/22 -1/22 1 -5/11 5/11 1/22 - 1/22 800/11230/11500/11500/11jP1P2 1 1 12211 d ddd- 0 0 0 0 x3x1x2 1 -10/7 6/7 -6/7 44/7 -18/7 18/7 -1 1 1 2/7 3/7 -3/7 1 2/7 -4/7 4/7 300/7 92/7 360/7 360/7jP1P2 1 1 12dE點(diǎn)點(diǎn)D點(diǎn)點(diǎn) cj P2 P1 P1bcBxB x1 x2 x3 P2 P1 0 x3 1 2 1 -1 10 12 1 -1 2 1 1 10 62.4 8jP1P2 2211 d d

13、dd-P2P10 x1 jP1P2 21dd-10-1-12-21221dd 1 1/2 1/2 4 7 -5 1 -1 22.4 3/2 -1/2 1 -1 6 -7-3/251/212 cj P2 P1 P1bcBxB x1 x2 x3 P2 P1 0 x1 jP1P2 2211 d ddd-P200 x2 x1 jP1P2 21dd1d-7-3/251/211 0 3/2 -1/2 1 -1 6 0 7 -5 1 -1 22.4 1 1/2 1/2 4 0 1 -5/7 1/7 -1/7 3.2 0 0 4/7 1 -1 1.2 1 0 6/7 2.4-4/7111 cj P2 P1 P1bcBxB x1 x2 x3 P2 0 0 x2 x1 jP1P2 2211 d ddd- 0 0 0 x3 x2 x1 jP1P2 1 0 0 4/7 1 -1 1.2 0 1 -5/7 1/7 -1/7 3.2 1 0 6/7 2.4 0 1 0 5/4 -5/4 1/7 -1/7 4.7 0 0 1 7/