剧场安排模型

《剧场安排模型》由会员分享，可在线阅读，更多相关《剧场安排模型（13页珍藏版）》请在装配图网上搜索。

1、剧场演出安排问题吕国录 李欣欣 刘永臻 张振摘要本文对剧团演出的安排做出分析与求解。考虑到公司与剧团的长期利益、方案的合理性、可操作性，利用显式整数规划模型（GTSP），求得最优路线。基于在半年的短期内，做出能够灵活变动的方案。在变动尽可能小、公司与剧团利益尽量不受损失的前提下，将模型推广到一般情况来解决问题。对于问题一，在公司与剧团双方共赢的前提下，根据各个城市之间的距离，运用显式整数规划模型模型（GTSP），利用lingo程序,求得一个演出的最优路线。最优路线为：青岛市扬州市杭州市东阳市衢州市温州市绍兴市嘉兴市无锡市。然后基于所建立的多目标优化模型和剧场在各个城市的分布的特点，在以公司和剧

2、团实现共赢的前提下：得到公司应与26个剧团签订合同，并以7天为一轮的结论。利用剧团两两组合的方法将13个组合剧团合理的安排在各个城市，最后按照演出循环最优路线制定合理的巡回演出方案。对于问题二利用问题一中得出的结论，将时间控制在前六个月内，运用问题一中的方法为各个剧团建立了合理、可行的循环演出表。对于问题三以方案变动尽量小，切实可行，公司与剧团双方利益损失尽量少为目的，将问题一中建立的多目标优化模型进行一般的推广，来应对突发状况。关键词: GTSP模型 LINGO程序 多目标优化 共赢一 问题重述某演出公司旗下有 11 家剧场，分别位于以下地点： 山东省青岛市、江苏省无锡市2 家、江苏省扬州市

3、、浙江省嘉兴市、 浙江省杭州市2 家、浙江省温州市、浙江省绍兴市、浙江省东阳市、 浙江省衢州市。 公司需要组织若干演出团体于各剧场演出，每家剧场每天均需安排一场演出。为了保证上座率和演出效果，同一剧团每轮（指在同一家剧场连续不间断演出）演出时间有一上界。分别为： 青岛市：14 天；无锡市：各 14 天；扬州市：7 天，嘉兴市：7 天； 杭州市：各 14 天；温州市：7 天；绍兴市：7 天；东阳市：7 天； 衢州市：7 天。 同一演出团体可以在不同剧场巡回演出，但不能在同一剧场多轮演出。同一演出团体在同城的两家剧场（杭州或无锡）演出的间隔（指自一家剧场演出结束至另一家剧场演出开始）不能小于45

4、天。 对加盟的演出团体，公司都需支付一笔固定费用；根据每个剧团演出场次的不同，还需支付该剧团相应的演出费用；另外公司还需承担剧团在不同城市巡回时所需的交通费用。其中前两项费用所占比例较大。对演出团体而言，一旦加盟就希望演出较多的场次，并且在不同剧场演出之间不能有太大的时间间隔，巡回路线也尽可能合理。1试为公司制定一个这 11 家剧场的演出团体长期安排方案，使公司支付的费用尽可能少，方案应切实可行、便于操作、有利管理、公司和剧团合作双赢。2准备一份给公司经理参阅的关于方案的简要说明（不超过两页），并附一份简明直观的前六个月的安排方案，作为公司和剧团执行的指南。 3是否能将你的模型推广到一般情形。

5、简述出现各种特殊情况时你的应急预案。如某剧团因故不能完成剩余演出，某剧团的节目不适合在某城市演出，某剧场另有专项演出任务等。二 模型假设1 每个加盟团的演出效果及上座率相同；2 每个演出团的固定费用一样，每个演出团演一场的演出费用相同；3 每个演出团在一个地方演完后第二天就能到下一个地方演出;4 所有的剧团在所有的剧场都适合演出；5 每个剧团都能无意外按安排演出。 三 符号说明四 问题分析4.1 问题一的分析要制定一个安排方案，使公司支付的交通费用尽可能少，且方案必须切实可行、便于操作、有利管理、以实现公司和剧团合作双赢，则需要考虑最优化问题。根据各个城市之间的距离，建立了旅行售货员（TSP）

6、模型，运用lingo程序，求得一个演出的最优路线。最优路线为：青岛市扬州市杭州市东阳市衢州市温州市绍兴市嘉兴市无锡市。然后基于所建立的多目标优化模型和剧场在各个城市的分布的特点，在为实现公司和剧团共赢的前提下，得到公司应与26个剧团签订合同，并以7天为一轮，利用剧团两两组合的方法将13个组合剧团合理的安排在各个城市，最后按照演出循环最优路线同步调进行巡回演出的可行方案4.2问题二的分析问题二中，将时间控制在前六个月内，故可以利用问题（一）中得出的结论，将问题一中的问题短期化，根据问题（一）中的方法建立了各个剧团循环演出表。4.3问题三的分析针对问题（三），将模型推广到一般情况。考虑到公司与剧团

7、的利益，以损失尽量少、调度灵活为原则，来解决紧急情况。五 模型的建立与求解5.1问题一模型的建立与求解 5.1.1模型的建立对于问题一，为了使公司支付的费用尽可能少，达到公司和剧团合作双赢的目的且制定的方案切实可行、便于操作、有利管理，建立多目标优化模型。考虑到公司在签订剧团时，为使公司的收入尽可能多支出尽可能的少，因此建立了关于公司利益的目标函数：公司的最大利润： （1）对于已经加盟的剧团则希望得到合理的演出场次和路线，因此建立关于剧团的目标函数：剧团的最大利润： （2）剧团的个数： （3）在安排演出公司旗下的剧场时，先根据剧场所在城市的具体位置，利用旅行售货员(TSP)模型，建立（4），借

8、用数学软件（lingo）求解最优路线。 （4）5.1.2 模型的求解通过Google搜索剧场所在的9个城市（图1）以及任意剧场所在城市的距离整理得到下列表格见（表1）青岛无锡扬州嘉兴杭州温州绍兴东阳衢州青岛0665554781844120790910451050无锡6650165131220551253391449扬州5541650280300660360443552嘉兴781131280088422121255316杭州84422030088036764150258温州12075516604223670317307287绍兴909253360121643170151249东阳10453914

9、432551503071510155衢州10504495523162582872491550表1各个城市之间的距离图1各个城市间的空间分布图2各剧团演出的最优路线通过运用lingo程序解得最优路线如图2所示，为：青岛市扬州市杭州市东阳市衢州市温州市绍兴市嘉兴市无锡市在以公司和剧团达到共赢的前提下，得到公司应与26个剧团签订合同，并以7天为一轮的方案。考虑到某些城市有两个剧场（无锡、杭州），为了使循环演出切实可行、便于操作、有利管理，故规定两两剧团组合巡回演出。当某个小组到达有2个剧场的城市（无锡和杭州）时，两个剧团各自在一个剧场演出。当该小组到达只有一个剧场的城市时，让某一剧团演出，而另一剧团

10、休息。当到达下个只有一个剧场的城市时，让上一个没有演出的剧团演出，另一剧团休息。5.2 问题二的求解对于问题二考虑有如下两点：1. 公司盈利多，每家剧场每天都安排一场演出;提出的方案需便于操作、有利管理、切实可行；2. 各剧团演出场次相同，具有较多的场次，并且在不同剧场演出之间不能有太大的时间间隔，巡回路线尽可能合理。综合考虑以上2点得出如表2的各个剧团的循环演出表剧场时间青岛扬州杭州东阳衢州温州绍兴嘉兴无锡ABCDEFGHIJK演出休息演出休息演出演出休息演出休息演出休息演出休息演出休息演出1-71234567891011121314151617188-1419202122232425262

11、143568791015-21121114131516171820192221232426251222-283465781091112131416151817192029-3521222423252612435678910121136-421413151617181920222123242526213443-49658710912111314161517182019212250-5624232625123456781091112141357-6315161817192021222324252612436564-7087910121114131615171819202221242371-7726

12、252134657810912111314151678-84181720192122242325261234567885-919101112141315161718192021222324262592-9821436587109121114131615181799-105201922212423262512346578109106-1121112131416151817192021222423252621113-11943568791012111413151617182019120-126222123242625213465871091112127-1331314161518172019212

13、2242326251243134-1405678910111214131516181719202221141-147232425262143658791012111314148-154161517182019222124232625213456155-161781091112131415161817201921222324162-168252612435687910111214131615169-1751718192022212324262521436587176-18110912111314161518172019222124232526表2各个剧团的循环演出表5.3 问题三的求解若要将问题

14、二的模型推广到一般情形，就要能够适应各种特殊情况，能够及时作出调整，且调度小，尽量减小公司的损失。对于问题三提出的三种特殊情况做出以下方案：1 某剧团因故不能完成剩余演出，则安排距离该剧场最近的休息的剧团帮忙演出；2. 某剧团的节目不适合在某城市演出，则安排距离该剧场最近的休息的剧团帮忙演出；3. 某剧场另有专项演出任务，则安排原应在该剧场的剧团休息。六：模型的评价与推广6.1模型的优点1 该模型结合实际情况，根据剧场具体的分布情况合理的采用剧团两两组合的方法，安排巡回演出方案。2在确定签订剧团个数时，综合考虑建立的多目标多约束优化模型和剧场实际情况，使制定的方案贴切实际具有切实可行、便于操作

15、、有利管理的特点，并满足公司与剧团共赢。6.2 模型的缺点1 在统计路线的里程时数据采集只通过网络查询，考虑的因素较少，存在误差。 2 剧团巡回演完一个周期（两圈）再次回到演出过的剧场时，这样可能会影响演出效果，上座率存在偏差。6.3 模型的推广建立整数数学规划的模型，将目标函数进行相应的确定型转化降之推广到灰色旅行售货员问题。在现实生活中，汽车的调度问题可用到此模型。七：参考文献1 薛毅 数学建模基础 第二版 科学出版社 2011年 2 刘来福， 曾文艺 数学模型与建模 北京师范大学出版社 2002年3 胡运权， 郭耀煌运筹学教程 第二版 清华大学出版社 2003年4 王茂芝、郭科、蚂蚁算法

16、求解TSP问题的性能分析及改进【J】 成都理工大学报自然科学版 2009年.八：附录利用LINGO求解到最优路线的运行程序和结果：运行程序：model: sets: city/1.9/:u; link(city,city): dist, x; endsets data: dist= 0 665 554 781 844 1207 909 1045 1050665 0 165 131 220 551 253 391 449554 165 0 280 300 660 360 443 552781 131 280 0 88 422 121 255 316844 220 300 88 0 367 64

17、150 2581207 551 660 422 367 0 317 307 287909 253 360 121 64 317 0 151 2491045 391 443 255 150 307 151 0 1551050 449 552 316 258 287 249 155 0;enddata min=sum(link:dist*x); n=size(city);u(1)=0; for(link: bin(x); for(city(k)|k#gt#1:sum(city(i)|i#ne#k:x(i,k)=1); for(city(k)|k#gt#1#and#k#ne#9:u(9)=u(k)+

18、x(k,9)-(n-2)*(1-x(k,9)+(n-3)*x(9,k);sum(city(j)|j#gt#1:x(1,j)=1; for(city(k)|k#gt#1:u(k)=1);for(city(k)|k#gt#1:u(k)=n-1-(n-2)*x(1,k); end运行结果：Global optimal solution found. Objective value: 1493.000 Objective bound: 1493.000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations:

19、 3 Model Class: MILP Total variables: 89 Nonlinear variables: 0 Integer variables: 81 Total constraints: 33 Nonlinear constraints: 0 Total nonzeros: 196 Nonlinear nonzeros: 0 Variable Value Reduced Cost N 9.000000 0.000000 U( 1) 0.000000 0.000000 U( 2) 1.000000 0.000000 U( 3) 1.000000 0.000000 U( 4)

20、 1.000000 0.000000 U( 5) 1.000000 0.000000 U( 6) 1.000000 0.000000 U( 7) 1.000000 0.000000 U( 8) 1.000000 0.000000 U( 9) 2.000000 0.000000 DIST( 1, 1) 0.000000 0.000000 DIST( 1, 2) 665.0000 0.000000 DIST( 1, 3) 554.0000 0.000000 DIST( 1, 4) 781.0000 0.000000 DIST( 1, 5) 844.0000 0.000000 DIST( 1, 6)

21、 1207.000 0.000000 DIST( 1, 7) 909.0000 0.000000 DIST( 1, 8) 1045.000 0.000000 DIST( 1, 9) 1050.000 0.000000 DIST( 2, 1) 665.0000 0.000000 DIST( 2, 2) 0.000000 0.000000 DIST( 2, 3) 165.0000 0.000000 DIST( 2, 4) 131.0000 0.000000 DIST( 2, 5) 220.0000 0.000000 DIST( 2, 6) 551.0000 0.000000 DIST( 2, 7)

22、 253.0000 0.000000 DIST( 2, 8) 391.0000 0.000000 DIST( 2, 9) 449.0000 0.000000 DIST( 3, 1) 554.0000 0.000000 DIST( 3, 2) 165.0000 0.000000 DIST( 3, 3) 0.000000 0.000000 DIST( 3, 4) 280.0000 0.000000 DIST( 3, 5) 300.0000 0.000000 DIST( 3, 6) 660.0000 0.000000 DIST( 3, 7) 360.0000 0.000000 DIST( 3, 8)

23、 443.0000 0.000000 DIST( 3, 9) 552.0000 0.000000 DIST( 4, 1) 781.0000 0.000000 DIST( 4, 2) 131.0000 0.000000 DIST( 4, 3) 280.0000 0.000000 DIST( 4, 4) 0.000000 0.000000 DIST( 4, 5) 88.00000 0.000000 DIST( 4, 6) 422.0000 0.000000 DIST( 4, 7) 121.0000 0.000000 DIST( 4, 8) 255.0000 0.000000 DIST( 4, 9)

24、 316.0000 0.000000 DIST( 5, 1) 844.0000 0.000000 DIST( 5, 2) 220.0000 0.000000 DIST( 5, 3) 300.0000 0.000000 DIST( 5, 4) 88.00000 0.000000 DIST( 5, 5) 0.000000 0.000000 DIST( 5, 6) 367.0000 0.000000 DIST( 5, 7) 64.00000 0.000000 DIST( 5, 8) 150.0000 0.000000 DIST( 5, 9) 258.0000 0.000000 DIST( 6, 1)

25、 1207.000 0.000000 DIST( 6, 2) 551.0000 0.000000 DIST( 6, 3) 660.0000 0.000000 DIST( 6, 4) 422.0000 0.000000 DIST( 6, 5) 367.0000 0.000000 DIST( 6, 6) 0.000000 0.000000 DIST( 6, 7) 317.0000 0.000000 DIST( 6, 8) 307.0000 0.000000 DIST( 6, 9) 287.0000 0.000000 DIST( 7, 1) 909.0000 0.000000 DIST( 7, 2)

26、 253.0000 0.000000 DIST( 7, 3) 360.0000 0.000000 DIST( 7, 4) 121.0000 0.000000 DIST( 7, 5) 64.00000 0.000000 DIST( 7, 6) 317.0000 0.000000 DIST( 7, 7) 0.000000 0.000000 DIST( 7, 8) 151.0000 0.000000 DIST( 7, 9) 249.0000 0.000000 DIST( 8, 1) 1045.000 0.000000 DIST( 8, 2) 391.0000 0.000000 DIST( 8, 3)

27、 443.0000 0.000000 DIST( 8, 4) 255.0000 0.000000 DIST( 8, 5) 150.0000 0.000000 DIST( 8, 6) 307.0000 0.000000 DIST( 8, 7) 151.0000 0.000000 DIST( 8, 8) 0.000000 0.000000 DIST( 8, 9) 155.0000 0.000000 DIST( 9, 1) 1050.000 0.000000 DIST( 9, 2) 449.0000 0.000000 DIST( 9, 3) 552.0000 0.000000 DIST( 9, 4)

28、 316.0000 0.000000 DIST( 9, 5) 258.0000 0.000000 DIST( 9, 6) 287.0000 0.000000 DIST( 9, 7) 249.0000 0.000000 DIST( 9, 8) 155.0000 0.000000 DIST( 9, 9) 0.000000 0.000000 X( 1, 1) 0.000000 0.000000 X( 1, 2) 0.000000 665.0000 X( 1, 3) 1.000000 554.0000 X( 1, 4) 0.000000 781.0000 X( 1, 5) 0.000000 844.0

29、000 X( 1, 6) 0.000000 1207.000 X( 1, 7) 0.000000 909.0000 X( 1, 8) 0.000000 1045.000 X( 1, 9) 0.000000 1050.000 X( 2, 1) 0.000000 665.0000 X( 2, 2) 0.000000 0.000000 X( 2, 3) 0.000000 165.0000 X( 2, 4) 0.000000 131.0000 X( 2, 5) 0.000000 220.0000 X( 2, 6) 0.000000 551.0000 X( 2, 7) 0.000000 253.0000

30、 X( 2, 8) 0.000000 391.0000 X( 2, 9) 0.000000 449.0000 X( 3, 1) 0.000000 554.0000 X( 3, 2) 0.000000 165.0000 X( 3, 3) 0.000000 0.000000 X( 3, 4) 0.000000 280.0000 X( 3, 5) 0.000000 300.0000 X( 3, 6) 0.000000 660.0000 X( 3, 7) 0.000000 360.0000 X( 3, 8) 0.000000 443.0000 X( 3, 9) 0.000000 552.0000 X(

31、 4, 1) 0.000000 781.0000 X( 4, 2) 1.000000 131.0000 X( 4, 3) 0.000000 280.0000 X( 4, 4) 0.000000 0.000000 X( 4, 5) 0.000000 88.00000 X( 4, 6) 0.000000 422.0000 X( 4, 7) 0.000000 121.0000 X( 4, 8) 0.000000 255.0000 X( 4, 9) 0.000000 316.0000 X( 5, 1) 0.000000 844.0000 X( 5, 2) 0.000000 220.0000 X( 5,

32、 3) 0.000000 300.0000 X( 5, 4) 1.000000 88.00000 X( 5, 5) 0.000000 0.000000 X( 5, 6) 0.000000 367.0000 X( 5, 7) 1.000000 64.00000 X( 5, 8) 1.000000 150.0000 X( 5, 9) 0.000000 258.0000 X( 6, 1) 0.000000 1207.000 X( 6, 2) 0.000000 551.0000 X( 6, 3) 0.000000 660.0000 X( 6, 4) 0.000000 422.0000 X( 6, 5)

33、 0.000000 367.0000 X( 6, 6) 0.000000 0.000000 X( 6, 7) 0.000000 317.0000 X( 6, 8) 0.000000 307.0000 X( 6, 9) 0.000000 287.0000 X( 7, 1) 0.000000 909.0000 X( 7, 2) 0.000000 253.0000 X( 7, 3) 0.000000 360.0000 X( 7, 4) 0.000000 121.0000 X( 7, 5) 1.000000 64.00000 X( 7, 6) 0.000000 317.0000 X( 7, 7) 0.000000 0.000000 X( 7, 8) 0.000000 151.0000 X( 7, 9) 0.000000 249.0000 X( 8, 1) 0.000000 1045.000 X( 8,