剧场安排模型.doc
《剧场安排模型.doc》由会员分享，可在线阅读，更多相关《剧场安排模型.doc（13页珍藏版）》请在冰点文库上搜索。
剧场演出安排问题
吕国录李欣欣刘永臻张振
摘要
本文对剧团演出的安排做出分析与求解。
考虑到公司与剧团的长期利益、方案的合理性、可操作性，利用显式整数规划模型（ GTSP），求得最优路线。
基于在半年的短期内，做出能够灵活变动的方案。
在变动尽可能小、公司与剧团利益尽量不受损失的前提下，将模型推广到一般情况来解决问题。
对于问题一，在公司与剧团双方共赢的前提下，根据各个城市之间的距离，运用显式整数规划模型模型（GTSP），利用lingo程序,求得一个演出的最优路线。
最优路线为：
青岛市→扬州市→杭州市→东阳市→衢州市→温州市→绍兴市→嘉兴市→无锡市。
然后基于所建立的多目标优化模型和剧场在各个城市的分布的特点，在以公司和剧团实现共赢的前提下：
得到公司应与26个剧团签订合同，并以7天为一轮的结论。
利用剧团两两组合的方法将13个组合剧团合理的安排在各个城市，最后按照演出循环最优路线制定合理的巡回演出方案。
对于问题二利用问题一中得出的结论，将时间控制在前六个月内，运用问题一中的方法为各个剧团建立了合理、可行的循环演出表。
对于问题三以方案变动尽量小，切实可行，公司与剧团双方利益损失尽量少为目的，将问题一中建立的多目标优化模型进行一般的推广，来应对突发状况。
关键词:
GTSP模型LINGO程序多目标优化共赢
一问题重述
某演出公司旗下有11家剧场，分别位于以下地点：
山东省青岛市、江苏省无锡市2家、江苏省扬州市、浙江省嘉兴市、
浙江省杭州市2家、浙江省温州市、浙江省绍兴市、浙江省东阳市、
浙江省衢州市。
公司需要组织若干演出团体于各剧场演出，每家剧场每天均需安排一场演出。
为了保证上座率和演出效果，同一剧团每轮（指在同一家剧场连续不间断演出）演出时间有一上界。
分别为：
青岛市：
14天；无锡市：
各14天；扬州市：
7天，嘉兴市：
7天；
杭州市：
各14天；温州市：
7天；绍兴市：
7天；东阳市：
7天；
衢州市：
7天。
同一演出团体可以在不同剧场巡回演出，但不能在同一剧场多轮演出。
同一演出团体在同城的两家剧场（杭州或无锡）演出的间隔（指自一家剧场演出结束至另一家剧场演出开始）不能小于45天。
对加盟的演出团体，公司都需支付一笔固定费用；根据每个剧团演出场次的不同，还需支付该剧团相应的演出费用；另外公司还需承担剧团在不同城市巡回时所需的交通费用。
其中前两项费用所占比例较大。
对演出团体而言，一旦加盟就希望演出较多的场次，并且在不同剧场演出之间不能有太大的时间间隔，巡回路线也尽可能合理。
1．试为公司制定一个这11家剧场的演出团体长期安排方案，使公司支付的费用尽可能少，方案应切实可行、便于操作、有利管理、公司和剧团合作双赢。
2．准备一份给公司经理参阅的关于方案的简要说明（不超过两页），并附一份简明直观的前六个月的安排方案，作为公司和剧团执行的指南。
3．是否能将你的模型推广到一般情形。
简述出现各种特殊情况时你的应急预案。
如某剧团因故不能完成剩余演出，某剧团的节目不适合在某城市演出，某剧场另有专项演出任务等。
二模型假设
1每个加盟团的演出效果及上座率相同；
2每个演出团的固定费用一样，每个演出团演一场的演出费用相同；
3每个演出团在一个地方演完后第二天就能到下一个地方演出;
4所有的剧团在所有的剧场都适合演出；
5每个剧团都能无意外按安排演出。
三符号说明
四问题分析
4.1问题一的分析
要制定一个安排方案，使公司支付的交通费用尽可能少，且方案必须切实可行、便于操作、有利管理、以实现公司和剧团合作双赢，则需要考虑最优化问题。
根据各个城市之间的距离，建立了旅行售货员（TSP）模型，运用lingo程序，求得一个演出的最优路线。
最优路线为：
青岛市→扬州市→杭州市→东阳市→衢州市→温州市→绍兴市→嘉兴市→无锡市。
然后基于所建立的多目标优化模型和剧场在各个城市的分布的特点，在为实现公司和剧团共赢的前提下，得到公司应与26个剧团签订合同，并以7天为一轮，利用剧团两两组合的方法将13个组合剧团合理的安排在各个城市，最后按照演出循环最优路线同步调进行巡回演出的可行方案
4.2问题二的分析
问题二中，将时间控制在前六个月内，故可以利用问题
（一）中得出的结论，将问题一中的问题短期化，根据问题
（一）中的方法建立了各个剧团循环演出表。
4.3问题三的分析
针对问题（三），将模型推广到一般情况。
考虑到公司与剧团的利益，以损失尽量少、调度灵活为原则，来解决紧急情况。
五模型的建立与求解
5.1．问题一模型的建立与求解
5.1.1模型的建立
对于问题一，为了使公司支付的费用尽可能少，达到公司和剧团合作双赢的目的且制定的方案切实可行、便于操作、有利管理，建立多目标优化模型。
考虑到公司在签订剧团时，为使公司的收入尽可能多支出尽可能的少，因此建立了关于公司利益的目标函数：
公司的最大利润：
（1）
对于已经加盟的剧团则希望得到合理的演出场次和路线，因此建立关于剧团的目标函数：
剧团的最大利润：
（2）
剧团的个数：
（3）
在安排演出公司旗下的剧场时，先根据剧场所在城市的具体位置，利用旅行售货员（TSP）模型，建立（4），借用数学软件（lingo）求解最优路线。
（4）
5.1.2模型的求解
通过Google搜索剧场所在的9个城市（图1）以及任意剧场所在城市的距离整理得到下列表格见（表1）
青岛
无锡
扬州
嘉兴
杭州
温州
绍兴
东阳
衢州
青岛
0
665
554
781
844
1207
909
1045
1050
无锡
665
0
165
131
220
551
253
391
449
扬州
554
165
0
280
300
660
360
443
552
嘉兴
781
131
280
0
88
422
121
255
316
杭州
844
220
300
88
0
367
64
150
258
温州
1207
551
660
422
367
0
317
307
287
绍兴
909
253
360
121
64
317
0
151
249
东阳
1045
391
443
255
150
307
151
0
155
衢州
1050
449
552
316
258
287
249
155
0
表1各个城市之间的距离
图1各个城市间的空间分布
图2各剧团演出的最优路线
通过运用lingo程序解得最优路线如图2所示，为：
青岛市→扬州市→杭州市→东阳市→衢州市→温州市→绍兴市→嘉兴市→无锡市
在以公司和剧团达到共赢的前提下，得到公司应与26个剧团签订合同，并以7天为一轮的方案。
考虑到某些城市有两个剧场（无锡、杭州），为了使循环演出切实可行、便于操作、有利管理，故规定两两剧团组合巡回演出。
当某个小组到达有2个剧场的城市（无锡和杭州）时，两个剧团各自在一个剧场演出。
当该小组到达只有一个剧场的城市时，让某一剧团演出，而另一剧团休息。
当到达下个只有一个剧场的城市时，让上一个没有演出的剧团演出，另一剧团休息。
5.2问题二的求解
对于问题二考虑有如下两点：
1.公司盈利多，每家剧场每天都安排一场演出;提出的方案需便于操作、有利管理、切实可行；
2.各剧团演出场次相同，具有较多的场次，并且在不同剧场演出之间不能有太大的时间间隔，巡回路线尽可能合理。
综合考虑以上2点得出如表2的各个剧团的循环演出表
剧场
时间
青岛
扬州
杭州
东阳
衢州
温州
绍兴
嘉兴
无锡
A
B
C
D
E
F
G
H
I
J
K
演出
休息
演出
休息
演出
演出
休息
演出
休息
演出
休息
演出
休息
演出
休息
演出
1-7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
8-14
19
20
21
22
23
24
25
26
2
1
4
3
5
6
8
7
9
10
15-21
12
11
14
13
15
16
17
18
20
19
22
21
23
24
26
25
1
2
22-28
3
4
6
5
7
8
10
9
11
12
13
14
16
15
18
17
19
20
29-35
21
22
24
23
25
26
1
2
4
3
5
6
7
8
9
10
12
11
36-42
14
13
15
16
17
18
19
20
22
21
23
24
25
26
2
1
3
4
43-49
6
5
8
7
10
9
12
11
13
14
16
15
17
18
20
19
21
22
50-56
24
23
26
25
1
2
3
4
5
6
7
8
10
9
11
12
14
13
57-63
15
16
18
17
19
20
21
22
23
24
25
26
1
2
4
3
6
5
64-70
8
7
9
10
12
11
14
13
16
15
17
18
19
20
22
21
24
23
71-77
26
25
2
1
3
4
6
5
7
8
10
9
12
11
13
14
15
16
78-84
18
17
20
19
21
22
24
23
25
26
1
2
3
4
5
6
7
8
85-91
9
10
11
12
14
13
15
16
17
18
19
20
21
22
23
24
26
25
92-98
2
1
4
3
6
5
8
7
10
9
12
11
14
13
16
15
18
17
99-105
20
19
22
21
24
23
26
25
1
2
3
4
6
5
7
8
10
9
106-112
11
12
13
14
16
15
18
17
19
20
21
22
24
23
25
26
2
1
113-119
4
3
5
6
8
7
9
10
12
11
14
13
15
16
17
18
20
19
120-126
22
21
23
24
26
25
2
1
3
4
6
5
8
7
10
9
11
12
127-133
13
14
16
15
18
17
20
19
21
22
24
23
26
25
1
2
4
3
134-140
5
6
7
8
9
10
11
12
14
13
15
16
18
17
19
20
22
21
141-147
23
24
25
26
2
1
4
3
6
5
8
7
9
10
12
11
13
14
148-154
16
15
17
18
20
19
22
21
24
23
26
25
2
1
3
4
5
6
155-161
7
8
10
9
11
12
13
14
15
16
18
17
20
19
21
22
23
24
162-168
25
26
1
2
4
3
5
6
8
7
9
10
11
12
14
13
16
15
169-175
17
18
19
20
22
21
23
24
26
25
2
1
4
3
6
5
8
7
176-181
10
9
12
11
13
14
16
15
18
17
20
19
22
21
24
23
25
26
表2各个剧团的循环演出表
5.3问题三的求解
若要将问题二的模型推广到一般情形，就要能够适应各种特殊情况，能够及时作出调整，且调度小，尽量减小公司的损失。
对于问题三提出的三种特殊情况做出以下方案：
1某剧团因故不能完成剩余演出，则安排距离该剧场最近的休息的剧团帮忙演出；
2.某剧团的节目不适合在某城市演出，则安排距离该剧场最近的休息的剧团帮忙演出；
3.某剧场另有专项演出任务，则安排原应在该剧场的剧团休息。
六：
模型的评价与推广
6.1模型的优点
1该模型结合实际情况，根据剧场具体的分布情况合理的采用剧团两两组合的方法，安排巡回演出方案。
。
2在确定签订剧团个数时，综合考虑建立的多目标多约束优化模型和剧场实际情况，使制定的方案贴切实际具有切实可行、便于操作、有利管理的特点，并满足公司与剧团共赢。
6.2模型的缺点
1在统计路线的里程时数据采集只通过网络查询，考虑的因素较少，存在误差。
2剧团巡回演完一个周期（两圈）再次回到演出过的剧场时，这样可能会影响演出效果，上座率存在偏差。
6.3模型的推广
建立整数数学规划的模型，将目标函数进行相应的确定型转化降之推广到灰色旅行售货员问题。
在现实生活中，汽车的调度问题可用到此模型。
七：
参考文献
[1]薛毅《数学建模基础》第二版科学出版社2011年
[2]刘来福，曾文艺《数学模型与建模》北京师范大学出版社2002年
[3]胡运权，郭耀煌《运筹学教程》第二版清华大学出版社2003年
[4]王茂芝、郭科、蚂蚁算法求解TSP问题的性能分析及改进【J】《成都理工大学报》自然科学版2009年.
八：
附录
利用LINGO求解到最优路线的运行程序和结果：
运行程序：
model:
sets:
city/1..9/:
u;
link（city,city）:
dist,x;
endsets
data:
dist=0665554781844120790910451050
6650165131220551253391449
5541650280300660360443552
781131280088422121255316
84422030088036764150258
12075516604223670317307287
909253360121643170151249
10453914432551503071510155
10504495523162582872491550;
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）+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
运行结果：
Globaloptimalsolutionfound.
Objectivevalue:
1493.000
Objectivebound:
1493.000
Infeasibilities:
0.000000
Extendedsolversteps:
0
Totalsolveriterations:
3
ModelClass:
MILP
Totalvariables:
89
Nonlinearvariables:
0
Integervariables:
81
Totalconstraints:
33
Nonlinearconstraints:
0
Totalnonzeros:
196
Nonlinearnonzeros:
0
VariableValueReducedCost
N9.0000000.000000
U
（1）0.0000000.000000
U
（2）1.0000000.000000
U（3）1.0000000.000000
U（4）1.0000000.000000
U（5）1.0000000.000000
U（6）1.0000000.000000
U（7）1.0000000.000000
U（8）1.0000000.000000
U（9）2.0000000.000000
DIST（1,1）0.0000000.000000
DIST（1,2）665.00000.000000
DIST（1,3）554.00000.000000
DIST（1,4）781.00000.000000
DIST（1,5）844.00000.000000
DIST（1,6）1207.0000.000000
DIST（1,7）909.00000.000000
DIST（1,8）1045.0000.000000
DIST（1,9）1050.0000.000000
DIST（2,1）665.00000.000000
DIST（2,2）0.0000000.000000
DIST（2,3）165.00000.000000
DIST（2,4）131.00000.000000
DIST（2,5）220.00000.000000
DIST（2,6）551.00000.000000
DIST（2,7）253.00000.000000
DIST（2,8）391.00000.000000
升级会员 