对只具有两个决策变量的目标规划的数学模型解析课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《对只具有两个决策变量的目标规划的数学模型解析课件.ppt》由用户(ziliao2023)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 具有 两个 决策 变量 目标 规划 数学模型 解析 课件
- 资源描述:
-
1、 对只具有两个决策变量的目标规划的数学模型,对只具有两个决策变量的目标规划的数学模型,我们可以用图解法来分析求解。通过图解示例,可以我们可以用图解法来分析求解。通过图解示例,可以看到目标规划中优先因子,正、负偏差变量及权系数看到目标规划中优先因子,正、负偏差变量及权系数等的几何意义。等的几何意义。图解法的基本步骤图解法的基本步骤1.令各偏差变量为令各偏差变量为0,作出所有的约束直线,作出所有的约束直线2.作图表示偏差变量增加对约束直线的影响作图表示偏差变量增加对约束直线的影响3.确定满足第一优先级目标集的最优解空间(不考确定满足第一优先级目标集的最优解空间(不考虑其他优先级)虑其他优先级)4.
2、转到第转到第k+1优先级,求出其相应的最优解空间优先级,求出其相应的最优解空间5.令令k=k+1反复执行步骤(反复执行步骤(4),直到所有的优先级),直到所有的优先级均求解完毕。均求解完毕。上周内容回顾上周内容回顾【例题例题】某电视机厂装配黑白和彩色两种电视机,每装某电视机厂装配黑白和彩色两种电视机,每装配一台电视需占用装配线配一台电视需占用装配线1小时,装配线每周计划开动小时,装配线每周计划开动40小时,预计市场每周彩色电视机的销量是小时,预计市场每周彩色电视机的销量是24台,每台台,每台可获利为可获利为80元,黑白电视机的销量为元,黑白电视机的销量为30台,每台可获利台,每台可获利40元。
3、该厂确定的目标为:元。该厂确定的目标为:第一优先级:充分利用装配线每周计划开动第一优先级:充分利用装配线每周计划开动40小时;小时;第二优先级:允许装配线加班;但加班时间每周尽量第二优先级:允许装配线加班;但加班时间每周尽量不超过不超过10小时;小时;第三优先级:装配电视机的数量尽量满足市场需要。第三优先级:装配电视机的数量尽量满足市场需要。因彩色电视机的利润高,取其权系数为因彩色电视机的利润高,取其权系数为2。试建立该问题的目标规划模型,并求解黑白电视试建立该问题的目标规划模型,并求解黑白电视机和彩色电视机的产量。机和彩色电视机的产量。设设x1,x2分别表示黑白和彩色电视机的产量,该问分别表
4、示黑白和彩色电视机的产量,该问题的目标规划模型为:题的目标规划模型为:11223341211122213324412min240502430,0,1,2,3,4iiZpdpdpddxxddxxddxddxddxx ddi用图解法求解,见下图。用图解法求解,见下图。x1x2050 40 30 20 10 10 20 30 40 501.令各偏差变量为令各偏差变量为0,作出所有的约束直线作出所有的约束直线121112221332444050.2430 xxddxxddstxddxdd GHFEDCBAx1x2050 40 30 20 10 10 20 30 40 50d4+d3-d2+d2-d1+
5、d1-d4-d3+2.作图表示偏差变量增作图表示偏差变量增加对约束直线的影响加对约束直线的影响P1,P2的目标实的目标实现后,现后,x1,x2的取的取值范围为值范围为ABCD 11223342pdpdpdd3.确定满足第一优先级确定满足第一优先级目标集的最优解空间目标集的最优解空间(不考虑其他优先级)(不考虑其他优先级)4.转到第转到第k+1优先级,求优先级,求出其相应的最优解空间出其相应的最优解空间GHFEDCBAx1x2050 40 30 20 10 10 20 30 40 50d4+d3-d2+d2-d1+d1-d4-d3+P目标要求,目标要求,d3-权系数权系数大于大于d4-,取取d3
6、-=0,x1,x2的取值范围为的取值范围为ABEF在在ABEF中,只有中,只有 E 点点d4-取极小值。取极小值。取取E点为满意解点为满意解(24,26)11223342pdpdpdd5.令令k=k+1反复执行步骤(反复执行步骤(4),),直到所有的优先级均求解完毕。直到所有的优先级均求解完毕。GHFEDCBAx1x2050 40 30 20 10 10 20 30 40 50d4+d3-d2+d2-d1+d1-d4-d3+第第1010章章 动态规划动态规划10.1 10.1 多阶段决策问题多阶段决策问题10.2 10.2 多阶段决策的有关概念多阶段决策的有关概念10.3 10.3 动态规划的
7、基本思想和基本方程动态规划的基本思想和基本方程10.4 10.4 动态规划模型的建立与求解动态规划模型的建立与求解10.5 10.5 动态规划应用举例动态规划应用举例 动态规划所研究的对象是多阶段决策问题。动态规划所研究的对象是多阶段决策问题。所谓所谓多阶段决策问题是多阶段决策问题是指一类活动过程,它可以指一类活动过程,它可以分为若干个相互联系的阶段,在每个阶段都需要作出分为若干个相互联系的阶段,在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益,而且决定决策。这个决策不仅决定这一阶段的效益,而且决定下一阶段的初始状态。下一阶段的初始状态。每个阶段的决策确定以后,就得到一个决策序列,每个
8、阶段的决策确定以后,就得到一个决策序列,称为策略。多阶段决策问题就是求一个策略,使各阶称为策略。多阶段决策问题就是求一个策略,使各阶段的效益的总和达到最优。段的效益的总和达到最优。10.1 多阶段决策问题多阶段决策问题 在实际生产经营活动中,存在着一类将过程划分在实际生产经营活动中,存在着一类将过程划分为若干个相互联系的为若干个相互联系的阶段阶段,而每个阶段都需要做出,而每个阶段都需要做出决决策策,并且一个阶段的决策确定后,常影响下一阶段的,并且一个阶段的决策确定后,常影响下一阶段的决策,即决策,即多阶段决策问题多阶段决策问题。在这类多阶段决策问题中,整个问题的各个阶段在这类多阶段决策问题中,
9、整个问题的各个阶段所确定的所确定的决策决策构成一个决策序列,通称为构成一个决策序列,通称为策略策略。对应。对应于一个策略,就有确定活动效果,且可用数量指标来于一个策略,就有确定活动效果,且可用数量指标来衡量。因此多阶段决策问题就需要在允许选择的那些衡量。因此多阶段决策问题就需要在允许选择的那些策略中选择最优策略,使在预定的标准下达到最好的策略中选择最优策略,使在预定的标准下达到最好的效果。效果。动态规划是一种解决问题的思路,而不是一种算法。动态规划是一种解决问题的思路,而不是一种算法。这一点与线性规划不同,线性规划是一种算法。这一点与线性规划不同,线性规划是一种算法。【例例10-110-1】生
10、产与存储问题生产与存储问题 某工厂每季度需供应市场某工厂每季度需供应市场600600,700700,500500和和12001200件产品,未销售完的产品存入仓库,存储费为件产品,未销售完的产品存入仓库,存储费为每件每季度每件每季度1 1元,生产费用为件数的平方成正比,元,生产费用为件数的平方成正比,比例系数为比例系数为0.0050.005。现要制定生产计划,在满足市。现要制定生产计划,在满足市场需求的条件下,使一年的生产与存储费用最少。场需求的条件下,使一年的生产与存储费用最少。按季度的顺序分为按季度的顺序分为4个阶段,个阶段,k=1,2,3,4 设设第第k季季生产的产品为生产的产品为uk件
11、件,第第k季初的库存量季初的库存量为为sk,第第k季的季的销售量为销售量为 qk,则则sk+1=sk+uk-qk 假设年初和年底无存货,即假设年初和年底无存货,即 s1=s5=0全过程目标管理全过程目标管理函数为函数为:4211(0.005)kkkfus 该问题是求最优的生产决策序列,即全年中每该问题是求最优的生产决策序列,即全年中每季度的最优生产量季度的最优生产量u u1 1*,u,u2 2*,u,u3 3*,u,u4 4*,在满足市场需,在满足市场需求的条件下,使得一年的总费用最少。则该问题的求的条件下,使得一年的总费用最少。则该问题的数学模型为:数学模型为:4211115min(0.00
12、5)0,0kkkkkkkfusssuqss 【例【例10-2】最短路线问题。设有一辆汽车由最短路线问题。设有一辆汽车由A城到城到B城,中间可经过城,中间可经过v1到到v8城市,各城市的交通路线及城市,各城市的交通路线及距离如图所示,问应选择哪一条路线,可使总距离最距离如图所示,问应选择哪一条路线,可使总距离最短。短。Av285685547 866924337131234v39v6Bv8v7v5v4v1这一问题看成是四个阶段的决策问题,由这一问题看成是四个阶段的决策问题,由A到到(v1,v2,v3)中的点是第一阶段;由中的点是第一阶段;由(v1,v2,v3)中的点到中的点到(v4,v5,v6)中
13、的中的点是第二阶段;由点是第二阶段;由(v4,v5,v6)中的点到中的点到(v7,v8)中的点是中的点是第二阶段;由第二阶段;由(v7,v8)中的一点到中的一点到B是第四阶段。是第四阶段。要求在各个阶段选取一个恰当的决策,由这些决策要求在各个阶段选取一个恰当的决策,由这些决策组成的决策序列所决定的一条路线,其总路程最短。组成的决策序列所决定的一条路线,其总路程最短。Av285685547 866924337131234v39v6Bv8v7v5v4v110.2 10.2 多阶段决策的有关概念多阶段决策的有关概念 1.阶段阶段 把所给问题的过程恰当地分为若干个相互联系的把所给问题的过程恰当地分为若
14、干个相互联系的阶段,以便按一定顺序去求解。阶段,以便按一定顺序去求解。描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量,用,用k表示。表示。阶段的划分,一般是按时间和空间的自然特征来阶段的划分,一般是按时间和空间的自然特征来划分划分。【例例10-1】生产与存储问题按自然时间分为生产与存储问题按自然时间分为4个阶个阶段(季度)段(季度)K=1,2,3,4。【例例10-2】最短路问题按空间的自然特征分为最短路问题按空间的自然特征分为4个个阶段。阶段。年、年、月、月、路段路段2.状态状态 状态表示每个阶段开始时所处的自然状态或客观状态表示每个阶段开始时所处的自然状态或客观条件,描述了问题过程的状
15、况,又称为不可控因素。条件,描述了问题过程的状况,又称为不可控因素。描述过程状态的变量称为描述过程状态的变量称为状态变量状态变量。用。用sk表示表示第第k阶段所处的状态。阶段所处的状态。状态变量的取值有一定的允许集合或范围,此状态变量的取值有一定的允许集合或范围,此集合称为集合称为状态允许集合状态允许集合。【例例10-1】中状态是每个阶段开始时的库存量,它中状态是每个阶段开始时的库存量,它既是前一阶段决策的结果,又是后一阶段决策的开始。既是前一阶段决策的结果,又是后一阶段决策的开始。通常一个阶段有若干个状态。构成状态集合。通常一个阶段有若干个状态。构成状态集合。【例例10-1】中中s1=0,s
16、5=0表示状态变量表示状态变量s1,s5的值的值为为0,而,而s2,s3,s4的取值可能有多种情况。的取值可能有多种情况。s1=A,s2=(v1,v2,v3),s3=(v4,v5,v6),s4=(v7,v8)状态应具有无后效性状态应具有无后效性 如果某阶段状态给定后,则在这个阶段以后过程如果某阶段状态给定后,则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响;的发展不受这个阶段以前各段状态的影响;过程的过去历史只能通过当前的状态去影响它未来过程的过去历史只能通过当前的状态去影响它未来的发展;的发展;构造动态规划模型时,要充分注意是否满足无构造动态规划模型时,要充分注意是否满足无后效性的要
17、求;后效性的要求;如果状态变量不能满足无后效性的要求,如果状态变量不能满足无后效性的要求,应适当地改变状态的定义或规定方法。应适当地改变状态的定义或规定方法。Av285685547 866924337131234v39v6Bv8v7v5v4v1【例【例10-2】中中 在实际问题中决策变量的取值往往在某一范围在实际问题中决策变量的取值往往在某一范围之内,此范围称为之内,此范围称为允许决策集合允许决策集合。常用。常用Dk(sk)表示第表示第k阶段从状态阶段从状态sk出发的允许决策集合。出发的允许决策集合。决策变量是状态变量的函数。决策变量是状态变量的函数。常用常用uk(sk)表示第表示第k阶段当状
18、态为阶段当状态为 sk时的决策变量。时的决策变量。3.决策决策 过程的某一阶段、过程的某一阶段、某个状态某个状态,可以做出不同的可以做出不同的决决定定(选择选择),决定下一阶段的状态,这种决定称为决定下一阶段的状态,这种决定称为决策决策。描述决策的变量,称为描述决策的变量,称为决策变量决策变量。【例例10-1】中,从第一阶段的状态中,从第一阶段的状态s1=0出发,其允许出发,其允许决策集合为决策集合为Dk(sk)=600,601,3000【例【例10-2】中,从第二阶段的状态中,从第二阶段的状态s2=v1出发,其允许出发,其允许决策集合为决策集合为Dk(sk)=v4,v5,v6。可供选择的策略
展开阅读全文