北航最优化大作业.docx
- 文档编号:18364694
- 上传时间:2023-08-16
- 格式:DOCX
- 页数:10
- 大小:38.62KB
北航最优化大作业.docx
《北航最优化大作业.docx》由会员分享,可在线阅读,更多相关《北航最优化大作业.docx(10页珍藏版)》请在冰点文库上搜索。
北航最优化大作业
非线性规划与0-1规划在DVD分配问题中的应用
北京航空航天大学数学与系统科学学院
张博学学号:
********
Email:
***********************
【摘要】
大一的时候我曾经想要参加数学建模的比赛,在参考书中遇到了这个问题,当时由于知识非常匮乏,我放弃了这个问题,同时也放弃了参加数学建模比赛。
现在再来看这个问题,我觉得我有能力也有信心可以通过自己的最优化的知识解决这个问题。
本文通过对DVD租赁问题的分析,运用最优化理论方法中的0-1规划和非线性规划的方法特点,结合Lingo优化软件以及MATLAB,对“会员获得最大满意度”问题进行了最优化的计算,对最优化理论中的0-1规划和整数规划有了更深刻的学习和认识。
【关键词】0-1规划非线性规划满意度
1、DVD租赁问题
随着信息时代的到来,DVD在线租赁已是一种可行的服务。
在线DVD租赁问题中,顾客交纳一定数量的月费就可以成为会员,可得到DVD租赁服务。
在该问题中,通过市场需求来确定网站DVD的购买量以及如何分配这些DVD。
会员在线提交的订单包括多张DVD,这些DVD是基于偏爱程度排序的。
网站会根据手里现有的DVD数量和会员的订单进行分发。
每个会员每个月租赁次数不得超过两次,每次获得3张DVD。
会员看完三张DVD后,将DVD寄回,方可继续下次租赁。
问题:
根据网站DVD现存量及会员在线订单,确定最佳分配方案,使会员获得最大满意度,并列举出会员C001~C030的分配量。
DVD编号
D001
D002
D003
D004
…
DVD现有数量
10
40
15
20
…
会员在线订单
C0001
6
0
0
0
…
C0002
0
0
0
0
…
C0003
0
0
0
3
…
C0004
0
0
0
0
…
…
…
…
…
…
…
2、DVD租赁问题优化建模
为了表述方便,下面给出一些集合、变量、参数的定义说明及基本假设
符号说明
——第j种DVD的现有数量
——第i个会员对第j张DVD的偏爱程度
——第i个会员获得第j张DVD的满意度
n——在线会员人数
T——租赁周期
Y——所有会员的满意度
=
——0-1变量
基本假设
1、会员入会后不考虑退出情况;
2、邮寄过程中不会出现DVD意外丢失、损坏或不能到达目的地的情况;
3、会员租赁DVD有一定的循环周期T,在周期T内会员及时看完DVD并将其寄回网站
4、网站中每位会员每月都会向网站提交一次或两次订单,每次获得3张DVD;
5、会员将上次所租赁的碟片还回网站后,方可继续下次租赁;
问题分析:
该问题是在一定约束条件下的最优化问题。
现有100位会员已向网站提交了订单,其中每位会员对各种DVD的偏爱程度都有所差异,同时又由于DVD的现有数量有限,无法满足每位会员都看到他们所偏爱的DVD种类。
因此,为了兼顾会员和网站双方的利益,应以满足会员的主观意愿为主,使会员得到最大的满意度,从而形成稳定的消费群体。
综上,该问题归结为:
网站尽量根据每位会员对各种DVD的不同偏爱度,找到一种最佳的分配方案。
网站越能满足会员的偏爱,会员满意度就会越大,即会员的满意度与偏爱度成正比。
又有偏爱值越小表示会员的偏爱程度越高,故会员的满意度
应与偏爱值
成反比,即可用如下关系式表示:
由前面的分析已经知道,此分配问题为一个多约束条件下的最优化问题。
若确定了各种DVD的最佳分配,也就解决了所有会员的最大满意度问题,则建立如下的非线性规划与0-1规划相结合的模型:
MaximizeY=
(1)
Subjectto
(2)
=n
60%
2
3+n
40%
3(3)
(4)
>0(5)
=0或1(6)
其中,n=100人,T=15天,i=1,2,…,100,j=1,2,…,20。
目标函数及约束条件的分析:
(1)式:
目标函数为会员获得最大满意度。
(2)式:
每月租赁次数约束,本问题中,每个会员每月租赁次数不得超过2次,每次获得3张DVD,则会员只可能租到3张或6张DVD。
(3)式:
DVD总流动张数的约束。
(4)式:
获得某种DVD的总会员数要受该DVD在某段时间内可供租出的次数的约束。
(5)式:
只需考虑在线订单中会员的偏爱程度,这可是计算过程中时间复杂度和空间复杂度大大降低。
(6)式:
的取值服从0-1规划,即
只能等于0或1。
问题简化后得到:
MaximizeY=
(7)
Subjectto
(8)
3
(9)
,
=0或1(10)
目标函数及约束条件的分析:
(7)式:
目标函数为会员获得最大满意度。
(8)式:
获得某种DVD的总会员数要受该DVD在某段时间内可供租出的次数的约束。
(9)式:
对于x矩阵每一行的求和为0或3
(10)式:
x,y均为0-1变量
3、求解最优化问题
基本lingo代码如下:
Model:
Sets:
MAN/1..1000/:
y;
DVD/1..100/:
b;
MY(MAN,DVD):
x,c;
Endsets
Max=@sum(MY:
c*x);
@for(DVD(j):
@sum(MAN(i):
x(I,j))<=b(j));
@for(MAN(i):
@sum(DVD(j):
x(i,j))<=3*y(i));
@for(MAN(i):
@bin(y(i)));
@for(MY:
@bin(x));
Data:
C=[8,1,22,10,8,40,40,1,8,15,19,20,10,2,5,8,30,10,8,38]
基本MATLAB代码如下:
data3=zeros(100,20);
n=1;
num=zeros(1,20);
people=zeros(100,1);
fori=1:
9;
fork=1:
20
form=1:
100;
ifdata2(m,k)==i%data2为偏爱度矩阵
ifnum(1,k) data3(m,k)=1 num(1,k)=num(1,k)+1 end end end end 第二种MATLAB的算法 第一步: 碟片1对于满意度为1的会员优先考虑分发,如果不能满足全部,则优先满足排在前面的会员。 第二步: 从一个会员开始,依次检查每人获得的碟片数量。 如果已经得到3张或者一张也没得到,则不变。 如果获得的数量大于0而小于3,对该会员进行第二次分配。 分配时首先按照该会员的意愿,然后对照碟片的已有数量,使得该会员得到三张碟片。 data4=zeros(100,20); data5=zeros(1,20); fori=1: 3; form=1: 100; forn=1: 20; ifdata2(m,n)==i data4(m,n)=1; end end end end fornn=1: 20; formm=1: 100; data5(1,nn)=data4(mm,nn)+data5(1,nn); end end 解出最大满意度为: 151.2444。 解出结果为: 会员编号 分配DVD编号 C001 D003 D017 D020 C002 D001 D006 D012 C003 D013 D017 D020 C004 D007 D012 D017 C005 D006 D007 D019 C006 D006 D012 D015 C007 D007 D011 D020 C008 D012 D013 D014 C009 D003 D007 D015 C010 D010 D012 D017 C011 Null Null Null C012 D007 D011 D019 C013 D006 D019 D020 C014 D006 D016 D017 C015 D007 D017 D020 C016 D007 D011 D017 C017 D004 D007 D017 C018 D007 D018 D020 C019 D006 D011 D017 C020 D006 D009 D020 C021 D006 D013 D015 C022 D003 D007 D011 C023 D011 D012 D013 C024 D007 D011 D017 C025 D010 D016 D017 C026 D003 D006 D016 C027 D006 D007 D010 C028 D005 D007 D009 C029 D012 D013 D020 C030 D003 D011 D017 4、结果分析 结果在理论上令人满意,但是在DVD分发过程中,由于模型要求的是考虑会员整体满意度的最大化,因此,在分发过程中,部分会员有可能在短期内得不到想要的DVD,只能在下次的配发过程中再将他所要的DVD配发给这些会员。 5、反思和感想 在一开始的时候我本来是想用二分图的匹配方法即匈牙利算法,这种优化算法在计算机竞赛中经常用到,但是尽管匈牙利算法可以解决二分图的匹配问题,对于这种对选择有“期望值”的问题我却一时想不出如何运用匈牙利算法,因为匈牙利算法只能求出匹配“对儿数”的最大值,而现在的问题当中不单单是求“对儿数”的最大值或者说不是求“对儿数”最大值,而是求每一对上的“期望值”之和的最大值。 在学习了很多资料,也借鉴了很多前辈的算法后,我选择了用最简洁的非线性方程优化问题算法来解决这个问题,在尝试了很多种方法后有种豁然开朗的感觉。 完成这次试验,让我对一般问题的数学抽象以及优化软件的使用都有了极大的提高,给了我一次将知识运用于实践的机会,虽然我在这个过程中犯了很多很多的错误,但我觉得这些经历都是我宝贵的财富,让我以后解决实际问题时可以少犯错误。 参考文献 【1】韩中庚.数学建模方法及其应用.北京: 高等教育出版社,2005 【2】钱颂迪.运筹学(修订版).北京: 清华大学出版社,2003 【3】雷功炎.数学模型讲义.北京: 北京大学出版社,2000
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北航 优化 作业