《吉林大学远程教育运筹学课件review(3)》由会员分享，可在线阅读，更多相关《吉林大学远程教育运筹学课件review(3)（15页珍藏版）》请在金锄头文库上搜索。
1、运 筹 学,复 习 指 南,此演示文稿会与参加人员进行相关讨论，所以你将需要加入“会议细节”来辅助讨论。 请充分运用 PowerPoint “会议记录”将会议细节记录于你演示文稿进行中，方法如下： 在幻灯片放映状态单击鼠标右键 选取会议记录 选取会议细节 将意见记录于其中 按下确定以结束此对话框 这个功能将随着意见的加入，而自动于幻灯片下方产生一个执行项目,第三讲,第五章、第六章 动态规划及应用举例,一、本章内容简要回顾 在第五章中,我们首先通过两个实例（最短路线问题、带回收的资源分配问题）引出了多阶段决策问题;接着介绍了动态规划的基本概念和最优性原理。最优性原理用一句话概括即：最优策略的任何
2、一部分子策略也必须是最优的。最后详细介绍了建立动态规划数学模型的步骤。 一般来说，利用动态规划方法求解实际多阶段决策问题需先建立问题的动态规划模型（即动态规划基本方程），具体步骤如下： 将问题按时间或空间次序划分成若干阶段。有些问题不具有时空次序，也可以人为地引进时空次序，划分阶段。 正确选择状态变量xk。状态变量是动态规划模型中最重要的参数。它要能够描述决策过程的演变特征；要满足无后效性。即如果某阶段状态已给定后，则以后过程的进展不受以前各状态的影响；要有递推性。即由k阶段的状态变量xk及决策变量uk可以计算出k+1阶段的状态变量xk+1。,建立动态规划数学模型的步骤,确定决策变量uk及允许
3、决策变量集合Dk(uk)。 根据状态变量之间的递推关系，写出状态转移方程： xk+1=T(xk, uk(xk) 建立指标函数。一般用rk(xk, uk)描写阶段效应，fk(xk)表示kn阶段的最优子策略函数。 建立动态规划基本方程： fk(xk)= optrk(xk,uk(xk)fk+1(xk+1) ukDk(uk) fn+1(xn+1)=C k=n,n-1,1 在动态规划基本方程中， rk(xk, uk)， xk+1=T(xk, uk)都是已知函数，最优子策略fk(xk)与fk+1(xk+1)之间是递推关系，要求出fk(xk)及uk(xk)，需要先求出fk+1(xk+1)，这就决定了应用动态
4、规划基本方程求最优策略总是逆着阶段的顺序进行的。由后向前逐步计算，最终可以算出全过程的最优策略函数值及最优策略。另一方面，由于k+1阶段的状态xk+1=T(xk, uk)是由前面的状态xk和决策uk所形成的，在计算fk+1(xk+1)时还不能具体确定xk+1的值，所以，这就要求必须就k+1阶段的各个可能状态计算fk+1(xk+1)，因此动态规划方法不但能求出整个问题的最优策略和最优目标值，而且还能求出决策过程中所有可能状态的最优策略及最优目标值。,在第六章中,详细介绍了应用动态规划方法求解的八类实际问题 二、应重点掌握的问题 1、根据实际问题建立动态规划基本方程； 2、资源分配问题； 3、生产
5、与存贮问题； 4、设备更新问题。,三、典型例题分析,(带回收的资源分配问题)某厂新购某种机床125台。据估计，这种设备5年后将被其它设备所代替。此机车如在高负荷状态下工作，年损坏率为1/2，年利润为10万元；如在低负荷状态下工作，年损坏率为1/5，年利润为6万元。问应如何安排这些机床的生产负荷，才能使5年内获得的利润最大？ 本问题具有时间上的次序性，在五年计划的每一年都要作出关于这些机床生产负荷的决策，并且一旦作出决策，不仅影响到本年利润的多少，而且影响到下一年初完好机床数，从而影响以后各年的利润。所以在每年初作决策时，必须将当年的利润和以后各年利润结合起来，统筹考虑。,解：以年为阶段，k=1
6、，2，3，4，5 取k年初完好的机床数为状态变量xk;以k年初投入高负荷运行的机床数为决策变量uk，则低负荷运行机床数是xk-uk，于是状态转移方程为： xk+1=1/2uk+4/5(xk-uk)=0.8xk-0.3uk 以利润为目标函数，则k年利润为： 10uk+6(xk-uk)=4uk+6xk 记fk(xk)为k年至5年末最大总利润，则动态规划基本方程为： fk(xk)=max4uk+6xk+fk+1(0.8xk-0.3uk) 0ukxk f6(x6)=0 k=5,4,3,2,1,所以，当k=5时，有 f5(x5)= max 4u5+6x5+f6(x6)=10x5 u5=x5 0u5x5
7、当k=4时 f4(x4)= max 4u4+6x4+f5(0.8x4-0.3u4) 0u4x4 = max 4u4+6x4+10(0.8x4-0.3u4) 0u4x4 = maxu4+14x4=15x4 u4=x4 0u4x4,典型例题分析,当k=3时 f3(x3)= max 4u3+6x3+f4(0.8x3-0.3u3) 0u3x3 = max 4u3+6x3+15(0.8xk-0.3uk) 0u3x3 = max -0.5u3+18x3=18x3 u3=0 0u3x3 当k=2时 f2(x2)= max 4u2+6x2+f3(0.8x2-0.3u2) 0u2x2 = max 4u2+6x2
8、+18(0.8x2-0.3u2) 0u2x2 = max-1.4u2+20.4x2=20.4x2 u2=0 0u2x2 当k=1时 f1(x1)= max 4u1+6x1+f2(0.8x1-0.3u1) 0u1x1 = max 4u1+6x1+20.4(0.8x1-0.3u1) 0u1x1 = max -2.12u1+22.32x1=22.32x1 0u1x1 u1=0 =22.32125=2790（万元）,典型例题分析,至此已算得最大总利润2790万元，再按与计算过程相反的顺序推回去，可得最优计划如下表所示：,第七章 图与网络分析,一、本章内容简要回顾 在本章中,我们首先由哥尼斯堡七桥问题引
9、出了图论的问题,接着给出了图与网络的基本概念;介绍了树的理论及求最小部分树的破圈法与避圈法;然后介绍了求最短路的狄克斯拉（Dijkstra）算法和图上标示法;介绍了求网络最大流的标号法;最后介绍了求最小费用最大流的方法及中国邮递员问题的解法。 二、应重点掌握的问题 1、求网络的最短路问题； 2、求网络的最大流问题。,第七章 典型例题分析,三、典型例题分析 1、求下图中v1 到v8 的最短路。,v4,v2,3,2,6,5,v3,v5,v6,v7,v8,6,3,5,5,2,1,1,1,4,7,9,v1,方法一：狄克斯拉（Dijkstra）算法,1标p（v1）=0，其余点标T（vi）=+，i=2,3
10、,4,5,6,7,8;,2由刚刚获得p标号的v1点出发，改善与之相邻点的T标号,即 新的T(v2)= min老的T(v2), p (v1)+12=min+,0+3=3, 新的T(v3)= min老的T(v3), p (v1)+13=min+,0+5=5, 新的T(v4)= min老的T(v4), p (v1)+14=min+,0+6=6,3找出当前具有最小T标号的v2点,标 p(v2)=3；且记k(v2)=v1,4改善刚刚获得p标号的v2点之相邻点的T标号： 新的T(v3)= min老的T(v3), p(v2)+23=min5,3+1= 4, 新的T(v5)= min老的T(v5), p(v2
11、)+25=min+,3+7=10, 新的T(v6)= min老的T(v6), p(v2)+26=min+,3+4=7,5找出当前具有最小T标号的v3点,标 p(v3)=4；且记k(v3)=v2,6改善刚刚获得p标号的v3点之相邻点的T标号： 新的T(v4)= min老的T(v4), p(v3)+34=min6,4+1=5, 新的T(v6)= min老的T(v6), p(v3)+36=min7,4+2=6,v4,v2,3,2,6,5,v3,v5,v6,v7,v8,6,3,5,2,1,1,1,4,9,v1,7,p（v1）=0,p（v2）=3,p（v3）=4,5,7找出当前具有最小T标号的v4点,标
12、 p(v4)=5；且记k(v4)=v3,8改善刚刚获得p标号的v4点之相邻点的T标号： 新的T(v6)= min老的T(v6), p(v4)+46=min6,5+3=6, 新的T(v7)= min老的T(v7), p(v4)+47=min+,5+5=10,p（v4）=5,9找出当前具有最小T标号的v6点,标 p(v6)=6；且记k(v6)=v3,10改善刚刚获得p标号的v6点之相邻点的T标号： 新的T(v5)= min老的T(v5), p(v6)+65=min10,6+2=8, 新的T(v7)= min老的T(v7), p(v6)+67=min10,6+1=7, 新的T(v8)= min老的T
13、(v8), p(v6)+68=min+,6+9=15,p（v6）=6,第七章 典型例题分析,第七章 典型例题分析,12改善刚刚获得p标号的v7点之相邻点的T标号： 新的T(v8)= min老的T(v8), p(v7)+78=min15,7+5=12,11找出当前具有最小T标号的v7点,标 p(v7)=7；且记k(v7)=v6,v4,v2,3,2,6,5,v3,v5,v6,v7,v8,6,3,5,2,1,1,1,4,9,v1,7,p（v1）=0,p（v2）=3,p（v3）=4,5,p（v4）=5,p（v6）=6,p（v7）=7,13找出当前具有最小T标号的v5点,标 p(v5)=8；且记k(v5
14、)=v6,14改善刚刚获得p标号的v5点之相邻点v8的T标号： 新的T(v8)= min老的T(v8), p(v5)+68=min12,8+6=12,15至此,v8点可获得标号: p(v8)=12；且记k(v8)=v7,p（v5）=8,由k(v8)反向追踪,可得最短路径:v1v2v3v6v7v8 ； 因p（v8）=12，所以v1v8 的最短距离为12。,第七章 典型例题分析,方法二：图上标示法,v4,v2,3,2,6,5,v3,v5,v6,v7,v8,6,3,5,5,2,1,1,1,4,7,9,v1,6 v5v8,6 v6v7,5 v7v8,9 v4v6,8 v3v6,9 v2v3,12 v1
15、v2,由此得最短路径:v1v2v3v6v7v8 ； 最短距离为12。,2、,用标号法求下图所示网络的最大流。,vs,vt,v1,v2,v3,v4,（3，3）,（4，3）,（1，1）,（1，1）,（5，3）,（3，0）,（2，1）,（2，2）,（5，1）,解：标vs （0，+） 标v2（vs ，L（v2）=（vs ，min+,cs2-fs2）= （vs ，4） 标v1（-v2，L（v1）=（-v2 ,minL（v2）, f12）=（-v2 ，1）,标v3（v1 ，L（v3） =v3（v1 ，1） 标v4（-v1 ，L（v4） =v4（-v1 ，1）,标vt（v3 ，L（vt） = vt（v3 ，1）,得增广链：vs v2 v1v3vt,
