没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
《运筹学通论》课程上机实验报告
课程名称: 年级: 上机实验成绩:
任课教师: 姓名: 专业:
上机实验名称: 学号: 上机实验日期:
上机实验编号: 组号: 上机实验时间:
一.实验目的
使用标号算法(Ford-Fulkerson)解决最大流问题。 其基本思想是从某个可行流 F 出发,
找到关于这个流的一个可改进路经 P,然后沿着 P 调整 F,对新的可行流试图寻找关于
他的可改进路经,如此反复直至求得最大流。
二.实验内容
1.标号过程
在这个过程中,网络中的点或者是标号点(又分为已检查和未检查两种),或者是未标
号点,每个标号点的标号包含两部分:第一个标号表明它的标号是从哪一点得到的,以便
找出增广链;第二个标号是为确定增广链的调整量 用的.
标号过程开始,总先給 Vs 标上(0, + ),这时 Vs 是标号而未检查过的点,其余都是未
标号的点.一般地,取一个标号而未检查的点 Vi, 对一切未标号的点 Vj:
(1).若在弧( Vi, Vj)上,Fij<Cij,则給 Vj 标号(Vi, l(Vj))。这里 l(Vj)=min[l(Vi),Cij-Fij].
这时点 Vj 成为标号而未检查的点.
(2) 若在弧( Vj, Vi)上,Fij>0, 则給 Vj 标号(-Vi,l(Vj)),这里 l(Vj)=min[l(Vi),Fij].这时点
Vj 成为标号而未检查的点.若所有标号都是已检查过的,而标号过程进行不下去时,则算
法结束,这时的可行流就是最大流.
2.调整过程
首先按 Vt 及其他点的第一个标号,利用”反向追踪”的办法,找出增广链 u. 例如设 Vt
的第一个标号为 Vk(-Vk) , 则弧(Vk,Vt)(Vt,Vk)是 u 上的弧. 接下来检查 Vk 的第一个
标号,若为 Vi (-Vi) , 则找出(Vi,Vk)(或相应的(Vk,Vi)).再检查的第一个标号,依此下去,
直到为止.这时被找出的弧就构成了增广链 u.
令调整量 θ 是 l(Vt),即 Vt 的第二个标号:
Fij﹢θ (vi
,
vj)∈u+
Fij= Fij﹣θ (vi
,
vj)∈u-
Fij (vi
,
vj) u
去掉所有的标号,对新的可行流 F’={Fij ‘},重新进入标号过程.
三.使用环境
资源评论
- lolelixu2014-01-18觉得还行吧,可以学到东西的
地心加速度
- 粉丝: 0
- 资源: 4
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功