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

1、第四章第四章 目的規(guī)劃目的規(guī)劃第一節(jié)第一節(jié) 根本概念及模型的建立根本概念及模型的建立一、單一目的問(wèn)題一、單一目的問(wèn)題 資料資料 耗費(fèi)耗費(fèi) 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è)要?jiǎng)?wù)虛現(xiàn)現(xiàn)企業(yè)要?jiǎng)?wù)虛現(xiàn)3000元的利潤(rùn)目的，該如何消費(fèi)？元的利潤(rùn)目的，該如何消費(fèi)？一偏向變量一偏向變量0 1-dd值的

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

3、 30 80 2 120 32 s.t 22121x xxxx3000706021ddxx0,21ddxx二、多目的問(wèn)題二、多目的問(wèn)題上例中，除要求完成上例中，除要求完成3000元利潤(rùn)外，還要求盡能夠?qū)⒃麧?rùn)外，還要求盡能夠?qū)?0Kg的鋁材用完。的鋁材用完。30302222ddxx300070601121ddxx一優(yōu)先因子一優(yōu)先因子kPPPP.321。恰好用完鋁材：元；：超額完成利潤(rùn)指標(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ī)劃模型個(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í)題某彩電組裝廠，消費(fèi)某彩電組裝廠，消費(fèi)A、B、C三種規(guī)格電視機(jī)，裝配任務(wù)在三種規(guī)格電視機(jī)，裝配任務(wù)在同一消費(fèi)線上完成。三種產(chǎn)品裝配時(shí)的工時(shí)耗費(fèi)分別為同一消費(fèi)線上完成。三種產(chǎn)品裝配時(shí)的工時(shí)耗費(fèi)分別為6小時(shí)、小時(shí)、8小時(shí)和小時(shí)和10小時(shí)。消費(fèi)線每月正常任務(wù)時(shí)間為小時(shí)。

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

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

7、潤(rùn)下降的利潤(rùn)下降1.5元，每元，每件產(chǎn)品件產(chǎn)品2的利潤(rùn)下降的利潤(rùn)下降1元，決策者希望在允元，決策者希望在允許的任務(wù)和加班時(shí)間內(nèi)獲取最大利潤(rùn)，試許的任務(wù)和加班時(shí)間內(nèi)獲取最大利潤(rùn)，試建立該問(wèn)題的目的規(guī)劃模型。建立該問(wèn)題的目的規(guī)劃模型。產(chǎn)品工時(shí)利潤(rùn)1利潤(rùn)213108.522.587總有效工時(shí)：120小時(shí)設(shè)x1,x2分別為方案消費(fèi)產(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 . 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、絕對(duì)約束，可行域、絕對(duì)約束，可行域OABD2、滿足、滿足P1，三角形，三角形ABF3、思索、思索P2，ABF與與OD 的最接的最接 近點(diǎn)近點(diǎn)F稱心解稱心解F 40，200/33/80, 01221dddd5010015050100150 x1x2O246810246810l1l2l3ABP112/4.3(1)1、絕對(duì)約束

10、：、絕對(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 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點(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 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