运筹学动态规划

1、运筹学运筹学动态规划动态规划复合系统工作可靠性问题姓名：佘俊学号：20070150212内容动态规划的基本概念和基本原理动态规划模型的建立和求解动态规划在经济管理中的应用复合系统工作可靠性问题动态规划基本原理最优化原理 “一个过程的最优策略具有这样的性质：即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的决策应构成最优策略”。AMB内容1、划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。 2、正确选择状态变量选择变量既要能确切描述过程演变又要

2、满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。 3、确定决策变量及允许决策集合通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。动态规划模型的建立动态规划模型的建立 4、确定状态转移方程根据k 阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。 5、确定阶段指标函数和最优指标函数，建立动态规划基本方程 阶段指标函数是指第k 阶段的收益，最优指标函数是指从第k 阶段状态出发到第n 阶段末所获得收益的最优值，最后写出动态规划基本方程。 以上五步是建立动态规划数学模型的一般步骤。由

3、于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。 动态规划的求解离散变量的分段穷举法连续变量的解法逆序解法顺序解法连续变量的离散化解法高维问题的降维法AB1B2C1C2C3D2433332111412ks1u1s2u2s3skuksk+112ks1u1s2u2s3skuksk+1)(),()(111kkkkkukksfusvoptsfk0)(10sf)(),()(11kkkkkukksfusvoptsfk0)(11nnsf11拉格朗日乘子法逐次逼近法疏密格子点法 byaxtsyxppniiniiii

4、i11 .),(max内容复合系统可靠性问题复合系统可靠性问题部件部件1部件部件2.部件部件n部件部件i装有装有zi个备用元件，它失败的概率为个备用元件，它失败的概率为pi(zi);部件部件i装一个备用元件的费用为装一个备用元件的费用为ci，系统总费用不得超过，系统总费用不得超过c;部件部件i装一个备用元件的重量为装一个备用元件的重量为wi，系统总费用不得超过，系统总费用不得超过w;求可以使得求可以使得p达到最大的达到最大的zi的选取方法。的选取方法。 niuwuwcuctsupPupziniiiniiiniiiniii,.2,1 , .)(min)(1max1111非非负负整整数数静态规划的

5、模型为：静态规划的模型为：状态转移方程允许决策集合动态规划基本方程 部件部件1部件部件2.部件部件n某种复合系统由某种复合系统由n个部件串联而成；个部件串联而成；部件部件i装有装有zi个备用元件，它正常工作的概率为个备用元件，它正常工作的概率为pi(zi);系统正常工作的概率为：系统正常工作的概率为： niiizpp1)(部件部件i装一个备用元件的费用为装一个备用元件的费用为ci，系统总费用不得超过，系统总费用不得超过c;部件部件i装一个备用元件的重量为装一个备用元件的重量为wi，系统总费用不得超过，系统总费用不得超过w;求可以使得求可以使得p达到最大的达到最大的zi的选取方法。的选取方法。复

6、合系统可靠性问题复合系统可靠性问题 nizwuwcuctsuppiniiiniiiniii,.2 , 1 , .)( max111非负整数非负整数静态规划的模型为：静态规划的模型为：状态转移方程允许决策集合动态规划基本方程 例：某厂设计一种电子设备，由三种元件D1，D2、D3组成。已知这三种元件的价格和可靠性如表99所示，要求在 设计中所使用元件的费用不超过105元。试问应如何设计使设备的可靠性达到最大(不考虑重量的限制)。元件元件单位单位/元（元（Ck）可靠性可靠性(Pk)D1300.9D2150.8D3200.5 nixcxctsxppiniiiniii,.2 , 1 , .)( max1

7、1非负整数非负整数静态规划的模型为：静态规划的模型为：D1D2D3X1X3X2S3S2S1=105S4状态转移方程状态转移方程动态规划方程动态规划方程局限性局限性应用的局限性维数障碍内容内容 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？物品物品 1 2 j n重量（公斤重量（公斤/ /件）件） a1 a2 aj an每件使用价值每件使用价值 c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。背包问题背包问题静态规划模型： ). 2 . 1( 0max1njxaxaxcZjnijjjnjjj且且为为整整数数状态转移方程允许决策集合动态规划基本方程 内容生产和存储问题生产和存储问题设某公司对某种产品要制定一项n个阶段的生产(或购买)计划。已知它的初始库存量为零，每阶段生产(或购买)该产品的数量有上限的限制；每阶段社会对该产品的需求量是已知的，公司保证供应；在n阶段末的终结库存量为零。问该公司如何制定每个阶段的生产(或采购)计划，从而使总成本最小。状态转移方程允许决策集合动态规划基本方程 内容设备更