《优化方法运筹学PPT课件》由会员分享，可在线阅读，更多相关《优化方法运筹学PPT课件（93页珍藏版）》请在金锄头文库上搜索。
1、第四章最优化方法(运筹学)第一节线性(LinearPrograming)规划第二节运输问题和指派问题第三节动态规划问题？怎样才是最漂亮的最帅？金字塔、巴特农神殿、巴黎铁塔等金字塔、巴特农神殿、巴黎铁塔等,在文艺复兴时期也更有许在文艺复兴时期也更有许多以黄金比例创造出来旳作品多以黄金比例创造出来旳作品人从肚脐开始分人从肚脐开始分,上半身到头上半身到头,下半身到脚下半身到脚,这个比例符合这个比例符合1:1.168是最美旳。是最美旳。鼻子以及嘴巴旳宽度鼻子以及嘴巴旳宽度=1:1.618。鼻子侧面字型鼻子侧面字型,鼻梁旳长度以及鼻尖高度旳比鼻梁旳长度以及鼻尖高度旳比=1:1.618。从正面看来嘴巴长度
2、以及嘴角到脸部轮廓边旳长度比从正面看来嘴巴长度以及嘴角到脸部轮廓边旳长度比=1:1.618。脸宽以及脸长各为眼睛长度旳脸宽以及脸长各为眼睛长度旳5倍以及倍以及8倍倍,比比=5:8。也相。也相近于近于1:1.618欧洲的古代城堡为什么建成圆形？案例：生产计划问题例1.某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：v问题：工厂应分别生产多少单位问题：工厂应分别生产多少单位、产品才能产品才能使工厂获利最多？使工厂获利最多？第一节线性规划一、在管理中一些典型的线性规划应用二、线性规划的一般模型三、线性规划问题的计算机求解（Excel
3、，lingo）第一节线性规划一、在管理中一些典型的线性规划应用1、合理利用线材问题：如何在保证生产的条件下，下料最少2、配料问题：在原料供应量的限制下如何获取最大利润3、投资问题：从投资项目中选取方案，使投资回报最大4、产品生产计划：合理利用人力、物力、财力等，使获利最大5、劳动力安排：用最少的劳动力来满足工作的需要6、运输问题：如何制定调运方案，使总运费最小小知识茅于轼择优分配原理茅于轼通过引进帕累托最优理论和帕累托改进理论，提出他的择优分配原理帕累托最优（ParetoOptimality）是指资源分配的一种理想状态：如果固有的一群人和可分配的资源，从一种分配状态到另一种分配状态的变化中，在
4、没有使任何人境况变坏的前提下，不会使任何一个人变得更好。帕累托改进（Paretoimprovement）是指资源分配的一种改进状态：如果固有的一群人和可分配的资源，从一种分配状态到另一种分配状态的变化中，在没有使任何人境况变坏的前提下，可以使其中至少一个人变得更好。帕累托改进是达到帕累托最优的路径和方法。由于从帕累托改进到帕累托最优的核心精神是资源优化配置，而西方经济学的本质是配置经济学，“帕累托最优”、“帕累托改进”成了100多年来西方经济学的核心概念。第一节线性规划二、线性规划的一般模型（一）线性规划的组成：目标函数MaxF或MinF约束条件s.t.(subjectto)满足于决策变量用符
5、号来表示可控制的因素第一节线性规划（二）建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件第一节线性规划（三）线性规划模型的一般形式目标函数：Max（Min）z=c1x1+c2x2+cnxn约束条件：s.t.a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2am1x1+am2x2+amnxn（=,）bm x1，x2，xn0例题分析1：生产计划问题例1.某工厂在
6、计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问：工厂应分别生产多少单位问：工厂应分别生产多少单位、产品才能使工产品才能使工厂获利最多？厂获利最多？例题分析1：生产计划问题解：工厂应分别生产、产品x1、x2单位，则所求的线性规划模型为：Maxz=50x1+100x2s.t.x1+x23002x1+x2400x2250x1,x20例题分析2：食谱问题例1已知某人每周所需的营养成分、所食用的食品及单位食品所含营养如下表所示：营养成分营养成分 大米大米 白菜白菜 鸡蛋鸡蛋 猪肉猪肉 营养成分的需要量（周）营养成分的需要量（周）蛋白质蛋白质
7、某维生素某维生素某矿物质某矿物质 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+c3x3+c4x4s.t.a11x1+a12x2+a13x3+a14x4b1a21x1+a22x2+a23x3+a24x4b2a3
8、1x1+a32x2+a33x3+a34x4b3x1,x2,x3,x40小知识明尼苏达大学建立食物营养价值评估数据库，可对每天需要的营养与食物作最优化选择作业：建立自己的小营养优化选择例题分析3：人力资源分配问题例2某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连设司机和乘务人员分别在各时间段一开始时上班，并连续工作续工作八小时八小时(注意每班次才注意每班次才4小时小时)，问该公交线路怎样安排，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员务人员?例题
9、分析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,x4,x5,x6 0例题分析4：合理下料问题例4假定现有一批某种型号的圆钢长8米，需要裁取长2.5米的毛坯100根、长1.3米的毛坯200根，问应该怎样选择下料方式才能既满足需要，又使总的用料最省？解：各种可能的裁剪方案如下表所
10、示：型号型号方案方案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种方案下料的原材料根数。这样我们建立如下的数学模型。Minf=x1+x2+x3+x4s.t.3x1+2x2+x31002x2+4x3+6x4200 x1,x2,x3,x40例题分析5：投资问题例5 某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到
11、第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过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 x11x21x31x41x51 B x12x22x32x42C
12、x33Dx24例题分析5：投资问题Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11(第二年的投资与第一年投资回收的本利金相等) x31 + x32+ x33 = 1.1x21+ 1.25x12 x41 + x42 = 1.1x31+ 1.25x22 x51 = 1.1x41+ 1.25x32 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的
13、台数，y表示B的台数F目标函数：利润最大maxf(x,y)=x6y7F约束条件：2x+3y=242x+y=0图作业法0510xY10502x+y=162x+3y=603x+2y=405x+y=35x=0y=0线性规划的图解法P97 例4：Max S(x,y)=7x+12y9x+4y=3604x+5y=2003x+10y=122x+2y=84x+12y=240=x=7，0=y=72 4 6 776426x+2y=122x+2y=84x+12y=24y=7x=7E(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
14、)圆圈表示可行域的边界圆圈表示可行域的边界最优解在圆圈所在的点取得把这些点分别代入目标把这些点分别代入目标函数，求得函数，求得S值分别为：值分别为：A1200，B760，C680，D960，E1120，F2520，G1400，所以，所以C为最优点。为最优点。例:求以下最优解MaxZ(x,y)=2x+3yS.T.x+y=4x=0y=0线性规划求解结论线性规划求解结论若线性规划有可行解，则可行域是个凸多边形，或是凸集（集中任两点线段仍在集中）若线性规划有最优解，则最优解可能是唯一，也可能是无穷。如唯一一定在凸多边形的某顶点上；如是无穷则一定充满凸多边形的一条边界上如有可行解，但没有有限最优解，这时
15、凸多边形是无界的，反之不一定成立（如上例）没有可行解，即可行解集是空集用EXCEL进行线性规划例：学校准备为学生添加营养餐，每个学生每月至少要补充60单位碳水倾到物，40单位蛋白质和35单位脂肪。已知A、B两种营养品的含量价格如下表，问A、B分别要多少单位既满足学生需要又价格最省？AB碳水化合物52蛋白质32脂肪51单价1.5元/斤0.7元/斤第一步：描述问题并建立问题模型MinS(x,y)=1.5x+0.7yS.T.5x+2y=603x+2y=405x+y=35X,y=0第二步利用规划求解工具（注意如没有，需要另外加载）目标单元格是必须可计算公式注意是求解最大还是最小值可变单元格是最优解约束
16、条件根据需要添加操作实验：对课堂上的线性规划例子用Excel求解实例1某企业生产混合饲料，规定：蛋白质至少有15%，脂肪至少4.5%，淀粉至少30%，纤维素不得超过10%。所提供的原材料有：花生饼，每吨单价500元，含25%蛋白质、2%脂肪、10%淀粉、2%纤维素花生秧，每吨50元，含8%蛋白质、1%脂肪、5%淀粉、40%纤维素骨粉，每吨350元，20%蛋白质、8%脂肪、1%淀粉、0.5%纤维素玉米，每吨450元，7%蛋白质、5%脂肪、40%淀粉、6%纤维素满足营养成分前提下，配合费用最低建模决策变量：四种原料，各自需要为X1、X2、X3、X4目标函数：max=500X1+50X2+350X3
17、+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,X40X1+X2+X3+X4=1(归一条件)发现问题总量没有为1而是1.17所以要增加约束条件，决策总量单元格G6=1计算后发现无解,需要重新调整原料和降低营养成份对偶问题与影子价格在经济活动中可以追求最大利润，也可以追求最低成本，这是一个问题两种不同表现形式。反映在数学上，就是互为对偶的线性规划问题表达，而且这两个问题可以同时实现。对偶问题变换规则原问题原问题对偶
18、问题对偶问题目标函数max目标函数min约束条件=约束条件=约束条件=对偶变量=对偶变量=对偶变量=约束条件=自由变量自由变量约束条件=例题分析1：生产计划问题对偶问题例1.某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问：工厂应分别生产多少单位问：工厂应分别生产多少单位、产品才能使工产品才能使工厂获利最多？厂获利最多？对偶问题设备x1,原料Ax2，原料Bx3目标函数minZ=300*x1+400*x2+250*x3S.TX1+2*x2=50X1+x2+x3=100X1、X2、X3=0习题：食品营养例中的对偶问题MinS(x
19、,y)=1.5x+0.7yS.T.5x+2y=603x+2y=405x+y=35X,y=0对偶MaxS(Z1,Z2,Z)=60*Z1+40*z2+35*z3S.T.5*z1+3*z2+5*z3=1.52*z1+2*z2+z3=0敏感性分析注意线性模型与假定非负勾选上敏感性分析作用低于阴影价格购买或应用该约束条件是好的决策可以分析哪个约束条件比较敏感，对此部分条件因素要变化时要慎重决策第二节运输问题和指派问题（特殊的线性规划问题）一、运输问题二、指派问题案例：产销平衡问题例1某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如
20、下表所示，问：应如何调运可使总运输费用最小？案例：产销平衡问题解：产销平衡问题：总产量=总销量设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.决策区域中，分别对供销，用su
21、m函数进行合计计算4.点击目标公式区域，用线性规划选择目标和变量区域约束条件设置很重要（变量区域0，sum函数统计的区域要与常数区域数值相等）求解完成注意：如某产销条件不平衡时，只需要在条件上根据情况修改第二节运输问题和指派问题一、运输问题及其模型A1、A2、Am表示某物资的m个产地；B1、B2、Bn表示某物质的n个销地；si表示产地Ai的产量；dj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价设xij为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：（一）产销平衡问题mnMinf=cij xiji=1j=1ns.t.xij=sii=1,2,m j=1mxi
22、j=djj=1,2,ni=1xij0(i=1,2,m;j=1,2,n)第二节运输问题和指派问题（二）产大于销问题mnMinf=cij xiji=1j=1ns.t.xijsii=1,2,m j=1mxij=djj=1,2,ni=1xij0(i=1,2,m;j=1,2,n)第二节运输问题和指派问题（三）销大于产问题mnMinf=cij xiji=1j=1ns.t.xij=sii=1,2,m j=1mxijdjj=1,2,ni=1xij0(i=1,2,m;j=1,2,n)注：产销不平衡时，可加入假想的产地（销大于产时）注：产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时），把它化为产销
23、平衡问题。或销地（产大于销时），把它化为产销平衡问题。例题分析2：产大于销问题（四）运输问题的计算机求解例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？例题分析2：产大于销问题解：增加一个虚设的销地运输费用为0例题分析3：销大于产问题例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？例题分析3：销大于产问题解：增加一个虚设的产地运输费用为0习题From
24、/toFrom/toE EF FG GH HFactory Factory supplysupplyA A25253535363660601515B B55553030454538386 6C C40405050262665651414D D60604040666627271111Destination Destination requirementrequirement1010121215159 94646第二节运输问题和指派问题二、指派问题（特殊的运输问题）（一）任务数=人数（产销平衡的运输问题）任务数与人数相等的指派问题实质上就是产销平衡的运输问题，且每行、每列的产量或销量都等于1。mn
25、Minf=cij xiji=1j=1ns.t.xij=1i=1,2,m j=1mxij=1j=1,2,ni=1xij0(i=1,2,m;j=1,2,n)例题分析4：指派问题例13有一份说明书，要分别译成英、日、德、俄四种文字，因各人专长不同，他们完成翻译不同文字所需的时间见下表：解法：匈牙利法匈牙利法是求解及小型（优化方向为极小）指派问题的一种方法，这种方法最初由w.w.kuhn提出，后经改进而形成，解法基于匈牙利数学家D.Knig给出的一个定理而得名。理论基础:（1）若从效率矩阵(cij)的行（或列）的各元素中分别减去该行（或列）的最小元素后得到一个新矩阵（bij）,则以（bij）为效率矩阵
26、的指派问题与原问题有相同的最优解。经过上述变换后，（bij）中的每行和每列都至少含有一个0元素，称位于不同行不同列的0元素为独立的0元素。（2）若（bij）有n个独立的0元素，由此可得一个解矩阵，方法为在X中令对应于（bij）的0元素位置的元素为1，其它位置的元素为0，则X为指派问题的最优解。（3）D.Knig定理：矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。匈牙利法步骤第一步变换效率矩阵（Cij），使变换后效率矩阵（bij）的每行每列至少出现一个0元素，同时不出现负元素。（对效率矩阵每行每列减去该行该列最小元素）2109715414813141611415139Cij-2-4
27、-11-40875110104235001195-5082511054230001145第二步画出包含所有0的直线，并使画出直线条数最少。如果直线条数与表中的行或列相等，则获最优解。否则第三步（注意不能画斜线）（例中3条直线0，特别注注意意要在选项中，将“线性模型”和“假定非负钩”选上第二节运输问题和指派问题（二）任务数人数（产销不平衡的运输问题）1、若任务数人数，就增加假想人，就可以化为产销平衡问题。2、若任务数人数，就增加假想工作，就可以化为产销平衡问题。习题项目领导者项目领导者1 12 23 3terryterry101015159 9CandyCandy9 918185 5TomTom
28、6 614143 3第三节动态规划一、动态规划的基本概念和方法二、动态规划模型的建立与求解步骤三、动态规划的应用案例：最短路问题例16位于城市A的某公司要把一批货物送到位于城市E的销售门市部，途中可能经过的城市有B1,B2,B3;C1,C2,C3;D1,D2等8个城市，问如何走，能使路线最短？BACBDBCDEC41231231296487689356231435第三节动态规划一、基本概念和方法：（一）基本概念1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。2、状态sk：在各阶段开始时的客观条件称为各阶段的状态。状态可以是数量，也可以是字符。3、决策uk：从某一状态向下一状态过渡
29、时所做的选择。决策是所在状态的函数，记为uk(sk)。决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。4、状态转移方程sk+1=Tk(sk,uk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。5、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称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
30、+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+1,un)称指标具有可乘性。最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即第三节动态规划（二）基本方法1、最优化原理不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。2、基本方法从最后一个阶段的优化开始，按逆向顺序逐步向前一阶段扩展，并将后一阶段的优化结果带到扩展后的阶段中去，以此逐步向前推
31、进，直到得到全过程的优化结果。3、递推方程第三节动态规划二、动态规划模型的建立与求解步骤（一）建立动态规划模型的基本要求1.所研究的问题必须能够分成几个相互联系的阶段，而且在每一个都具有需要决策的问题.2.在每一阶段都必须有若干个与该阶段相关的状态。（二）动态规划的求解步骤1.列出本阶段的所有可能状态变量sk。2.对每一状态sk列出所有可能的决策变量uk(sk)。第三节动态规划3.对每一阶段sk,uk(sk)计算本阶段的指标值dk(sk,uk)。4.确定状态转移方程sk+1=T(sk,uk)，对于每对sk,uk求出sk+1的值。5.对于每一对sk,uk，计算相应的指标值dk(sk,uk)+fk
32、+1(sk+1)。6.比较各个指标值，取最优者（最大值或最小值）作为本阶段sk状态开始的后部子过程的最优指标值fk(sk),相应的决策uk即是本阶段以sk为起始状态的最优决策u*k。7.在第一阶段的最优策略确定后，再从第一阶段开始，根据状态转移方程确定各阶段的最优策略u*k。例题分析1：定价问题例17考虑为某新产品定价，该产品的单价从5元、6元、7元、8元这四种价格中选取其中之一来定价，每年年初允许价格变动，但幅度不能超过1元。该公司预计该产品畅销只有5年，5年后将被淘汰，另据销售情况预测，在价格不同的情况下年度的预计利润入下表所示，问如何定价，能使利润最大？单价单价 第一年第一年 第二年第二
33、年 第三年第三年 第四年第四年 第五年第五年5元元 10 12 15 20 256元元 12 13 16 20 247元元 14 14 16 18 188元元 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（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,u
34、k)+fk+1(uk),f6(s6)=0,（k=1,2,3,4,5）以下我们从第五阶段开始计算例题分析1：定价问题u5s5d5(s5,u5)+f6(s6) 5 6 7 8 f5(s5) U*55 25 2556 24 2467 18 1878 14 148第五阶段：第五阶段：s5=u5例题分析1：定价问题第四阶段:s5=u4=s4-1,s4,s4+1u4s4d4(s4,u4)+f5(s5)= d4(s4,u4)+f5(u4) 5 6 7 8f4(s4) U*45 20+25 20+24 4556 20+25 20+24 20+18 4557 18+24 18+18 18+14 4268 14+
35、18 14+14 327例题分析1：定价问题第三阶段:s4=u3=s3-1,s3,s3-1u3s3d3(s3,u3)+f4(s4)= d3(s3,u3)+f4(u3) 5 6 7 8 f3(s3) U*3515+45 15+45 605,6616+45 16+45 16+42 615,67 16+45 16+42 16+326168 15+42 15+32 577例题分析1：定价问题第二阶段:s3=u2=s2-1,s2,s2+1u2s2d2(s2,u2)+f3(s3)= d2(s2,u2)+f3(u2) 5 6 7 8 f2(s2) U*25 12+60 12+61 7366 13+60 13
36、+6113+61 746,77 14+61 14+61 14+57756,78 15+61 15+57 767例题分析1：定价问题第一阶段:s2=u1=s1-1,s1,s1+1u1s1d1(s1,u1)+f2(s2)= d1(s1,u1)+f2(u1) 5 6 7 8 f1(s1) U*1510+73 10+74 846612+73 12+74 12+75 8777 14+74 14+75 14+769088 16+75 16+76 928 由第一阶段分析知道由第一阶段分析知道s1=8,故故s2=u*1=8得得u*2=8,故故s3=u*2=8得得u*3=7,故故s4=u*3=7得得u*4=6,
37、故故s5=u*4=6得得u*5=5。即当第一。即当第一年定价年定价8元，第二年定价元，第二年定价8元，第三年定价元，第三年定价7元，第四年定价元，第四年定价6元，第五年定价元，第五年定价5元时，利润最大，最大利润为元时，利润最大，最大利润为92万元。万元。例题分析2：资源分配问题例18.某公司拟将某种设备5台，分配给所属的甲、乙、丙、丁四个工厂。各工厂获得此设备后，预测可创造的利润如下表所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？ 工厂工厂盈利盈利设备台数设备台数 甲甲 厂厂 乙乙 厂厂 丙丙 厂厂 丁厂丁厂 0 0 0 0 0 1 6 3 5 4 2 7 7 10 6
38、 3 10 9 11 11 4 12 12 11 12 5 15 13 11 12例题分析2：资源分配问题解：（1）将问题按工厂分为四个阶段，甲、乙、丙、丁四个厂分别编号为1、2、3、4厂。（2）设sk:分配给第k个厂至第4个厂的设备台数（k=1、2、3、4）。（3）uk:分配给第k个工厂的设备台数（k=1、2、3、4）。（4）状态转移方程为sk+1=sk-uk，即s2=s1-u1,s3=s2-u2,且有s4=u4,s1=5（5）最优指标函数的递推公式：fk(sk)=maxdk(sk,uk)+fk+1(sk+1)，f5(s5)=0以下我们从第四阶段开始计算例题分析2：资源分配问题u4s4d4(
39、s4,u4)012345f4(s4) u*40 0 001 4 412 6 623 11 1134 12 1245 12125第四阶段：第四阶段：s4=u4例题分析2：资源分配问题 u3s3d3(s3,u3)+f4(s3-u3)01 2 3 4 5f3(s3)u*300+0 0010+4 5+0 5120+6 5+4 10+0 10230+11 5+6 10+4 11+0 14240+12 5+11 10+6 11+4 11+0 161,250+12 5+12 10+11 11+6 11+4 11+0212第三阶段：第三阶段：s4=s3-u3例题分析2：资源分配问题 u2s2d2(s2,u2)
40、+f3(s2-u2)01 2 3 4 5f2(s2)u*200+0 0010+5 3+0 5020+10 3+5 7+0 10030+14 3+10 7+5 9+0 14040+16 3+14 7+10 9+5 12+0 171,250+21 3+16 7+14 9+10 12+5 13+0210,2第二阶段：第二阶段：s3=s2-u2例题分析2：资源分配问题u1s1d1(s1,u1)+f2(s1-u1)0 1 23 4 5f1(s1) u*150+21 6+17 7+14 10+10 12+5 15+0 23 1第一阶段：第一阶段：s2=s1-u1 由第一阶段知由第一阶段知u*1=1，故，故s2=s1-u1=5-1=4,由第二阶段得知由第二阶段得知u*2=1或或2，故，故s3=s2-u2=4-1或或4-2=3或或2，由第三阶段得知，由第三阶段得知u*3=2,故故s4=s3-u3=3-2或或2-2=1或或0，由第一阶段知，由第一阶段知u*4=1或或0。 当分给甲当分给甲1台、乙台、乙1台、丙台、丙2台、丁台、丁1台或分给甲台或分给甲1台、乙台、乙2台、台、丙丙2台、丁台、丁0台时利润最大，最大利润为台时利润最大，最大利润为23万元。万元。
