管理運(yùn)籌學(xué)講義動(dòng)態(tài)規(guī)劃

管理運(yùn)籌學(xué)講義動(dòng)態(tài)規(guī)劃第1頁(yè)，共47頁(yè)，2023年，2月20日，星期二第七章動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃DynamicProgramming研究多階段決策的最優(yōu)化問(wèn)題的方法。多階段決策問(wèn)題含有一個(gè)描述過(guò)程時(shí)序或空間演變的階段變量，將復(fù)雜問(wèn)題劃分成若干階段，根據(jù)“最優(yōu)性原理”，逐段解決而最終實(shí)現(xiàn)全局最優(yōu)。經(jīng)濟(jì)、管理、工業(yè)生產(chǎn)、工程技術(shù)等領(lǐng)域，許多問(wèn)題可歸結(jié)為多階段決策問(wèn)題。一些用線性規(guī)劃、非線性規(guī)劃處理有困難的問(wèn)題，往往可以用動(dòng)態(tài)規(guī)劃方便地求解。動(dòng)態(tài)規(guī)劃是美國(guó)運(yùn)籌學(xué)家貝爾曼(R.Bellman)等人1959年提出的。2第2頁(yè)，共47頁(yè)，2023年，2月20日，星期二第一節(jié)多階段決策問(wèn)題多階段決策：經(jīng)濟(jì)管理決策中，有些管理決策問(wèn)題可以按時(shí)序或空間演變劃分成多個(gè)階段，呈現(xiàn)出明顯的階段性；于是可把這類(lèi)決策問(wèn)題分解成幾個(gè)相互聯(lián)系的階段，每個(gè)階段即為一個(gè)子問(wèn)題；原有問(wèn)題的求解就化為逐個(gè)求解幾個(gè)簡(jiǎn)單的階段子問(wèn)題；每個(gè)階段的決策一旦確定，整個(gè)決策過(guò)程也隨之確定，此類(lèi)問(wèn)題稱(chēng)為多階段決策問(wèn)題。

例如：企業(yè)生產(chǎn)物流：可分為物料供應(yīng)、生產(chǎn)制造、分銷(xiāo)零售等階段。最短路問(wèn)題：可以按空間順序劃分階段。一、問(wèn)題的提出

3第3頁(yè)，共47頁(yè)，2023年，2月20日，星期二第一節(jié)多階段決策問(wèn)題從生產(chǎn)廠Q到某公司T選擇那條路線,使總運(yùn)費(fèi)最低(路程最短)？最短路問(wèn)題QTA1A2A3B1B2B3C1C124374642442514633334生產(chǎn)商某公司出口港進(jìn)口港城市階段1階段2階段3階段44第4頁(yè)，共47頁(yè)，2023年，2月20日，星期二第一節(jié)多階段決策問(wèn)題這是一個(gè)多階段決策問(wèn)題，它可分為四個(gè)階段：第一階段：從Q(制造廠)到A(出口港)；第二階段：從A(出口港)到B(進(jìn)口港)；第三階段：從B(進(jìn)口港)到C(城市)；第四階段：從C(城市)到T(某公司)。每個(gè)階段選取的路線不同，對(duì)應(yīng)從Q到T就有一系列不同的運(yùn)輸路線:從始點(diǎn)Q到終點(diǎn)T共有3×3×2×1=18條不同路線現(xiàn)在的問(wèn)題是如何選擇一條費(fèi)用最小的路線？5第5頁(yè)，共47頁(yè)，2023年，2月20日，星期二例一、從A

地到D

地要鋪設(shè)一條煤氣管道,其中需經(jīng)過(guò)兩級(jí)中間站，兩點(diǎn)之間的連線上的數(shù)字表示距離，如圖所示。問(wèn)應(yīng)該選擇什么路線，使總距離最短？AB1B2C1C2C3D24333321114二、最短路徑問(wèn)題第6頁(yè)，共47頁(yè)，2023年，2月20日，星期二

解：整個(gè)計(jì)算過(guò)程分三個(gè)階段，從最后一個(gè)階段開(kāi)始。

第一階段（C→D）：C

有三條路線到終點(diǎn)D

。

AB1B2C1C2C3D24333321114DC1C2C3顯然有f1(C1)

=1；

f1(C2)

=3；

f1(C3)

=4

7第7頁(yè)，共47頁(yè)，2023年，2月20日，星期二

d(B1,C1)+f1(C1)

3+1f2(B1)=mind(B1,C2

)+f1(C2)

=min3+3

d(B1,C3)+f1(C3)1+44=min6=45第二階段（B→C）：B到C

有六條路線。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B1→C1→D)8第8頁(yè)，共47頁(yè)，2023年，2月20日，星期二

d(B2,C1)+f1(C1)

2+1f2(B2)=mind(B2,C2

)+f1(C2)

=min3+3

d(B2,C3)+f1(C3)1+43=min6=35AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B2→C1→D)9第9頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三階段（

A→B

）：A到B有二條路線。

f3(A)1=d(A,B1)＋f2(B1)＝2＋4＝6

f3(A)2=d(A,B2)＋f2(B2)＝4＋3＝7∴f3(A)

=min=min｛6,7｝=6d(A,B1)＋f2(B1)d(A,B2)＋f2(B2)(最短路線為A→B1→C1→D)AB1B2C1C2C3D24333321114DC1C2C3B1B2A10第10頁(yè)，共47頁(yè)，2023年，2月20日，星期二AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路線為A→B1→C1→D

路長(zhǎng)為611第11頁(yè)，共47頁(yè)，2023年，2月20日，星期二第一節(jié)多階段決策問(wèn)題最短路徑：Q→A3→B1→C1→T二、動(dòng)態(tài)規(guī)劃的標(biāo)號(hào)法

QTA1A2A3B1B2B3C1C224374642442514633334階段1階段2階段3階段403,T4,T4,C17,C26,C111,B1,B28,B18,B111,A312第12頁(yè)，共47頁(yè)，2023年，2月20日，星期二第一節(jié)多階段決策問(wèn)題最短路的基本特征從始點(diǎn)Q到終點(diǎn)T的最短路徑：Q→A3→B1→C1→T，則從中點(diǎn)A3

到終點(diǎn)T的最短路徑必為：A3→B1→C1→T，從中點(diǎn)B1

到終點(diǎn)T的最短路徑必為：B1→C1→T，…。推廣：從始點(diǎn)Q到終點(diǎn)T的最短路徑：Q→S1→S2→…→Sk→Sk+1→…→Sn→T，則從中點(diǎn)Sk

到終點(diǎn)T的最短路徑必為：Sk→Sk+1→…→Sn→T。三、多階段決策的基本特征

13第13頁(yè)，共47頁(yè)，2023年，2月20日，星期二第二節(jié)動(dòng)態(tài)規(guī)劃原理階段(stage)處理多階段決策，需將全過(guò)程劃為若干階段，每個(gè)階段進(jìn)行一次抉擇。各階段按一定順序聯(lián)接在一起組成統(tǒng)一的整體。用k表示階段變量。階段編號(hào)順序編號(hào)逆序編號(hào)一、動(dòng)態(tài)規(guī)劃的基本概念

14第14頁(yè)，共47頁(yè)，2023年，2月20日，星期二第二節(jié)動(dòng)態(tài)規(guī)劃原理狀態(tài)(state)狀態(tài)表示過(guò)程發(fā)展中某階段的起始狀況。過(guò)程的發(fā)展可以通過(guò)各階段狀態(tài)的演變來(lái)描述。狀態(tài)可用一個(gè)變量來(lái)描述，稱(chēng)為狀態(tài)變量，用Sk表示。選取的狀態(tài)變量必須滿足無(wú)后效性。某階段的狀態(tài)給定后，則過(guò)程未來(lái)發(fā)展不受該階段以前各階段狀態(tài)的影響。

第k

階段可能有若干狀態(tài)，用Sk表示階段k的狀態(tài)集合，sk(i)表示第k階段的第i

個(gè)狀態(tài)。15第15頁(yè)，共47頁(yè)，2023年，2月20日，星期二第二節(jié)動(dòng)態(tài)規(guī)劃原理決策(decision)從上一階段某狀態(tài)演變到下一階段某狀態(tài)要作一次選擇，稱(chēng)為決策。用變量xk(sk)表示第k階段狀態(tài)為sk時(shí)的決策，稱(chēng)為決策變量，簡(jiǎn)記xk決策變量的取值被限制在某一范圍內(nèi)，此范圍稱(chēng)為允許決策集合Xk(sk)

16第16頁(yè)，共47頁(yè)，2023年，2月20日，星期二第二節(jié)動(dòng)態(tài)規(guī)劃原理策略(policy)多階段決策過(guò)程中，每一階段均有一個(gè)決策，依序組合成一個(gè)全過(guò)程的決策序列，稱(chēng)為全過(guò)程策略。

p1,n(s1)={x1(s1),x2(s2),…,xn(sn)}，簡(jiǎn)記p1,n={x1,x2,…,xn}從過(guò)程的某個(gè)階段開(kāi)始到最終階段結(jié)束稱(chēng)為后部子過(guò)程。從第k階段開(kāi)始的后部子策略稱(chēng)為第k子過(guò)程策略。

pk,n(sk)={xk(sk),xk+1(sk+1),…,xn(sn)}，簡(jiǎn)記pk,n

={xk,xk+1,…,xn}每一階段有若干狀態(tài),每個(gè)狀態(tài)又有若干個(gè)不同的決策,即有許多策略可供選擇。全體策略構(gòu)成允許策略集合Pk,n(sk)。能使預(yù)期目標(biāo)達(dá)到最優(yōu)效果的策略稱(chēng)為最優(yōu)策略P*k,n

，構(gòu)成最優(yōu)策略的各決策稱(chēng)為相應(yīng)階段的最優(yōu)決策x*k。17第17頁(yè)，共47頁(yè)，2023年，2月20日，星期二第二節(jié)動(dòng)態(tài)規(guī)劃原理狀態(tài)轉(zhuǎn)移方程下一階段狀態(tài)sk+1是本階段狀態(tài)變量sk和決策變量xk的函數(shù)，即sk+1=T(sk,xk(sk))=T(sk,xk)從狀態(tài)sk出發(fā)到下一階段狀態(tài)sk+1的轉(zhuǎn)移規(guī)律稱(chēng)為狀態(tài)轉(zhuǎn)移方程。18第18頁(yè)，共47頁(yè)，2023年，2月20日，星期二第二節(jié)動(dòng)態(tài)規(guī)劃原理指標(biāo)函數(shù)用來(lái)衡量每一階段決策效果的優(yōu)劣的數(shù)量指標(biāo)，稱(chēng)為階段指標(biāo)函數(shù)vk

，階段指標(biāo)是狀態(tài)變量和相應(yīng)決策變量的函數(shù)，即vk=vk(sk,xk)。最短問(wèn)題是運(yùn)費(fèi)或路程。對(duì)階段的不同狀態(tài)，采取不同的決策，運(yùn)費(fèi)不同。指標(biāo)函數(shù)也可以是利潤(rùn)、成本、產(chǎn)量等。從第k階段的狀態(tài)sk出發(fā)到最后階段結(jié)束，各階段績(jī)效綜合起來(lái)反映這個(gè)后部子過(guò)程的績(jī)效，稱(chēng)為過(guò)程指標(biāo)函數(shù)，記為Vk,n。Vk,n的大小取決于從第k階段到最后階段所采取的子策略。即Vk,n=Vk,n(sk,xk,sk+1,xk+1,…,sn)根據(jù)實(shí)際問(wèn)題的性質(zhì)，指標(biāo)函數(shù)Vk,n

可以是各個(gè)階段指標(biāo)的和或積。從狀態(tài)sk出發(fā)，選取最優(yōu)策略所得的指標(biāo)函數(shù)值稱(chēng)為最優(yōu)指標(biāo)函數(shù)值。fk(sk)=opt{Vk,n}=opt{vk(sk,xk)+fk+1(sk+1)}opt表示最優(yōu)化，取最大max或最小min。19第19頁(yè)，共47頁(yè)，2023年，2月20日，星期二第二節(jié)動(dòng)態(tài)規(guī)劃原理逆序算法：逆著階段順序的方向，由后向前推算。把尋求最優(yōu)策略看作連續(xù)遞推過(guò)程，從最終階段開(kāi)始，逆著實(shí)際過(guò)程的進(jìn)展方向逐段求解；在每一階段求解過(guò)程中都是其后部子過(guò)程最優(yōu)策略的基礎(chǔ)上，再考慮本階段的指標(biāo)函數(shù)，求出本階段的最優(yōu)策略；直到第一階段為止。最優(yōu)性原理：美國(guó)運(yùn)籌學(xué)家貝爾曼提出無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。將決策問(wèn)題劃分為若干個(gè)階段，全過(guò)程的優(yōu)化問(wèn)題就分解為子過(guò)程的優(yōu)化問(wèn)題，由后向前逐步倒推，最優(yōu)化的子過(guò)程逐漸成為全過(guò)程最優(yōu)。作為全過(guò)程的最優(yōu)策略P*1,n的組成部分的任一子策略P*k,n(Sk)，一定是從狀態(tài)Sk

出發(fā)直至終點(diǎn)的最優(yōu)策略。二、動(dòng)態(tài)規(guī)劃方法的基本思路

20第20頁(yè)，共47頁(yè)，2023年，2月20日，星期二第二節(jié)動(dòng)態(tài)規(guī)劃原理基本遞推方程據(jù)最優(yōu)性原理，階段k的階段指標(biāo)vk(sk,xk)加上(或乘以)從下一階段k+1開(kāi)始到過(guò)程結(jié)束采取最優(yōu)策略取得的最優(yōu)指標(biāo)函數(shù)值fk+1(sk+1)，再?gòu)闹羞x出最優(yōu)，便是階段k從狀態(tài)sk出發(fā)到全過(guò)程結(jié)束的最優(yōu)指標(biāo)函數(shù)值。21第21頁(yè)，共47頁(yè)，2023年，2月20日，星期二第二節(jié)動(dòng)態(tài)規(guī)劃原理階段1階段2階段k階段k+1階段n……狀態(tài)S1決策x1狀態(tài)S2v1決策x2狀態(tài)S3v2決策xk狀態(tài)Sk+1vk決策xk+1vk+1決策xnvn尋求最優(yōu)解的方向22第22頁(yè)，共47頁(yè)，2023年，2月20日，星期二第二節(jié)動(dòng)態(tài)規(guī)劃原理建模步驟（小結(jié)）對(duì)問(wèn)題進(jìn)行階段劃分，確定階段變量k確定狀態(tài)變量sk確定決策變量xk

、允許決策集合Xk(sk)寫(xiě)出狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,xk)寫(xiě)出指標(biāo)函數(shù)的基本遞推方程明確邊界條件動(dòng)態(tài)規(guī)劃模型分類(lèi)三、動(dòng)態(tài)規(guī)劃模型

過(guò)程變量確定隨機(jī)離散連續(xù)離散確定型離散隨機(jī)型連續(xù)確定型連續(xù)隨機(jī)型23第23頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例資源分配問(wèn)題：把有限的資源(如資金、材料、設(shè)備、人力等)分配給若干使用者，而使某一指標(biāo)為最優(yōu)的問(wèn)題即為資源分配問(wèn)題。資源可以有一種或若干種，只有一種資源可供分配的問(wèn)題稱(chēng)之為一維資源分配問(wèn)題。一維資源分配問(wèn)題一、資源分配問(wèn)題

設(shè)備臺(tái)數(shù)分廠0123456I0356765II04678910III0259887如何分配設(shè)備，可使獲利最大？各分廠在不同設(shè)備臺(tái)數(shù)下所獲利潤(rùn)24第24頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型將三個(gè)分廠看作是三個(gè)階段，即階段變量k=1,2,3;狀態(tài)變量sk表示第k階段初可分配的設(shè)備臺(tái)數(shù),0≤sk≤6;決策變量xk表示第k階段分配給分廠k的設(shè)備臺(tái)數(shù)，允許決策集合Xk(sk)={xk︱0≤

xk

≤sk};狀態(tài)轉(zhuǎn)移方程為sk+1=sk-xk;階段指標(biāo)vk(sk,xk)表示第k階段從sk臺(tái)設(shè)備中分配給k分廠xk臺(tái)設(shè)備的階段效益;

最優(yōu)指數(shù)函數(shù)fk(sk)表示第k階段從sk開(kāi)始到最后階段采用最優(yōu)分配策略取得的最大的效益值;遞推方程函數(shù)式25第25頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例逆序求解K=3x3s3v3

(s3,x3)f3

(s3)x3*第III分廠在不同設(shè)備臺(tái)數(shù)下所獲利潤(rùn)0123456012345600202502590259802598802598870259999012333326第26頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例k=2x2s2v2

(s2,x2)+f3(s3)f2

(s2)x2*第II分廠在不同設(shè)備臺(tái)數(shù)下所獲利潤(rùn)01234560123456004046046704678046789046789100469131516011,20,1123第III分廠在設(shè)備臺(tái)數(shù)為s3下所獲得的最大利潤(rùn)0+00+24+00+54+26+00+94+56+27+00+94+96+57+28+00+94+96+97+58+29+00+94+96+97+98+59+210+027第27頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例k=1x1s1v1

(s1,x1)+f2(s2)f1

(s1)x1*第I分廠在不同設(shè)備臺(tái)數(shù)下所獲利潤(rùn)0123456第II分廠在設(shè)備臺(tái)數(shù)為s2下所獲得的最大利潤(rùn)60356765181,2順序遞推，得出結(jié)論第I分廠1套或2套第II分廠2套或1套第III分廠3套0+163+155+136+97+66+45+028第28頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例企業(yè)一年中的產(chǎn)品生產(chǎn)往往是分期分批生產(chǎn)的。組織每批產(chǎn)品的生產(chǎn)，都要花費(fèi)一些生產(chǎn)準(zhǔn)備費(fèi)和存貯費(fèi)用。若某一時(shí)期增大生產(chǎn)批量則可減少生產(chǎn)批次，從而降低生產(chǎn)成本。與此同時(shí)，批量大了，必然增加庫(kù)存而使存貯費(fèi)用增加。在企業(yè)產(chǎn)品的生產(chǎn)成本、存貯費(fèi)用、市場(chǎng)需求量確定的情況下，正確計(jì)劃各時(shí)期的生產(chǎn)量，既滿足市場(chǎng)需求，又使總支出最少，這是一個(gè)多階段決策問(wèn)題。二、生產(chǎn)與存儲(chǔ)問(wèn)題

29第29頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例例，某工廠與用戶(hù)簽訂了4個(gè)月的交貨合同如表所示

該廠生產(chǎn)能力為每月5件，該廠倉(cāng)庫(kù)的存貨能力為4件。已知生產(chǎn)費(fèi)用為c=1千元/件，在進(jìn)行生產(chǎn)的月份，工廠要支出固定費(fèi)用b=2千元，每月倉(cāng)庫(kù)保管費(fèi)用h=0.2千元/件/月。假定開(kāi)始時(shí)及4月底交貨后無(wú)存貨，試問(wèn)應(yīng)在每月各生產(chǎn)多少件產(chǎn)品，才能滿足交貨任務(wù)，又使總費(fèi)用最?。吭?234需求量dk(件)323230第30頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型每個(gè)月為一個(gè)階段，即階段變量k=1,2,3,4分別表示這四個(gè)月;狀態(tài)變量sk表示第k

月初的產(chǎn)品庫(kù)存量，0≤sk≤4;決策變量xk表示第k月的生產(chǎn)量，允許決策集合Xk(sk)={xk︱0≤

xk

≤5};狀態(tài)轉(zhuǎn)移方程為sk+1=sk+xk

–

dk;階段指標(biāo)vk(sk,xk)表示第k月的費(fèi)用：本月若不安排生產(chǎn)，則僅需支出保管費(fèi)；本月若安排生產(chǎn)，則需支出生產(chǎn)費(fèi)用和固定費(fèi)，同時(shí)還需交付保管費(fèi)。當(dāng)xk

=0時(shí)，vk(sk,xk)=h·sk=0.2sk當(dāng)xk

＞0時(shí)，vk(sk,xk)=b+c·xk+h·sk=2+xk+0.2sk

最優(yōu)指數(shù)函數(shù)fk(sk)表示第k階段從sk開(kāi)始到最后階段采用最優(yōu)生產(chǎn)策略實(shí)現(xiàn)的最低生產(chǎn)費(fèi)用;31第31頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例逆序求解K=4x4s4v4

(s4,x4)=0.2

s4v4

(s4,x4)=2+

x4+0.2

s4f4(s4)x4*012012----4--3.2--0.4----43.20.4210d4=2，4月末無(wú)庫(kù)存則s5=0，狀態(tài)轉(zhuǎn)移方程s5=s4+

x4–d4，則s4=

d4–x4=

2–x4x4≥0,則s4=

2–x4={0,1,2}s4≥0,則x4=

2–s4={0,1,2}32第32頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例k=3x3s30.2

s3+f4(s4)v3

(s3,x3)+f4(s4)=2+

x3+0.2

s3+f4(s4)f3(s3)x3*012340123457.46.65.84.64.254300-----9.09.27.4----8.28.46.6----7.47.65.8----4.66.85.0------44.2--------d3=3，0≤s4≤

2，狀態(tài)轉(zhuǎn)移方程s4=s3+

x3–d3，則0≤

s3+

x3–

d3

≤

2，即3≤

s3+

x3≤

50≤s3≤4，則s3={0,1,2,3,4}生產(chǎn)能力限制0≤x3≤

5，則x3={0,1,2,3,4,5}4月在庫(kù)存量為s4下的最低生產(chǎn)成本33第33頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例k=2x2s20.2

s2+f3(s3)v2

(s2,x2)+f3(s3)=2+

x2+0.2

s2+f3(s3)f2

(s2)x2*01201234511.410.67.8210----11.411.611.811.6--10.610.811.010.811.27.810.010.210.010.4--d2=2，0≤s3≤

4，狀態(tài)轉(zhuǎn)移方程s3=s2+

x2–d2，則0≤

s2+

x2–

d2≤

4，即2≤

s2+

x2≤

6s1=0，則s2=s1+

x1–d1=x1–3；

x1

≤5，則s2≤2生產(chǎn)能力限制0≤x2≤

5，則x2={0,1,2,3,4,5}3月在庫(kù)存量為s3下的最低生產(chǎn)成本34第34頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例k=1x1s1v1

(s1,x1)+f2(s2)=2+

x2+0.2

s2+f2(s2)f1

(s1)x1*3452月在庫(kù)存量為s2下的最低生產(chǎn)成本014.85順序遞推，得出結(jié)論第1月生產(chǎn)5萬(wàn)件s2=s1+

x1–d1=0+5-3=2，第2月不生產(chǎn)s3=s2+

x2–d2=2+0-2=0，第3月生產(chǎn)5萬(wàn)件s4=s3+

x3–d3=0+5-3=2，第4月不生產(chǎn)16.416.614.8d1=3，s1=0，狀態(tài)轉(zhuǎn)移方程則s2=s1+

x1–d1=x1–3；s2≥0，則x1

≥

3，生產(chǎn)能力限制x1≤

5，則3≤

x1

≤5，x1={3,4,5}35第35頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例有一種設(shè)備可以在高低兩種不同的負(fù)荷下運(yùn)行，在高負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量Q1與投入生產(chǎn)的設(shè)備臺(tái)數(shù)x1的關(guān)系為：Q1=9x1

，年完好率(折損后)a=0.75；在低負(fù)荷下生產(chǎn)時(shí)，年產(chǎn)量Q2與投入生產(chǎn)的設(shè)備臺(tái)數(shù)x2的關(guān)系為:Q2=6x2

，年完好率為b=0.96，若開(kāi)始時(shí)擁有完好機(jī)器臺(tái)數(shù)為100臺(tái)，要求制定一個(gè)4年計(jì)劃，在每年初時(shí)應(yīng)決定如何重新分配設(shè)備在高低不同的負(fù)荷下生產(chǎn)，使得4年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。三、機(jī)器負(fù)荷問(wèn)題

36第36頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型每年為一個(gè)階段，即階段變量k=1,2,3,4;狀態(tài)變量sk表示第k年初所擁有的完好機(jī)器臺(tái)數(shù)，s1=100;決策變量xk表示第k年投入高負(fù)荷生產(chǎn)的機(jī)器數(shù)，允許決策集合Xk(sk)={xk︱0≤

xk

≤sk};狀態(tài)轉(zhuǎn)移方程為sk+1=axk+b(sk

–

xk)=0.75xk+0.96(sk

–

xk)=0.96sk–0.21xk;階段指標(biāo)vk(sk,xk)表示第k年的產(chǎn)量：vk(sk,xk)=9xk+6(sk

–

xk)=6sk+3xk;最優(yōu)指數(shù)函數(shù)fk(sk)表示第k階段從sk開(kāi)始到最后階段采用最優(yōu)分配策略實(shí)現(xiàn)的最大產(chǎn)量;37第37頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例K=4f4(s4)是關(guān)于x4

的單增函數(shù)，故x*4=s4

時(shí)，f4(s4)最大，f4(s4)=9s4K=3f3(s3)是關(guān)于x3

的單增函數(shù)，故x*3=s3

時(shí)，f3(s3)最大，f3(s3)=15.75s338第38頁(yè)，共47頁(yè)，2023年，2月20日，星期二第三節(jié)應(yīng)用舉例K=2f2(s2)是關(guān)于x2的單減函數(shù)，故x*2=0

時(shí)，f2(s2