数学建模优秀论文

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

2005 高教社杯全国大学生数学建模竞赛

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的 资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规 则的行为，我们将受到严肃处理。

我们参赛的题目是： B 题：DVD 在线租赁 我们的参赛报名号为（如果赛区设置报名号的话）：

国防科大

所属学校（请填写完整的全名）：

刘 健 参赛队员 (打印并签名) ：1. 张云安 2. 3. 李宝娟

指导教师或指导教师组负责人 (打印并签名)： 指导教师组

日期： 2005 年 9 月 19 日

赛区评阅编号（由赛区组委会评阅前进行编号）：

1

2005 年全国大学生数学建模竞赛全国一等奖

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

2005 高教社杯全国大学生数学建模竞赛

编 号 专 用 页

赛区评阅编号（由赛区组委会评阅前进行编号）：

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

2005 年全国大学生数学建模竞赛全国一等奖

2

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

DVD 在线租赁

摘要

本问题是一个 DVD 在线租赁中，网站方如何对于市场进行需求预测、如何对 DVD 进行分配才能同时最好的实现其经济效益和社会效益。

第一问中，基于需求预测基础上的 DVD 购买方案设计中，我们分别考虑了悲观情 况和均值情况。为了保证希望看到某种 DVD 的会员中，有 50%以上在一个月内能看到 该 DVD，在悲观情况下，各种 DVD 的购买量分别为：9000，4500，2250，1125，450。 在均值情况下，各种 DVD 的购买量分别为：6250，3125，1563，720，313。为了保证

在三个月内 95%以上的会员能够看到，在悲观情况下，各种 DVD 的购买量分别为：4500， 2250，1125，563，225。在均值情况下，各种 DVD 的购买量分别为：3959，1980，990， 495，198。最后，不考虑具体的会员的借还 DVD 时间，我们使用概率的方法解决了该 问题。结果与均值情况相近。

对于第二问，对于当前订单的分配方案确定。我们建立了 0-1 规划模型，求得此时 的最大满意度为 24746，我们给出了此时的最优分配方案。

第三问，是一个多目标规划问题，既要考虑使得会员的满意度尽量大，还要使得网 站所购买的总的 DVD 数目最少，在具体处理时，我们让会员满意度在一定的范围内变 动，给出各种情况下使得总 DVD 数最少的方案。其中当会员相对满意度为 0.8 时的最 少 DVD 总数为 2059 张。

分析第三问的结果，我们发现了有趣的双峰现象，并对其合理性进行了阐述。同时， 我们还可以发现，会员相对满意度与最少 DVD 之间呈现总数近似线性的关系。如下表 所示：

相对满意度 0.5 0.6 1486 0.7 1760 0.8 2059 0.9 2567 1.0 3098 所需 DVD 数 1202

DVD 种类 DVD1 DVD2 DVD3 DVD4 DVD5 对于网站而言，其经营管理的目的是获得最大的经济效益，不同的租赁模式设置下 购买量 9000 4500 2250 1125 450 网站会得到不同的经济效益，第四问中我们讨论网站经营管理的最优模式。求得了在一 DVD 种类 DVD1 DVD2 DVD3 DVD4 DVD5 种情况下，限定每月最多租赁两次的情况下，得到使得网站的效益达到最大时，应该限 购买量 4500 2250 1125 563 225 定每个会员每次租赁最多2 张 的会员数DVD。同时讨论了对于限定每次最多租赁 3 张 DVD 的情 时间 想看到但并未看到的会员数已看到该 DVD 况下，最佳的租赁次数。 m 20000 m 1 月 1 本文论证严密，所给出的结果具有启发性和借鉴意义。 1 月 15 日 2 月 1 2 月 15 日 3 月 1 3 月 15 日 DVD 种类 DVD1 DVD2 DVD3 DVD4 DVD5 购买量 6250 3125 1563 782 313 名称 DVD1 DVD2 DVD3 DVD4 DVD5 2005 数量（张）年全国大学生数学建模竞赛全国一等奖 3 3959 1980 990 495 198

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

一 问题重述

随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站 利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。例如，音 像制品的在线租赁就是一种可行的服务。这项服务充分发挥了网络的诸多优势，包括传 播范围广泛、直达核心消费群、强烈的互动性、感官性强、成本相对低廉等，为顾客提 供更为周到的服务。

考虑如下的在线 DVD 租赁问题。顾客缴纳一定数量的月费成为会员，订购 DVD 租赁服务。会员对哪些 DVD 有兴趣，只要在线提交订单，网站就会通过快递的方式尽 可能满足要求。会员提交的订单包括多张 DVD，这些 DVD 是基于其偏爱程度排序的。 网站会根据手头现有的 DVD 数量和会员的订单进行分发。每个会员每个月租赁次数不

得超过 2 次，每次获得 3 张 DVD。会员看完 3 张 DVD 之后，只需要将 DVD 放进网站 提供的信封里寄回（邮费由网站承担），就可以继续下次租赁。请考虑以下问题：

1）网站正准备购买一些新的 DVD，通过问卷调查 1000 个会员，得到了愿意观看这些 DVD 的人数（表 1 给出了其中 5 种 DVD 的数据）。此外，历史数据显示，60%的会 员每月租赁 DVD 两次，而另外的 40%只租一次。假设网站现有 10 万个会员，对表 1 中的每种 DVD 来说，应该至少准备多少张，才能保证希望看到该 DVD 的会员中 至少 50%在一个月内能够看到该 DVD？如果要求保证在三个月内至少 95%的会员能 够看到该 DVD 呢？

2）表 2 中列出了网站手上 100 种 DVD 的现有张数和当前需要处理的 1000 位会员的在 线 订 单 （ 表 2 的 数 据 格 式 示 例 如 下 表 2 ， 具 体 数 据 请 从 http://mcm.edu.cn/mcm05/problems2005c.asp 下载），如何对这些 DVD 进行分配，才 能使会员获得最大的满意度？请具体列出前 30 位会员（即 C0001~C0030）分别获得 哪些 DVD。

3）继续考虑表 2，并假设表 2 中 DVD 的现有数量全部为 0。如果你是网站经营管理人 员，你如何决定每种 DVD 的购买量，以及如何对这些 DVD 进行分配，才能使一个 月内 95%的会员得到他想看的 DVD，并且满意度最大？

4）如果你是网站经营管理人员，你觉得在 DVD 的需求预测、购买和分配中还有哪些重 要问题值得研究？请明确提出你的问题，并尝试建立相应的数学模型。

2005 年全国大学生数学建模竞赛全国一等奖

4

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

二背景介绍

DVD 在线租赁业务是一项近年来在网络技术高度发展的基础上出现的新业务。1998 年， 成立于美国的 Nexfix 是目前炙手可热的 DVD 在线租赁商。该公司有多种 DVD 出租业 务。其中，典型的是一种这样的：顾客每月缴纳 19.9 美元成为会员。定购 DVD 租赁服 务。顾客对哪些 DVD 感兴趣，只须在线提交订单，网站收到顾客的订单之后，会根据 手头现有的 DVD 数量和会员的订单尽可能将 DVD 以快递的方式投递给会员。

一般情况下，在一天之内，网站即可将会员所需的 DVD 送到会员手中，会员每次最多 得到 3 张 DVD。每个月订购的次数是有限的，顾客拿到这些 DVD 之后可以无限期的保 留这些 DVD，前提是在这段时期内，他仍然是该网站的会员。如果会员想拿进行下一 次租赁，则它必须首先将手上的 DVD 放进网站提供的信封里寄回。之后，即可进行下 一次租赁。

三 问题分析

本问题是一个在 DVD 租赁业务中，网站方如何进行 DVD 需求预测、如何购置新 DVD、如何将手头的 DVD 分配给会员，从而可以保证会员满意而同时又使自己收到良 好的经济效益的问题。

第一问中，1000 个会员的调查表即是 10 万个会员的需求预测。由于具体会员订单 的不可确知性，，无法考虑“每个会员每次最多获得 3 张 DVD”的约束，同时各种 DVD 之间的横向数量约束也无法考虑。故计算时，对于每种 DVD 的购买量可单独考虑。此 时，由于每月租赁两次 DVD 会员的不确定性，我们可以以均值情况估计和最悲观情况 估计。

第二问中，网站给出了网站手上 100 种 DVD 的现有张数和当前需要处理的 1000 位 会员的再现订单。要求我们给出一个使得会员总的满意度最大的分配方案。显然这是一 个大规模的 0—1 规划问题。

第三问中综合考虑一个月内 DVD 的购买分配方案，这其实是一个多目标规划的问 题。从网站的经济效益角度考虑看，在保证所有会员中 95%以上的会员一个月内看到自 己想看的 DVD 的情况下，希望购买的 DVD 尽量少，但是从其社会效应来看，则要尽 可能地考虑让所有会员的总的满意度最大。这时，可以使用多种方式将多目标规划变为 单目标规划，以求得一个经济效益与社会效益的综合最优。具体的 1000 位会员中到底 会有哪些会员是可能会在一个月内租赁两次 DVD，这个数据我们无从得知。我们可以 随机地从 1000 名会员中选择 600 名。认为这些会员将会在一个月内两次租赁 DVD，由 于所给数据的均匀性，无论是哪 600 名会员将会两次租赁 DVD，对目标影响并不会很 大。

对于网站而言，其经营管理的目的是获得最大的经济效益，不同的租赁模式设置下 网站会得到不同的经济效益，第四问中我们讨论网站经营管理的最优模式。

2005 年全国大学生数学建模竞赛全国一等奖

5

Cij

xij

di

b j

C ： x1： xij 2 ：

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

第 i 名会员获得第 j 张 DVD 时的满意度。

xij 1 第 i 名会员获得第 j 张 DVD 时， ，反之为 0

di 1时，第 i 名会员在该月两次租赁 DVD，反之为 0

网站第 j 种 DVD 的拥有量

网站每月收向每位会员取的月费。

第 i 名会员第一次分配时获得第 j 张 DVD 时，

第 i 名会员第一次分配时获得第 j 张 DVD 时， 四 符号说明

xij1 1

，反之为 0 xij 2 1 ，反之为 0

五 基本假设

1．网站对 1000 名会员的调查结果足以反映网站的 10 万名会员对于各种 DVD 的需求及 喜好

2．会员中总是有 60%的会员每月租赁 DVD 两次，40%的会员每月租赁 DVD 一次 3．会员只有在需要再次租赁 DVD 时，才会将将上次租赁的 DVD 归还。

4．因为 60%的会员每月租赁 2 次 DVD，40%的会员每月租赁 1 次 DVD，所以假设每位 会员每月至少会租赁 1 次。

5．如果会员对某种 DVD 感兴趣，但是本次提交订单后，并没有得到该 DVD 则他的下 一份订单中仍然会有兴趣观看该 DVD

6．网站对于会员归还 DVD 的期限不作。

7．对于每一类被租赁出去的 DVD总是有 60%分布在每个月会租赁两次 DVD的会员中， 40%分布在每月租赁一次 DVD 的会员中。

8．会员在一个月内只要看到一张他想看到的 DVD 就认为他看到了想看的 DVD.

2005 年全国大学生数学建模竞赛全国一等奖

6

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

六、模型的建立与求解

6．1 DVD 购置方案的确定

通过对 1000 个会员的调查问卷，网站可以获得其 10 万个会员对于各种 DVD 的需 求状况，在制定订购方案时，可以不用考虑每个会员每次最多租赁 3 张 DVD 的。 同时不考虑各种 DVD 数量之间的横向联系，而对每种 DVD 单独考虑其购买量。

我们称每个月内只租赁一次 DVD 的会员为 1 类会员，每个月内租赁两次 DVD 的会 员为 2 类会员。此时，由于每个月内会两次租赁 DVD 会员的不确定性，在制定 DVD 的购买方案时我们分别考虑悲观情况估计及均值估计两种方式。 6．1．1 悲观情况估计 a）50%情形

对于某种 DVD，如 DVD1，假设其购买量为 m，而希望看到 DVD1 的会员有 2 万人， 假设经过一段时间的租赁后，DVD1 都已被租赁出去，这 m 张 DVD 可能在占总会员 60% 的该月将要租赁两次 DVD 的人的手中，也可能在另外 40%该月只租赁一次 DVD 的会 员手中。如果在前者手中，则一个月内该 DVD 还可被其余会员看到，但是如果在 40% 的人手中时，则该 DVD 在这个月内不会再被其余会员看到。考虑一种悲观情况，m 的 一部分首先被占总会员 40%的会员借走了，这部分人借了就不会在该月再还。为了保证 至少有 50%的会员在一个月内能看到该 DVD,那么此时总的碟数应该满足：

40% *20000 (m 40% * 20000) *2 50% * 20000

上式的意义是：在悲观情况下，占想看到 DVD1 的会员 40%的会员令其都租赁到 DVD1，并且在一个月内不还，另外 60%的会员中有部分租到 DVD1 并且在一个月内该 DVD 只被第二个会员看到。

此时

m 9000

同理，对于其他的 DVD 也有类似的表达式。此时为保证一个月内至少 50%的会员 看到他想看到的 DVD，则每种 DVD 的购买量为：

表 1

相对满意度 0.5 0.6 1486 0.7 1760 0.8 2059 0.9 2567 1.0 3098 所需 DVD 数 1202

DVD 种类 DVD1 DVD2 DVD3 DVD4 DVD5 b) 95%情形购买量 9000 4500 2250 1125 450 基于上述悲观情况，要使三个月内的会员能够看到该 DVD，则（以DVD 种类 DVD1 DVD2 95%DVD3 DVD4 DVD5 DVD1 为 例）： 购买量4500 2250 1125 563 225 时间 已看到该 DVD 的会员数 m (2m 40% * 2000) *2 (40% *20000 m) 2m 想看到但并未看到的会员数95% * 20000 m 20000 m 1 月 1 求得1 月 15 日 m 4500 同理，对于其他的各种 DVD，要保证三个月内至少 95%的会员看到他想看得 DVD, 2 月 1 则每种 DVD 的购买量为： 表 2 2 月 15 日 相对满意度 0.5 0.6 0.7 0.8 0.9 1.0 所需 DVD 数 1202 1486 1760 2059 2567 3098 DVD 种类 DVD1 DVD2 DVD3 DVD4 DVD5 3 月 1 购买量 9000 4500 2250 1125 450 2005 7 DVD 种类DVD1 DVD2 DVD3 DVD4 DVD5 3 月 年全国大学生数学建模竞赛全国一等奖15 日 购买量 4500 2250 1125 563 225 时间 种类已看到该想看到但并未看到的会员数 DVD 的会员数DVD DVD1 DVD2 DVD3 DVD4 DVD5 m 20000 m 1 月 1 购买量6250 3125 1563 782 313

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

6．1．2 均值情况估计

现实情况是这样的，DVD 在线租赁是一个实时性很强的业务，在每个月的每一天内， 都会有顾客提交订单，同时也会有会员归还已借的 DVD。这种会员订单的提交以及 DVD 的归还是服从参数为 的泊松分布的。但是考虑一种平均的情况我们可以认为：所有的

会员在每个月的某天（不妨假设为 1 号）要提交订单，同时那些需要租赁两次 DVD 的 人也集中在 15 号的时候归还已租赁的 DVD 并提交下一份订单。如果认为会员租赁、归 还的时间服从泊松分布，对该分布进行长期考察，可以发现上述的简化不过是泊松分布 时的平均情况。因而，我们在处理时可以不必考虑每个会员的具体租赁、归还 DVD 的 时间，而只考虑每个月内两次的分配方案，即 1 号和 15 号的分配方案。

同时，在 DVD 被租赁出去后，对于某种 DVD，从平均意义上看，应该是均匀的分 布在每月只租赁 1 次 DVD 的会员和每月租赁两次 DVD 的会员中，即是说在 15 号，该 DVD 将有 60%被归还。 a) 50%情形

在上述所说的网站运营模式下，设 DVD1 有 m 张，，则在 1 号时被分配出去，在 15 号 时，又有 0.6m 张被归还。这样，为保证 1 个月内至少 50%的会员时看到该 DVD 则应满 足：

1.6m 50% 20000  m 6250

即 DVD 至少准备 6250 张。

同理可得其余 DVD 应该准备的数量。 此时结果为：

表 3

相对满意度 0.5 0.6 0.7 0.8 0.9 1.0 所需 DVD 数 1202 1486 1760 2059 2567 3098 DVD DVD1 DVD2 DVD3 DVD4 DVD5 种类 购买量 9000 4500 2250 1125 450 b) 95%情形DVD 种类 DVD1 DVD2 DVD3 DVD4 DVD5 对于要使 DVD 的会员中 95%看到该 DVD 则考虑一下过程： 购买量 3 个月内希望看到该4500 2250 1125 563 225 相对满意度 已看到该0.5 0.6 的会员数0.7 0.8 0.9 1.0 时间 想看到但并未看到的会员数 DVD 所需 DVD 1486 2059 2567 3098 m 1760 20000 m 1 月1 数 1202 DVD 种类DVD1 DVD2 DVD3 DVD4 DVD5 1 月 15 日 购买量 9000 4500 2250 1125 450 DVD 种类 DVD1 DVD2 DVD3 DVD4 DVD5 2 月 1 购买量 4500 2250 1125 563 225 时间想看到但并未看到的会员数2 月 15 日 已看到该 DVD 的会员数 m 20000 m 1 月 1 日月 15 日 1 m2 m min(0.6m, 0.6 (20000 m)) 20000 m2 3 月 1 2 月 1 m3 m2 min(m, 20000 m2 ) 20000 m3 日月 15 日 3 2 月 15 日 20000 m4 m4 m3 min(0.6m, 0.6 (20000 m3 )) DVD 种类 DVD1 DVD2 DVD3 DVD4 DVD5 购买量 6250 3125 1563 782 313 2005 8 名称 1 3 月年全国大学生数学建模竞赛全国一等奖DVD1 DVD2 DVD3 DVD4 DVD5 数量（张） 3959 1980 990 495 198 3 月 15 日

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

要使三个月内希望看到某种 DVD 的会员中至少 95%的会员能够看到该 DVD，则要使：

此时，计算得

20000 m6 20000 5%

m 3959

同理，求得为使三个月内希望看到该 DVD，则每种 DVD 的购买数量如下表所示：

相对满意度 0.5 0.6 1486 0.7 1760 0.8 2059 0.9 2567 1.0 3098 所需 DVD 数 1202

DVD 种类 DVD1 DVD2 DVD3 DVD4 DVD5 6．1．3 理论证明 购买量 9000 4500 2250 1125 450 事实上，不必认为所有的人都在 1 号的时候来借 DVD，我们可以从理论求解该问题。 DVD 种类 DVD1 DVD2 DVD3 DVD4 DVD5 假设某种 0.4，被看到两次的概率为 0.6，则其服从 购买量 DVD 一个月内被看到一次的概率为4500 2250 1125 563 225 分布：时间 想看到但并未看到的会员数已看到该 DVD 的会员数 m 1 220000 m 1 月 1 1 月 15 日  0.4 0.6为使希望看到该 DVD 的会员中至少 50%在一个月内能够看到该 DVD，即是要求 2 月 1 n  50% * 20000 2 月 15 日 i1 为保证希望看到该 DVD 的会员中至少 50%在一个月内能够看到该 DVD，则要使得上成 立的概率尽可能大，不妨取： 3 月 1 n

3 月 15 日 P(i 50% *20000) 95% i1

n DVD 种类 DVD1 DVD2 DVD3 DVD4 DVD5 i 购买量 6250 n 的数量很大，由中心极限定理知，3125 1563 782 313 由于i 是同分布的，且i1 近似服从正态分布。 名称 DVD1 DVD2 DVD3 DVD4 DVD5 将其化为标准正态分布即为： 数量（张） 3959 495 198 1980 990 n 10000 1.6n 1  i 1 (i1.6) p( * ) 0.95

n * 0.4*0.6 n 0.4*0.6 查表可得：

100001.6n

1.5

n * 0.4*0.6 解得

n (0.25 0.252 6250 ) 2 6250 同理亦可推出均值情况下的其他解。

2005 年全国大学生数学建模竞赛全国一等奖

9

6．2 100 种 DVD 对于 1000 个会员在线订单的分配

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

6．2．1 模型建立

在问题 2 中，网站当前需要处理 1000 位会员的在线订单。网站手上现有数量有限的 100 种 DVD 进行分配，并使所有会员的满意度最高。

在此先对满意度的定义给一说明，设第 i 个会员对第 j 种 DVD 感兴趣，并且在他

acij 11 aij 的订单中，给出的偏爱程度为 。 ,则第 i个会员获得第 j种 DVD 时的满意度为 此时，在最好情况下每个会员的满意度最大为 27，定义第 i 个人的个人相对满意度 为：

ci

ci '27

其中, ci 表示第 i 个人的满意度。 建立如下的 0—1 规划模型： 1000 100

max  c x ij ij

i1 j1

c

其中， ij 以喜好程度表示的会员的满意度，对于会员感兴趣的 DVD 如果在会

员的订单中，给出的偏爱程度为 a，则相应的 为 11-a,其余为 0

s.t 每个会员每次最多获得 3 张 DVD

100

 3  x ij

j1

每种碟的总数的约束：

1000

 x ij  bj

i1

0—1 的约束：

1000

 x ij  0或者1

i1

2005 年全国大学生数学建模竞赛全国一等奖

10

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

6．2．2 模型求解

使用 lingo 软件求解上述模型，得到使得所有会员满意度最大的分配方案。在该方案下， 所有会员的满意度为 24746。

给出分配后，前 30 位会员获得的 DVD 情况如表 4：

表 4

C0001 C0002 C0003 C0004 C0005 DVD 编号 008 041 098 006 044 062 032 050 080 007 018 041 011 066 068 序号 10 4 8 10 9 7 7 9 10 10 9 8 8 10 9 C0016 C0017 C0018 C0019 C0020 会员 C0001 C0002 C0003 C0004 C0005 DVD 编号 008 041 098 006 044 062 032 050 080 007 018 041 011 066 068 序号 10 4 8 10 9 7 7 9 10 10 9 8 8 10 9 C0016 C0017 C0018 C0019 C0020 会员 C0001 C0002 C0003 C0004 C0005 DVD 编号 008 041 098 006 044 062 032 050 080 007 018 041 011 066 068 序号 10 4 8 10 9 7 7 9 10 10 9 8 8 10 9 C0016 C0017 C0018 C0019 C0020 会员 C0001 C0002 C0003 C0004 C0005 DVD 编号 008 041 098 006 044 062 032 050 080 007 018 041 011 066 068 序号 10 4 8 10 9 7 7 9 10 10 9 8 8 10 9 C0016 C0017 C0018 C0019 C0020 会员 C0001 C0002 C0003 C0004 C0005 DVD 编号 008 041 098 006 044 062 032 050 080 007 018 041 011 066 068 序号 10 4 8 10 9 7 7 9 10 10 9 8 8 10 9 C0016 C0017 C0018 C0019 C0020 会员 C0001 C0002 C0003 C0004 C0005 DVD 编号 008 041 098 006 044 062 032 050 080 007 018 041 011 066 068 序号 10 4 8 10 9 7 7 9 10 10 9 8 8 10 9 C0016 C0017 C0018 C0019 C0020 2005 年全国大学生数学建模竞赛全国一等奖

11

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

下图给出 1000 位会员的个人满意度统计情况：

fig1

上图中，横轴表示个人满意度，纵轴表示相应个人满意度的会员。可见，绝大部分 的会员其满意度都在 0.8 以上。可见，该分配方案是很好的。

6．3 一个月的 DVD 分配方案 6．3．1 模型建立

前述 6.2 中只讨论了 1 次分配的最优性问题，下面，我们来考虑一个月内如何分 配，如何购置 DVD 才能使得会员的满意度最大。并且满足 95%的会员得到他想看到的 DVD。

这是一个多目标规划的问题。从自己的经济利益出发，网站希望所需购买的 DVD 越少 越好，而从自己的社会效应出发，网站希望尽可能提高会员的满意度。

我们考虑如前 6.1 所述的均值情况，即所有的会员均在每月的 1 号租赁 DVD，对 于当月只租赁 1 次 DVD 的会员，他们将 DVD 保留到下一个月，对于当月租赁两次的 会员，均在当月的 15 号归还，同时租赁第二次。这样，在一个月内，我们只需考虑对 所有 DVD 做两次分配即可。即 1 号分配方案和 15 号分配方案。

由于占会员 60%的该月租赁两次 DVD 的人员无法确切预知，我们采取从 1000 个会员中随机选取 600 名让其该月租赁两次 DVD。由于题目中所给订单数据的均匀值， 不会出现选取不同的 600 名会员时，最终结果偏差很大的情况，我们认为这样做是合理 的。同时，当这种随即的选取数次之后，一个平均的结果可以认为是合理的。

对于满意度的定义，我们考虑一个相对满意度的概念，在最理想的概念，在最理 想的情况下，第一次分配时两个会员都获得自己最满意的 3 张 DVD，在第二次分配时，

2005 年全国大学生数学建模竞赛全国一等奖

12

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

参与分配的每个会员都获得此时自己最满意的 3 张 DVD。在第二次分配时，参与分配 的每个会员都获得此时自己最满意的 3 张 DVD。这种情况下的总体满意度为

600 45 400 27 37800 假设某种分配方案的总体满意度为 C ，则定义其相对满意度为

C 'C 37800

基于上述几点考虑，该问题转化为如下的 0—1 规划模型：

1000 100 1000 100 max  c x ij ij1 i1 j1

 cij xij 2 i1 j1

100

min  b j j1 其中：

x1 第1次分配时第i名会员获得第j张DVD ij1

0 第1次分配时第i名会员未获得第j张DVD

x1 第2次分配时第i名会员获得第j张DVD ij 2

0 第2次分配时第i名会员未获得第j张DVD s.t.

第 1 次分配时 DVD 总数约束：100

 x

 b j j1 第 1 次分配时每名会员最多获得 n 张 DVD 100  x  n j1 第 2 次分配时，DVD 总数的约束：

100  x

 b j ' j1 其中， b ' 表示第 2 次分配时，网站拥有第 j 种 DVD 的数量

1000

b j ' bj xij1 c j i1

表示第 2 次分配时占总数 60%的会员归还的第 j 种 DVD 的数量 1000

c j xij1di i1 2005 年全国大学生数学建模竞赛全国一等奖

13

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

其中， di 随机生成，为 1 表示第 i 个人在该月内两次租赁 DVD，反之为 0。 有一部分人未借第二次的约束：

xij 2 di

第一次已看到的 DVD 第二次就不再租赁了的约束：

xij1 xij 2 1

e1i xij1 e2i xij 2

反之为 0

xij1 1或0 xij 2 1或0

di 1或0

14

1000 100

e1i xij1 i1 j1

e2i xij 2 i1 j1

1000 100

0 eki 1

上式中， eki =1 表示第 k 次分配时第 i 个人在一个月内至少可以看到一张 DVD，

2005 年全国大学生数学建模竞赛全国一等奖

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

6．3．2 模型求解

上述为多目标规划，具体处理时，可采用线性加权法等经典方法，将多目标规划变 为了单目标规划处理。在此，我们将相对满意度在一定的范围内变化，分别求出一组在 各种满意度下所需的最少 DVD 数即相应的 DVD 分配方案。

我们得到在相对满意度在 0.5~1 之间变化时，所需最少 DVD 数如下表所示：

表 5

相对满意度 0.5 0.6 1486 0.7 1760 0.8 2059 0.9 2567 1.0 3098 所需 DVD 数 1202

购买量 购买量 购买量 DVD 种类 DVD 种类 DVD 种类 从上可以看出，要使满意度不低于 0.5 至少需要 DVD,而要使得总的满意度 D001 22 D034 20 1202 张D067 26 达到 1.0,则至少要 3098 要达到最好的满意度，则至少需要 DVD. D002 28 张 DVD.D035 30 D068 3098 张32 此时，相对满意度和所需 DVD 总数的关系图如下： D069 D003 29 D036 29 26 D004 28 D037 20 D070 26 D005 22 D038 24 D071 26 D006 29 D039 26 D072 28 D007 24 D040 25 D073 21 D008 26 D041 35 D074 20 D009 27 D042 30 D075 25 D010 24 D043 28 D076 20 D011 28 D044 24 D077 22 D012 26 D045 33 D078 27 D013 24 D046 20 D079 25 D014 27 D047 25 D080 26 D015 18 D048 25 D081 23 D016 33 D049 27 D082 19 D017 30 D050 23 D083 17 D018 27 D051 29 D084 21 D019 33 D052 22 D085 28 D020 32 D053 33 D086 20 D021 24 D0 22 D087 28 D022 27 D055 26 D088 19 D023 31 D056 28 D0 23 D024 22 D057 fig2 27 D090 21 D025 23 D058 23 D091 31 D026 25 D059 24 D092 24 上图中横坐标表示会员总的相对满意度，纵坐标表示达到这个满意度时的购买 DVD 总数。 D027 24 D060 29 D093 23 D028 20 D061 24 D094 27 从上图可以看出：随着满意度的增加，所需的 DVD 总数近似线性的增加。这表明： D028 23 D062 27 D095 27 如果要增加总体满意度，必须以多购买 DVD 为代价，而且，满意度的增加与 DVD 总 D030 28 D063 30 D096 20 数的增加近似成一定的比例。 D031 29 D0 34 D097 31 D032 24 D065 28 D098 28 D033 24 D066 30 D099 18 D100 27 2005 年全国大学生数学建模竞赛全国一等奖 15

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

当满意度为 0.9 时所需的 DVD 购买量：

表 6

相对满意度 0.5 0.6 1486 0.7 1760 0.8 2059 0.9 2567 1.0 3098 所需 DVD 数 1202 DVD 种类 D001 D002 D003 D004 D005 D006 D007 D008 D009 D010 D011 D012 D013 D014 D015 D016 D017 D018 D019 D020 D021 D022 D023 D024 D025 D026 D027 D028 D028 D030 D031 D032 D033 购买量 22 28 29 28 22 29 24 26 27 24 28 26 24 27 18 33 30 27 33 32 24 27 31 22 23 25 24 20 23 28 29 24 24 DVD 种类 D034 D035 D036 D037 D038 D039 D040 D041 D042 D043 D044 D045 D046 D047 D048 D049 D050 D051 D052 D053 D0 D055 D056 D057 D058 D059 D060 D061 D062 D063 D0 D065 D066 购买量 20 30 29 20 24 26 25 35 30 28 24 33 20 25 25 27 23 29 22 33 22 26 28 27 23 24 29 24 27 30 34 28 30 DVD 种类 D067 D068 D069 D070 D071 D072 D073 D074 D075 D076 D077 D078 D079 D080 D081 D082 D083 D084 D085 D086 D087 D088 D0 D090 D091 D092 D093 D094 D095 D096 D097 D098 D099 D100 购买量 26 32 26 26 26 28 21 20 25 20 22 27 25 26 23 19 17 21 28 20 28 19 23 21 31 24 23 27 27 20 31 28 18 27 2005 年全国大学生数学建模竞赛全国一等奖 16

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

下表给出前 30 位会员月初（1 号）时分配方案

表 7

相对满意度 0.5 0.6 1486 0.7 1760 0.8 2059 0.9 2567 1.0 3098 所需 DVD 数 1202 购买量 DVD 种类 DVD 种类 D001 22 D034 D002 28 D035 D003 29 D036 相对满意度0.7 D004 0.5 28 0.6 D037 所需 DVD 数 1202 22 1486 D038 1760 D005 购买量DVD 种类 DVD 种类 D006 29 D039 D001 22 D034 D007 24 D040 D002 28 D035 D008 26 D041 D003 29 D036 D009 27 D042 相对满意度0.7 D004 D037 D010 0.5 28 24 0.6 D043 所需 DVD 数 1202 22 1760 D005 D011 28 1486 D038 D044 购买量DVD 种类 DVD 种类 D006 29 D039 D012 26 D045 D001 22 D034 D007 24 D040 D013 D046 D002 28 D035 D008 26 D041 D014 27 D047 D003 29 D036 D009 27 D042 D015 18 D048 相对满意度0.7 D004 D037 D010 24 D043 D016 0.5 28 33 0.6 D049 所需 DVD 数 1202 22 1760 D005 D011 28 D044 D017 30 1486 D038 D050 购买量DVD 种类 DVD 种类 D006 29 D039 D012 26 D045 D018 27 D051 D001 22 D034 D007 24 D040 D013 D046 D019 33 D052 D002 28 D035 D008 26 D041 D014 27 D047 D020 32 D053 D003 29 D036 D009 27 D042 D015 18 D048 D021 24 D0 相对满意度0.7 D004 D037 D010 24 D043 D016 33 D049 D022 0.5 28 27 0.6 D055 所需 DVD 数 1202 22 1760 D005 D011 28 D044 D017 30 D050 D023 31 1486 D038 D056 购买量DVD 种类 DVD 种类 D006 29 D039 D012 26 D045 D018 27 D051 D024 22 D057 D001 22 D034 D007 24 D040 D013 D046 D019 33 D052 D025 23 D058 D002 28 D035 D008 26 D041 D014 27 D047 D020 32 D053 D026 25 D059 D003 29 D036 D009 27 D042 D015 18 D048 D021 24 D0 D027 D060 相对满意度 0.5 0.6 0.7 D004 28 D037 D010 24 D043 D016 33 D049 D022 27 D055 D028 20 D061 所需 DVD 数 1202 22 1486 D038 1760 D005 D011 28 D044 D017 30 D050 D023 31 D056 D028 23 D062 购买量 DVD 种类 DVD 种类 D006 29 D039 D012 26 D045 D018 27 D051 D024 22 D057 D030 28 D063 D001 22 D034 D007 24 D040 D013 D046 D019 33 D052 D025 23 D058 D031 29 D0 D002 28 D035 D008 26 D041 D014 27 D047 D020 32 D053 D026 25 D059 D032 24 D065 D003 29 D036 D009 27 D042 D015 18 D048 D021 D0 D027 24 D060 D033 D066 D004 28 D037 D010 24 D043 D016 33 D049 D022 27 D055 D028 20 D061 D005 22 D038 D011 28 D044 D017 30 D050 D023 31 D056 D028 23 D062 D006 29 D039 D012 26 D045 D018 27 D051 D024 22 D057 D030 28 D063 D007 24 D040 D013 D046 D019 33 D052 D025 23 D058 D031 29 D0 D008 26 D041 D014 27 D047 D020 32 D053 D026 25 D059 D032 24 D065 D009 27 D042 D015 18 D048 D021 D0 D027 24 D060 D033 D066 D010 24 D016 33 D049 D022 27 D055 2005 年全国大学生数学建模竞赛全国一等奖 D043 D028 20 D061 D011 28 D044 D017 30 D050 D023 31 D056 D028 23 D062 D012 26 D045 D018 27 D051 D024 22 D057 D030 28 D063 D013 24 D046 D019 33 D052 D025 23 D058 D031 29 D0 购买量 20 30 29 0.8 20 2059 24 购买量26 20 25 30 35 29 30 0.8 20 28 2059 24 购买量26 33 20 25 30 35 25 29 30 25 0.8 20 28 27 2059 24 23 购买量26 33 29 20 25 20 22 30 35 25 33 29 30 25 22 0.8 20 28 27 26 2059 24 23 28 购买量26 33 29 27 20 25 22 23 30 35 25 33 24 29 30 25 22 29 0.8 20 28 27 26 24 2059 24 23 28 27 购买量 26 33 29 27 30 20 25 22 23 34 30 35 25 33 24 28 29 30 25 22 29 30 20 28 27 26 24 24 23 28 27 26 33 29 27 30 25 20 22 23 34 35 25 33 24 28 30 25 22 29 30 28 27 26 24 24 23 28 27 33 29 27 30 20 22 23 34 DVD 种类 D067 D068 D069 0.9 D070 2567 D071 DVD 种类 D072 D067 D073 D068 D074 D069 D075 0.9 D070 D076 2567 D071 D077 DVD 种类 D072 D078 D067 D073 D079 D068 D074 D080 D069 D075 D081 0.9 D070 D076 D082 2567 D071 D077 D083 DVD 种类 D072 D078 D084 D067 D073 D079 D085 D068 D074 D080 D086 D069 D075 D081 D087 0.9 D070 D076 D082 D088 2567 D071 D077 D083 D0 DVD 种类 D072 D078 D084 D090 D067 D073 D079 D085 D091 D068 D074 D080 D086 D092 D069 D075 D081 D087 D093 0.9 D070 D076 D082 D088 D094 2567 D071 D077 D083 D0 D095 DVD 种类 D072 D078 D084 D090 D096 D067 D073 D079 D085 D091 D097 D068 D074 D080 D086 D092 D098 D069 D075 D081 D087 D093 D099 D070 D076 D082 D088 D094 D100 D071 D077 D083 D0 D095 D072 D078 D084 D090 D096 D073 D079 D085 D091 D097 D074 D080 D086 D092 D098 D075 D081 D087 D093 D099 D076 D082 D088 D094 D100 D077 D083 D0 D095 D078 D084 D090 D096 D079 D085 D091 D097 购买量 26 32 26 1.0 26 3098 26 购买量28 26 21 32 20 26 25 1.0 26 20 3098 26 22 购买量28 27 26 21 25 32 20 26 26 25 23 1.0 26 20 19 3098 26 22 17 购买量28 27 21 26 21 25 28 32 20 26 26 25 23 28 1.0 26 20 19 3098 26 22 17 23 购买量28 27 21 26 21 25 28 31 32 20 26 20 24 26 25 23 28 1.0 26 20 19 27 3098 26 22 17 23 27 购买量 28 27 21 20 26 21 25 28 31 32 20 26 24 28 26 25 23 28 23 18 26 20 19 27 26 22 17 23 27 28 27 21 20 21 25 28 31 20 26 24 28 25 23 28 18 20 19 27 22 17 23 27 27 21 20 25 28 31 17

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

相应的此时，会员的个人满意度的分布如下图所示：

fig3

对比 fig1 和 fig3，我们可以发现，在 fig3 中出现了一个很奇怪的现象，即会员的个 人满意度集中的分布在 0.7 左右和 1 左右。这是为什么呢？其实在总的 DVD 数量有限 的情况下，为了使得总体的满意度最大，分配时总是倾向于让每月租赁两次的会员（称 2 类会员）尽量多拿到 DVD，这样才可以保证 DVD 最大限度的利用。那么在此时，总 是首先考虑月内租赁两次的会员，让他们得到 3 张 DVD,而其余的人呢只能得到小于 3 张的 DVD，这样，2 类会员的满意度总是大约为 1，而 1 类会员的满意度总是集中一个 小一些的数上。从上图也可以看到，这两者的比例大致为 4：6。

显然，当总的 DVD 数量越大是，1 类会员的满意度高，也即两个峰靠得越紧。下 面给出满意度为 0.8 时的个人满意度分布图（fig4）,我们可以从中看到这一点。

Fig4

2005 年全国大学生数学建模竞赛全国一等奖

18

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

6．4 最优经营策略和多种服务

网站在经营中，其最主要的目标是获得最大的利润。假设会员每个月所缴纳的会 费为 C ，而此时网站的经营模式为限定每个月会员租赁次数不得超过 m 次。每次租赁不 得超过 n 张碟。从网站的角度来看，当 m、n 增大时，可能网站的经营成本会增加，因 为此时，网站需要付出更多的邮费以及出资购买更多的 DVD，因此，网站总是向于尽 量减小 m,n，但是考虑到顾客满意读不能太低，此时，m,m 有不可以太小，这样，对于 网站来说，存在一个 m，n 的最优值，以该模式运营，在满足满意度达到一定指标的情 况下，网站会获得最优的效益。下面我们分别来考虑每月最大租赁次数 m 和每次最多租 赁 DVD 数目 n 对网站经营利润的影响。

6．4．1 最优每次租赁 DVD 数 6．4．1．1 模型建立

我们首先来考察限定每月最多租赁两次的情况下，为了使得网站获得最大的利润， 应该如何限定会员每次租赁 DVD 的数目。

考虑如下的问题：继续考虑表 2，表中列出了网站手头上 100 种 DVD 的现有张数 和当前需要处理的 1000 位会员的在线订单。假定购买一张新 DVD 的费用为 M=10 美元。 每份快递的费用为 2 美元，会员每月租赁次数不得超过 2 次。每个会员每月的月费为 19.9 美元，n 为每次会员最多获得的 DVD 数目，如何确定 n 以及如何对这些 DVD 进行分配， 才能使网站所获利润最大，同时使得会员的满意度不低于 0.8。在此，我们建立以下的 0

xij 1 —1 规划模型：（ 表示第 i 个会员获得第 j 张 DVD）

max

e1i 2 e2i 10 b j 19.91000 2i1 i1 j1 1000 1000 100

第k此分配第i个人获得DVD 1 eki

0 否则 其中： s.t

第 1 次分配时 DVD 总数约束：

100

 b j  x j1

第 2 次分配时每名会员最多获得 3 张 DVD 100  3  x j1

第 2 次分配时，DVD 总数的约束：

100

 b j '  x b ' 其中， 表示第 2 次分配时，网站拥有第 j 种 DVD 的数量

2005 年全国大学生数学建模竞赛全国一等奖

19

j1

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

b j ' bj xij1 c j

表示第 2 次分配时占总数 60%的会员归还的第 j 种 DVD 的数量

c j xij1di i1 1000

i1

1000

其中， di 随机生成，为 1 表示第 i 个人在该月内两次租赁 DVD，反之为 0。 有一部分人未借第二次的约束：

xij 2 di

第一次已看到的 DVD 第二次就不再租赁了的约束：

xij1 xij 2 1

一个月内 95%以上的会员看到自己想看到的 DVD 的约束：

ei xij1 ei xij 2

上式中， ei =1 表示第 i 个人在一个月内至少可以看到一张 DVD，反之为 0

xij1 1或0 xij 2 1或0

di 1或0

20

1000 100 1000 100

ei xij1 xij 2 i1 j1 i1 j1 1000  950  e i

i1 0 ei 1

2005 年全国大学生数学建模竞赛全国一等奖

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

6．4．1．2 模型求解

求解上述模型，可以得到在限定每个会员每月最多租赁 2 次 DVD 的情况下，对于 上述问题，要使得网站所获得的总利润最大网站应该制定时的会员每月最多可获得 2 张 DVD，此时网站可得利润： -4800 美元，之所以会出现利润是负值，是因为，我们付 出了很大一部分费用购买新的 DVD，这部分钱，其实在两个月后就可收回了。

这时，1000 为会员的个人满意度统计如下：

Fig5

上图中，横轴表示个人满意度，纵轴表示相应个人满意度的会员。此时，会员的满 意度可以达到 0.8。

这就是说，在本问题所给的情况下，对于每月最多租赁两次的情况下，允许会 员每次借 2 张 DVD 网站所获得的经济效应会好于每次最所允许每位会员借 3 张 DVD. 此事建议，刚网站，不妨采用 2-2 模式来运营。即每月允许会员最多租赁 2 次，每次最 多得 2 张 DVD。

2005 年全国大学生数学建模竞赛全国一等奖

21

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

6．4．2 最优租赁次数

这里，我们接着讨论当每次最多租赁数目确定的情况下，如何一个月内租赁的次 数才可以保证在一定的满意度下。使得网站获得最大的经济效益最大。显然，随着 每月租赁次数的增加，问题的规模迅速地增大。但是现实的情况是，由于一些客观因素 及主管因素的 制约，会员在一个月内租赁 DVD 的次数是有限的。这样，我们只需要将 m 限定在一个较小的范围内讨论，如限定在 5 次以内。

类似的，也可以建立上述的 0-1 规划模型进行求解求得在一定条件下的每月最优租 赁次数 m。

6.4.3 对于网络经营方式的一些建议

为了在购买新 DVD 时能够更准确地对需求进行预测，我们建议网站的调查表可以设 计为让每位会员按其偏爱程度给出自己感兴趣的十张 DVD，这时在考虑具体购买新的 DVD。我们相当于已经有了一个具体的订单，这样会使我们的购买方案更加合理和精确。

另外，建议网站对于其所有会员的租赁记录给以统计，从而大体上掌握 1 类会员和 2 类会员的具体情况。

2005 年全国大学生数学建模竞赛全国一等奖

22

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组

七 模型评价

模型优点：

1、 对于问题 1，我们从理论上证明了“6250”的合理性。逻辑严密，推理正确。 2、 我们巧妙的将原本很复杂的非线性问题转化为线性问题，是的问题的求解大

大简化。

3、 我们求出了多种满意度下的最小 DVD 总数，并发现了二者之间近似线性的

关系。

4、 我们求出了限定每月最多租赁两次的情况下，为使网站利润达到最大，会员

每次最多租赁的 DVD 张数，这对于网站的经营、管理具有参考价值。 模型缺点：

题目中大量使用了大规模的规划，没有考虑对模型进行精简。这使得求解的运算量 较大。

1. 2. 3. 4. 5.

《运筹学》教材编写组，运筹学（修订版），北京：清华大学出版社，1990。

叶其孝主编，大学生数学建模竞赛辅导教材（一），长沙：湖南教育出版社，1993。 叶其孝主编，大学生数学建模竞赛辅导教材（二），长沙：湖南教育出版社，1997。 叶其孝主编，大学生数学建模竞赛辅导教材（三），长沙：湖南教育出版社，1998。 姜启源，数学模型（第二版），北京：高等教育出版社，1993。

23

八 参考文献

2005 年全国大学生数学建模竞赛全国一等奖