第三節(jié)動(dòng)態(tài)規(guī)劃的應(yīng)用舉例定價(jià)問(wèn)題資源分配問(wèn)題生產(chǎn)存儲(chǔ)問(wèn)題一、定價(jià)問(wèn)題某公司考慮為某新產(chǎn)品定價(jià)，該產(chǎn)品的單價(jià)擬從每件5元、6元、7元和8元這四個(gè)中選取一個(gè)，每年允許價(jià)格有1元幅度的變動(dòng)，該產(chǎn)品預(yù)計(jì)暢銷五年，據(jù)預(yù)測(cè)不同價(jià)格下各年的利潤(rùn)如表3-1所示。單價(jià)第一年第二年第三年第四年第五年5元6元7元8元1012141612131415151616152020181425241814表3-2每年預(yù)計(jì)利潤(rùn)額建立數(shù)學(xué)模型按年劃分階段，k=1,2,...,5每階段的狀態(tài)變量為本年(上一年已確定)的價(jià)格，狀態(tài)變量的可行集合Sk=(5,6,7,8)。決策變量為每年依據(jù)當(dāng)年價(jià)格為下一年度決定價(jià)格，根據(jù)題意決策變量的可行集合是：采用逆序算法，因此狀態(tài)轉(zhuǎn)移方程是最優(yōu)值函數(shù)遞推方程為進(jìn)行各階段的計(jì)算采用逆序法，設(shè)當(dāng)k=5時(shí)，S5=(5,6,7,8)，由表3-1得到當(dāng)k=4時(shí)，S4=(5,6,7,8)，由遞推方程得繼續(xù)求解同理得其它各階段的最優(yōu)解反推得最優(yōu)路線按照與求最優(yōu)值函數(shù)方向相反的順序求最優(yōu)狀態(tài)路線：最優(yōu)決策變量。即從第一年單價(jià)應(yīng)為8元開(kāi)始，向后推算。得第二年定價(jià)8元，第三年定價(jià)7元，第四年定價(jià)6元，第五年定價(jià)5元。最大利潤(rùn)值為92萬(wàn)元。也可用決策圖求解二、資源分配問(wèn)題某公司將5臺(tái)加工中心分配給甲、乙、丙、丁四個(gè)工廠，各工廠或設(shè)備后可產(chǎn)生如表3-2所示的利潤(rùn)，應(yīng)怎么分配設(shè)備可使公司總利潤(rùn)最大？工廠設(shè)備數(shù)甲乙丙丁012345067101215037912130510111111046111212建立數(shù)學(xué)模型按工廠次序劃分階段，k=1，2，3，4狀態(tài)變量為各階段可用于分配的設(shè)備總臺(tái)數(shù)決策變量是分配給第k工廠的設(shè)備數(shù)采用逆序算法，狀態(tài)轉(zhuǎn)移方程最優(yōu)值函數(shù)遞推方程第4階段的最優(yōu)解當(dāng)k=4時(shí)，S4=(0,1,2,3,4,5)012345012345046111212046111212012345第3階段的最優(yōu)解當(dāng)k=3時(shí)，S3=(0,1,2)000000010105404551201205106406910102第3階段的最優(yōu)解（續(xù)）當(dāng)k=3時(shí)，S3=3301230510111164011111411142第3階段的最優(yōu)解（續(xù)）當(dāng)k=3時(shí)，S3=44012340510111112116401216161511161，2第3階段的最優(yōu)解（續(xù)）當(dāng)k=3時(shí)，S3=550123450510111111121211640121721171511212第2階段的最優(yōu)解當(dāng)k=2時(shí)，S2=(0,1,2)000000010103505350201203710501087100第2階段的最優(yōu)解（續(xù)）當(dāng)k=2時(shí)，S2=33012303791410501413129140第2階段的最優(yōu)解（續(xù)）當(dāng)k=2時(shí)，S2=4401234037912161410501617171412171，2第2階段的最優(yōu)解（續(xù)）當(dāng)k=2時(shí)，S2=55012345037912132116141050211921191715210，2第1階段的最優(yōu)解（續(xù)）當(dāng)k=1時(shí)，S1=5

50123450671012152117141050212321201715231反向求最佳狀態(tài)路線方案一方案二工廠名分配設(shè)備數(shù)工廠名分配設(shè)備數(shù)甲乙丙丁1121甲乙丙丁1220三、生產(chǎn)存儲(chǔ)問(wèn)題某公司生產(chǎn)并銷售某產(chǎn)品。根據(jù)市場(chǎng)預(yù)測(cè)，今后四個(gè)月的市場(chǎng)需求量如表3-7所示。時(shí)期（月）需求量（dk）12342324已知的其它條件已知生產(chǎn)一件產(chǎn)品的成本是1千元，每批產(chǎn)品的生產(chǎn)準(zhǔn)備成本是3千元；每月僅能生產(chǎn)一批，每批6件。每件存儲(chǔ)成本為0.5千元，且第一個(gè)月初無(wú)存貨，第四個(gè)月末的存貨要求為零。求最優(yōu)生產(chǎn)計(jì)劃。設(shè)第k月的生產(chǎn)量uk，存儲(chǔ)量為Sk,則總成本為建立數(shù)學(xué)模型以月劃分階段，k=1,2,3,4各階段決策變量為該階段生產(chǎn)量uk，狀態(tài)變量為該階段的存儲(chǔ)量Sk。采用逆序算法，則狀態(tài)轉(zhuǎn)移方程為最低成本遞推公式是第四階段的最優(yōu)解當(dāng)k=4時(shí)，d4=4,因第四階段末無(wú)存貨，因此S4=(0,1,2,3,4)S4u4本期成本C4S5f5(S5)f4(S4)生產(chǎn)存儲(chǔ)01234432107654000.511.5276.565.52000000000076.565.52第三階段最優(yōu)解當(dāng)k=3時(shí)，由于，且第三階段需求量d3=2，S3=(0,1,2,3,4,5,6)S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲(chǔ)0234565678900000567890123476.565.521212.51313.511第三階段最優(yōu)解:S3=1S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲(chǔ)112345456780.50.50.50.50.54.55.56.57.58.50123476.565.5211.512.012.513.010.5第三階段最優(yōu)解:S3=2S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲(chǔ)2012340456711111156780123476.565.52811.512.012.510.0第三階段最優(yōu)解:S3=3,4S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲(chǔ)3012304561.51.51.51.51.55.56.57.512346.565.52811.512.09.5401204522226723465.52811.59第三階段最優(yōu)解:S3=5,6S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲(chǔ)501042.52.52.56.5345.5288.560033425第二階段最優(yōu)解當(dāng)k=2時(shí)，d2=3，由于最大生產(chǎn)能力為6，而d1=2，因此S2=(0,1,2,3,4)S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲(chǔ)03456678900006789012311.010.58.08.01717.51617第二階段最優(yōu)解:S2=1S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲(chǔ)123456567890.50.50.50.50.55.56.57.58.59.50123411.010.58.08.08.016.51715.516.517.5第二階段最優(yōu)解:S2=2S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲(chǔ)2123456456789111111567891001234511.010.58.08.08.08.016.016.515.016.017.018.0第二階段最優(yōu)解:S2=3S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲(chǔ)3012345604567891.51.51.51.51.51.51.51.55.56.57.58.59.510.5012345611.010.58.08.08.08.05.012.516.014.515.516.517.515.5第二階段最優(yōu)解:S2=4S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲(chǔ)4012345045678222222267891012345610.58.08.08.08.05.012.51415161715第一階段最優(yōu)解當(dāng)k=1時(shí)，d1=2，S1=0S1u1本期成本C1S2f2(S2)f1(S1)生產(chǎn)存儲(chǔ)0234565678900000567890123416.015.515.012.512.52121.5