DVD租赁问题的模型设计和求解.pdf

维普资讯 第22卷 第7期 工 程 数 学 学 报 V0ll_22No．7 2005年 12月 CHINESE JOURNALOF ENGINEERING MATHEMATICS Dec．2005 文章编号：1005—3085(2005)07—0092—09 DVD租赁问题的模型设计及求解 王 成，文 野，俞寅涛 指导教师：宋宝瑞 (上海交通大学电子信息与电气工程学院，上海 200240) 编者按：本文有显著特色，问题二、三的通常觯法是用 LINGO软件求解0-1规划模型，本文另辟蹊径，成功地用网 络流lf】的最小费用最大流方法，得到了令人满意的结果。体现了作者较强的创新意识和能力。 摘 要：本文讨论了DVD在线租赁的服务供应商可能遇到的问题与其解决方案 模型 II解决了在已知订单与各 种 DVD数量的情况 F‘，如何分配 DVD使得满意的人数最多，且总的满意度最大。模型III解决了在已知 订单的情况下，在一定的满意率与总满意度最大的约束下，如何以最小的成本购买各种 DVD，并确定分配 方案。模型 v对原问题作了更深入的推广。解决了在 DVD数量有限且租赁费用与租赁时间成正比的条件 F如何选择性地出租DVD 以获得最大收入的问题。本文所讨论的问题均为最优化问题，但是各题的约束条 件均不相同 本文对各个问题建立不同的网络模型，经过严密的理论论证，并用统一的费用流算法在微机上 实现，充分利用了网络流模型适用面，。结果精确，计算‘简单的优点，对 DVD租赁的现实问题提供了高效 的解决方案。 关键词：数学模型；网络流：最小费用最大流 分类号：AMS(2000)90C35 中图分类号：O221 文献标识码：A 1 问题背景 考虑如下的在线 DVD租赁问题。顾客缴纳…定数量的月费成为会员，订购 DVD租赁服 务。会员对哪些 DVD有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要 求。会员提交的订单包括多张 DVD，这些 DVD是基于其偏爱程度排序的。网站会根据手 头现有的DVD数量和会员的订单进行分发。每个会员每个月租赁次数不得超过2次，每次获 得3张 DVD。会员看完3张DVD之后，只需要将 DVD放进网站提供的信封里寄回 (邮费由 网站承担)，就可以继续下次租赁。我们考虑以下问题。 2 问题一 DVD碟片的选购数量问题 问题一中DVD碟片的选购数量讨论与其它几篇有类似之处，在这儿我们不再展开。而将 本文的重点放在下面几个问题的解决中。 3 问题二 DVD碟片的分配 问题 3．1 问题的描述 给定各种DVD的数量，以及每个会员的订单和其对相应DVD的偏爱程度，求出如何分配 这些DVD，使得会员的满意度最大。 3．2 问题的分析 维普资讯 第7期 王成等：DVD 租赁问题的模型设计及求解 93 对于本问题，我们认为，所谓使会员获得最大满意度 ，即指在使得每个会员尽可能地租借 到他在订单中预定的数种 DVD 中的三种的前提下，使得每个人对他借到的DVD 的偏爱值总 和最小 (数值越小，表示偏爱程度越大)。 3．3 模型 II的建立 我们采用网络流的模型来解决问题二。设加权有向图1中G= {E)，V 中除两个特 殊点 source与 terminal外，其余各点入度及 出度均大于0：source为源点，其入度为0， 出度大于0：terminal为汇点，其入度大于0，出度为0。且对于每一边 e∈E，均带有三个 权值：容量 capacity(e)(0)，单位流量费用 cost(e)，流量flow(e)。对于图G 的各边，权 值capacity(e)与cost(e)为既定的，flow(e)为可变的，当以下三个性质被满足时(参见[1])， 称 flow(e)为网络G 中的一个可行流： 性质1 Ve∈E，有0≤flo