优化方法运筹学课件

1、优化方法运筹学课件 第四章 最优化方法(运筹学) 第一节 线性(Linear Programing )规划 第二节 运输问题和指派问题 第三节 动态规划 优化方法运筹学课件 问题？ 怎样才是最漂亮的最帅？ 金字塔、巴特农神殿、巴黎铁塔等金字塔、巴特农神殿、巴黎铁塔等, ,在文艺复兴时期也更有许在文艺复兴时期也更有许 多以黄金比例创造出来旳作品多以黄金比例创造出来旳作品 人从肚脐开始分人从肚脐开始分, ,上半身到头上半身到头, ,下半身到脚下半身到脚, ,这个比例符合这个比例符合 1:1.168 1:1.168 是最美旳。是最美旳。 鼻子以及嘴巴旳宽度鼻子以及嘴巴旳宽度 。 鼻子侧面字型鼻子侧面

2、字型, ,鼻梁旳长度以及鼻尖高度旳比鼻梁旳长度以及鼻尖高度旳比 。 从正面看来嘴巴长度以及嘴角到脸部轮廓边旳长度比从正面看来嘴巴长度以及嘴角到脸部轮廓边旳长度比 。 脸宽以及脸长各为眼睛长度旳脸宽以及脸长各为眼睛长度旳 5 5 倍以及倍以及 8 8 倍倍, ,比比 = 5:8= 5:8。也。也 相近于相近于 欧洲的古代城堡为什么建成圆形？ 优化方法运筹学课件 优化方法运筹学课件 案例：生产计划问题 例1. 某工厂在计划期内要安排、两种产品的 生产，已知生产单位产品所需的设备台时及A、B两 种原材料的消耗、资源的限制，如下表： v问题：工厂应分别生产多少单位问题：工厂应分别生产多少单位、产品才能

3、产品才能 使工厂获利最多？使工厂获利最多？ 优化方法运筹学课件 第一节 线性规划 一、在管理中一些典型的线性规划应用 二、线性规划的一般模型 三、线性规划问题的计算机求解 （Excel，lingo） 优化方法运筹学课件 第一节 线性规划 一、在管理中一些典型的线性规划应用 1、合理利用线材问题：如何在保证生产的条件下， 下料最少 2、配料问题：在原料供应量的限制下如何获取最大 利润 3、投资问题：从投资项目中选取方案，使投资回报 最大 4、产品生产计划：合理利用人力、物力、财力等， 使获利最大 5、劳动力安排：用最少的劳动力来满足工作的需要 6、运输问题：如何制定调运方案，使总运费最小 优化方

4、法运筹学课件 小知识 茅于轼择优分配原理 茅于轼通过引进帕累托最优理论和帕累托改进理论，提 出他的择优分配原理 帕累托最优（Pareto Optimality）是指资源分配的一种 理想状态：如果固有的一群人和可分配的资源，从一种 分配状态到另一种分配状态的变化中，在没有使任何人 境况变坏的前提下，不会使任何一个人变得更好。帕累 托改进（Pareto improvement）是指资源分配的一种改 进状态：如果固有的一群人和可分配的资源，从一种分 配状态到另一种分配状态的变化中，在没有使任何人境 况变坏的前提下，可以使其中至少一个人变得更好。帕 累托改进是达到帕累托最优的路径和方法。由于从帕累 托

5、改进到帕累托最优的核心精神是资源优化配置，而西 方经济学的本质是配置经济学，“帕累托最优”、“帕 累托改进”成了100多年来西方经济学的核心概念。 优化方法运筹学课件 第一节 线性规划 二、线性规划的一般模型 （一）线性规划的组成： 目标函数 Max F 或 Min F 约束条件 s.t. (subject to) 满足于 决策变量 用符号来表示可控制的因素 优化方法运筹学课件 第一节 线性规划 （二）建模过程 1.理解要解决的问题，了解解题的目标和条件； 2.定义决策变量（ x1 ，x2 ， ，xn ），每一 组值表示一个方案； 3.用决策变量的线性函数形式写出目标函数， 确定最大化或最小化

6、目标； 4.用一组决策变量的等式或不等式表示解决问 题过程中必须遵循的约束条件 优化方法运筹学课件 第一节 线性规划 （三）线性规划模型的一般形式 目标函数： Max （Min） z = c1 x1 + c2 x2 + + cn xn 约束条件：s.t. a11 x1 + a12 x2 + + a1n xn （ =, ） b1 a21 x1 + a22 x2 + + a2n xn （ =, ） b2 am1 x1 + am2 x2 + + amn xn （ =, ） bm x1 ，x2 ， ，xn 0 优化方法运筹学课件 例题分析1：生产计划问题 例1. 某工厂在计划期内要安排、两种产品的 生

7、产，已知生产单位产品所需的设备台时及A、B两 种原材料的消耗、资源的限制，如下表： 问：工厂应分别生产多少单位问：工厂应分别生产多少单位、产品才能使工产品才能使工 厂获利最多？厂获利最多？ 优化方法运筹学课件 例题分析1：生产计划问题 解：工厂应分别生产、产品x1、x2单位，则所求的线性 规划模型为： Max z = 50 x1 + 100 x2 s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0 优化方法运筹学课件 例题分析2：食谱问题 例1 已知某人每周所需的营养成分、所食用的食品及 单位食品所含营养如下表所示： 营养成分营养成分 大米大米 白菜

8、白菜 鸡蛋鸡蛋 猪肉猪肉 营养成分的需要量（周）营养成分的需要量（周） 蛋白质蛋白质 某维生素某维生素 某矿物质某矿物质 a11 a12 a13 a14 a21 a22 a23 a24 a31 a32 a33 a34 b1 b2 b3 单价（元）单价（元） c1 c2 c3 c4 问这个人每周应食用大米、白菜、鸡蛋和猪肉各多问这个人每周应食用大米、白菜、鸡蛋和猪肉各多 少，能使生活费用最省？少，能使生活费用最省？ 优化方法运筹学课件 例题分析2：食谱问题 解：设这个人每周应食用大米、白菜、鸡蛋、猪肉各为x1、 x2、x3、x4，则所求的线性规划模型为： minZ = c1x1+c2x2+c3x

9、3+c4x4 s.t. a11x1+a12x2 +a13x3+a14x4b1 a21x1+a22x2+a23x3+a24x4 b2 a31x1+a32x2+a33x3+a34x4 b3 x1,x2,x3,x4 0 优化方法运筹学课件 小知识 明尼苏达大学建立食物营养价值评估数据库，可对每 天需要的营养与食物作最优化选择 作业：建立自己的小营养优化选择 优化方法运筹学课件 例题分析3：人力资源分配问题 例2某昼夜服务的公交线路每天各时间段内所需司机和乘务 人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连设司机和乘务人员分别在各时间段一开始时上班，并连 续工作八小时续工作八小时(注意

10、每班次才注意每班次才4小时小时)，问该公交线路怎样安排，问该公交线路怎样安排 司机和乘务人员，既能满足工作需要，又配备最少司机和乘司机和乘务人员，既能满足工作需要，又配备最少司机和乘 务人员务人员? 优化方法运筹学课件 例题分析3：人力资源分配问题 解：设 xi 表示从第i班次开始上班的司机和乘务人员数 (i=1,2,3,4,5,6),这样我们建立如下的数学模型。 Min Z = x1 + x2 + x3 + x4 + x5 + x6 s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,

11、x4,x5,x6 0 优化方法运筹学课件 例题分析4：合理下料问题 例4 假定现有一批某种型号的圆钢长8米，需要裁取长米 的毛坯100根、长米的毛坯200根，问应该怎样选择下料方 式才能既满足需要，又使总的用料最省？ 解：各种可能的裁剪方案如下表所示： 型号型号方案方案1 方案方案2 方案方案3 方案方案4需要根数需要根数 2.5米米 1.3米米 3 2 1 0 0 2 4 6 100 200 余料余料(米米) 0.5 0.4 0.3 0.2 优化方法运筹学课件 例题分析4：合理下料问题 设 x1,x2,x3,x4 分别为上面4种方案下料的原材料根数。 这样我们建立如下的数学模型。 Min f

12、 = x1 + x2 + x3 + x4 s.t. 3x1 + 2x2 + x3 100 2x2 + 4x3 + 6x4 200 x1,x2,x3,x4 0 优化方法运筹学课件 例题分析5：投资问题 例5 某部门现有资金200万元，今后五年内考虑给以下的项目 投资。已知： 项目A：从第一年到第五年每年年初都可投资，当年末能收回 本利110%； 项目B：从第一年到第四年每年年初都可投资，次年末能收回 本利125%，但规定每年最大投资额不能超过30万元； 项目C：需在第三年年初投资，第五年末能收回本利140%，但 规定最大投资额不能超过80万元； 项目D：需在第二年年初投资，第五年末能收回本利15

13、5%，但 规定最大投资额不能超过100万元。 问应如何确定这些项目的每年投资额，使得第五年年末拥 有资金的本利金额为最大？ 优化方法运筹学课件 例题分析4：投资问题 解：设 xij ( i = 15，j = 14)表示第 i 年初投资于A(j=1)、 B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的 决策变量： 1 2 3 4 5 A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24 优化方法运筹学课件 例题分析5：投资问题 x51x42x33 x24 s.t. x11+ x12 = 200 x21 + x22+ x24x

14、11(第二年的投资与第一年投资回收的 本利金相等) x31 + x32+ x33x21x12 x41 + x42x31x22 x51 x41x32 xi2 30 ( i =1、2、3、4 ) x33 80 x24 100 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4） 优化方法运筹学课件 线性规划解法（图解法） F变量：x表示A的台数，y表示B的台数 F目标函数：利润最大 max f(x,y)=x6y7 F约束条件：2x+3y=24 2x+y=0 优化方法运筹学课件 图作业法 0510 x Y 10 5 0 2x+y=16 2x+3y=60 3x+2y=40 5x+y=3

15、5 x=0 y=0 优化方法运筹学课件 优化方法运筹学课件 线性规划的图解法 P97 例4： Max S(x,y)=7x+12y 9x+4y=360 4x+5y=200 3x+10y=126x+2y=12 2x+2y=82x+2y=8 4x+12y=244x+12y=24 0=x=70=x=7， 0=y=70=y=7 2 4 6 7 7 6 4 2 6x+2y=12 2x+2y=8 4x+12y=24 y=7 x=7 E(0,7) D(0,6) (0,4) (0,2) (0,0) (2,0) (4,0) A(6,0)G(7,0) F(7,7) C(1,3) B(3,1) 圆圈表示可行域的边界圆

16、圈表示可行域的边界 最优解在圆圈所在的点取得 把这些点分别代入目标把这些点分别代入目标 函数，求得函数，求得S值分别为：值分别为： A1200，B760，C680， D960，E1120，F2520， G1400，所以，所以C为最优为最优 点。点。 优化方法运筹学课件 例:求以下最优解 Max Z(x,y)=2x+3y S.T. x+y=4 x=0 y=0 优化方法运筹学课件 优化方法运筹学课件 线性规划求解结论线性规划求解结论 若线性规划有可行解，则可行域是个凸多边形，或是 凸集（集中任两点线段仍在集中） 若线性规划有最优解，则最优解可能是唯一，也可能 是无穷。如唯一一定在凸多边形的某顶点上

17、；如是无 穷则一定充满凸多边形的一条边界上 如有可行解，但没有有限最优解，这时凸多边形是无 界的，反之不一定成立（如上例） 没有可行解，即可行解集是空集 优化方法运筹学课件 用EXCEL进行线性规划 例：学校准备为学生添加营养餐，每个学生每月至少 要补充60单位碳水倾到物，40单位蛋白质和35单位 脂肪。已知A、B两种营养品的含量价格如下表， 问A、B分别 要多少单位既满足学生需要又价格最省？ A AB B 碳水化合物52 蛋白质32 脂肪51 单价1.5元/斤0.7元/斤 优化方法运筹学课件 第一步：描述问题并建立问题模型 S.T. 5x+2y=60 3x+2y=40 5x+y=35 X,y

18、=0 优化方法运筹学课件 第二步 利用规划求解工具 （注意如没有，需要另外加 载） 优化方法运筹学课件 目标单元格是必须可计算公式 注意是求解最大还是最小值 可变单元格是最优解 约束条件根据需要添加 优化方法运筹学课件 操作实验 ： 对课堂上的线性规划例子用Excel求解 优化方法运筹学课件 实例1 某企业生产混合饲料，规定：蛋白质至少有15%，脂 肪至少4.5%，淀粉至少30%，纤维素不得超过10% 。所提供的原材料有： 花生饼，每吨单价500元，含25%蛋白质、2%脂肪、 10%淀粉、2%纤维素 花生秧，每吨50元，含 8%蛋白质、1%脂肪、5%淀 粉、40%纤维素 骨粉，每吨350元，2

19、0%蛋白质、8%脂肪、1%淀粉 、0.5%纤维素 玉米，每吨450元，7%蛋白质、5%脂肪、40%淀粉 、6%纤维素 满足营养成分前提下，配合费用最低 优化方法运筹学课件 建模 决策变量：四种原料，各自需要为X1、X2、X3、 X4 目标函数：max=500X1+50X2+350X3+450X4 约束条件：25%x1+8%x2+20%x3+7%x415% 2%x1+1%x2+8%x3+5%x44.5% 10%x1+5%x2+1%x3+40%x430% 2%x1+40%x2+0.5%x3+6%x410% X1,X2,X3,X4 0 X1+X2+X3+X4=1(归一条件) 优化方法运筹学课件 优化

20、方法运筹学课件 发现问题 总量没有为1而是 所以要增加约束条件，决策总量单元格G6=1 计算后发现无解,需要重新调整原料和降低营养成份 优化方法运筹学课件 对偶问题与影子价格 在经济活动中可以追求最大利润，也可以追求最低成 本，这是一个问题两种不同表现形式。反映在数学上 ，就是互为对偶的线性规划问题表达，而且这两个问 题可以同时实现。 对偶问题变换规则 原问题原问题对偶问题对偶问题 目标函数max目标函数min 约束条件=约束条件= 约束条件= 对偶变量=对偶变量= 对偶变量= 约束条件=自由变量 自由变量约束条件= 优化方法运筹学课件 例题分析1：生产计划问题对偶问题 例1. 某工厂在计划期

21、内要安排、两种产品的 生产，已知生产单位产品所需的设备台时及A、B两 种原材料的消耗、资源的限制，如下表： 问：工厂应分别生产多少单位问：工厂应分别生产多少单位、产品才能使工产品才能使工 厂获利最多？厂获利最多？ 优化方法运筹学课件 对偶问题 设备x1,原料Ax2，原料Bx3 目标函数minZ=300*x1+400*x2+250*x3 X1+2*x2=50 X1+x2+x3=100 X1、X2、X3=0 优化方法运筹学课件 习题：食品营养例中的对偶问题 S.T. 5x+2y=60 3x+2y=40 5x+y=35 X,y=0 优化方法运筹学课件 对偶 Max S(Z1,Z2,Z)=60*Z1+

22、40*z2+35*z3 S.T. z1,z2,z3=0 优化方法运筹学课件 敏感性分析 注意线性模型与假定非负勾选上 优化方法运筹学课件 敏感性分析作用 低于阴影价格购买或应用该约束条件是好的决策 可以分析哪个约束条件比较敏感，对此部分条件因素 要变化时要慎重决策 优化方法运筹学课件 第二节 运输问题和指派问题（特殊的线性规划问 题） 一、运输问题 二、指派问题 优化方法运筹学课件 案例：产销平衡问题 例1 某公司从两个产地A1、A2将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产 地运往各销地每件物品的运费如下表所示，问：应 如何调运可使总运输费用最小？ 优化方法运筹学

23、课件 案例：产销平衡问题 解：产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输 量表： Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3） 优化方法运筹学课件 EXCEL求解过程 1.建立决策变量区域 2.用函数 sumproduct建立决策目标公式 3.决策区域中，分别对供

24、销，用sum函数进行合计计 算 4.点击目标公式区域，用线性规划 选择目标和变量区域 约束条件设置很重要（变量区域0，sum函数统计的 区域要与常数区域数值相等） 求解完成 注意：如某产销条件不平衡时，只需要在条件上根据 情况修改 优化方法运筹学课件 第二节 运输问题和指派问题 一、运输问题及其模型 A1、 A2、 Am 表示某物资的m个产地； B1、B2、 Bn 表示某物质的n个销地；si 表示产地Ai的产量； dj 表示销 地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价 设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量 问题的模型： （一）产销平衡问题

25、 m n Min f = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,m j = 1 m xij = dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n) 优化方法运筹学课件 第二节 运输问题和指派问题 （二）产大于销问题 m n Min f = cij xij i = 1 j = 1 n s.t. xij si i = 1,2,m j = 1 m xij = dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n) 优化方法运筹学课件 第二节 运输问题和指派问题 （

26、三）销大于产问题 m n Min f = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,m j = 1 m xij dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n) 注：产销不平衡时，可加入假想的产地（销大于产时）注：产销不平衡时，可加入假想的产地（销大于产时） 或销地（产大于销时），把它化为产销平衡问题。或销地（产大于销时），把它化为产销平衡问题。 优化方法运筹学课件 例题分析2：产大于销问题 （四）运输问题的计算机求解 例2、某公司从两个产地A1、A2将物品运往三个 销地B1、B2、B3，各产地的产量

27、、各销地的销量 和各产地运往各销地每件物品的运费如下表所示， 问：应如何调运可使总运输费用最小？ 优化方法运筹学课件 例题分析2：产大于销问题 解：增加一个虚设的销地运输费用为0 优化方法运筹学课件 例题分析3：销大于产问题 例3、某公司从两个产地A1、A2将物品运往三个销 地B1、B2、B3，各产地的产量、各销地的销量和 各产地运往各销地每件物品的运费如下表所示，问： 应如何调运可使总运输费用最小？ B1 B2 B3 产产量量 A1 6 4 6 200 A2 6 5 5 300 销销量量 250 200 200 500 650 优化方法运筹学课件 例题分析3：销大于产问题 解：增加一个虚设的

28、产地运输费用为0 B1 B2 B3 产量产量 A1 6 4 6 200 A2 6 5 5 300 A3 0 0 0 150 销量销量 250 200 200 650 650 优化方法运筹学课件 习题 From/toFrom/toE EF FG GH H Factory Factory supplysupply A A25253535363660601515 B B55553030454538386 6 C C40405050262665651414 D D60604040666627271111 Destination Destination requirementrequirement101

29、0121215159 94646 优化方法运筹学课件 第二节 运输问题和指派问题 二、指派问题（特殊的运输问题） （一）任务数=人数（产销平衡的运输问题） 任务数与人数相等的指派问题实质上就是产销平衡 的运输问题，且每行、每列的产量或销量都等于1。 m n Min f = cij xij i = 1 j = 1 n s.t. xij = 1 i = 1,2,m j = 1 m xij = 1 j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n) 优化方法运筹学课件 例题分析4：指派问题 例13 有一份说明书，要分别译成英、日、德、 俄四种文字，因各人专长不

30、同，他们完成翻译 不同文字所需的时间见下表： 优化方法运筹学课件 解法：匈牙利法 匈牙利法是求解及小型（优化方向为极小）指派问题 的一种方法，这种方法最初由提出，后经改进而形成 ，解法基于匈牙利数学家给出的一个定理而得名。 理论基础: （1）若从效率矩阵(cij)的行（或列）的各元素中分别减去 该行（或列）的最小元素后得到一个新矩阵（bij）,则以（ bij）为效率矩阵的指派问题与原问题有相同的最优解。经 过上述变换后，（bij）中的每行和每列都至少含有一个0元 素，称位于不同行不同列的0元素为独立的0元素。 （2）若（bij）有n个独立的0元素，由此可得一个解矩阵， 方法为在X中令对应于（b

31、ij）的0元素位置的元素为1，其它 位置的元素为0，则X为指派问题的最优解。 （3）定理：矩阵中独立0元素的最多个数等于能覆盖所有0 元素的最少直线数。 优化方法运筹学课件 匈牙利法步骤 第一步 变换效率矩阵（Cij），使变换后效率矩阵（ bij）的每行每列至少出现一个0元素，同时不出现负 元素。（对效率矩阵每行每列减去该行该列最小元素 ） 2 210109 97 7 15154 414148 8 1313141416161111 4 4151513139 9 Cij -2 -4 -11 -4 优化方法运筹学课件 0 08 87 75 5 11110 010104 4 2 23 35 50 0

32、 0 011119 95 5 -5 0 08 82 25 5 11110 05 54 4 2 23 30 00 0 0 011114 45 5 优化方法运筹学课件 第二步 画出包含所有0的直线，并使画出直线条数最 少。如果直线条数与表中的行或列相等，则获最优解 。否则第三步（注意不能画斜线）（例中3条直线0，特别 注意注意要在选项中，将“线性模型”和“假定非负钩 ”选上 优化方法运筹学课件 第二节 运输问题和指派问题 （二）任务数人数（产销不平衡的运输问题） 1、若任务数人数，就增加假想人，就可以化为产 销平衡问题。 2、若任务数 人数，就增加假想工作，就可以化为 产销平衡问题。 优化方法运筹

33、学课件 习题 项目领导者项目领导者1 12 23 3 terryterry101015159 9 CandyCandy9 918185 5 TomTom6 614143 3 优化方法运筹学课件 第三节 动态规划 一、动态规划的基本概念和方法 二、动态规划模型的建立与求解步骤 三、动态规划的应用 优化方法运筹学课件 案例：最短路问题 例16 位于城市A的某公司要把一批货物送到位于城市E的销 售门市部，途中可能经过的城市有B1,B2,B3;C1,C2,C3;D1,D2 等8个城市，问如何走，能使路线最短？ BA C B D B C D E C 4 1 2 3 1 2 3 1 2 9 6 4 8 7

34、 6 8 9 3 5 6 2 3 1 4 3 5 优化方法运筹学课件 第三节 动态规划 一、基本概念和方法： （一）基本概念 1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空 间划分。 2、状态sk：在各阶段开始时的客观条件称为各阶段的状态。 状态可以是数量，也可以是字符。 3、决策uk：从某一状态向下一状态过渡时所做的选择。决 策是所在状态的函数，记为uk(sk)。 决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。 4、状态转移方程 sk+1=Tk(sk, uk)：某一状态以及该状态下的 决策，与下一状态之间的函数关系。 5、策略Pk,n(sk)：从第k阶段开始到最后第n阶

35、段的决策序列， 称k子策略。P1,n(s1)即为全过程策略。 优化方法运筹学课件 第三节 动态规划 6、阶段指标函数dk(sk, uk)：从状态sk出发，选择决策uk所 产生的第k阶段指标。 过程指标函数Vk,n(sk, uk, uk+1, un)：从状态sk出发， 选择决策uk,uk+1, , un所产生的过程指标。动态规划要求过 程指标具有可分离性，即 Vk,n(sk, uk, uk+1, , un) = vk(sk, uk)+Vk+1(sk+1, uk+1, , un)称指标具有可加性，或 Vk,n(sk, uk, uk+1, , un) = vk(sk, uk)Vk+1(sk+1,uk

36、+1, , un)称指标具有 可乘性。 最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过 程指标Vk,n的最优值，即 ),()( , )( nkknk sDx kk PsVsf opt kkk 优化方法运筹学课件 第三节 动态规划 （二）基本方法 1、最优化原理 不管在此最优策略上的某个状态以前的状态和决策如何， 对该状态来说，以后的所有决策必定构成最优子策略。就 是说，最优策略的任意子策略都是最优的。 2、基本方法 从最后一个阶段的优化开始，按逆向顺序逐步向前一阶段 扩展，并将后一阶段的优化结果带到扩展后的阶段中去， 以此逐步向前推进，直到得到全过程的优化结果。 3、递推方

37、程 nksfusdsf kkkkk sDx kkopt kkk , 2 , 1)(),()( 11 )( 优化方法运筹学课件 第三节 动态规划 二、动态规划模型的建立与求解步骤 （一）建立动态规划模型的基本要求 1.所研究的问题必须能够分成几个相互联系 的阶段，而且在每一个都具有需要决策的问 题. 2.在每一阶段都必须有若干个与该阶段相关 的状态。 （二）动态规划的求解步骤 1.列出本阶段的所有可能状态变量sk。 2.对每一状态sk列出所有可能的决策变量 uk(sk)。 优化方法运筹学课件 第三节 动态规划 3.对每一阶段sk,uk(sk)计算本阶段的指标值dk(sk,uk)。 4.确定状态转

38、移方程sk+1=T(sk,uk)，对于每对sk,uk求 出sk+1的值。 5.对于每一对sk,uk，计算相应的指标值 dk(sk,uk)+fk+1(sk+1)。 6.比较各个指标值，取最优者（最大值或最小值） 作为本阶段sk状态开始的后部子过程的最优指标值 fk(sk),相应的决策uk即是本阶段以sk为起始状态的最 优决策u*k。 7.在第一阶段的最优策略确定后，再从第一阶段开 始，根据状态转移方程确定各阶段的最优策略u*k。 优化方法运筹学课件 例题分析1：定价问题 例17 考虑为某新产品定价，该产品的单价从5元、6元、7元、 8元这四种价格中选取其中之一来定价，每年年初允许价格变 动，但幅

39、度不能超过1元。该公司预计该产品畅销只有5年，5 年后将被淘汰，另据销售情况预测，在价格不同的情况下年 度的预计利润入下表所示，问如何定价，能使利润最大？ 单价单价 第一年第一年 第二年第二年 第三年第三年 第四年第四年 第五年第五年 5元元 10 12 15 20 25 6元元 12 13 16 20 24 7元元 14 14 16 18 18 8元元 16 15 15 14 14 优化方法运筹学课件 例题分析1：定价问题 解：（1）该问题按年度分为5个阶段进行，即k=5。 （2）状态变量sk:第k年初的价格（k=1,2,3,4,5） （3）决策变量uk:第k+1年初的价格,即sk+1=uk

40、 （k=1,2,3,4,5） （4）状态转移方程：sk+1=uk=sk-1,sk,sk+1, （k=1,2,3,4,5） （5）最优指标函数的递推公式： fk(sk)=maxdk(sk,uk)+fk+1(sk+1)= maxdk(sk,uk)+fk+1(uk), f6(s6)=0, （k=1,2,3,4,5） 以下我们从第五阶段开始计算 优化方法运筹学课件 例题分析1：定价问题 u5 s5 d5(s5,u5)+f6(s6) 5 6 7 8 f5(s5) U*5 5 25 255 6 24 246 7 18 187 8 14 148 第五阶段：第五阶段：s5=u5 优化方法运筹学课件 例题分析1

41、：定价问题 第四阶段:s5=u4=s4-1,s4,s4+1 u4 s4 d4(s4,u4)+f5(s5)= d4(s4,u4)+f5(u4) 5 6 7 8f4(s4) U*4 5 20+25 20+24 455 6 20+25 20+24 20+18 455 7 18+24 18+18 18+14 426 8 14+18 14+14 327 优化方法运筹学课件 例题分析1：定价问题 第三阶段:s4=u3=s3-1,s3,s3-1 u3 s3 d3(s3,u3)+f4(s4)= d3(s3,u3)+f4(u3) 5 6 7 8 f3(s3) U*3 515+45 15+45 605,6 616+45 16+45 16+42 615,6 7 16+45 16+42 16+32616 8 15+42 15+32 577 优化方法运筹学课件 例题分析1：定价问题 第二阶段:s3=u2=s2-1,s2,s2+1 u2 s2 d2(s2,u2)+f3(s3)= d2(s2,u2)+f3(u2) 5 6 7 8 f2(s2) U*2 5 12+60 12+61 736 6 13+60 13+6113+61 746,7 7 14+61 14+61 14+57756,7 8 15+61 15+57 767 优化方法运筹学课件 例题分析1：定价问题 第一阶段:s2=u1=s1-1,s1,s1+1