运筹学讲义2汇总
- 格式:doc
- 大小:187.50 KB
- 文档页数:22
OPERATIONS RESEARCH运筹学Ⅰ——怎样把事情做到最好第一章绪论♦1.1题解Operations 汉语翻译工作、操作、行动、手术、运算Operations Research日本——运用学港台——作业研究中国大陆——运筹学Operational Research原来名称,意为军事行动研究——历史渊源绪论♦1.2 运筹学的历史早期运筹思想:田忌赛马丁渭修宫沈括运粮Erlang 1917 排队论Harris 1920 存储论Levinson 1930 零售贸易康脱洛维奇1939 LP绪论♦1.2运筹学的历史军事运筹学阶段德军空袭防空系统Blackett运输船编队空袭逃避深水炸弹轰炸机编队绪论♦1.2运筹学的历史管理运筹学阶段战后人员三分:军队、大学、企业大学:课程、专业、硕士、博士企业:美国钢铁联合公司英国国家煤炭局运筹学在中国:50年代中期引入华罗庚推广优选法、统筹法中国邮递员问题、运输问题1.3学科性质▪应用学科▪Morse&Kimball定义:运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。
▪Churchman定义:运筹学是应用科学的方法、技术和工具,来处理一个系统运行中的问题,使系统控制得到最优的解决方法。
▪中国定义:运筹学是应用分析、试验、量化的方法,对经济管理系统中人力、物力、财力等资源进行统筹安排,为决策者提供有依据的最优方案,以实现最有效的管理。
1.4定性与定量♦例:店主进货♦两者都是常用的决策方法♦定性是基础,定量是工具,定量为定性服务。
♦定性有主观性也有有效性,定量有科学性也有局限性。
管理科学的发展,定量越来越多。
但定量不可替代定性。
1.5运筹学的模型♦模型:真实事物的模仿,主要因素、相互关系、系统结构。
♦形象模型:如地球仪、沙盘、风洞♦模拟模型:建港口,模拟船只到达。
学生模拟企业管理系统运行。
♦数学模型:用符号或数学工具描述现实系统。
第一章绪论一运筹学的发展历史1学科起源:二战期间英美等国军事部门集中多学科人员,研究提高武器系统效能,如反空袭雷达控制系统,使雷达和高炮相配合。
诺将物理学家布莱克特(Blackett)领导研究小组“Operational Research”,多学科构成(布莱克特马戏团)。
战争结束后专家转移到企业和院校——学科形成。
2我国古代的运筹思想:齐王赛马——齐王“上中下”,田忌“下上中”丁渭修皇宫——北宋真宗宰相丁渭(澶chan州之盟的主和派),主持皇宫失火后的修复。
宫前大街取土、引汴河运料、完工后回填废土。
3我国近代以来:50年代开始钱学森、许志国等引进运筹学理论,华罗庚教授回国后从事优选法和统筹法研究推广(烧茶壶的故事)4翻译:来自汉高祖“夫运筹帷幄之中,决胜千里之外,吾不如子房;填国家,抚百姓,给饷馈,不绝粮道,吾不如萧何;连百万之众,战必胜,攻必取,吾不如韩信。
”台湾地区直译为“运作研究”。
二运筹学的特点运筹学存在多种定义,如“依照给定目标和条件,从众多方案中选择最优方案的最优化技术”,学科特点:最优化、定量化1 多种专家的协作2 科学的方法:从实际情况出发,通过假设的模型打到一个符合实际的结论3 目的在于解决实际问题。
4 需要系统的信息资料5 需要建立模型——运筹学的核心问题就是通过合适的模型分析系统的未来情况6 对于复杂问题,需要计算机三运筹学的模型运筹学的主要特点是通过模型来描述和分析所认定范围内的系统状态。
分析过程包括:1 系统分析和问题描述。
认定问题的实质——社会经济问题复杂性、不可重复性,不同于具有可控性的物理模型(提高企业效益:开发市场?增加设备?加强研发?)。
明确系统的主要目标(利润最大化、市场占有率最大化、销售收入最大化?GDP增长、可持续协调增长?)、找出系统主要变量和参数、变化范围、相互关系及其对目标的影响。
分析问题的可行性:技术可行性—有无现成的运筹学方法?经济可行性—研究的成本和预期的效果,考虑运筹决策的时间和代价,要对研究问题的深度和广度作出一定限制操作可行性—研究人员的配备2 建立数学模型——要尽可能简单;要能完整的描述所研究的系统。
运筹学复习要点运筹学复习要点第二章线性规划与单纯形法一、标准型:规定具有下述条件的线性规划问题为标准型式的线性规划问题:1、目标函数为求最大;2、约束条件为等式约束;3、决策变量为非负。
二、线性规划问题具有的特征:1、每一问题都用一组决策变量(x1, x2, . . . ,xn)表示某一方案;2这组决策变量的值就代表一个具体方案,一般这些变量值是非负的;3、存在一定的约束条件,它们可用线性等式或不等式表示;4、都有一个要求达到的目标,它们可用决策变量的线性函数表示,称目标函数。
根据问题不同,要求目标函数实现最大化或最小化。
三、图解法的结论:1、可行域一定是凸集,即该区域内任意两点间连线上的点仍在该区域内;2、线性规划最优解不可能在凸集内的点上实现;3、线性规划问题有可能存在无穷多最优解;4、如果可行域无界,则最优解可能是无界解;5、如果不存在可行域,则没有可行解,也一定不存在最优解;6图解法只适用于两个决策变量的情况。
四、单纯形法:其基本思路是首先确定一个初始基可行解,然后判断该基可行解是否为最优解。
如果是最优解,则求解过程结束;如果不是最优解,则在此基础上变换找出另一个基可行解,该基可行解的目标函数值应该优于原基可行解。
再判断新的基可行解是否为最优解,如果是最优解,则求解过程结束;如果不是最优解,则在此基础上变换再找出另一个新基可行解,如此进行下去,直到找到最优解为止。
五、最优性检验与解的形式:最优解的判别定理,若X(0) = (b′1, b′2, ……… ,b′m, 0, …… , 0)T为对应于基B的一个基可行解,且对于一切j = m + 1, …… , n,有σj6 0,则X(0)为最优解,称σj为检验数。
无穷最多解判别定理,若X(0) = (b′1, b′2, …… , b′m, 0, …… , 0)T为对应于基B的一个基可行解,且对于一切j = m + 1, …… , n,有σj6 0,又存在某个非基变量的检验数σm+k= 0,则线性规划问题有无穷多最优解。
第二章 线性规划教学重点:线性规划可行区域的几何结构,基本可行解及可行区域的基本定理,单纯形方法,两阶段法,对偶和对偶理论,灵敏度分析。
教学难点:线性规划可行区域的几何结构,基本可行解及可行区域的基本定理,单纯形方法,两阶段法,对偶性,灵敏度分析。
教学课时:24学时主要教学环节的组织:首先通过各种形式的例子归纳出线性数学规划的一般形式,然后在详细讲解主要内容的基础上,尽可能以图形和例题的形式给以形象的说明,使学生对知识点有更直观、具体的认识。
再通过大量习题巩固知识,也可以应用软件包解决一些实际问题。
第一节 线性规划问题教学重点:线性规划问题的实例,线性规划的一般形式、规范形式和标准形式教学难点:线性规划一般形式转换成标准形式。
教学课时:2学时主要教学环节的组织:首先通过几个实例总结出线性规划问题的一般形式,再介绍如何将一般形式转换成标准形式。
1、线性规划问题举例 生产计划问题某工厂用三种原料生产三种产品,已知的条件如下表所示,试制订总利润最大的生产计划可控因素(所求变量):设每天生产3种产品的数量分别为321,,x x x . 目标:使得每天的生产利润最大,就是使得利润函数:321453x x x ++ 达到最大. 受制条件:每天原料的需求量不超过可用量:原料1P :15003221≤+x x原料2P :8004232≤+x x原料3P :2000523321≤++x x x蕴含约束:产量为非负数0,,321≥x x x模型321453max x x x ++15003221≤+x xs.t. 8004232≤+x x2000523321≤++x x x0,,321≥x x x运输问题一个制造厂要把若干单位的产品从两个仓库2,1;=i A i 发送到零售点4,3,2,1;=j B j ,仓库 i A 能供应的产品数量为2,1;=i a i ,零售点 j B 所需的产品的数量为4,3,2,1;=j b j 。
运筹学讲义《管理运筹学》1、运筹学的工作步骤(1)提出和形成问题.(2)建立模型.(3)求解.(4)解的检验.(5)解的控制.(6)解的实施.2、运筹学模型三种基本形式:(1)形象模型(2)模拟模型(3)符号或数学模型构模的五种方法和思路: (1)直接分析法 (如线性规划)(2)类比法(手机的普及与电视机的普及)(3)数据分析法(如汽车销售量预测模型)(4)试验分析法(销售量与价格之间的关系模型)(5)想定(构想)法(销售与心理)3、如何将线性规划问题的一般形式化为标准形式:1.如果问题是求目标函数的最小值,求min f=∑Cjxj则可先将目标函数乘(-1),化为求极大值问题,即求 max Z=-f=-∑Cjxj2.如果有某个bk≤0,则可将该等式两边均乘以(-1),使右端常数项bk=-bk≥03.如果第k个约束条件是∑akjxj≤bk,引入松弛变量sk≥0 , 将它写成∑akjxj+sk=bk如果第l个约束条件是∑aljxj≥bl则引入剩余变量(也可称为松弛变量)sl≥0,将它写成∑aljxj—sl=bl 且使松弛变量和剩余变量在目标函数中的系数为零。
4.如果对某个变量xj没有非负限制(这种变量称为自由变量或无约束变量),则引进两个非负变量xj′,xj″,令xj=xj′-xj″代人目标函数和约束条件中,可将它化为对全部变量都有非负限制的问题。
4、①目标函数为变量的线性函数,约束条件也为变量的线性等式或不等式的模型称之为线性规划。
②如果目标函数是变量的非线性函数,或约束条件中含有变量非线性的等式或不等式的数学模型则称之为非线性规划。
③满足所有约束条件的解称为该线性规划的可行解。
④把使得目标函数值最大(即利润最大)的可行解称为该线性规划的最优解,此目标函数值称为最优目标函数值,简称最优值5、图解法的启示1.最优解:如果某一个线性规划问题有最优解,则一定有一个可行域的顶点对应一个最优解。
(一般为封闭可行域凸集)2.无穷多个最优解:若将上例中的目标函数变为求maxZ=50x1+50x2则代表目标函数的直线平移到最优位置后将和直线x1+x2=300重合。
运筹学课程讲义第一部分 线性规划 第一章 线性规划的基本性质 1.1 线性规划的数学模型一、 线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。
桌子售价50元/个,椅子售价30元/个。
生产桌子和椅子需木工和油漆工两种工种。
生产一个桌子需要木工4小时,油漆工2小时。
生产一个椅子需要木工3小时,油漆工1小时。
该厂每月可用木工工时为120小时,油漆工工时为50小时。
问该厂如何组织生产才能使每月的销售收入最大?213050m ax x x z +=⎪⎩⎪⎨⎧≥≤+≤+0,50212034212121x x x x x x 例:某工厂生产某一种型号的机床。
每台机床上需要 2.9m 、2.1m 、1.5m 的轴,分别为1根、2根和1根。
这些轴需用同一种圆钢制作,圆钢的长度为74m 。
如果要生产100台机床,问应如何安排下料,才能用料最省?二、 数学模型的标准型 1. 繁写形式 2. 缩写形式 3. 向量形式 4. 矩阵形式三、 任一模型如何化为标准型?1. 若原模型要求目标函数实现最大化,如何将其化为最小化问题?2. 若原模型中约束条件为不等式,如何化为等式?3. 若原模型中变量x k 是自由变量,如何化为非负变量?4. 若原模型中变量x j 有上下界,如何化为非负变量?⎪⎪⎩⎪⎪⎨⎧≥≤-=--≤+--≥-+----=无约束321321321321321,0,052010651535765max x x x x x x x x x x x x x x x z 令'''3'3''3'331'1,0,,,Z Z x x x x x x x =-≥-=-=⎪⎪⎩⎪⎪⎨⎧≥-=+-++=+-+-=+-+-+--+-++-=0,,,,,,,5201010651533507765min 7654''3'32'17''3'32'15''3'32'164''3'32'1765''3'32'1'x x x x x x x x x x x x x x x x x x x x x x x x Mx Mx x x x x x z 1. 2图解法该法简单直观,平面作图适于求解二维问题。
第二章线性规划与单纯形法所以线性规划问题的求解变得相当的重要,首先最为直观的为图解法,通过作图直观方便的求解相应解。
由于其直观的结果,可以轻易地看出三中情况:1、无穷多最优解2、无界解3、无可行解。
为了形式化求解办法我们将所有的线性规划问题化为标准形式。
区分四个概念:1、可行解:2、基:3、基可行解:4、可行基:由于图解法自身的弊端,即只能表示两个变量(最多三个)的规划问题,所以产生了单纯形法:其本质是对于图解法的拓展,所谓的单纯形其实就是指各个维度中的图形,只不过图解法是单纯形法在二维中的情况。
而单纯形的寻优其实就是对于单纯形的各个边界以及定点的寻优。
单纯形法的根基:单纯形法基于以下几个定理:几个概念1、凸集:K是n维空间的一点集,若任意的两点X(1)ϵK,X(2)ϵK的连线上的所有的点满足αX(1)+ (1-α)X(1) ϵK,(0≤α≤1);则K为凸集。
2、凸组合:3、顶点:几个定理:1、若线性规划问题存在可行域,则其可行域是凸集2、线性规划问题的可行解X=(x1,x2,x3……xn)T为基可行解的充分必要条件是X的正分量所对应的系数列向量是线性独立的。
3、线性规划问题的基可行解X对应于可行域D的顶点。
4、若K是有界凸集,则任何一点X ϵK科表示为K的顶点的凸组合5、若可行域有界,线性规划问题的目标函数一定可以再起可行域的顶点上达到最优松弛变量与人工变量:为了使约束中的不等式变为等式的标准形式,我们将多余的部分表示成松弛变量就得到了标准形式,加入的松弛变量其实质是表明没有利用上的资源,人工变量其实就像是为了方便找初始基多引入的东西。
不过要说的是人工变量在目标函数中的系数的正负要注意。
其实一般来说≤ 的情况下要“+松弛变量”;在≥ 的情况下要“-松弛变量+人工变量”。
但是可以将≥ 的情况两边取负,变成≤ 的情况然后“+松弛变量”,这实质上是等价于在原式子基础上单单“-松弛变量”。
人工变量的功用有待探讨……人工变量的功用:标准形式的转换step:目标函数→变量→约束条件转为max →注意无约束的变量→注意≥的那个“减松加人”解的判别:1、最优解的判别准则:所有的非基变量σj≤0 ;2、无穷多最优解的判别准则:有一个非基变量σj=0,其余的非基变量σj≤0 ;3、无界解的判别准则:有一个σj>0,但是对应的该列系数都≤0 ;4、无解的判别准则:所有σj≤0但是基变量中存在人工变量而且人工变量不为0 ;基变换:1、在所有的非基变量σj中找正的最大的为换入变量2、在所有的非基变量Ѳ中找正的最小的为换出变量关于两阶段法:两阶段法实质上是在真正求解之前做的预判,求min条件下的人工变量的影响,目标是证明所加的人工变量其实可以全部同时取零,如若不然则证明原问题无解也就不用再费劲求解复杂的原问题了,但是一旦证明其可以同时取到0还要在去掉人工变量用松弛变量求解最优解。
第二部分动态规划(Dymamic Programming)第三章动态规划动态规划是解决一类多阶段决策问题的优化方法,也是考察问题的一种途径,而不是一种算法(如LP 单纯形法)。
因此它不象LP 那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。
动态规划方法是现代企业管理中的一种重要决策方法。
如果一个问题可将其过程划分为若干个相互联系的阶段问题,且它的每一阶段都需进行决策,则这类问题均可用动态规划方法进行求解。
根据多阶段决策过程的时序和决策过程的演变,动态规划方法有以下四种类型:离散确定性、离散随机性、连续确定性和连续随机性。
§1动态规划的基本概念和最优化原理一、引例(最短路线问题)上图是一个线路网络,两点之间连线上的数字表示两点间的距离(或费用),试求一条由A 到E 的铺管线路,使总距离最短(或总费用最小)。
将该问题划分为4个阶段的决策问题,即第一阶段为从A 到B j (j=1,2,3),有三种决策方案可供选择;第二阶段为从B j 到C j (j=1,2,3),也有三种方案可供选择;第三阶段为从C j 到D j (j=1,2,有两种方案可供选择;第四阶段为从D j 到E ,只有一种方案选择。
如果用完全枚举法,则可供选择的路线有3×3×2×1=18(条),将其一一比较才可找出最短路线:A →B 1→C 2→D 3→E其长度为15。
显然,这种方法是不经济的,特别是当阶段数很多,各阶段可供的选择也很多时,这种解法甚至在计算机上完成也是不现实的。
由于我们考虑的是从全局上解决求A 到E 的最短路问题,而不是就某一阶段解决最短路线,因此可考虑从最后一阶段开始计算,由后向前逐步推至A 点:第四阶段,由D 1到E 只有一条路线,其长度f 4(D 1)=4,同理f 4(D 2)=3。
第三阶段,由C j 到D i 分别均有两种选择,即⎡6+4*⎤⎡C 1D 1+f 4(D 1⎤f 3(C 1=min ⎢⎥=10,决策点为D 1 ⎥=min ⎢(C D +f D 42⎦⎣12⎣8+3⎦⎡C D +f 4(D 1⎤⎡3+4*⎤f 3(C 2=min ⎢21=min ⎥⎢5+3⎥=7, 决策点为D 1 (C D +f D ⎣⎦42⎦⎣22⎡C D +f 4(D 1⎤⎡8+4⎤f 3(C 3=min ⎢31=min =8,决策点为D 2 ⎥⎢*⎥⎣5+3⎦⎣C 3D 2+f 4(D 2⎦第二阶段,由B j 到C j 分别均有三种选择,即:⎡B 1C 1+f 3(C 1⎤⎡1+10⎤⎥=min ⎢*⎥=10,决策点为C (f 2(B 1=min ⎢B C +f C 222323+7⎢⎥⎢⎥⎢⎢⎣6+8⎥⎦⎣B 3C 3+f 3(C 3⎥⎦⎡B 2C 2+f 3(C 1⎤⎡8+10⎤⎥=min ⎢*⎥=14,决策点为C 或C (f 2(B 2=min ⎢B C +f C 237+72232⎢⎥⎢⎥* ⎢⎢⎣6+8⎥⎦⎣B 3C 3+f 3(C 3⎥⎦⎡B 3C 1+f 3(C 1⎤⎡2+10⎤⎥=min ⎢*⎥=11,决策点为C (f 2(B 3=min ⎢B C +f C 232324+7⎢⎥⎢⎥⎢⎢⎣6+8⎥⎦⎣B 3C 3+f 3(C 3⎥⎦第一阶段,由A 到B ,有三种选择,即:⎡AB 1+f 2(B 2⎤⎡5+10*⎤⎥=min ⎢⎥=15,决策点为B 1 (f 1(A =min ⎢AB +f B 2223+14⎢⎥⎢⎥⎢⎢⎣5+11⎥⎦⎣AB 5+f 2(B 5⎥⎦f 1(A=15说明从A 到E 的最短铺管线长为1,最短路线的确定可按计算顺序反推而得。
即A →B 1→C 2→D 1→E图中各点上方框的数,表示该点到E 的最短距离。
图中双箭线表示从A 到E 的最短路线。
从引例的求解过程可以得到以下启示:①对一个问题是否用上述方法求解,其关键在于能否将问题转化为相互联系的多个阶段的决策问题。
所谓多阶段决策问题是:把一个问题看作是一个前后关联具有链状结构的多阶段过程,也称为序贯决策过程。
如下图所示:②在处理各阶段决策的选取上,不仅只依赖于当前面临的状态,而且还要注意对以后的发展。
即是从全局考虑解决局部(阶段)的问题。
③各阶段选取的决策,一般与“时序”有关,决策依赖于当前的状态,又随即引起状态的转移,整个决策序列就是在变化的状态中产生出来,故有“动态”含义。
因此,把这种方法称为动态规划方法。
④决策过程是与阶段发展过程逆向而行。
二、动态规划的基本概念1、阶段。
阶段的划分,一般根据时序和空间的自然特征来划分,但要便于把问题的过程能转化为阶段决策的过程。
描述阶段的变量称为阶段变量,常用自然数k 表示。
如引例可划分为4个阶段求解,k=1,2,3,4。
2、状态。
状态就是阶段的起始位置。
它既是该阶段某支路的起点,又是前一阶段某支路的终点。
(1)状态变量和状态集合。
描述过程状态的变量称为状态变量。
它可用一个数、一组数或一向量(多维情形)来描述,常用S k 表示第k 阶段的状态变量。
通常一个阶段有若干个状态。
第k 阶段的状态就是该阶段所有始点的集合。
如引例中S 1={A },S 2={B 1, B 2, B 3},S 3={C 1, C 2, C 3},S 4={D 1, D 2}(2)状态应具有无后效性(即马尔可夫性)。
即如果某阶段状态给考虑,则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。
在构造决策过程的动态规划模型时,不能仅由描述过程的具体特征这点去规定状态变量,而要充分注意是否满足无后效性要求。
3、决策与决策变量。
在某阶段对可供选择状态的决定(或选择),称为决策。
描述的变量称为决策变量。
常用d k (Sk 表示第k 阶段处于状态S k 时的决策变量,它是状态变量的函数。
决策变量允许取值的范围,称为允许决策集合,常用D k (Sk 表示。
显然d k (S k )∈D k (Sk 。
如在引例的第一阶段中,若从B 1出发,D 2(B 1)={C 1, C 2, C 3},如果决定选取C 2,则d 2(B 1)=C2。
4、策略与子策略。
策略是一个决策序列的集合。
当k=1时,P in (S 1)={d 1(S 1, d 2(S 2, d n (S n }就称为全过程的一个策略,简称策略,简记为P in (S1.称P k,n (Sk = {d k (S k 1, d k +12(S k +1, d n (S n }为由第k 阶段开始到最后阶段止的一个子策略,简称后部子策略。
简记为P k,n (Sk称可供选择策略的范围,为允许策略集,用P 表示。
动态规划方法就是要从允许策略集P 中找出最优策略P in *。
5、状态转移方程。
它是确定过程由某一阶段的一个状态到下一阶段另一状态的演变过程,用S k+1=Tk (Sk ,d k 表示。
该方程描述了由第k 阶段到第k+1阶段的状态转移规律。
因此又称其为状态转移函数。
6、阶段指标、指标函数和最优指标函数(1)衡量某阶段决策效益优劣的数量指标,称为阶段指标,用v k (Sk ,d k 表示第k 阶段的阶段指标。
在不同的问题中,其含义不同。
它可以是距离、利润、成本等。
在引例中,用d k =Uk (Sk ,d k 表示在第k 阶段由点S k 到点S k+1=dk (Sk 距离。
如d 2(B3,C 1=2。
(2)用于衡量所选定策略优劣的数量指标,称为指标函数。
它是定义在全过程和所有后部子过程上确定的数量函数。
记为V k,n (Sk ,P k,n .V k,n (Sk ,P k,n =Vk,n (Sk ,d k ,S k+1, …S n+1 k=1,2,…,n 。
构成动态规划模型的指标函数,应具有可分离性,并满足递推关系。
常见的指标函数的形式有:①V k , n (S k , u k , S k +1 , S n +1=∑v (Sj j =kn j =knj, d j =v k (S ku , d k +V k +1, k (S k +1, P k , n②V k , n (S k , u k , S k +1 , S n +1=∏u i (S j u j =v k (S ku , d k ⋅V k +1(S k +1, d k +1 S n +1 (3)最优指标函数f k (Sk , 表示从第k 阶段的状态S k 开始采用最优子策略P*k,n ,到第n 阶段的终止时所得到的指标函数值。
即f k (Sk =0PtVk,n (Sk ,u k , …S n+1其中0Pt 是最优化(0Ptimiyation )的缩写,可根据题意取max 或min 。
在引例中,指标函数V k,n 表示在第k 阶段由点S k 至终点E 的距离。
f k (sk 表示第k 阶段点S k 到终E 的最短距离。
f 2(B1=10表示从第2阶段中的点B 1到点E 的最短距离。
7、基本方程(递推关系式)从引例求A 到E 的最短路的计算过程中可以看出,在求解的各个阶段,我们利用了k 阶段与k+1阶段之间的递推关系;U k (s k , d k +f k +1(s k +1}⎡f k (s k =min {⎢d k (s k ∈D k (S k , (k =4, 3, 2, 1 ⎢⎢⎣f 5(s 5=0一般地,若V k , n =∑U j (S j , d j , 则有j =k nU k (s k , d k +f k +1(s k +1 }, ⎡f k (s k =0Pt {⎢d k ∈D k (s k k =n , n -1, 1 ⎢⎢⎣f n +1(s n +1 =0(边界条件若V k , n =∏U j (s j , d j , 则有j =knU k (s k , d k ⋅f k +1(s k +1 }⎡f k (s k =0pt {⎢d k (s k ∈D k (s k , (k =n , n -1, 1 ⎢⎢⎣f n +1(s n +1 =1(边界条件以上递推关系式称为动态规划的基本方程。
三、动态规划方法的基本思想与最优化原理1、基本思想:动态规划方法的关键在于正确地写出基本方程,因此首先必须将问题的过程划分为多个相互联系的多阶段决策过程,恰当地选取状态变量和决策变量及定义最优指标函数,从而把问题化成一族同类型的子问题。
然后从边界条件开始,逆过程行进方向,逐段递推寻优。
在每个子问题求解时,均利用它前面已求出的子问题的最优化结果依次进行,最后一个子问题所得的最优解,就是整个问题的最优解。
在多阶段决策过程中,动态规划方法是既把当前的一段和未来的各段分开,又把当前效益和未来效益结合起来考虑的一种最优化方法。
因此,每阶段决策的选取是从全局来考虑,与该段的最优选择一般是不同的。