目標(biāo)規(guī)劃 (運(yùn)籌學(xué))

1、4.1 4.1 目標(biāo)規(guī)劃問題及其建模目標(biāo)規(guī)劃問題及其建模4.2 4.2 目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的圖解法4.3 4.3 目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的單純形法4.4 4.4 目標(biāo)規(guī)劃應(yīng)用目標(biāo)規(guī)劃應(yīng)用第2章 單純形法2引引例例4-14-1 某企業(yè)計(jì)劃生產(chǎn)甲、乙、丙三種產(chǎn)品，需要在兩種設(shè)備A、B上加工，消耗C、D兩種原料，有關(guān)數(shù)據(jù)見下表。第4章 目標(biāo)規(guī)劃3甲甲乙乙丙丙現(xiàn)有資源現(xiàn)有資源A A（設(shè)備）（設(shè)備）312200B B（設(shè)備）（設(shè)備）224200C C（原料）（原料）451360D D（原料）（原料）235300利潤（元利潤（元/件）件）403050設(shè) 分別為甲、乙、丙的產(chǎn)量，則利潤最大的線性規(guī)

2、劃模型為：線性規(guī)劃最優(yōu)解為X* =（50，30，10） Z*=3400第4章 目標(biāo)規(guī)劃4321,xxx0,3005323605420042220023. .503040max321321321321321321xxxxxxxxxxxxxxxtsxxxz決策者考慮以下實(shí)際目標(biāo)：利潤不少于3200元產(chǎn)品甲的產(chǎn)量不超過產(chǎn)品乙的產(chǎn)量的1.5倍提高丙的產(chǎn)量達(dá)到30以上設(shè)備加工能力不足時(shí)可以加班，但最好不加班原料只能使用現(xiàn)有的原料。企業(yè)如何制定生產(chǎn)計(jì)劃，才能實(shí)現(xiàn)決策者的目標(biāo)？第4章 目標(biāo)規(guī)劃5如果用線性規(guī)劃求解，模型如下：該線性規(guī)劃模型無可行解。0,30053236054200422200233005 .

3、 .503040max321321321321321321321321xxxxxxxxxxxxxxxxxxxxxtsxxxz-6-線性規(guī)劃：單一目標(biāo)，最優(yōu)解目標(biāo)規(guī)劃：多目標(biāo)、優(yōu)先次序、滿意解目標(biāo)規(guī)劃（目標(biāo)規(guī)劃（Goal ProgrammingGoal Programming）研究企業(yè)考慮研究企業(yè)考慮現(xiàn)有的資源條件下，在多個目標(biāo)中去尋求滿意現(xiàn)有的資源條件下，在多個目標(biāo)中去尋求滿意解，使得完成目標(biāo)的總體結(jié)果與事先制定目標(biāo)解，使得完成目標(biāo)的總體結(jié)果與事先制定目標(biāo)的差距最小的差距最小。 目標(biāo)規(guī)劃是按事先制定的目標(biāo)順序進(jìn)行檢查，盡可能使目標(biāo)達(dá)到預(yù)定的目標(biāo)，即使不能達(dá)到目標(biāo)也要使

4、得偏離目標(biāo)的差距最小，也就是求得滿意解滿意解。（1 1） 設(shè)置偏差變量，表明實(shí)際值同目標(biāo)值之間的差異設(shè)置偏差變量，表明實(shí)際值同目標(biāo)值之間的差異d+, d- 分別為正、負(fù)偏差變量, d+表示實(shí)際值超過目標(biāo)值部分； d- 表示實(shí)際值未達(dá)到目標(biāo)值部分；d+ 和 d- 兩者中必定至少有一個為零。（2 2）絕對約束和目標(biāo)約束）絕對約束和目標(biāo)約束絕對約束絕對約束：必須嚴(yán)格滿足的等式約束和不等式約束，也稱硬約束。目標(biāo)約束目標(biāo)約束：允許發(fā)生正或負(fù)偏差，也稱軟約束。第4章 目標(biāo)規(guī)劃7-第4章 目標(biāo)規(guī)劃- 目標(biāo)值d1-d1+實(shí)際值實(shí)際值d1- d1+ =0d1- 0， d1+ 0正偏差變量負(fù)偏差變量（3 3）優(yōu)先

5、因子（優(yōu)先等級）與權(quán)系數(shù)）優(yōu)先因子（優(yōu)先等級）與權(quán)系數(shù) 一個規(guī)劃問題常常有若干目標(biāo)，但決策者在要求達(dá)到這些目標(biāo)時(shí)，是有主次和輕重緩急的不同。要求第一位達(dá)到的目標(biāo)賦予優(yōu)先因子P1，次位的目標(biāo)賦予優(yōu)先因子P2, 規(guī)定PkPk+1，k=1,2, ,K。（4 4）目標(biāo)規(guī)劃的目標(biāo)函數(shù)）目標(biāo)規(guī)劃的目標(biāo)函數(shù) 每當(dāng)一目標(biāo)值確定后，決策者的要求是盡可能縮小偏離目標(biāo)值，因此目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是min Z=f (d+, d- )。其基本形式有三種：恰好達(dá)到目標(biāo)值，正、負(fù)偏差變量都盡可能地小，min Z=f (d+, d- )不超過目標(biāo)值，正偏差變量要盡可能地小，min Z=f (d+)超過目標(biāo)值，負(fù)偏差變量要盡

6、可能地小，min Z=f (d- )第4章 目標(biāo)規(guī)劃9例例4-14-1用目標(biāo)規(guī)劃表示的模型為其滿意解為X=（28，20，30）， d1+ =20， d2- =2， d4-=36， d5+ =16，其余變量為零。 第4章 目標(biāo)規(guī)劃10030053236054200422200233005 . .min32132132155321443213332221113215444332211xxxxxxxxxddxxxddxxxddxddxxddxxxtsdPdPdPdPdPz決策者考慮以下實(shí)際目標(biāo)：利潤不少于3200元產(chǎn)品甲的產(chǎn)量不超過產(chǎn)品乙的產(chǎn)量的1.5倍提高丙的產(chǎn)量達(dá)到30

7、以上設(shè)備加工能力不足時(shí)可以加班，但最好不加班原料只能使用現(xiàn)有的原料。企業(yè)如何制定生產(chǎn)計(jì)劃，才能實(shí)現(xiàn)決策者的目標(biāo)？目標(biāo)規(guī)劃的數(shù)學(xué)模型的一般形式為目標(biāo)規(guī)劃的數(shù)學(xué)模型的一般形式為 其中：Pl為第l級優(yōu)先因子，l=1, ,L; -lk， +lk為分別賦予第l個目標(biāo)約束的正負(fù)偏差變量的權(quán)系數(shù)。gk為第k個目標(biāo)的預(yù)期目標(biāo)值，k=1, ,K。第4章 目標(biāo)規(guī)劃11KkddnjxKkgddxcmibxatsddPzkkjkkknjjkjinjjijKkklkklkLll, 10, 10, 1, 1. .min1111，第4章 目標(biāo)規(guī)劃12 擁有量 原材料(kg) 設(shè)備(hr) 2 1 1 2 11 10 利潤(

8、元/件) 8 10 （1) 根據(jù)市場信息，產(chǎn)品的銷售量有下降的趨勢，故考慮產(chǎn)品的產(chǎn)量不大于產(chǎn)品。(2) 超過計(jì)劃供應(yīng)的原材料時(shí)，需用高價(jià)采購，會使成本大幅度增加(3) 應(yīng)盡可能充分利用設(shè)備臺時(shí)，但不希望加班。 (4) 應(yīng)盡可能達(dá)到并超過計(jì)劃利潤指標(biāo)56元。決策者在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上考慮：首先是產(chǎn)品的產(chǎn)量不低于產(chǎn)品的產(chǎn)量；其次是充分利用設(shè)備有效臺時(shí)，不加班；再次是利潤額不小于56元。求決策方案 。-第4章 目標(biāo)規(guī)劃-13-3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii滿

9、足約束條件：目標(biāo)函數(shù)：u當(dāng)目標(biāo)規(guī)劃問題中只包含兩個決策變量時(shí)，可以用圖解法進(jìn)行求滿意解。目標(biāo)規(guī)劃圖解法的計(jì)算步驟如下目標(biāo)規(guī)劃圖解法的計(jì)算步驟如下：（1）對所有目標(biāo)約束，去掉偏差變量，畫出相應(yīng)直線，然后標(biāo)出偏差變量變化時(shí)直線平移方向。（2）確定第一優(yōu)先級P1級各目標(biāo)的解空間R1。（3）轉(zhuǎn)到下一個優(yōu)先級PJ級個目標(biāo)，確定它的“最佳”解空間RJ。（4）在求解過程中，若解空間 RJ已縮小為一點(diǎn)，則結(jié)束求解過程，因?yàn)榇藭r(shí)已沒有進(jìn)一步改進(jìn)的可能。（5）重復(fù)第（3）步和第（4）步過程，直到解空間縮小為一點(diǎn)，或者所有L個優(yōu)先級都已搜索過，求解過程也告結(jié)束。第4章 目標(biāo)規(guī)劃14例例4-2 4-2 用圖解法求解下

10、列目標(biāo)規(guī)劃問題第4章 目標(biāo)規(guī)劃1511223344112111222123324412min(53)2629242,01 , 2 , 3 , 4iizPdPdPddPdxxddxxddxxddxddxxidd解：所有目標(biāo)約束，去掉偏差變量，畫出相應(yīng)直線，然后標(biāo)出偏差變量變化時(shí)直線平移方向。P1、P2的目標(biāo)實(shí)現(xiàn)后，x1 , x2 的取值范圍為ABCD?？紤]P3的目標(biāo)中 d3- 盡量小的要求后， x1 , x2 的取值范圍縮小為ABEF區(qū)域；然后考慮 ，在ABEF中無法滿足d4- =0,因此只能在ABEF中取一點(diǎn)，使d4- 盡可能小，這就是E點(diǎn)。故E點(diǎn)為滿意解。其坐標(biāo)為（13/2，5/4）。X=X

11、=（ x1 ，x2 ）= =（13/213/2，5/45/4），），Z=9/4 PZ=9/4 P3 3 +3 P+3 P4 4 第4章 目標(biāo)規(guī)劃16-第4章 目標(biāo)規(guī)劃-17-3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii求解線性規(guī)劃的單純形法的過程基本一致，只是在檢驗(yàn)數(shù)處理時(shí)，需要考慮優(yōu)先次序的影響。而且，目標(biāo)規(guī)劃的目標(biāo)函數(shù)是求最小化，所以當(dāng)檢驗(yàn)數(shù)均為大于等于零時(shí)為滿意解。例例4-34-3用單純形法求解例4-2第4章 目標(biāo)規(guī)劃18Step (0):初始單純初始單純形表形表第4章

12、 目標(biāo)規(guī)劃19Step (1):x x2 2 入基，入基，d d4 4- - 出基出基Step (2):d4d4+ + 入基，入基，d d1 1- - 出基出基第4章 目標(biāo)規(guī)劃20Step (3):x x1 1 入基，入基， d d4 4+ +出基出基Step (4):d4d4- - 入基，入基， d d3 3- - 出基出基第第4章 目標(biāo)規(guī)劃21Step (5):d1d1+ + 入基，入基， d d2 2- -出基出基這時(shí)，所有非基變量的檢驗(yàn)數(shù)都大于零，所以有唯一最優(yōu)解。X X* *= =（13/213/2，5/45/4） Z Z* *=9/4P=9/4P3 3+3P+3P4 4例例4-44

13、-4 利用Excel求解目標(biāo)規(guī)劃問題。某工廠要生產(chǎn)兩種新產(chǎn)品：門和窗。生產(chǎn)所需的時(shí)間如下表所示。根據(jù)經(jīng)市場調(diào)查得到的該兩種新產(chǎn)品的市場需求狀況可以確定，按當(dāng)前的定價(jià)可確保所有新產(chǎn)品均能銷售出去。問該工廠如何安排這兩種新產(chǎn)品的生產(chǎn)計(jì)劃，可使總利潤最大？其最優(yōu)解為：X*=（ x1 ，x2 ）=（2，6） Z*=3600第4章 目標(biāo)規(guī)劃22車間車間單位產(chǎn)品的生產(chǎn)時(shí)間單位產(chǎn)品的生產(chǎn)時(shí)間每周可以獲得的每周可以獲得的生產(chǎn)時(shí)間（小時(shí)）生產(chǎn)時(shí)間（小時(shí)）門門窗窗11042021233218單位利潤（元）300500現(xiàn)在工廠領(lǐng)導(dǎo)要考慮市場等一系列其他因素，提出如下目標(biāo)：（1）根據(jù)市場信息，窗的銷售量有下降的趨勢，

14、故希望窗的產(chǎn)量不超過門的2倍；(希望)（2）由于車間3有另外新的生產(chǎn)任務(wù),因此希望車間3節(jié)省4個工時(shí)用于新的生產(chǎn)任務(wù);(希望)（3）應(yīng)盡可能達(dá)到并超過計(jì)劃的每周利潤3000元。 （希望）第4章 目標(biāo)規(guī)劃23則目標(biāo)規(guī)劃模型為：11222331212211112Min z()4 212 3218 s.t.20 32PdP ddPdxxxxxxddxx2212331214 3005003000,0,0 (1,2,3)iiddxxddx xddiExcel電子表格求解目標(biāo)規(guī)劃是按照優(yōu)先級漸進(jìn)的。假設(shè)三個目標(biāo)優(yōu)先級依次為（1）（2）（3）。由于有三個目標(biāo)優(yōu)先級（P1，P2，P3），所以要分三步完成：第1

15、步：首先保證P1級目標(biāo)的實(shí)現(xiàn)，這時(shí)不考慮其他次級目標(biāo)。優(yōu)先級1的數(shù)學(xué)模型為：第4章 目標(biāo)規(guī)劃2411121221111222123312112233M in z42123218s.t.2032143005003000,0dxxxxxxddxxddxxddxxdddddd第4章 目標(biāo)規(guī)劃25第2步：在保證P1級目標(biāo)實(shí)現(xiàn)的基礎(chǔ)上考慮P2級目標(biāo)。優(yōu)先級2的數(shù)學(xué)模型為：第4章 目標(biāo)規(guī)劃262221212211112221233112112233M in z4212321820s.t. 321430050030000,0ddxxxxxxddxxddxxdddxxdddddd第4章 目標(biāo)規(guī)劃27第3步：在保證P1級和P2級目標(biāo)實(shí)現(xiàn)的基礎(chǔ)上考慮P3級目標(biāo)。優(yōu)先級3的數(shù)學(xué)模型為：第4章 目標(biāo)規(guī)劃2833121221111222123312212112233M in z421 2321