2005年全国大学生数学建模国家二等奖获奖论文 DVD在线租赁的研究 尹作龙,姚明,金伟 指导教师汪晓银 摘要 随着信息时代的到来,网络成为人们生活中越来越不可或缺的元素之一。许多网站 利用其强大的资源和知名度,面向其会员群提供日益专业化和便捷化的服务。例如,音 像制品的在线租赁就是一种可行的服务。本文主要讨论了在线DVD租赁的问题,对网站 如何购买DⅦD,如何分配DⅦD进行了一些研究。对于问题一,我们首先把会员根据每月 租赁次数分成A、B两类,并对两类会员归还日期作了合理的假设,根据求出DVD归还 的期望值。最后求得会员归还一张DVD的时间期望为12天。然后用DVD的周转次数来 计算网站对某种DVD的购买量,最后根据问题的要求,求得每种DVD至少准备的张数如 DVD名称 DVDI DVD2DVD3 DVD4 DVDs 个月内至少50% 4000 2000 1000 看到的最少张数 三个月内至少95% 2534 267 634 317 127 看到的最少张数 问题二,我们首先对满意度进行了定义,并作出相应的假设。根据假设建立 规划模型,用 LINGO软件编程求得各种DVD的分配方案。我们根据实际情况修改了偏 爱程度,再次用 LINGO编程求解,得出第二中分配方案。第一种分配方案的总偏爱度 U为7924,有30张DVD分配给了没有预订这些DⅤD的会员;第二种分配方案的总偏 爱度U为8191,有8张DVD分配给了没有预订这些DVD的会员。虽然第一种分配方 案的总偏爱度优于第二种,但是经证明无论怎么分配,至少有8张DVD会分配给没有 预定这些DVD的会员,因此我们选择第二种分配方案 问题三,根据满意度最大,我们建立了一个规划模型,由于模型难以用计算机求解, 我们改用计算机仿真来模拟现实购DVD方案,模拟生成的购买的总DVD数为3086。 问题四,在DVD的需求预测、购买和分配中重要问题的研究中,首先研究了DVD 的需求预测,并建立了灰色GM(1,1)模型,灰色GM(1,1)模型能够克服相关数 据不足的缺陷和避免人为因素的影响。这表明基于灰色理论的预测方法,适合于对DD 在线租赁业务趋势进行预测。该方法是切实可行并有效的,并对DWD在线租赁业务发展 规划有重要参考价值。然后从网站的赢利角度出发,建立了一个以赢利函数为目标的线 性规划模型,此模型在租赁方面有着较髙的参考价值。 最后我们对我们所建立的模型及求解方案进行评价,推广。我们考虑到对于更大规 模问题,现有模型的求解就会困难。因此我们想了模型的另外一个算法:贪心算法。贪 心算法速度快,但得到的解难以达到最优 关键词]:DVD在线租赁0-1规划概率模型计算杋仿真灰色GM(l,1模型
2005 年全国大学生数学建模国家二等奖获奖论文 1 DVD 在线租赁的研究 尹作龙，姚明，金伟 指导教师 汪晓银 [摘 要]： 随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站 利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。例如，音 像制品的在线租赁就是一种可行的服务。本文主要讨论了在线 DVD 租赁的问题，对网站 如何购买 DVD，如何分配 DVD 进行了一些研究。对于问题一，我们首先把会员根据每月 租赁次数分成 A、B 两类，并对两类会员归还日期作了合理的假设，根据求出 DVD 归还 的期望值。最后求得会员归还一张 DVD 的时间期望为 12 天。然后用 DVD 的周转次数来 计算网站对某种 DVD 的购买量，最后根据问题的要求，求得每种 DVD 至少准备的张数如 下。 DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5 一个月内至少 50% 看到的最少张数 4000 2000 1000 500 200 三个月内至少 95% 看到的最少张数 2534 1267 634 317 127 问题二，我们首先对满意度进行了定义，并作出相应的假设。根据假设建立 0—1 规划模型，用 LINGO 软件编程求得各种 DVD 的分配方案。我们根据实际情况修改了偏 爱程度，再次用 LINGO 编程求解，得出第二中分配方案。第一种分配方案的总偏爱度 U 为 7924，有 30 张 DVD 分配给了没有预订这些 DVD 的会员；第二种分配方案的总偏 爱度 U 为 8191，有 8 张 DVD 分配给了没有预订这些 DVD 的会员。虽然第一种分配方 案的总偏爱度优于第二种，但是经证明无论怎么分配，至少有 8 张 DVD 会分配给没有 预定这些 DVD 的会员，因此我们选择第二种分配方案。 问题三，根据满意度最大，我们建立了一个规划模型，由于模型难以用计算机求解， 我们改用计算机仿真来模拟现实购 DVD 方案，模拟生成的购买的总 DVD 数为 3086。 问题四，在 DVD 的需求预测、购买和分配中重要问题的研究中，首先研究了 DVD 的需求预测，并建立了灰色 GM（1，1）模型，灰色 GM（1，1）模型能够克服相关数 据不足的缺陷和避免人为因素的影响。这表明基于灰色理论的预测方法，适合于对 DVD 在线租赁业务趋势进行预测。该方法是切实可行并有效的，并对 DVD 在线租赁业务发展 规划有重要参考价值。然后从网站的赢利角度出发，建立了一个以赢利函数为目标的线 性规划模型，此模型在租赁方面有着较高的参考价值。 最后我们对我们所建立的模型及求解方案进行评价，推广。我们考虑到对于更大规 模问题，现有模型的求解就会困难。因此我们想了模型的另外一个算法：贪心算法。贪 心算法速度快，但得到的解难以达到最优。 [关键词]：DVD 在线租赁 0—1 规划 概率模型 计算机仿真 灰色 GM（1，1）模型
2005年全国大学生数学建模国家二等奖获奖论文 、问题的重述 考虑如下的在线DVD租赁问题。顾客缴纳一定数量的月费成为会员,订购DVD 租赁服务。会员对哪些DVD有兴趣,只要在线提交订单,网站就会通过快递的方式尽 可能满足要求。会员提交的订单包括多张DVD,这些DⅤD是基于其偏爱程度排序的 网站会根据手头现有的DVD数量和会员的订单进行分发。每个会员每个月租赁次数不 得超过2次,每次获得3张DVD。会员看完3张DVD之后,只需要将DVD放进网站 提供的信封里寄回(邮费由网站承担),就可以继续下次租赁。请考虑以下问题: (1)网站正准备购买一些新的DVD,通过问卷调查1000个会员,得到了愿意观 看这些DⅤD的人数。此外,历史数据显示,60%的会员每月租赁DVD两次,而另外的 40%只租一次。假设网站现有10万个会员,对表1中的每种DVD来说,应该至少准备 多少张,才能保证希望看到该DVD的会员中至少50%在一个月内能够看到该DVD?如 果要求保证在三个月内至少95%的会员能够看到该DVD呢? (2)表2中列出了网站手上100种DVD的现有张数和当前需要处理的1000位会 员的在线订单,如何对这些DVD进行分配,才能使会员获得最大的满意度?请具体列 出前30位会员(即C0001~C0030)分别获得哪些DVD (3)考虑表2,并假设表2中DVD的现有数量全部为0。如果你是网站经营管理 人员,你如何决定每种DVD的购买量,以及如何对这些DVD进行分配,才能使一个 月内95%的会员得到他想看的DVD,并且满意度最大? (4)如果你是网站经营管理人员,你觉得在DVD的需求预测、购买和分配中还有 哪些重要问题值得研究?请明确提出你的问题,并尝试建立相应的数学模型 二、问题的假设 1、假设所有的DVD都不能拷贝 2、假设调查资料具有一定代表性 3、假设所有会员自觉遵守会员规定 4、假设在租赁和归还过程中DⅴD的遗失或损坏忽略不计 5、假设DVD的种类与购DVD费用无关 、符号的说明 符号 符号说明 该网站拥有的总会员数 第i个会员在线定单中第j种DVD的需求情况 第i个会员对第j种DVD的偏爱程度 第i张DVD的现有量 M愿意观看第i种DVD的总人数 P 愿意观看第i种DVD的人数占总人数的百分比 2
2005 年全国大学生数学建模国家二等奖获奖论文 2 一、问题的重述 考虑如下的在线 DVD 租赁问题。顾客缴纳一定数量的月费成为会员，订购 DVD 租赁服务。会员对哪些 DVD 有兴趣，只要在线提交订单，网站就会通过快递的方式尽 可能满足要求。会员提交的订单包括多张 DVD，这些 DVD 是基于其偏爱程度排序的。 网站会根据手头现有的 DVD 数量和会员的订单进行分发。每个会员每个月租赁次数不 得超过 2 次，每次获得 3 张 DVD。会员看完 3 张 DVD 之后，只需要将 DVD 放进网站 提供的信封里寄回（邮费由网站承担），就可以继续下次租赁。请考虑以下问题： （1）网站正准备购买一些新的 DVD，通过问卷调查 1000 个会员，得到了愿意观 看这些 DVD 的人数。此外，历史数据显示，60%的会员每月租赁 DVD 两次，而另外的 40%只租一次。假设网站现有 10 万个会员，对表 1 中的每种 DVD 来说，应该至少准备 多少张，才能保证希望看到该 DVD 的会员中至少 50%在一个月内能够看到该 DVD？如 果要求保证在三个月内至少 95%的会员能够看到该 DVD 呢？ （2）表 2 中列出了网站手上 100 种 DVD 的现有张数和当前需要处理的 1000 位会 员的在线订单，如何对这些 DVD 进行分配，才能使会员获得最大的满意度？请具体列 出前 30 位会员（即 C0001~C0030）分别获得哪些 DVD。 （3）考虑表 2，并假设表 2 中 DVD 的现有数量全部为 0。如果你是网站经营管理 人员，你如何决定每种 DVD 的购买量，以及如何对这些 DVD 进行分配，才能使一个 月内 95%的会员得到他想看的 DVD，并且满意度最大？ （4）如果你是网站经营管理人员，你觉得在 DVD 的需求预测、购买和分配中还有 哪些重要问题值得研究？请明确提出你的问题，并尝试建立相应的数学模型。 二、问题的假设 1、假设所有的 DVD 都不能拷贝 2、假设调查资料具有一定代表性 3、假设所有会员自觉遵守会员规定 4、假设在租赁和归还过程中 DVD 的遗失或损坏忽略不计 5、假设 DVD 的种类与购 DVD 费用无关 三、符号的说明 符号 符号说明 V 该网站拥有的总会员数 Dij 第 i 个会员在线定单中第 j 种 DVD 的需求情况 DLij 第 i 个会员对第 j 种 DVD 的偏爱程度 yi 第 i 张 DVD 的现有量 Mi 愿意观看第 i 种 DVD 的总人数 Pi 愿意观看第 i 种 DVD 的人数占总人数的百分比
2005年全国大学生数学建模国家二等奖获奖论文 R为满足会员要求的百分比数 会员获得DVD后所得到的总偏爱度,其值越小满意度越高 四、问题的分析及模型的建立及求解 41问题的背景资料 Netflix目前是美国最大的DVD出租网站,现在公司预计可在2006年达到500万订 户。这家网站的经营方法是,顾客在成为网站的固定会员后,可在网站上选取自己喜欢 的DⅤD影片,该公司现有DVD种类有5万多种,包括一些最新面世的大片,由这家 网站快速寄送到顾客的登记地址,每次最多3张。顾客可以无限期地借用这些影片,但 只有在寄回这些影片后才能借用新影片。顾客只需每月缴纳19.95美元的会员费,而 邮寄费用全部由网站支付。对顾客而言,坐在电脑前拖动几下鼠标就可得到中意的影片, 既省时又省力 据统计,超过60%的美国家庭至少拥有一台DVD影DVD机。去年,美国人在家 看DVD的时间平均为78小时,比2000年上升了53%。DVD的销量和出租量则上升 了6765%5。 42问题一的求解 42.1问题一模型的建立与求解 对问题一的分析,我们根据实际情况作了一些积极的假设,并简化了模型。从网站 经营者的角度出发,出于对自身赢利的考虑,希望DⅤD的周转越快越好。那么我们就 从DVD的周转情况来考虑对DVD数的需求量。 由题目我们把所有会员分成A、B两类:如表1 表1 类型每月租赁DVD次数所占会员总数的百分比会员人数 A类 两次 60% 60000 B类 40% 40000 考虑到DVD的周转,我们对两类会员作以下假设 A类会员归还一张DVD的时间X范围为3-15天 B类会员归还一张DVD的时间K2范围为3-30天 根据现实情况,我们假设X,脸2都服从等概率分布,则: EH,=15+3 EX =16.5 2 则会员归还一张DVD的时间期望为:=0.6×EX+04×EX2=12天。这就是说每张 DVD在会员手中保存的时间大约在12天, 那么: 在一个月内DVD的周转次数为:N=30÷12=25 在三个月内DVD的周转次数为:N=90÷12=7.5。(设30天为一个月) 根据题目中调査1000人愿意观看各种DVD的人数,我们得到会员愿意观看各种 DVD的经验概率分布统计结果如下(见表2): 表2
2005 年全国大学生数学建模国家二等奖获奖论文 3 R 为满足会员要求的百分比数 U 会员获得 DVD 后所得到的总偏爱度，其值越小满意度越高 四、问题的分析及模型的建立及求解 4.1 问题的背景资料 Netflix 目前是美国最大的 DVD 出租网站，现在公司预计可在 2006 年达到 500 万订 户。这家网站的经营方法是，顾客在成为网站的固定会员后，可在网站上选取自己喜欢 的 DVD 影片，该公司现有 DVD 种类有 5 万多种，包括一些最新面世的大片，由这家 网站快速寄送到顾客的登记地址，每次最多 3 张。顾客可以无限期地借用这些影片，但 只有在寄回这些影片后才能借用新影片。顾客只需每月缴纳 19．95 美元的会员费，而 邮寄费用全部由网站支付。对顾客而言，坐在电脑前拖动几下鼠标就可得到中意的影片， 既省时又省力。 据统计，超过 60%的美国家庭至少拥有一台 DVD 影 DVD 机。去年，美国人在家 看 DVD 的时间平均为 78 小时，比 2000 年上升了 53%。DVD 的销量和出租量则上升 了 676.5%[5]。 4.2 问题一的求解 4.2.1 问题一模型的建立与求解 对问题一的分析，我们根据实际情况作了一些积极的假设，并简化了模型。从网站 经营者的角度出发，出于对自身赢利的考虑，希望 DVD 的周转越快越好。那么我们就 从 DVD 的周转情况来考虑对 DVD 数的需求量。 由题目我们把所有会员分成 A、B 两类：如表 1 表 1 类型 每月租赁 DVD 次数 所占会员总数的百分比 会员人数 A 类 两次 60% 60000 B 类 一次 40% 40000 考虑到 DVD 的周转，我们对两类会员作以下假设： A 类会员归还一张 DVD 的时间 X1 范围为 3—15 天； B 类会员归还一张 DVD 的时间 X2 范围为 3—30 天； 根据现实情况，我们假设 X1， X2 都服从等概率分布，则： 9 2 15 3 1 = + EX = 16.5 2 30 3 2 = + EX = 则会员归还一张 DVD 的时间期望为：µ=0.6×EX1+0.4×EX2=12 天。这就是说每张 DVD 在会员手中保存的时间大约在 12 天， 那么： 在一个月内 DVD 的周转次数为：N=30÷12=2.5； 在三个月内 DVD 的周转次数为：N=90÷12=7.5。（设 30 天为一个月） 根据题目中调查 1000 人愿意观看各种 DVD 的人数，我们得到会员愿意观看各种 DVD 的经验概率分布统计结果如下（见表 2）： 表 2
2005年全国大学生数学建模国家二等奖获奖论文 DVD名称 DVDI DVD2 DVD3 DVD4 DVDS 经验概率P 20% 10% 2.5%1% R为满足会员要求的百分比:一个月为50%;三个月为95% 因此愿意观看第i种DVD的人数M为:M=×P×R=1000001×R(V为总会 员数)。 那么所需要DVD的最小数量为:S=M÷N。(向上取整) 我们得到S的函数表达式:S=XP×R÷N 求解得到每种DVD的准备张数(见表3): DVD名称 DVDI DVD2 DVD3 DVD4 DVDS 个月内至少50% 4000 2000 1000 500 200 看到的最少张数 三个月内至少95% 看到的最少张数 2534 1267 634 317 127 作为一个租赁网站的经营者,总是希望赢利更多,就要提高周转次数,减少周转天 数,这样他的先期投入也将减少。就可以考虑尽可能缩短租借的天数,来增加网站的赢 利和减少先期投入。若我们将归还时间定为3-9天,则期望为6。一个月的DD1所需 最少张数为2000张(小于4000张)。 4.3问题二模型的建立与求解 43.1问题二的分析 顾客满意度可以简要地定义为:顾客接受产品和服务的实际感受与其期望值比较的 程度。首先对满意度进行了如下假设:在会员的在线订单D中,数字越小表示会员的 偏爱程度越高,如果会员得到他偏爱程度越髙的DVD,则会员的满意度越大。假设会 员对DVD的偏爱度为:DLn= 11,D=0 该问题的目的就是分配当前的订单,使得这些顾客的满意度最大,可以用0-1规划 模型来求解,定义0-1变量Cn(=1…1000=1…100),C为1时表示第i个顾客租到了 第j种DVD,其值为0时表示没有租到相应的DVD 43.2问题二模型的建立 会员租赁DVD满意度的目标函数为:min∑∑ DL xC 0-1规划模型的约束条件为 1、每个顾客一次能并且只能租到3张DⅤD 2、租赁给会员的每种DⅤD总张数不能超过现有DⅤD数量。 由上述分析得到如下的0-1规划模型:
2005 年全国大学生数学建模国家二等奖获奖论文 4 DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5 经验概率 Pi 20% 10% 5% 2.5% 1% R 为满足会员要求的百分比：一个月为 50%；三个月为 95%。 因此愿意观看第 i 种 DVD 的人数 Mi 为：Mi=V×Pi×R=100000×Pi×R （V 为总会 员数）。 那么所需要 DVD 的最小数量为：S=M÷N。（向上取整） 我们得到 S 的函数表达式：S=V×Pi×R÷N ； 求解得到每种 DVD 的准备张数（见表 3）： 表 3 DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5 一个月内至少 50% 看到的最少张数 4000 2000 1000 500 200 三个月内至少 95% 看到的最少张数 2534 1267 634 317 127 作为一个租赁网站的经营者，总是希望赢利更多，就要提高周转次数，减少周转天 数，这样他的先期投入也将减少。就可以考虑尽可能缩短租借的天数，来增加网站的赢 利和减少先期投入。若我们将归还时间定为 3-9 天，则期望为 6。一个月的 DVD1 所需 最少张数为 2000 张（小于 4000 张）。 4.3 问题二模型的建立与求解 4.3.1 问题二的分析 顾客满意度可以简要地定义为：顾客接受产品和服务的实际感受与其期望值比较的 程度。首先对满意度进行了如下假设：在会员的在线订单 Dij 中，数字越小表示会员的 偏爱程度越高，如果会员得到他偏爱程度越高的 DVD，则会员的满意度越大。假设会 员对 DVD 的偏爱度为： ïî ï í ì ¹ = = , 0 11, 0 ij ij ij ij D D D DL 该问题的目的就是分配当前的订单，使得这些顾客的满意度最大，可以用 0-1 规划 模型来求解，定义 0-1 变量 Cij（i=1…1000,j=1…100）, Cij 为 1 时表示第 i 个顾客租到了 第 j 种 DVD，其值为 0 时表示没有租到相应的 DVD。 4.3.2 问题二模型的建立 会员租赁 DVD 满意度的目标函数为： åå= = ´ 1000 1 100 1 min i j DLij Cij 0- 1 规划模型的约束条件为： 1、每个顾客一次能并且只能租到 3 张 DVD； 2、租赁给会员的每种 DVD 总张数不能超过现有 DVD 数量。 由上述分析得到如下的 0-1 规划模型：
2005年全国大学生数学建模国家二等奖获奖论文 DL×C Cn=0,1 0,1变量 >C=3 每位会员租3张DVD C.≤ DVD现有数量的限制 (=1…1000J=1…100 433问题二的求解 对于上述的模型,在用 LINGO编程求解(具体程序请见附件),得到分配方案为 C求得总偏爱度为U=∑∑DxCn为7924由C得到分配了30张DVD给没有要求 预订这些DVD的会员。前30个会员租到DVD的情况如下表4: 会员号c00c0002c000004c0005c00c0007c008c0009c0010 分配 8(1)6(1)32(4)7(1)11(3)19(1)26(3)31(4)53(1)41(6) DvD的[24(7)41[50(2)18(2)6(1)53(266)35(578(3)5(2) 种类号阝398(362(48(1)4(3)68(2)66(4[81(1)71(1)102)85(3) 会员号|c0011c0012c0013c0014c0015c0016C0017c0018c0019c0020 分配159(12(2)21(3)23(2)13(1)10(4)47(2)41(1)66(4)45(1) DVD的|2|63(2)31(1)78(2)52(1)52(4)84(1)51(3)60(2)84(1)61(3) 种类号 66(4)41(7)%6(1)89(6)85(3)97(2)67(1)78(3)86(2)89(2) 会员号C0021C0022c0023C0024c0025c006|c0027c008C0029c0030 分配 45(2)38(3)29(2)37(4)9(1)22(1)50(4)8(1)26(4)37(2) DD的2505)5281(3)41(2)69(2)682)58(134(2)30(2)62(1 种类号|3|53(1)57(1)95(1)76(1)|94(3)95(3)78(7)82(3)551)98(5) 注:括号内的值为会员对该DVD喜好程度。 为使会员得到自己没有预定的DVD总数最少,可以将DL中为11的数增大变为 1000,即将此偏爱程度降低,再如上求解得到一种新的分配方案C,求得总偏爱度U 为8191(>7924),但是经分析,只分配了8张DVD给没有要求预订这些DVD的会员。 事实上这里的8张DVD已经最小,具体原因是,现有DVD总数为3007张,每个人得 到3张DVD,1000个人就得到3000张DVD,则还有7张未出租。根据所给的数据, 第37种DVD现有106张,只有91个会员愿意租此DVD,即第37张DVD按照会员的 需求无论怎么发放,也会有106-91=15张剩余,而总共应该只有7张DVD未出租,这 样就无法满足所有的会员租到自己想看的DVD,而且一定至少有15-7=8张DVD发给 了没有订这8张DVD的会员 比较上面两种分配方案,我们选择第二种分配方案。第二种方案下,前30会员的 租赁情况是只有第25个会员的第3张DVD与第一种分配方案不同,其值为81(4) 44问题三模型的建立与求解
2005 年全国大学生数学建模国家二等奖获奖论文 5 ï ï ï ï î ï ï ï ï í ì = = £ = = ´ å å åå = = = = ( 1 1000, 1 100) 3 0,1 . . min 1000 1 100 1 1000 1 100 1 i L j L C y C C st DL C i ij j j ij ij i j ij ij 4.3.3 问题二的求解 对于上述的模型，在用 LINGO 编程求解（具体程序请见附件），得到分配方案为 Ci,j 求得总偏爱度为 åå= = = ´ 1000 1 100 i j 1 U Dij Cij 为 7924。由 Ci,j 得到分配了 30 张 DVD 给没有要求 预订这些 DVD 的会员。前 30 个会员租到 DVD 的情况如下表 4： 表 4 会员号 C0001 C0002 C0003 C0004 C0005 C0006 C0007 C0008 C0009 C0010 1 8（1） 6（1） 32（4） 7（1） 11（3） 19（1） 26（3） 31（4） 53（1） 41（6） 2 41（7） 44（2） 50（2） 18（2） 66（1） 53（2） 66（6） 35（5） 78（3） 55（2） 分配 DVD 的 种类号 3 98（3） 62（4） 80（1） 41（3） 68（2） 66（4） 81（1） 71（1） 100（2） 85（3） 会员号 C0011 C0012 C0013 C0014 C0015 C0016 C0017 C0018 C0019 C0020 1 59（1） 2（2） 21（3） 23（2） 13（1） 10（4） 47（2） 41（1） 66（4） 45（1） 2 63（2） 31（1） 78（2） 52（1） 52（4） 84（1） 51（3） 60（2） 84（1） 61（3） 分配 DVD 的 种类号 3 66（4） 41（7） 96（1） 89（6） 85（3） 97（2） 67（1） 78（3） 86（2） 89（2） 会员号 C0021 C0022 C0023 C0024 C0025 C0026 C0027 C0028 C0029 C0030 1 45（2） 38（3） 29（2） 37（4） 9（1） 22（1） 50（4） 8（1） 26（4） 37（2） 2 50（5） 55（2） 81（3） 41（2） 69（2） 68（2） 58（1） 34（2） 30（2） 62（1） 分配 DVD 的 种类号 3 53（1） 57（1） 95（1） 76（1） 94（3） 95（3） 78（7） 82（3） 55（1） 98（5） 注：括号内的值为会员对该 DVD 喜好程度。 为使会员得到自己没有预定的 DVD 总数最少，可以将 DLij 中为 11 的数增大变为 1000，即将此偏爱程度降低，再如上求解得到一种新的分配方案 Ci,j，求得总偏爱度 U 为 8191(>7924)，但是经分析，只分配了 8 张 DVD 给没有要求预订这些 DVD 的会员。 事实上这里的 8 张 DVD 已经最小，具体原因是，现有 DVD 总数为 3007 张，每个人得 到 3 张 DVD，1000 个人就得到 3000 张 DVD，则还有 7 张未出租。根据所给的数据， 第 37 种 DVD 现有 106 张，只有 91 个会员愿意租此 DVD，即第 37 张 DVD 按照会员的 需求无论怎么发放，也会有 106-91=15 张剩余，而总共应该只有 7 张 DVD 未出租，这 样就无法满足所有的会员租到自己想看的 DVD，而且一定至少有 15-7=8 张 DVD 发给 了没有订这 8 张 DVD 的会员。 比较上面两种分配方案，我们选择第二种分配方案。第二种方案下，前 30 会员的 租赁情况是只有第 25 个会员的第 3 张 DVD 与第一种分配方案不同，其值为 81（4） 4.4 问题三模型的建立与求解 0，1 变量 每位会员租 3 张 DVD DVD 现有数量的限制