随笔-141  评论-9  文章-3  trackbacks-0
【问题分析】

网络优化问题,用最小费用最大流解决。

【建模方法】

把每天分为二分图两个集合中的顶点Xi,Yi,建立附加源S汇T。

1、从S向每个Xi连一条容量为ri,费用为0的有向边。
2、从每个Yi向T连一条容量为ri,费用为0的有向边。
3、从S向每个Yi连一条容量为无穷大,费用为p的有向边。
4、从每个Xi向Xi+1(i+1<=N)连一条容量为无穷大,费用为0的有向边。
5、从每个Xi向Yi+m(i+m<=N)连一条容量为无穷大,费用为f的有向边。
6、从每个Xi向Yi+n(i+n<=N)连一条容量为无穷大,费用为s的有向边。

求网络最小费用最大流,费用流值就是要求的最小总花费。

【建模分析】

这个问题的主要约束条件是每天的餐巾够用,而餐巾的来源可能是最新购买,也可能是前几天送洗,今天刚刚洗好的餐巾。每天用完的餐巾可以选择送到快洗部或慢洗部,或者留到下一天再处理。

经过分析可以把每天要用的和用完的分离开处理,建模后就是二分图。二分图X集合中顶点Xi表示第i天用完的餐巾,其数量为ri,所以从S向Xi连接容量为ri的边作为限制。Y集合中每个点Yi则是第i天需要的餐巾,数量为ri,与T连接的边容量作为限制。每天用完的餐巾可以选择留到下一天(Xi->Xi+1),不需要花费,送到快洗部(Xi->Yi+m),费用为f,送到慢洗部(Xi->Yi+n),费用为s。每天需要的餐巾除了刚刚洗好的餐巾,还可能是新购买的(S->Yi),费用为p。

在网络上求出的最小费用最大流,满足了问题的约束条件(因为在这个图上最大流一定可以使与T连接的边全部满流,其他边只要有可行流就满足条件),而且还可以保证总费用最小,就是我们的优化目标。
posted on 2011-10-17 21:36 小阮 阅读(453) 评论(0)  编辑 收藏 引用 所属分类: 数据结构和算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理