多目標(biāo)動態(tài)優(yōu)化

1、系統(tǒng)分析方法系統(tǒng)分析方法秦華鵬秦華鵬北京大學(xué)深圳研究生院北京大學(xué)深圳研究生院 環(huán)境與城市學(xué)院環(huán)境與城市學(xué)院Office: E414 Tel: 26035291(O) Mobile:mail: 2006年年3月月第第6講講 多目標(biāo)、動態(tài)優(yōu)化多目標(biāo)、動態(tài)優(yōu)化一一 多目標(biāo)優(yōu)化多目標(biāo)優(yōu)化二二 目標(biāo)規(guī)劃目標(biāo)規(guī)劃三三 動態(tài)優(yōu)化動態(tài)優(yōu)化一一 多目標(biāo)優(yōu)化多目標(biāo)優(yōu)化多目標(biāo)優(yōu)化模型多目標(biāo)優(yōu)化模型多目標(biāo)優(yōu)化解的性質(zhì)多目標(biāo)優(yōu)化解的性質(zhì)多目標(biāo)優(yōu)化技術(shù)簡介多目標(biāo)優(yōu)化技術(shù)簡介1.1 多目標(biāo)優(yōu)化模型多目標(biāo)優(yōu)化模型決策變量決策變量lX（x1，x2， xn）目標(biāo)函數(shù)目標(biāo)函數(shù)lZF(x1，x2， xn)約

2、束條件約束條件lg1(x1，x2， xn) ll gm(x1，x2， xn),.,()(21nXXXFZMinMaxmnmnnbXXXgbXXXgbXXXg或或或,),.,(. .,),.,(,),.,(2122121211系統(tǒng)優(yōu)化模型一般形式系統(tǒng)優(yōu)化模型一般形式單目標(biāo)優(yōu)化與多目標(biāo)優(yōu)化單目標(biāo)優(yōu)化與多目標(biāo)優(yōu)化單目標(biāo)優(yōu)化：單目標(biāo)優(yōu)化： max(min)Z=f (x1，x2，xn) 系統(tǒng)期望達到的目標(biāo)可用一個函數(shù)來表達系統(tǒng)期望達到的目標(biāo)可用一個函數(shù)來表達多目標(biāo)優(yōu)化：多目標(biāo)優(yōu)化： max(min)Z1=f1 (x1，x2，xn) max(min)Z 2 =f 2(x1，x2，xn) max(min)Z

3、 m =f m(x1，x2，xn) 系統(tǒng)期望達到的系統(tǒng)期望達到的m個目標(biāo)應(yīng)該分別用個目標(biāo)應(yīng)該分別用m個函數(shù)來表達個函數(shù)來表達線性多目標(biāo)優(yōu)化線性多目標(biāo)優(yōu)化如果多目標(biāo)優(yōu)化問題的所有目標(biāo)和約束條件都可如果多目標(biāo)優(yōu)化問題的所有目標(biāo)和約束條件都可用線性方程來表達，則為線性多目標(biāo)問題，其目用線性方程來表達，則為線性多目標(biāo)問題，其目標(biāo)函數(shù)可表達為：標(biāo)函數(shù)可表達為：nnmmmmnnnnxcxcxcXfxcxcxcXfxcxcxcXf22112222121212121111)(max(min)(max(min)(max(min)1.2 多目標(biāo)優(yōu)化問題解的性質(zhì)多目標(biāo)優(yōu)化問題解的性質(zhì) 單目標(biāo)問題中，各種方案的目標(biāo)函

4、數(shù)值具有可比性，單目標(biāo)問題中，各種方案的目標(biāo)函數(shù)值具有可比性，可以分出優(yōu)劣，因此一般存在最優(yōu)解可以分出優(yōu)劣，因此一般存在最優(yōu)解多目標(biāo)問題中，對某個目標(biāo)的多目標(biāo)問題中，對某個目標(biāo)的“優(yōu)化優(yōu)化”可能導(dǎo)致其可能導(dǎo)致其它目標(biāo)的它目標(biāo)的“劣化劣化” ，因此，一般不存在能夠同時，因此，一般不存在能夠同時滿足各個目標(biāo)最優(yōu)化的最優(yōu)解滿足各個目標(biāo)最優(yōu)化的最優(yōu)解多目標(biāo)優(yōu)化問題的求解，除了要多目標(biāo)優(yōu)化問題的求解，除了要“優(yōu)化優(yōu)化”單個目標(biāo)單個目標(biāo)本身，還要本身，還要平衡平衡各個目標(biāo)間的關(guān)系，因此，多目標(biāo)各個目標(biāo)間的關(guān)系，因此，多目標(biāo)優(yōu)化問題的解是優(yōu)化問題的解是經(jīng)過各目標(biāo)權(quán)衡后相對滿意的方案經(jīng)過各目標(biāo)權(quán)衡后相對滿意的

5、方案1.3 多目標(biāo)規(guī)劃求解技術(shù)簡介多目標(biāo)規(guī)劃求解技術(shù)簡介 一般思路為：采取某種方式，一般思路為：采取某種方式，平衡平衡各個目各個目標(biāo)間的關(guān)系，將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為標(biāo)間的關(guān)系，將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為單單目標(biāo)規(guī)劃目標(biāo)規(guī)劃問題去處理。問題去處理。平衡平衡的技術(shù)有：的技術(shù)有：v效用最優(yōu)化模型效用最優(yōu)化模型v罰款模型罰款模型v目標(biāo)規(guī)劃模型目標(biāo)規(guī)劃模型v約束模型約束模型v （1）效用最優(yōu)化模型）效用最優(yōu)化模型按一定方式，將一系列的目標(biāo)函數(shù)與效用按一定方式，將一系列的目標(biāo)函數(shù)與效用函數(shù)建立相關(guān)關(guān)系，對各效用函數(shù)加權(quán)求函數(shù)建立相關(guān)關(guān)系，對各效用函數(shù)加權(quán)求和，以該和函數(shù)作為的單目標(biāo)規(guī)劃問題的和，以該和函數(shù)作為

6、的單目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)目標(biāo)函數(shù)目標(biāo)函數(shù)目標(biāo)函數(shù)fi (X)效用函數(shù)效用函數(shù)i (X)kiii1max式中，式中，是與各目標(biāo)函數(shù)相關(guān)的效用函數(shù)的和函是與各目標(biāo)函數(shù)相關(guān)的效用函數(shù)的和函數(shù)；數(shù)；權(quán)值權(quán)值i來反映原問題中各目標(biāo)函數(shù)在總體目來反映原問題中各目標(biāo)函數(shù)在總體目標(biāo)中的權(quán)重，滿足：標(biāo)中的權(quán)重，滿足：kii11minmaxminiiiiffffi指標(biāo)的最大和最小值分別為iiifffniminmax, 2, 1minmaxmaxjjjjffffj指標(biāo)的最大和最小值分別為jjjfffnjminmax, 2, 12,max211,max,1,1,12maxmin122maxmin11jfffjjff

7、fjfffjjjjjj為指標(biāo)的最佳穩(wěn)定區(qū)間指標(biāo)的最大和最小值分別為, 2, 121minmaxjjjfffnj（2）罰款模型）罰款模型如果對每一個目標(biāo)函數(shù)，決策者都能提出如果對每一個目標(biāo)函數(shù)，決策者都能提出一個一個期望值期望值（或稱滿意值（或稱滿意值）f *i ，那么，可，那么，可通過比較實際值與期望值通過比較實際值與期望值 f *i 之間的偏差之間的偏差來構(gòu)造單目標(biāo)問題。來構(gòu)造單目標(biāo)問題。在上式中，在上式中，i 是與第是與第i個目標(biāo)函數(shù)相關(guān)的權(quán)重個目標(biāo)函數(shù)相關(guān)的權(quán)重（3）目標(biāo)規(guī)劃模型）目標(biāo)規(guī)劃模型 目標(biāo)規(guī)劃模型與罰款模型類似，它也需要目標(biāo)規(guī)劃模型與罰款模型類似，它也需要預(yù)先確定各個目標(biāo)的期望

8、值預(yù)先確定各個目標(biāo)的期望值 f *i （4）約束模型）約束模型 如果規(guī)劃問題的某一目標(biāo)可以給出一個可如果規(guī)劃問題的某一目標(biāo)可以給出一個可供選擇的范圍，則該目標(biāo)就可以作為約束供選擇的范圍，則該目標(biāo)就可以作為約束條件而被排除出目標(biāo)組，進入約束條件組條件而被排除出目標(biāo)組，進入約束條件組中中假如，除了第一個目標(biāo)外，其余目標(biāo)都可假如，除了第一個目標(biāo)外，其余目標(biāo)都可以提出一個可供選的范圍，則：以提出一個可供選的范圍，則：max(minZ)=f1(x1,x2,xn) 二二 目標(biāo)規(guī)劃目標(biāo)規(guī)劃目標(biāo)規(guī)劃由線性規(guī)劃發(fā)展演變而來目標(biāo)規(guī)劃由線性規(guī)劃發(fā)展演變而來處理多目標(biāo)問題的簡單實用的方法處理多目標(biāo)問題的簡單實用的方法

9、目標(biāo)規(guī)劃與線性規(guī)劃問題的對比目標(biāo)規(guī)劃與線性規(guī)劃問題的對比目標(biāo)規(guī)劃問題的數(shù)學(xué)模型目標(biāo)規(guī)劃問題的數(shù)學(xué)模型目標(biāo)規(guī)劃求解方法目標(biāo)規(guī)劃求解方法案例分析案例分析2.1 目標(biāo)規(guī)劃與線性規(guī)劃問題的對比目標(biāo)規(guī)劃與線性規(guī)劃問題的對比線性規(guī)劃線性規(guī)劃v單單目標(biāo)問題目標(biāo)問題v目標(biāo)值目標(biāo)值待求待求v追求目標(biāo)的追求目標(biāo)的最優(yōu)值最優(yōu)值（最大或最?。ㄗ畲蠡蜃钚。┠繕?biāo)規(guī)劃目標(biāo)規(guī)劃v單單或或多多目標(biāo)問題目標(biāo)問題v目標(biāo)值（理想值、期望值）目標(biāo)值（理想值、期望值）已知已知v追求追求盡可能接近盡可能接近理想值的解理想值的解滿意解滿意解例例1某廠生產(chǎn)甲、乙兩種產(chǎn)品，已知單件生產(chǎn)所某廠生產(chǎn)甲、乙兩種產(chǎn)品，已知單件生產(chǎn)所需工時、可用工時數(shù)

10、、及單件收益需工時、可用工時數(shù)、及單件收益 甲產(chǎn)品甲產(chǎn)品 乙產(chǎn)品乙產(chǎn)品 可用工時可用工時金工工時金工工時 4 2 400裝配工時裝配工時 2 4 500收益收益/件件 100 80 （1）從）從線性規(guī)劃線性規(guī)劃角度考慮角度考慮LP： maxZ=100X1 + 80X2 2X1+4X2 5004X1+2X2 400X1 , X2 0 X* =(50,100) Z* =13000 目標(biāo)：在現(xiàn)有資源條件下，追求最大收益目標(biāo)：在現(xiàn)有資源條件下，追求最大收益（2）從）從目標(biāo)規(guī)劃目標(biāo)規(guī)劃角度考慮角度考慮理想值理想值理想值（期望值）：去年總收益理想值（期望值）：去年總收益9000，期望增長期望增長11.1%

11、，即希望今年總收益達即希望今年總收益達到到10000v理想值已經(jīng)確定理想值已經(jīng)確定v允許計算值（決策值）小于或大于理想值允許計算值（決策值）小于或大于理想值v希望計算值與理想值之間的（負）差別盡希望計算值與理想值之間的（負）差別盡可能小可能?。?）從）從目標(biāo)規(guī)劃目標(biāo)規(guī)劃角度考慮角度考慮正、負偏差正、負偏差計算值與理想值之間三種可能：計算值與理想值之間三種可能：v計算值計算值理想值，超過，理想值，超過， d- = 0v計算值計算值=理想值，相等，理想值，相等， d+ = d- =0因此：因此：d+ * d- = 0 d+，d- 0 引入正、負偏差變量引入正、負偏差變量d+、d-vd+：計算值：計

12、算值超過超過理想值部分理想值部分(正偏差變量正偏差變量)vd-：計算值：計算值不足不足理想值部分理想值部分(負偏差變量負偏差變量)100X1+80X2 -d+d- =10000（2）從）從目標(biāo)規(guī)劃目標(biāo)規(guī)劃角度考慮角度考慮絕對約束與目標(biāo)約束絕對約束與目標(biāo)約束絕對約束：絕對約束：必須嚴(yán)格滿足的條件，不能滿必須嚴(yán)格滿足的條件，不能滿足絕對約束的解即為非可行解足絕對約束的解即為非可行解目標(biāo)約束：目標(biāo)約束：目標(biāo)規(guī)劃所特有的一種約束，目標(biāo)規(guī)劃所特有的一種約束，以目標(biāo)的以目標(biāo)的理想值作為約束方程右端常數(shù)項理想值作為約束方程右端常數(shù)項，不必嚴(yán)格滿足，允許發(fā)生正負偏差。不必嚴(yán)格滿足，允許發(fā)生正負偏差。4X1+2

13、X2 4002X1+4X2 500100X1+80X2 -d+d- =10000（2）從）從目標(biāo)規(guī)劃目標(biāo)規(guī)劃角度考慮角度考慮目標(biāo)函數(shù)目標(biāo)函數(shù)因為希望：因為希望：100X1+80X2 -d+d- =10000100X1+80X2 10000也就是希望：也就是希望：d- 0目標(biāo)函數(shù)為：目標(biāo)函數(shù)為：minZ= d- （2）例）例1的目標(biāo)規(guī)劃模型的目標(biāo)規(guī)劃模型GP：Min Z= d-100X1+80X2 -d+d- =100004X1+2X2 4002X1+4X2 500X1 , X2 , d- , d+ 0 d+ * d- =0LP：Max Z=100X1 + 80X2 2X1+4X2 5004X1

14、+2X2 400X1 , X2 02.2 目標(biāo)規(guī)劃問題的數(shù)學(xué)模型目標(biāo)規(guī)劃問題的數(shù)學(xué)模型案例介紹案例介紹絕對約束與目標(biāo)約束絕對約束與目標(biāo)約束目標(biāo)函數(shù)目標(biāo)函數(shù)目標(biāo)優(yōu)先級目標(biāo)優(yōu)先級目標(biāo)權(quán)因子目標(biāo)權(quán)因子小節(jié)小節(jié)例例2某工廠生產(chǎn)某工廠生產(chǎn)I、II兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需要的原材料及占用設(shè)備臺時、每天擁有的設(shè)備臺要的原材料及占用設(shè)備臺時、每天擁有的設(shè)備臺時、原材料最大供應(yīng)量、單件產(chǎn)品可獲利潤。時、原材料最大供應(yīng)量、單件產(chǎn)品可獲利潤。 I III II 資源擁有量資源擁有量原材料原材料(公斤公斤) 2 1 11設(shè)備設(shè)備(小時小時) 1 2 10利潤利潤(千元千元/件件) 8 10

15、 工廠在安排生產(chǎn)計劃的考慮工廠在安排生產(chǎn)計劃的考慮原材料情況：計劃使用原材料不能超過擁有量；原材料情況：計劃使用原材料不能超過擁有量；市場情況：產(chǎn)品市場情況：產(chǎn)品銷售量有下降趨勢，期望產(chǎn)銷售量有下降趨勢，期望產(chǎn)品品的產(chǎn)量不超過產(chǎn)品的產(chǎn)量不超過產(chǎn)品的產(chǎn)量。的產(chǎn)量。期望充分利用設(shè)備，但不希望加班。期望充分利用設(shè)備，但不希望加班。期望達到利潤計劃指標(biāo)期望達到利潤計劃指標(biāo)56千元。千元。2X1+X2 11X1 -X2 0X1 +2X2 =108X1 +10X2 56（1）絕對約束與目標(biāo)約束）絕對約束與目標(biāo)約束2X1+X2 11X1 -X2 +d1- -d1+=0X1 +2X2 +d2- -d2+=10

16、8X1 +10X2 +d3- -d3+=56X1 , X2 , di- , di+ 0 di- . di+ =0d1- : X1產(chǎn)量不足產(chǎn)量不足X2 部分部分d1+ : X1產(chǎn)量超過產(chǎn)量超過X2 部分部分d2- : 設(shè)備使用不足設(shè)備使用不足10 部分部分d2+ :設(shè)備使用超過設(shè)備使用超過10 部分部分d3- : 利潤不足利潤不足56 部分部分d3+ :利潤超過利潤超過56 部分部分設(shè)設(shè)X1 ，X2為產(chǎn)品為產(chǎn)品，產(chǎn)品，產(chǎn)品產(chǎn)量。產(chǎn)量。（2）目標(biāo)函數(shù)市場情況：產(chǎn)品市場情況：產(chǎn)品銷售量有下降趨勢，期望產(chǎn)銷售量有下降趨勢，期望產(chǎn)品品的產(chǎn)量不超過產(chǎn)品的產(chǎn)量不超過產(chǎn)品的產(chǎn)量。的產(chǎn)量。期望充分利用設(shè)備，但盡

17、可能不加班。期望充分利用設(shè)備，但盡可能不加班。期望達到利潤計劃指標(biāo)期望達到利潤計劃指標(biāo)56千元。千元。X1 -X2 0X1 +2X2 =108X1 +10X2 56X1 -X2 +d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +10X2 +d3- -d3+=56minZ1 = d1+minZ2 = d2- +d2+minZ3 = d3- （3）優(yōu)先級）優(yōu)先級在目標(biāo)規(guī)劃中，多個目標(biāo)之間往往有主次、在目標(biāo)規(guī)劃中，多個目標(biāo)之間往往有主次、緩急之區(qū)別緩急之區(qū)別v凡要求首先達到的目標(biāo)，賦予優(yōu)先級凡要求首先達到的目標(biāo)，賦予優(yōu)先級 p1v凡要求第二位達到的目標(biāo)，賦予優(yōu)先級凡要求第二位達

18、到的目標(biāo)，賦予優(yōu)先級 p2v優(yōu)化規(guī)則優(yōu)化規(guī)則v只有完成了高級別的優(yōu)化后，再考慮低級別的優(yōu)只有完成了高級別的優(yōu)化后，再考慮低級別的優(yōu)化化v再進行低級別的優(yōu)化時，不能破壞高級別以達到再進行低級別的優(yōu)化時，不能破壞高級別以達到的優(yōu)化值的優(yōu)化值（4）權(quán)因子）權(quán)因子在同一優(yōu)先級中有幾個不同的偏差變量要求在同一優(yōu)先級中有幾個不同的偏差變量要求極小，而這幾個偏差變量之間重要性又有區(qū)極小，而這幾個偏差變量之間重要性又有區(qū)別別可用可用“權(quán)因子權(quán)因子”來區(qū)分同一優(yōu)先級中來區(qū)分同一優(yōu)先級中不同偏差變量重要性不同，如不同偏差變量重要性不同，如 p p2 2（2 2d d2 2- - + d+ d2 2+ +） 表示表

19、示d d2 2- - 的重要程度為的重要程度為d d2 2+ + 的兩倍，的兩倍，表明表明 “ “充分利用設(shè)備充分利用設(shè)備”的愿望的愿望 “不希望加班不希望加班”的的愿望愿望權(quán)因子的數(shù)值一般需要分析者與決策者商討權(quán)因子的數(shù)值一般需要分析者與決策者商討確定確定例例2的多目標(biāo)規(guī)劃模型的多目標(biāo)規(guī)劃模型minZ=P1d1+P2(2d2-+d2+)+P3(d3-)2X1+X2 11X1 -X2 +d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +10X2 +d3- -d3+=56X1 , X2 , di- , di+ 0 小結(jié)小結(jié)1）約束條件）約束條件v硬約束硬約束(絕對約束絕對約束

20、)v軟約束軟約束 (目標(biāo)約束目標(biāo)約束)，引入，引入d -, d +2）目標(biāo)優(yōu)先級與權(quán)因子）目標(biāo)優(yōu)先級與權(quán)因子vP1 P2 PLv同一級中可以有若干個目標(biāo)：同一級中可以有若干個目標(biāo)：P21 , P22 ,P23 v其重要程度用權(quán)重系數(shù)其重要程度用權(quán)重系數(shù)W21 ,W22 ,W23 表示表示目標(biāo)規(guī)劃的基本思想是，給定若干目標(biāo)以及實現(xiàn)目標(biāo)規(guī)劃的基本思想是，給定若干目標(biāo)以及實現(xiàn)這些目標(biāo)的優(yōu)先順序，在有限的資源條件下，使這些目標(biāo)的優(yōu)先順序，在有限的資源條件下，使總的偏離目標(biāo)值的偏差最小總的偏離目標(biāo)值的偏差最小小結(jié)小結(jié)期望期望目標(biāo)函數(shù)目標(biāo)函數(shù)fi(X) =gi 恰好達到目標(biāo)恰好達到目標(biāo)minZ= f (d

21、 -+d+)fi(X) =gi 超過目標(biāo)超過目標(biāo)minZ= f (d -)fi(X) gi 不超過目標(biāo)不超過目標(biāo)minZ= f (d+)3）目標(biāo)函數(shù)（準(zhǔn)則函數(shù)）目標(biāo)函數(shù)（準(zhǔn)則函數(shù)）對目標(biāo)約束：對目標(biāo)約束：fi(X) +di- -di+=gi小結(jié)小結(jié)目標(biāo)函數(shù)的實質(zhì)：目標(biāo)函數(shù)的實質(zhì)：求一組決策變量的滿意值，求一組決策變量的滿意值，使決策結(jié)果與給定目標(biāo)總偏差最小。使決策結(jié)果與給定目標(biāo)總偏差最小。目標(biāo)函數(shù)的特點：目標(biāo)函數(shù)的特點：v目標(biāo)函數(shù)中只有偏差變量目標(biāo)函數(shù)中只有偏差變量v目標(biāo)函數(shù)總是求偏差變量最小目標(biāo)函數(shù)總是求偏差變量最小目標(biāo)函數(shù)值的含義目標(biāo)函數(shù)值的含義：vZ=0：各級目標(biāo)均已達到：各級目標(biāo)均已達

22、到vZ0：部分目標(biāo)未達到部分目標(biāo)未達到一般模型一般模型 KkddnjxKkqddxCkmibxadwdwPdwdwPZkkjnjkkkjjnjijijkkkLkkLkLkkkkkk10,1011,min11111112.3 目標(biāo)規(guī)劃的求解方法目標(biāo)規(guī)劃的求解方法序貫式算法序貫式算法 一種分解的算法，根據(jù)優(yōu)先級的先后次一種分解的算法，根據(jù)優(yōu)先級的先后次序，將原多目標(biāo)問題分解為一系列傳統(tǒng)的序，將原多目標(biāo)問題分解為一系列傳統(tǒng)的單目標(biāo)線性規(guī)劃問題，然后依次求解。單目標(biāo)線性規(guī)劃問題，然后依次求解。（1）序貫式算法的思路）序貫式算法的思路令令i=1，建立僅含建立僅含p1級目標(biāo)的線性規(guī)劃單目標(biāo)級目標(biāo)的線性規(guī)劃

23、單目標(biāo)模型：模型：min Z 1 (D-，D+)；利用單純形法求解利用單純形法求解 pi 級單目標(biāo)規(guī)劃，得到級單目標(biāo)規(guī)劃，得到min Z i (D-，D+) = Z*i令令i= i +1，建立僅含建立僅含 pi 級目標(biāo)的線性規(guī)劃單目標(biāo)級目標(biāo)的線性規(guī)劃單目標(biāo)模型：模型：min Z i =Z i (D-，D+)；同時考慮所有比同時考慮所有比 pi 高級別目標(biāo)相應(yīng)的約束條件高級別目標(biāo)相應(yīng)的約束條件；還要增加約束條件：還要增加約束條件： Z s(D-，D+) = Z*s s = 1, 2, i-1轉(zhuǎn)第轉(zhuǎn)第2步，直到考慮完所有級別目標(biāo)步，直到考慮完所有級別目標(biāo)第第1步：構(gòu)造步：構(gòu)造P1級目標(biāo)構(gòu)成的單目標(biāo)

24、線性級目標(biāo)構(gòu)成的單目標(biāo)線性minZ= P1d1+P2(2d2-+d2+)+P3(d3-)2X1+X2 11X1 -X2 +d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +10X2 +d3- -d3+=56X1 , X2 , di- , di+ 0 minZ1=d1+2X1+X2 11X1 -X2 +d1- -d1+=0在P1級只包含d1+ ，因此只取含有d1+的約束條件；絕對約束絕對約束第第2步步 求解求解 P1級單目標(biāo)規(guī)劃級單目標(biāo)規(guī)劃minZ1=d1+2X1+X2 11X1 -X2 +d1- -d1+=0計算結(jié)果：Min Z 1(D-，D+) = d1+ =0 第3步：

25、構(gòu)造P2級目標(biāo)構(gòu)成的單目標(biāo)線性上一級目標(biāo)所應(yīng)滿足的約束條件上一級目標(biāo)所應(yīng)滿足的約束條件本級目標(biāo)所應(yīng)滿足本級目標(biāo)所應(yīng)滿足的約束條件的約束條件為保證優(yōu)化時為保證優(yōu)化時P2，不破壞，不破壞P1的的最優(yōu)值而增加的約束條件最優(yōu)值而增加的約束條件minZ= P1d1+P2(2d2-+d2+)+P3(d3-)2X1+X2 11X1 -X2 +d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +10X2 +d3- -d3+=56X1 , X2 , di- , di+ 0 minZ2= 2d2-+d2+2X1+X2 11X1 -X2 +d1- -d1+=0X1 +2X2 +d2- -d2+=1

26、0d1+ =0minZ2= 2d2-+d2+2X1+X2 11X1 -X2 +d1- -d1+=0X1 +2X2 +d2- -d2+=10d1+ =0第4步：求解 P2級單目標(biāo)規(guī)劃minZ2= 2d2-+d2+2X1+X2 11X1 -X2 +d1- -d1+=0X1 +2X2 +d2- -d2+=10d1+ =0計算結(jié)果： Min Z 2(D-，D+) = 2d2-+d2+ =0 第5步：構(gòu)造P3級目標(biāo)構(gòu)成的單目標(biāo)線性minZ3= d3-2X1+X2 11X1 -X2 +d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +10X2 +d3- -d3+=56d1+ =02d2

27、-+d2+ =0較低級目標(biāo)所應(yīng)滿足的約束條件較低級目標(biāo)所應(yīng)滿足的約束條件本級目標(biāo)所應(yīng)滿足本級目標(biāo)所應(yīng)滿足的約束條件的約束條件為保證優(yōu)化時為保證優(yōu)化時P2，不破壞，不破壞P1的的最優(yōu)值而增加的約束條件最優(yōu)值而增加的約束條件minZ= P1d1+P2(2d2-+d2+)+P3(d3-)2X1+X2 11X1 -X2 +d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +10X2 +d3- -d3+=56X1 , X2 , di- , di+ 0 第6步： 求解 P3級單目標(biāo)規(guī)劃minZ3= d3-2X1+X2 11X1 -X2 +d1- -d1+=0X1 +2X2 +d2- -d

28、2+=108X1 +10X2 +d3- -d3+=56d1+ =02d2-+d2+ =0計算結(jié)果： Min Z 3(D-，D+) = 0 例例2結(jié)論結(jié)論Variable Valued3- 0.0 x1 2.0 x2 4.0d1- 0.0d1+ 0.0d2- 0.0d2+ 0.0d3+ 0.0Min Z 1(D-，D+) = d1+ =0，第，第1優(yōu)先級：優(yōu)先級：期望產(chǎn)品期望產(chǎn)品的產(chǎn)量不超過產(chǎn)品的產(chǎn)量不超過產(chǎn)品的產(chǎn)量的產(chǎn)量，得到滿足！得到滿足！Min Z 2(D-，D+) = 2d2-+d2+ =0，第，第2優(yōu)先優(yōu)先級：期望充分利用設(shè)備，但盡可能不加班，級：期望充分利用設(shè)備，但盡可能不加班，得到

29、滿足！得到滿足！Min Z3 (D-，D+) = d3- = 0，第第3優(yōu)先級：優(yōu)先級：期望達到利潤計劃指標(biāo)期望達到利潤計劃指標(biāo)56千元千元,得到得到滿足滿足vminZ= P1d1+P2(2d2-+d2+)+P3(d3-) = 0三三 動態(tài)規(guī)劃動態(tài)規(guī)劃動態(tài)規(guī)劃引論動態(tài)規(guī)劃引論動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本方程動態(tài)規(guī)劃的基本方程舉例舉例3.1 動態(tài)規(guī)劃引論動態(tài)規(guī)劃引論從案例說起從案例說起多階段決策問題與動態(tài)規(guī)劃多階段決策問題與動態(tài)規(guī)劃最短路徑問題最短路徑問題從從A 地到地到D 地要鋪設(shè)一條煤氣管道地要鋪設(shè)一條煤氣管道,其中需其中需經(jīng)過兩級中間站，兩點之間的連線上的數(shù)經(jīng)過兩級中

30、間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？路線，使總距離最短？AB1B2C1C2C3D24333321114機器負荷問題機器負荷問題某種機器可以在高低兩種不同的負荷下進行生產(chǎn)：某種機器可以在高低兩種不同的負荷下進行生產(chǎn)：在高負荷下生產(chǎn)時在高負荷下生產(chǎn)時，機器的年完好率為，機器的年完好率為70%70%，且，且，產(chǎn)品的年產(chǎn)量產(chǎn)品的年產(chǎn)量=8=8* *投入生產(chǎn)的機器數(shù)量投入生產(chǎn)的機器數(shù)量在低負荷下生產(chǎn)時在低負荷下生產(chǎn)時，機器的年完好率為，機器的年完好率為90%90%，且，且，產(chǎn)品的年產(chǎn)量產(chǎn)品的年產(chǎn)量=5=5* *投入生產(chǎn)的機

31、器數(shù)量投入生產(chǎn)的機器數(shù)量假定開始生產(chǎn)時完好的機器數(shù)量為假定開始生產(chǎn)時完好的機器數(shù)量為10001000要求制定一個五年計劃要求制定一個五年計劃, ,在在每年開始時決定機器在每年開始時決定機器在兩種不同負荷下生產(chǎn)的數(shù)量兩種不同負荷下生產(chǎn)的數(shù)量，使五年內(nèi)產(chǎn)品的總，使五年內(nèi)產(chǎn)品的總產(chǎn)量最高。產(chǎn)量最高。多階段決策問題與動態(tài)規(guī)劃多階段決策問題與動態(tài)規(guī)劃以上兩個問題都可以劃分為多個決策階段。以上兩個問題都可以劃分為多個決策階段。多階段決策問題：多階段決策問題：系統(tǒng)運行過程中可劃分為若干相繼系統(tǒng)運行過程中可劃分為若干相繼的的“階段階段”，每個階段都要進行決策，并使整個過程，每個階段都要進行決策，并使整個過程達

32、到最優(yōu)的一類問題。達到最優(yōu)的一類問題。階段：階段：階段按時間、空間或其它特征劃分，且各階段階段按時間、空間或其它特征劃分，且各階段相互聯(lián)系，某階段的結(jié)束是下一階段起始相互聯(lián)系，某階段的結(jié)束是下一階段起始問題的特征問題的特征：某階段的最優(yōu)策略，而對下一階段未必：某階段的最優(yōu)策略，而對下一階段未必最有利。為使整個過程效果最優(yōu)，必須將每階段作為最有利。為使整個過程效果最優(yōu)，必須將每階段作為整個決策鏈的一環(huán)，從整體考慮。整個決策鏈的一環(huán)，從整體考慮。動態(tài)規(guī)劃：動態(tài)規(guī)劃：用來多階段決策過程優(yōu)化的一種數(shù)量方法。用來多階段決策過程優(yōu)化的一種數(shù)量方法。12n狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)狀態(tài)狀態(tài)決策

33、決策3.2 動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本原理上世紀(jì)上世紀(jì)50年代，美國數(shù)學(xué)家貝爾曼提出年代，美國數(shù)學(xué)家貝爾曼提出解決多階段決策問題的解決多階段決策問題的“最優(yōu)性原理最優(yōu)性原理”假設(shè)采取了最優(yōu)策略，得到某個系統(tǒng)運動假設(shè)采取了最優(yōu)策略，得到某個系統(tǒng)運動的最優(yōu)軌線，該最優(yōu)軌線將的最優(yōu)軌線，該最優(yōu)軌線將s（起點）和（起點）和t（終點）連接。若在最優(yōu)軌線上取一點（終點）連接。若在最優(yōu)軌線上取一點k，則子軌線則子軌線k-s也是最優(yōu)的。也是最優(yōu)的。最優(yōu)策略的一部分也是最優(yōu)的最優(yōu)策略的一部分也是最優(yōu)的 s i j k q r t 最優(yōu)性原理的應(yīng)用最優(yōu)性原理的應(yīng)用從從A 地到地到D 地要鋪設(shè)一條煤氣管道地要

34、鋪設(shè)一條煤氣管道,其中需其中需經(jīng)過兩級中間站，兩點之間的連線上的數(shù)經(jīng)過兩級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？路線，使總距離最短？AB1B2C1C2C3D24333321114 解：整個計算過程分三個階段，從最后一個階段開始。解：整個計算過程分三個階段，從最后一個階段開始。 第一階段（第一階段（C D）：）： C 有三條路線到終點有三條路線到終點DAB1B2C1C2C3D24333321114DC1C2C3顯然有顯然有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4 sfkk

35、第第k階段從階段從Sk 到終點最短距離到終點最短距離第二階段（第二階段（B1 C）：）： B1 到到C有三條路線。有三條路線。 d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為最短路線為B1C1 D) d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = mi

36、n 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 5第二階段（第二階段（B2 C）：）： B2到到C有三條路線。有三條路線。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為最短路線為B2C1 D)第三階段（第三階段（ A B ）：）： A 到到B 有二條路線。有二條路線。 f3(A)1 = d(A, B1 ) f2 ( B1 ) 246 f3 (A)2 = d(A, B2 ) f2 ( B2 ) 437 f3 (A) = min = min6,7=6d(A, B1 ) f2 ( B1 )d(A, B2 ) f2 ( B2

37、 )AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為最短路線為AB1C1 D)3.33.3動態(tài)規(guī)劃的基本方程動態(tài)規(guī)劃的基本方程基本概念基本概念動態(tài)規(guī)劃基本方程動態(tài)規(guī)劃基本方程動態(tài)規(guī)劃的步驟動態(tài)規(guī)劃的步驟3.2.1基本概念基本概念階段階段狀態(tài)與狀態(tài)變量狀態(tài)與狀態(tài)變量決策決策策略策略狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù)（1）階段階段階段（階段（stage）把所研究的決策問題，按先）把所研究的決策問題，按先后順序劃分為若干相互聯(lián)系的決策步驟，后順序劃分為若干相互聯(lián)系的決策步驟，以便按一定的次序進行求解。以便按一定的次序進行求解。描述階段的變

38、量稱描述階段的變量稱階段變量階段變量，常用，常用k表示。表示。AB1B2C1C2C3D24333321114DC1C2C3（2）狀態(tài)與狀態(tài)變量狀態(tài)與狀態(tài)變量狀態(tài)（狀態(tài)（statestate）用用sk表示階段表示階段k的起始狀態(tài)（或輸入的起始狀態(tài)（或輸入狀態(tài)）；用狀態(tài)）；用sk+1表示階段表示階段k的結(jié)束狀態(tài)（或輸出狀態(tài)）的結(jié)束狀態(tài)（或輸出狀態(tài)）狀態(tài)變量的取值有一定的允許集合或范圍，此集合狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為稱為狀態(tài)允許集合狀態(tài)允許集合例如：最短路徑問題中，第例如：最短路徑問題中，第2階段有二個輸入狀態(tài)，階段有二個輸入狀態(tài)，三個輸出狀態(tài)。三個輸出狀態(tài)。AB1B2C1C

39、2C3D24333321114DC1C2C3（3）決策與決策變量決策與決策變量決策（決策（decisiondecision）用用x xk k表示從第表示從第k階段狀態(tài)階段狀態(tài)sk到到第第k+1階段的狀態(tài)階段的狀態(tài)sk+1所采取的策略，它使活動過程所采取的策略，它使活動過程從狀態(tài)從狀態(tài)sk轉(zhuǎn)變?yōu)檗D(zhuǎn)變?yōu)閟k+1。決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合允許決策集合，可用，可用DK(sK)表示表示。AB1B2C1C2C3D24333321114C1C2C3決策：決策：x x2(B1)=B1C1允許決策集合：允許決策集合：D2(B1)=B1C

40、1，B1C2 ，B1C3 （4）策略策略策略：策略：是一個按順序排列的決策組成的集合。在實是一個按順序排列的決策組成的集合。在實際問題中，可供選擇的策略有一定的范圍，稱為際問題中，可供選擇的策略有一定的范圍，稱為允允許策略集合許策略集合。從允許策略集合中找出達到最優(yōu)效果。從允許策略集合中找出達到最優(yōu)效果的策略稱為的策略稱為最優(yōu)策略最優(yōu)策略。12ks1x1s2x2s3skxksk+1AB1B2C1C2C3D24333321114C1C2C3策略：策略：AB1C1 D（5）狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：是確定過程由一個狀態(tài)到是確定過程由一個狀態(tài)到另一個狀態(tài)的方程，描述了狀態(tài)轉(zhuǎn)

41、移規(guī)律。另一個狀態(tài)的方程，描述了狀態(tài)轉(zhuǎn)移規(guī)律。12ks1x1s2x2s3skxksk+1AB1B2C1C2C3D24333321114C1C2C3),(),(),(122231112kkkkxsTsxsTsxsTsu2(B1)=B1C1s3=T2(B1,u2)=C1討論：狀態(tài)的無后效性討論：狀態(tài)的無后效性一般而言，系統(tǒng)某階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)當(dāng)一般而言，系統(tǒng)某階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)當(dāng)前狀態(tài)和決策有關(guān)，而且還與系統(tǒng)的歷史狀態(tài)和前狀態(tài)和決策有關(guān)，而且還與系統(tǒng)的歷史狀態(tài)和決策有關(guān)決策有關(guān)特殊的，系統(tǒng)狀態(tài)的轉(zhuǎn)移都只僅與前一時刻的狀特殊的，系統(tǒng)狀態(tài)的轉(zhuǎn)移都只僅與前一時刻的狀態(tài)有關(guān)、而與過去的狀態(tài)無關(guān)

42、，稱這樣的狀態(tài)具態(tài)有關(guān)、而與過去的狀態(tài)無關(guān)，稱這樣的狀態(tài)具有有“無后效性無后效性”動態(tài)規(guī)劃解決動態(tài)規(guī)劃解決“具有無后效性具有無后效性”的多階段的多階段決策問題決策問題),(22111kkkkxsxsxsTs),(1kkkkxsTs（6）指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)指標(biāo)函數(shù)又稱目標(biāo)函數(shù)，它又稱目標(biāo)函數(shù)，它用來表示系統(tǒng)用來表示系統(tǒng)所要實現(xiàn)的目標(biāo)，是衡量策略優(yōu)劣的尺度。所要實現(xiàn)的目標(biāo)，是衡量策略優(yōu)劣的尺度。指標(biāo)函數(shù)的含義可能是距離、利潤、成本、指標(biāo)函數(shù)的含義可能是距離、利潤、成本、產(chǎn)量或資源消耗等產(chǎn)量或資源消耗等衡量從衡量從k階段階段n階段階段決策過程總體效果的決策過程總體效果的

43、確定數(shù)量函數(shù)：確定數(shù)量函數(shù)：Vk,n衡量衡量第第k階段階段決策效果的決策效果的指標(biāo)：指標(biāo)：dk(sk,xk)指標(biāo)函數(shù)指標(biāo)函數(shù)Vk,n最優(yōu)值最優(yōu)值最優(yōu)值函數(shù)：最優(yōu)值函數(shù)：fk(sk)最短路徑問題中的指標(biāo)函數(shù)最短路徑問題中的指標(biāo)函數(shù)Vk,n第第k階段從階段從Sk 到終點的距離到終點的距離dk(sk,xk)從從Sk 到到xk決策所指節(jié)點的距離決策所指節(jié)點的距離fk(sk)第第k階段從階段從Sk 到終點最短距離到終點最短距離 d( B2,C1 ) + f1 (C1 ) 3 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 6 =3 d( B2,C3 ) + f1

44、(C3 ) 5AB1B2C1C2C3D24333321114C1C2C3遞推方程式遞推方程式這樣，就將原來的這樣，就將原來的n階段決策問題化為一階段決策問題化為一系列單變量優(yōu)化問題系列單變量優(yōu)化問題f fk k(s(sk k) ) opt opt dk(sk,xk)+f+fk+1k+1(s(sk+1k+1) opt opt dk(sk,xk)+f+fk+1k+1(T(s(T(sk k,x,xk k) 0 xkDk3.2.2 動態(tài)規(guī)劃基本方程動態(tài)規(guī)劃基本方程遞推方程式與狀態(tài)轉(zhuǎn)移方程式合稱為動態(tài)遞推方程式與狀態(tài)轉(zhuǎn)移方程式合稱為動態(tài)規(guī)劃基本方程規(guī)劃基本方程遞推方程式：遞推方程式：f fk k(s(s

45、k k) ) opt opt dk(sk,xk)+f+fk+1k+1(s(sk+1k+1) 0 xkDk 狀態(tài)轉(zhuǎn)移方程式：狀態(tài)轉(zhuǎn)移方程式：s sk+1k+1=T(s=T(sk k,x,xk k) ) 3.2.3 動態(tài)規(guī)劃的步驟動態(tài)規(guī)劃的步驟(1)將所研究問題的過程劃分為將所研究問題的過程劃分為n個恰當(dāng)?shù)碾A段個恰當(dāng)?shù)碾A段 (2)正確地選擇狀態(tài)變量正確地選擇狀態(tài)變量Sk，并確定初始狀態(tài)并確定初始狀態(tài)S1的值的值(3)確定決策變量確定決策變量xk以及各階段的允許決策集以及各階段的允許決策集Dk(Sk)(4) 給出狀態(tài)轉(zhuǎn)移方程；給出狀態(tài)轉(zhuǎn)移方程；(5) 給出滿足要求的指標(biāo)函數(shù)給出滿足要求的指標(biāo)函數(shù)Vk

46、,n及相應(yīng)的最優(yōu)值函及相應(yīng)的最優(yōu)值函(6) 寫出遞推方程，建立基本方程；寫出遞推方程，建立基本方程；(7) 按照基本方程遞推求解按照基本方程遞推求解 3.43.4舉例舉例：機器負荷問題：機器負荷問題某種機器可以在高低兩種不同的負荷下進行生產(chǎn)：某種機器可以在高低兩種不同的負荷下進行生產(chǎn)：在高負荷下進行生產(chǎn)時，機器的年完好率為在高負荷下進行生產(chǎn)時，機器的年完好率為70%70%，且，產(chǎn)品的年產(chǎn)量且，產(chǎn)品的年產(chǎn)量=8=8* *投入生產(chǎn)的機器數(shù)量投入生產(chǎn)的機器數(shù)量這時在低負荷下生產(chǎn)時，機器的年完好率為這時在低負荷下生產(chǎn)時，機器的年完好率為90%90%，且，產(chǎn)品的年產(chǎn)量且，產(chǎn)品的年產(chǎn)量=5=5* *投入生

47、產(chǎn)的機器數(shù)量投入生產(chǎn)的機器數(shù)量假定開始生產(chǎn)時完好的機器數(shù)量為假定開始生產(chǎn)時完好的機器數(shù)量為10001000要求制定一個五年計劃要求制定一個五年計劃, ,在每年開始時決定機器在在每年開始時決定機器在兩種不同負荷下生產(chǎn)的數(shù)量，使五年內(nèi)產(chǎn)品的總兩種不同負荷下生產(chǎn)的數(shù)量，使五年內(nèi)產(chǎn)品的總產(chǎn)量最高。產(chǎn)量最高。機器負荷問題機器負荷問題階階段段 高高負負 荷荷下下 機機器器 數(shù)數(shù) 低低負負 荷荷下下 機機器器 數(shù)數(shù) 剩剩 余余 機機器器數(shù)數(shù) 效效益益 狀狀態(tài)態(tài)轉(zhuǎn)轉(zhuǎn)移移方方程程 k Xk Sk-Xk Sk 1 X1 S1-X1 S1=1000 2 X2 S2-X2 S2 3 X3 S3-X3 S3 4 X4

48、S4-X4 S4 5 X5 S5-X5 S5 Vk =8Xk+5(Sk-Xk) =5Sk+3Xk Sk+1 =0.7Xk+0.9(Sk-Xk) =0.9Sk-0.2Xk x1x2x5125s1s2s3s5s6V1V2V5(1)按年數(shù)劃分為按年數(shù)劃分為5個階段，個階段，k=1,2,3,4,5(2)取第取第k年初完好的機器數(shù)年初完好的機器數(shù)sk為狀態(tài)變量為狀態(tài)變量, s1=1000(3)取第取第k年投入高負荷的機器數(shù)年投入高負荷的機器數(shù)xk為決策變量為決策變量, 0 xksk(4)狀態(tài)轉(zhuǎn)移方程為狀態(tài)轉(zhuǎn)移方程為 sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk(5)指標(biāo)函數(shù)為指標(biāo)函

49、數(shù)為Vk,5=8xj+5(sj-xj)=(5sj+3xj)解解:125s1s2s3s5s6V1V2V5基本方程基本方程(6)(6)基本方程為基本方程為 f fk k(s(sk k) ) max max 5sk+3xk +f +fk+1k+1(s(sk+1k+1) k=5,4,3,2,1) k=5,4,3,2,1 0 xksk f f6 6(s(s6 6) )0 0 根據(jù)狀態(tài)轉(zhuǎn)移方程：根據(jù)狀態(tài)轉(zhuǎn)移方程：Sk+1=0.9Sk-0.2Xk f fk k(s(sk k) ) max max 5sk+3xk +f +fk+1k+1( (0.9Sk-0.2Xk )因此基本方程因此基本方程f fk k最終可轉(zhuǎn)化為