動(dòng)態(tài)規(guī)劃應(yīng)用舉例.ppt

1、第九章：動(dòng)態(tài)規(guī)劃應(yīng)用舉例,第一節(jié)：資源分配問(wèn)題 分配問(wèn)題：將數(shù)量一定的一種或若干種資源（例如原材料，資金，機(jī)器設(shè)備，勞力，食品等等），恰當(dāng)?shù)胤峙浣o若干個(gè)使用者，使效益函數(shù)最優(yōu)。,1.1 多元投資分配問(wèn)題(離散） 設(shè)有某種原料，總數(shù)量為a，用于生產(chǎn)n種產(chǎn)品。若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品，其收益為gi(xi),問(wèn)應(yīng)如何分配，才能使生產(chǎn)n種產(chǎn)品的總收入最大？,靜態(tài)規(guī)劃,決策變量uk表示分配給生產(chǎn)第k種產(chǎn)品的原料數(shù)量，即uk=xk； 設(shè)狀態(tài)變量sk表示分配用于生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品的原料數(shù)量； 狀態(tài)轉(zhuǎn)移方程： sk+1=sk-uk=sk-xk 決策集合：Dk(sk)=uk|0uk=xksk 最

2、優(yōu)值函數(shù)fk(sk)表示數(shù)量為sk的原料分配給第k種產(chǎn)品至第n種產(chǎn)品所得到的最大總收益，動(dòng)態(tài)規(guī)劃的遞推關(guān)系為：,例1 某大型公司擬將某種高效率的設(shè)備5臺(tái)分配給所屬的甲、乙、丙三個(gè)工廠，各工廠若獲得這種設(shè)備之后，可以為公司提供的盈利如表。問(wèn)這五臺(tái)設(shè)備如何分配給各工廠，才能使公司得到的盈利最大。,解：將問(wèn)題按工廠分為三個(gè)階段，甲乙丙分別編號(hào)為1，2，3。用k表示，即階段變量 決策變量uk表示分配給第k個(gè)工廠的設(shè)備臺(tái)數(shù)，即uk=xk； 設(shè)狀態(tài)變量sk表示為分配給第k個(gè)工廠至第3工廠的設(shè)備臺(tái)數(shù)； 狀態(tài)轉(zhuǎn)移方程： sk+1=sk-uk=sk-xk 決策集合：Dk(sk)=uk|0uk=xksk 最優(yōu)值函

3、數(shù)fk(sk)表示數(shù)量為sk的設(shè)備臺(tái)數(shù)分配給第k個(gè)工廠至第n個(gè)工廠所得到的最大總收益，動(dòng)態(tài)規(guī)劃的遞推關(guān)系為：,用逆推法 當(dāng)階段k=3時(shí)，0s35， 0 x3s3，有,x3(s3),結(jié)果列于下表：,當(dāng)階段k=2時(shí)， s3=s2-x2， 0s25， 0 x2s2，有,結(jié)果列于下表：,當(dāng)階段k=1時(shí)， s2=s1-x1， s1=5， 0 x1s1，有,結(jié)果可寫(xiě)成表格的形式,然后按計(jì)算表格的順序反推，可知最優(yōu)分配方案有兩個(gè)： 由于x1*=0，根據(jù)s2=s1-x1*=5-0=5，查表知x2*=2，由s3=s2-x2*=5-2=3，故x3*=s3=3。即得甲工廠分配0臺(tái)，乙工廠分配2臺(tái)，丙工廠分配3臺(tái)。

4、由于x1*=2，根據(jù)s2=s1-x1*=5-2=3，查表知x2*=2，由s3=s2-x2*=3-2=1，故x3*=s3=1。即得甲工廠分配2臺(tái)，乙工廠分配2臺(tái)，丙工廠分配1臺(tái)。 以上兩個(gè)分配方案所得到的總盈利均為21萬(wàn)元。,問(wèn)題：如果原設(shè)備臺(tái)數(shù)是4臺(tái)，求最優(yōu)分配方案？ 如果原設(shè)備臺(tái)數(shù)是3臺(tái)，求最優(yōu)分配方案？,1.2 資源連續(xù)分配問(wèn)題: 一般問(wèn)題的提法是,如此進(jìn)行n年，如何確定投入A的資源量u1、un，使總收入最大？,此問(wèn)題的靜態(tài)規(guī)劃問(wèn)題模型為：,動(dòng)態(tài)規(guī)劃的逆推關(guān)系方程為：,最后求得的f1(s1)即為所求問(wèn)題的最大收入。,例2 機(jī)器負(fù)荷分配問(wèn)題 某種機(jī)器可在高低兩種不同負(fù)荷下進(jìn)行生產(chǎn)，設(shè)機(jī)器在高

5、負(fù)荷情況下的產(chǎn)量函數(shù)為g=8x，其中x是投入生產(chǎn)的機(jī)器數(shù)量，年完好率為 a=0.7，在低負(fù)荷情況下的產(chǎn)量函數(shù)為h=5y，其中y是投入生產(chǎn)的機(jī)器數(shù)量，年完好率為b=0.9。假定開(kāi)始生產(chǎn)時(shí)完好機(jī)器的數(shù)量為1000臺(tái)，試問(wèn)每年如何安排機(jī)器在高低兩種負(fù)荷下的生產(chǎn)，可使5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。, 允許決策集合0uksk,解： 設(shè)階段數(shù)k表示年度。 狀態(tài)變量sk為第k年度初擁有的完好機(jī)器臺(tái)數(shù)。 決策變量uk為第k年度中分配高負(fù)荷下生產(chǎn)的機(jī)器臺(tái)數(shù)。故低負(fù)荷下 生產(chǎn)的機(jī)器臺(tái)數(shù)是sk-uk。 狀態(tài)轉(zhuǎn)移方程,第k年度產(chǎn)量為,指標(biāo)函數(shù)為,遞推方程為,依次類推可得，,第二節(jié) 生產(chǎn)與存貯問(wèn)題,所謂生產(chǎn)與庫(kù)存問(wèn)題就是

6、一個(gè)生產(chǎn)部門，如何在已知生產(chǎn)成本、庫(kù)存費(fèi)用和各階段市場(chǎng)需求條件下，決定各階段產(chǎn)量，使計(jì)劃內(nèi)的費(fèi)用總和為最小的問(wèn)題。很多問(wèn)題可以化成此類問(wèn)題來(lái)解決。 生產(chǎn)與庫(kù)存問(wèn)題本身就是一個(gè)多階段決策過(guò)程。設(shè)某一生產(chǎn)部門，生產(chǎn)周期分為n個(gè)階段，已知最初庫(kù)存量為x1，階段市場(chǎng)的需求為dk，生產(chǎn)的固定成本為K，單位產(chǎn)品的消耗費(fèi)用為L(zhǎng)，單位產(chǎn)品的階段庫(kù)存費(fèi)用為h，倉(cāng)庫(kù)容量為M，階段生產(chǎn)能力為B。問(wèn)如何安排各階段產(chǎn)量，使計(jì)劃周期內(nèi)的費(fèi)用總和最小。,狀態(tài)變量xk選為階段k的初始庫(kù)存量，x1已知，xn+1=0。 階段k的庫(kù)存量即不能超過(guò)庫(kù)存容量M，也不能超過(guò)階段k至階段n的需求總量，即,決策變量uk選為階段k的產(chǎn)量。階段

7、產(chǎn)量必須不超過(guò)生產(chǎn)能力和第k階段到第n階段的總需求減去第k階段初的庫(kù)存量，同時(shí)要大于該階段的需求和庫(kù)存量之差，即,狀態(tài)轉(zhuǎn)移方程為,階段費(fèi)用為階段生產(chǎn)費(fèi)用和庫(kù)存費(fèi)用之和，即,階段k的生產(chǎn)費(fèi)用,k階段末的庫(kù)存費(fèi)用,動(dòng)態(tài)規(guī)劃基本方程,例 已知n=3，K=8，L=2，h=2，x1=1，M=4，x4=0（計(jì)劃周期末的庫(kù)存量為0），B=6，d1=3，d2=4，d3=3，求解生產(chǎn)與庫(kù)存問(wèn)題。 解：利用上述的遞推方程得,若,若,則,則,結(jié)果見(jiàn)下表：,時(shí),是唯一確定的，因此,最優(yōu)決策為,最優(yōu)路線為 1，0，0，0 最優(yōu)目標(biāo)函數(shù)值為42。,個(gè)人、單位等隨時(shí)均有設(shè)備更新問(wèn)題。隨著使用年限的增加而設(shè)備陳舊，處理價(jià)格愈

8、低，因此需要維修和更新的費(fèi)用增加。處于各種階段的設(shè)備總是面臨保留還是更新問(wèn)題。保留還是更新，應(yīng)該從整個(gè)計(jì)劃期間的總回收額來(lái)考慮，而不能從局部的某個(gè)階段的回收額來(lái)考慮，是一個(gè)多階段的決策問(wèn)題。,第三節(jié)：設(shè)備更新問(wèn)題,設(shè)備更新問(wèn)題（以一臺(tái)機(jī)器為例）： n為設(shè)備的計(jì)劃使用年數(shù)。 Ik(t) 為第k年（階段）機(jī)器役齡為t年的一臺(tái)機(jī)器運(yùn)行（再使用一年）所得的收入。 Ok(t) 為第k年機(jī)器役齡為t年的一臺(tái)機(jī)器運(yùn)行（再使用一年）時(shí)所需運(yùn)行的費(fèi)用（或維修費(fèi)用） 。 Ck(t) 為第k年機(jī)器役齡為t年的一臺(tái)機(jī)器更新時(shí)所需要的凈費(fèi)用（處理一臺(tái)役齡為t的舊設(shè)備，買進(jìn)一臺(tái)新設(shè)備的更新凈費(fèi)用）。,為折扣因子，表示一年

9、以后的收入是上一年的單位。 要求在n年內(nèi)的每年年初作出決策，是繼續(xù)使用舊設(shè)備還是更換一臺(tái)新的，使n年內(nèi)總效益最大？,建立動(dòng)態(tài)規(guī)劃模型如下： 階段k（k=1，2，n）表示計(jì)劃使用該設(shè)備的年限數(shù)。 狀態(tài)變量sk：第k年初，設(shè)備已使用過(guò)的年數(shù)，即役齡。 決策變量xk：是第k年初更新（Replacement），還是保留使用（Keep）舊設(shè)備，分別用K，R表示。 狀態(tài)轉(zhuǎn)移方程為：,階段效益為：,最優(yōu)指標(biāo)函數(shù)fk(sk)：表示第k年初，一臺(tái)已用了sk年的設(shè)備，到第n年末的最大收益，動(dòng)態(tài)規(guī)劃的基本方程為,實(shí)際上,例：設(shè)某臺(tái)新設(shè)備的年效益及年均維修費(fèi)用、更新凈費(fèi)用如下表，試確定今后五年內(nèi)的更新策略，使總效益最大。（設(shè)=1）,（單位：萬(wàn)元）,解：n=5,狀態(tài)變量s5可取1，2，3，4,例：設(shè)某臺(tái)新設(shè)備的年效益及年均維修費(fèi)用、更新凈費(fèi)用如下表，試確定今后五年內(nèi)的更新策略，使總效益最大。（設(shè)=1）,賣掉役齡2年的設(shè)備，買入新設(shè)備的更新費(fèi)用,狀態(tài)變量s4可取1，2，3,此時(shí)s3可取1或2,由于狀態(tài)s2只能取1，所以有,由于狀態(tài)s1只能取0，所以有,上述過(guò)程遞推回去，