当前位置:首页 >> 理学 >>

运筹学-第3版-课件-动态规划例题


8.1 用动态规划方法求整数规划模型,而 非线性规划模型的最优解。 例1 求解下列整数规划的最优解:

max Z ? 4 x1 ? 5 x2 ? 6 x3 ?3x1 ? 4 x2 ? 5 x3 ? 10 s.t.? ? x j ? 0 ( j ? 1,2,3), x j为整数
解 (1)建立动态规划模型: 阶段变量:将给每一个变量 x j 赋值看成一个阶段, 划分为3个阶段,且阶段变量 k ? 1,2,3

设决策变量xk 表示第k阶段赋给变量xk的值(k ? 1, 2, 3 )

设状态变量sk表示从第k阶段到第3阶段约束右端最大 值,则s1=10。 设决策变量xk表示第k阶段赋给变量xk的值(k=1,2,3)。 状态转移方程:s2=s1-3x1, s3=s2-4x2。 阶段指标:v1(s1,x1)=4x1, v2(s2,x2)=5x2, v3(s3,x3)=6x3 基本方程: ? f k ( sk ) ? max{ vk ( sk , xk ) ? f k ?1 ( sk ?1 )}

其中,a1=3,a2=4,a3=5。

? ? xk ? ? (0 ? xk ? ? ?, k ? 3,2,1) ? ? ak ? ? ? f (s ) ? 0 ? 4 4

(2)用逆序法求解:

当k=3时,

f 3 ( s3 ) ? max{ 6 x3 ? f 4 ( s4 )} ? max{ 6 x3}

因此,当s3=0,1,2,3,4时,x3=0;当s3=5,6,7,8,9时,x3可取 0或1;当s3=10时,x3可取0,1,2,由此确定f3(s3)。 现将有关数据列入表4.1中。

? s3 ? (0 ? x3 ? ? ? ) ?5? 而s3 ?{0,1,2,3,4,5,6,7,8,9,10} ,[x]表示不超过x的最大整数。

x3 s3

6x3+f4(s4) 0 1 2

f3(s3) 0
0 0 0 0

x3* 0
0 0 0 0 1

0
1 2 3 4 5

0
0 0 0 0 0 6

6

6 7 8

0 0 0

6 6 6

6 6 6

续表 1 1 1

9
10 当k=2时,有

0
0

6
6 12

6
12

1
2

f2(s2)=max{5x2+f3(s3)}=max{5x2+f3(s2-4x2)}

其中

? s2 ? 0 ? x2 ? ? ? ?4?

而s2 ?{0,1,2,3,4,5,6,7,8,9,10}. 所以当s2=0,1,2,3时,
由此确定f2(s2)。现将有关数据列入表中。 s2 x2 5x2+f3(s2-4x2) 0 1 2 f2(s2) x2* s3

x2=0;当s2=4,5,6,7时,x2=0或1;当s2=8,9,10时,x2=0,1,2。

0 1
2

0+0 0+0
0+0

0 0
0

0 0
0

0 1
2

3

0+0

0

0

3

4 5
6 7 8 9 10

0+0 0+6
0+6 0+6 0+6 0+6 0+12

5+0 5+0
5+0 5+0 5+0 5+6 5+6 10+0 10+0 10+0

5 6
6 6 10 11 12

1 0
0 0 2 1 0

0 5
6 7 0 5 10

当k=1时,有

f1 (s1 ) ? max{ 4 x1 ? f 2 (s2 )} ? max{ 4 x1 ? f 2 (s1 ? 3x1 )}
s1 ? ? 其中, 0 ? x1 ? ? ? ?3?
而s1=10,故x1只能取0,1,2,3,由此确定f1(s1)。现将有关 数据列入表中。 x1 s1 10 4x1+f2(s1-3x1) f1(s1) 13 x1* 2 4 s2

0
0+12

1
4+6

2
8+5

3
12+0

按计算顺序反推,由表可知,当x1*=2时,f1(s1)取得 最大值13。又由s2=4查前面的表可得x2*=1及s3=0 ,再者, x3*=0。因此,最优解为 x1*=2, x2*=1, x3*=0,最优值maxZ=13。 8.2 一维资源分配问题
例2 某科研项目由三个小组用不同方法独立进行研 究,它们失败的概率分别为0.40,0.60和0.80。为了减少 三个小组都失败的可能性,现决定暂派两名高级科学家 参加这一科研项目。把这两人分配到各组后,各小组仍 失败的概率如下表所示,问应如何分派这两名高级科学 家以使三个小组都失败的概率最小?

高级科学家的 人数

小 1

组 2 3

0 1
2 解

0.40 0.20
0.15

0.60 0.40
0.20

0.80 0.50
0.30

(1)建立动态规划模型

按小组数将问题划分为3个阶段,阶段变量k=1,2,3。

状态变量sk表示第k阶段初可用于分配的科学家数,s1=2。

决策变量xk表示第k阶段分配给第k个小组的高级科学家 人数。
状态转移方程:sk+1=sk-xk。 } 允许决策集合:Dk(sk)={xk 0 ? xk ?sk , xk为整数 阶段指标vk(sk,xk)表示第k 个小组失败的概率。 过程指标函数Vk.n=

? v ( s , x )。
i ?k i i i

3

因而基本方程采用乘积形式,即

? f k ( sk ) ? min ?vk ( sk , xk ) ? f k ?1 ( sk ?1 )? ? 0 ? xk ? s k ? ? ? f 4 ( s4 ) ? 1

(2)采用逆序法求解: 当k=3时,

f 3 ( s3 ) ? min ?v3 ( s3 , x3 )?
0? x3 ? s3

因为s4=s3-x3=0,所以x3=s3(即尚未分配给第1 和第2小组的全部分配给第3小组)。计算结果如表 所示:

s3
0 1 2

x3*
0 1 2

f3(s3)
0.80 0.50 0.30

当k=2时,

f 2 (s2 ) ? min ?v2 (s2 , x2 ) ? f 3 (s3 )?
0 ? x2 ? s 2

计算结果如表所示:

s2 0 1 2

f2(s2,x2)=v2(s2,x2) f3(s3)


x2=0 0.48 0.30 0.18

x2=1

x2=2

x2* 0

f2(s2) 0.48 0.30 0.16

0.32 0.20 0.16

0 2

当k=1时,

f1 (s1 ) ? min ?v1 (s1 , x1 ) ? f 2 (s2 )?
0? x1 ? 2

计算结果如表所示: s1 f1(s1,x1)=v1(s1,x1) f2(s2)


x1=0
0.064

x1=1
0.060

x1=2
0.072

x1*

f1(s1)

2

1

0.060

由上表知,x1*=1,f1(s1)=0.060,由s2=1查前面的表知, x2*=0;由s3=1查表得x3*=0。

因而此问题的最优解为 x ? 1, x ? 0, x ? 1 。即把两 名高级科学家分派到第1和第3两小组各一名,可使三 个小组都失败的概率减小到0.060。 注:此问题还有一种更简捷的解法,将它化为最短路 模型,即将各阶段状态作为结点,各小组失败的概率为 弧线上的数据,见下图。然后在图上用逆序法计算,计 算结果标于图上的方框? 内。 0.48 0.80 0.60 s2=0 s3=0
* 1 * 2 * 3

0.06 s1= 2

0.15

0.20

0.30 s2=1
0.16 s2=2

0.40

0.60 0.20 0.40 0.60

0.50 s3=1
0.30 s3=2

0.80

0.50

ss =0 =0 44

0.40

0.30

由上图可知,整个项目失败的概率为0.060,最优 路线为图中双线表示,即s1=2→ s2=1 → s3=1 → s4=0, * * * 由此可同样得出最优解为 x1 ? 1, x2 ? 0, x3 ? 1。 因此,所有一维资源分配(离散型)均可化为最短 路问题来求解,在图上用逆序算法求解较简便。

3.二维资源分配问题
例3 设现有两种原料,数量各为3单位,现要将这 两种原料分配用于生产3种产品。如果第一种原料以 数量xj单位,第二种原料以数量yj单位用于生产第j种产 品(j=1,2,3),所得的收入gj(xj,yj)如下表所示,问应如 何分配这两种原料于3种产品的生产,使总收入最大?

y

g1(x,y)

g2(x,y)

g3(x,y)

x 0
1 2 3

0 0
4 5 6

1 1
5 6 7

2 3
6 7 8

3 6
7 8 9

0 0
1 4 6

1 2
4 6 8

2 4
6 8 10

3 6
7 9 11

0 0
2 4 6

1 3
5 7 9

2 5
7 9 11

3 8
9 11 13

解 (1)建立动态规划模型

阶段变量:将两种原料分配用于生产每一种产品看 成一个阶段,则可将问题划分为3个阶段,即k=1,2,3。

状态变量(sk,uk), sk表示第k阶段初至第3阶段可用于 分配的第一种原料数量,uk表示第k阶段初至第3阶段 可用于分配的第二种原料数量。 决策变量(xk,yk), xk, yk分别表示第k阶段分配第k种产 品用的第一种,第二种原料的数量,xk, yk取整数。
状态转移方程: sk+1=sk-xk uk+1=uk-yk

阶段指标gk(xk, yk)表示第k阶段分配给第k种产品所用的 第一种,第二种原料数量分别为xk, yk所获得的收入。 基本递推方程为

? f k ( sk , uk ) ? max ?g k ?xk , yk ? ? f k ?1 ( sk ?1 , uk ?1 )? 0? x3 ? s3 ? 0? y k ?u k ? ? ? f 4 ( s4 , u 4 ) ? 0

(2)用逆序法求解

当k ? 3时

f 3 ( s3 , u3 ) ? max ?g 3 ( x3 , y3 )?
0? x3 ? s3 0 ? y3 ? u 3

而s3 ? ?0,1,2,3?, u3 ? ?0,1,2,3?, 故f 3 ( s3 , u3 )即为表4.8中的 g ( x, y ).


相关文章:
运筹学-第3版-课件-动态规划例题_图文.ppt
运筹学-第3版-课件-动态规划例题 - 8.1 用动态规划方法求整数规划模型,而
运筹学-第3版-课件-第5章 动态规划_图文.ppt
运筹学-第3版-课件-第5章 动态规划_理学_高等教育_教育专区。第5章 动态...应 用动态规划可以解决诸如最优路径问题、资源分配问 题、生产调度问题、库存...
运筹学动态规划习题_图文.ppt
运筹学动态规划习题_理学_高等教育_教育专区。习题三 一、某工厂购进100台机器,...管理运筹学--动态规划 暂无评价 150页 2下载券 运筹学-第3版-课件-动态.....
第10章__动态规划_(管理运筹学_第三版_课件__共17章_韩....ppt
第10章__动态规划_(管理运筹学_第三版_课件__共17章_韩伯棠)_管理学_高等教育_教育专区。第10章__动态规划_(管理运筹学_第三版_课件__共17章_韩伯棠) ...
第10章 动态规划 (管理运筹学 第三版 课件 共17章 韩伯....ppt
第10章 动态规划 (管理运筹学 第三版 课件 共17章 韩伯棠)_经济学_高等教育...11 20 24 动态规划的应用(1) §3 动态规划的应用解:用动态规划来求解此题...
运筹学课件第七章_动态规划_图文.ppt
运筹学课件第七章_动态规划 - 七章 动态规划 (Dynamic programming) 动态规划的基本概念、基本思想 动态规划模型的建立和求解 动态规划的应用:背包问题;生产 ...
运筹学课件(动态规划)_图文.ppt
运筹学课件(动态规划) - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是用来解决多阶段决策过程最优 化...
运筹学课件动态规划_图文.ppt
运筹学课件动态规划 - 十章 动态规划(DP) Dynamic Programming §1 多阶段决策过程最优化问题(掌握) §2 基本概念、基本方程与最优化原理 (掌握) §3 动态...
大学运筹学教程经典课件第九章动态规划_图文.ppt
大学运筹学教程经典课件第九章动态规划 - 九章 动态规划 本章以下内容 动态规划的基本原理 动态规划方法的基本步骤 动态规划方法应用举例 1 动态规划的基本...
大学运筹学经典课件第十章动态规划_图文.ppt
大学运筹学经典课件第十章动态规划 - 十章 动态规划 §1 多阶段决策过程最优化问题举例 §2 基本概念、基本方程与最优化原理 §3 §4 动态规划的应用(...
吉林大学远程教育-运筹学课件(第5章动态规划)_图文.ppt
吉林大学远程教育-运筹学课件(第5章动态规划)_研究生入学考试_高等教育_教育.
管理运筹学课件第9章 动态规划_图文.ppt
管理运筹学课件第9章 动态规划 - 9章 动态规划 教学目标与要求 ? ? ?
运筹学课件第5章 动态规划_图文.ppt
运筹学课件第5章 动态规划 - 5章 动态规划 运筹帷幄之中 Dynamic Programming 决胜千里之外第1页 综 述 动态规划运筹学的一个分支,...
运筹学动态规划PPT_图文.ppt
运筹学动态规划PPT_数学_自然科学_专业资料。动态...3 C1 C2 4 C3 3 1 D 3 1 第三阶段( A →...例题:设国家拨给60万元投资,供四个工厂扩建使用,每...
运筹学---动态规划_图文.ppt
运筹学---动态规划 - 这是关于运筹学里的动态规划课件ppt... 运筹学---动态规划_理学_高等教育_教育专区。这是关于运筹学里的动态规划课件ppt 动态...
运筹学课件第9章 动态规划.ppt
运筹学课件第9章 动态规划 运筹学课件运筹学课件隐藏>> 第9章 动态规划 重庆三峡学院 关文忠 http://blog.sina.com.cn/guanwenzhong 教学目标与要求 ? ? ? ...
运筹学教程课件五 动态规划_图文.ppt
运筹学教程课件动态规划 - 五章 动态规划 不要过河拆桥 1 动态规划 D
运筹学 动态规划应用---背包问题_图文.ppt
5 } 对于k=3 列出 f3(x3)的数值表 由题意知, 1 =5, x 由表 f1 (...北邮运筹学ch6-3 动态规... 33页 5下载券 第4章 运筹学课件线性规.....
清华大学运筹学课件动态规划_图文.pdf
清华大学运筹学课件动态规划 - 动态规划 主要内容 基本概念 多阶段问题 建模与
运筹学第10章-动态规划_图文.ppt
搜试试 4 悬赏文档 全部 DOC PPT TXT PDF XLS ...运筹学第10章-动态规划_医学_高等教育_教育专区。...问题、库存问题、资源分配、生产过程最优化问 题。 ...
更多相关文章: