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

1、第四章第四章 目的規(guī)劃目的規(guī)劃第一節(jié)第一節(jié) 根本概念及模型的建立根本概念及模型的建立一、單一目的問題一、單一目的問題 資料資料 耗費耗費 Kg/件件 A B資料庫存資料庫存 Kg材材料料不銹鋼不銹鋼鋼鋼 材材鋁鋁 材材 2 3 2 1 0 1 120 80 30 利利 潤潤 元元/件件 60 70該企業(yè)應(yīng)如何安排，能使企業(yè)獲利最大？該企業(yè)應(yīng)如何安排，能使企業(yè)獲利最大？0,x 30 802 12032 s.t 7060max213222112121xlx lxxlxxxxz現(xiàn)企業(yè)要務(wù)虛現(xiàn)現(xiàn)企業(yè)要務(wù)虛現(xiàn)3000元的利潤目的，該如何消費？元的利潤目的，該如何消費？一偏向變量一偏向變量0 1-dd值的

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

3、 30 80 2 120 32 s.t 22121x xxxx3000706021ddxx0,21ddxx二、多目的問題二、多目的問題上例中，除要求完成上例中，除要求完成3000元利潤外，還要求盡能夠?qū)⒃麧櫷猓€要求盡能夠?qū)?0Kg的鋁材用完。的鋁材用完。30302222ddxx300070601121ddxx一優(yōu)先因子一優(yōu)先因子kPPPP.321。恰好用完鋁材：元；：超額完成利潤指標(biāo)前例，30Kg 300021PP)(min22211ddPdPz 80 2 120 32 s.t 2121 xxxx300070601121ddxx30222ddx2 , 1 0,21iddxxii二模型二模型

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

5、消費線每月正常任務(wù)時間為200小時，三種小時，三種產(chǎn)品銷售后，每臺可獲利分別為產(chǎn)品銷售后，每臺可獲利分別為500元，元，650元和元和800元，每月元，每月銷售量估計為銷售量估計為12臺、臺、10臺、臺、6臺。該廠運營目的如下：臺。該廠運營目的如下：P1：利潤目的為每月：利潤目的為每月16000元；元；P2：充分利用消費才干；：充分利用消費才干；P3：加班時間不超越：加班時間不超越24小時；小時；P4；產(chǎn)量以估計銷量為規(guī)范；產(chǎn)量以估計銷量為規(guī)范；為確定消費方案，請建立該問題的為確定消費方案，請建立該問題的OP模型。模型。1600080065050011321ddxxx產(chǎn)品的數(shù)量、分別為計劃生產(chǎn)

6、設(shè)CBAxxx321,200108622321ddxxx224108633321ddxxx61012663552441ddxddxddx11mindPz22dP33dP)(6655444ddddddP1,2,.,6)0 ) 3 , 21( 0 (i,dd,jxi-ij 某企業(yè)消費兩種產(chǎn)品，每件產(chǎn)品某企業(yè)消費兩種產(chǎn)品，每件產(chǎn)品1可獲利可獲利10元，每件產(chǎn)品元，每件產(chǎn)品2可獲利可獲利8元，每消費一件產(chǎn)元，每消費一件產(chǎn)品品1，需求，需求3小時，每消費一件產(chǎn)品小時，每消費一件產(chǎn)品2，需求，需求2.5小時，每周總有效為小時，每周總有效為120小時，假設(shè)加小時，假設(shè)加班消費，每件產(chǎn)品班消費，每件產(chǎn)品1的利

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

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

9、11dddd210120012100180512 30032 )(min 221422213112122112111221, i,d,d,x x lddxx l ddxx l x.x lxx s.t ddPdPzii：例x1x2l1l2OCBAl31d1dD2d2dEFl41、絕對約束，可行域、絕對約束，可行域OABD2、滿足、滿足P1，三角形，三角形ABF3、思索、思索P2，ABF與與OD 的最接的最接 近點近點F稱心解稱心解F 40，200/33/80, 01221dddd5010015050100150 x1x2O246810246810l1l2l3ABP112/4.3(1)1、絕對約束

10、：、絕對約束：ABO1d1d2d2dCD2、P1：線段：線段CDE3、P2：線段：線段CE稱心解：稱心解：CE線段線段 C(0,5.2)02211ddddE(0.6,4.7)4 . 0, 01221dddd二、單純形法二、單純形法：剩余變量。：松弛變量，數(shù)：不同數(shù)量級的很大的ddPk, cj P1 P1 P2bcB xB 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 P2bcB xB x1 x2 x3 x4 0

11、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 01000P1P22d-221101-101 cj P1 P1 P2bcB xB 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 -6/11 1/22 -1/22

12、 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/72dE點點D點點 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 ddd-P2P10 x1 jP1P2 21dd-10-1

13、-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 P1bcB xB 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/4