数学模型**。
组号：第十九组。
题目：剧场演出安排问题。
剧场安排问题。
摘要。本文围绕剧场演出安排问题进行分析，将剧场从1到11进行编号， 用0-1整数规划和途程建构法的最近邻点法进行计算与分析11个剧场演出安排行程。通过数据分析和筛选，给出最适宜演出团体个数，从而满足“演出团体而言，一旦加盟就希望演出较多的场次”的条件。
由最佳路径，制定出剧场演出长期安排方案。并分析所建立模型的优缺点，优化剧场演出安排模型。
针对问题（1），由题设条件可得到公司需支付费用与剧团收益的数学表达式，即为目标函数，采用0-1整数规划分析的思想，得到一系列约束条件。运用0-1整数规划得到合理的演出巡回路线，从而得到有效循环路径。由于公司所需承担剧团在不同城市巡回时所需的交通费用，交通费用与具体行程路线相关，从而可以得出公司长期以来所需支付的交通费用。
针对问题（2），首先搜索11个剧场所在九个地区相互之间的距离，优先考虑当地有两个剧场的地区，剩下只有一个剧场的地区，用旅行商问题中的途程建构法的最近邻点法得出最短路径：杭州 → 无锡 → 青岛 → 扬州 → 绍兴 → 东阳 → 温州 → 衢州 → 嘉兴 → 无锡 → 杭州。结合“使公司支付的费用尽可能少”，采用问题（1）的结论给出剧场6个月的演出安排方案。
针对问题（3），主要对问题（1）的安排模型的优缺点做了简单的分析，并添加了紧急应急方案，考虑某剧团因故不能完成剩余演出，某剧团的节目不适合在某城市演出，某剧场另有专项演出任务等情况下的剧场演出安排方案。
最后，结合模型分析的结果，对剧场安排问题提出了建议，并对模型作出了客观的评价。
关键词】 剧场演出安排 0-1整数规划最短路径
1、问题的重述与提出。
1.1已知情况。
某演出公司旗下有11家剧场，分别位于以下地点：
山东省青岛市、江苏省无锡市 2 家、江苏省扬州市、浙江省嘉兴市、
浙江省杭州市 2 家、浙江省温州市、浙江省绍兴市、浙江省东阳市、
浙江省衢州市。
公司需要组织若干演出团体于各剧场演出，每家剧场每天均需安排一场演出。为了保证上座率和演出效果，同一剧团每轮（指在同一家剧场连续不间断演出）演出时间有一上界。分别为：
青岛市：14 天；无锡市：各14 天；扬州市：7 天，嘉兴市：7 天；
杭州市：各 14 天；温州市：7 天；绍兴市：7 天；东阳市：7 天；
衢州市：7 天。
同一演出团体可以在不同剧场巡回演出，但不能在同一剧场多轮演出。同一演出团体在同城的两家剧场（杭州或无锡）演出的间隔（指自一家剧场演出结束至另一家剧场演出开始）不能小于45 天。
对加盟的演出团体，公司都需支付一笔固定费用；根据每个剧团演出场次的不同，还需支付该剧团相应的演出费用；另外公司还需承担剧团在不同城市巡回时所需的交通费用。其中前两项费用所占比例较大。对演出团体而言，一旦加盟就希望演出较多的场次，并且在不同剧场演出之间不能有太大的时间间隔，巡回路线也尽可能合理。
1.2 需解决的问题。
1．为公司制定一个这11 家剧场的演出团体长期安排方案，使公司支付的费用尽可能少，方案应切实可行、便于操作、有利管理、公司和剧团合作双赢。
2．准备一份给公司经理参阅的关于方案的简要说明（不超过两页），并附一份简明直观的前六个月的安排方案，作为公司和剧团执行的指南。
3．是否能将你的模型推广到一般情形。简述出现各种特殊情况时你的应急预案。如某剧团因故不能完成剩余演出，某剧团的节目不适合在某城市演出，某剧场另有专项演出任务等。
2、符号说明。
每天11家剧场总收入，常数；
每天11家剧场共需付给演出团体的演出费，常数；
公司需给加盟的演出团体的固定费用，常数；
公司需支付给每个演出团体的交通费，常数；
加盟的演出团体的个数；
同一演出团体在同城的两家剧场演出的间隔时间；
同一演出团体在同城的两家剧场演出至少需途经演出场数，向上取整数；
一轮巡回演出的总时间；
公司总支出；
公司总收益；
公司日收益；
公司总承担的交通费用；
同一剧团每轮演出时间上界较大值，向上取得整数；
同一剧团每轮演出时间上界较小值；向上取得整数；
取值从0到10，分别对应一家剧场；
3、基本假设。
1）假设每个剧团都能按行程安排方案时间，到达演出城市剧场完成演出，且所有剧团演出节目适宜在所有城市演出；
2） 假设每个剧场演出上座率及演出效果一致，不随连续演出时间改变，且都没有特殊的专项演出任务；
3）假设剧团在不同城市巡回时所需的交通费用与城市之间的距离成正比；
4）假设公司给每个剧团加盟费及每场演出费一致；
4、问题的分析。
4.1 问题（1）的分析。
该问题要求为公司制定一个11家剧场演出团体长期安排方案，使得公司支付尽可能少的费用。这个优化问题的目标是使交通费用最少，要做的决策是如何设定路线，决策受的约束条件：每个城市都必须去，但仅能去一次。
按题目所给，将决定变量，目标函数和约束条件用数学符号及式子表示出来，就可得一下模型了，题目给出了9个城市、11个剧场，以及公司需要支付费用的组成：每个加盟的演出团体的固定费用+每个剧团在11家剧场演出的演出费用+各个剧团在不同城市巡回时所需的交通费用。
采用0-1整数规划，对目标函数公司的支付费用进行最小规划。0-1整数规划是决策变量仅取值0或1的一类特殊的整数规划。在处理经济管理中某些规划问题时，若决策变量采用 0-1变量即逻辑变量，可把本来需要分别各种情况加以讨论的问题统一在一个问题中讨论。
4.2 问题（2）的分析。
通过问题（1）的分析得出的基本结论，我们将时间设定为半年六个月，将城市按剧场个数分类，如杭州、无锡为一类，东阳、嘉兴、青岛、衢州、绍兴、温州、扬州等城市为另一类，分开考虑两类城市的最优路径， 青岛 → 扬州 → 绍兴 → 东阳 → 温州 → 衢州 → 嘉兴，再将两类最优路径合并为一条固定巡回演出路线，即得演出团体前往各个城市的交通路线，从而可以了解公司需支付的交通费。
然后具体给出给公司经理参阅的关于方案的简要说明。详见附件。
4.3 问题（3）的分析。
本问题是要在（1）中建立模型的基础上对其的优缺点进行分析，扩展模型的适用范围，使模型更贴近事实，考虑其他情况下不能使用原（1）方案时，提出剧场演出应急方案。整理好一些突发信息后，可单独分析其对剧场演出安排的影响，进而将其添加到基础模型中，完成模型的分析。
5、模型建立与求解。
5.1 问题（1）的模型建立与求解。
1.根据题目要求，为给出11家剧场的演出安排方案，首先由盈亏情况可以分析，公司的收益等于公司的收入减去公司的支出，支出少有以下几种情况：
a) 公司收入水平不高，收入低于支出，此时按公司应考虑放弃演出计划！
b) 公司收入水平中等，收入与支出基本持平，公司不盈不亏，此时考虑公司所花时间与精力，也应放弃演出计划！
c) 公司收入水平较高，收入远大于支出，理想的公司经营方式。
由以上3种情况，我们着重考虑第三种情况！
从第三种情况着手，设定一轮演出的时间为，由于公司的收益与演出时间相关，且由假设（2）知，在不考虑交通费的情况下，11家剧场的日收益是一致的。那么要使公司收益越高，支付费用越少，相比于公司日收益，我们则采用公司总收益作为目标函数。而一轮演出的时间与加盟演出团体个数显然是有关的。
即，加盟演出团体个数越多，一轮演出安排的时间也就越长，日收益固定的情况下，总收益等于日收益与时间的乘积减去剧团交通费。即：
2.考虑制定一轮演出的时间以及加盟的演出团体的个数。
公司所支付的固定费用与加盟的演出团体的个数成正比，因此要使支付费用越少，则演出团体的个数也要越少；演出团体而言要求，一旦加盟就希望演出较多的场次，可考虑让每个演出团体均去往9地11家剧场演出；又同一演出团体可以在不同剧场巡回演出，但不能在同一剧场多轮演出每个演出，那么演出团体在每个剧场演出时尽可能的多演出可以使公司和剧团收益都达到最佳。因此假设每个剧团在每个城市演出时都达到该城市的演出时间上界，青岛，无锡，杭州三个城市5个剧场的演出时间上界是14天，其余的六个城市6个剧场的演出时间上界皆为7天，就假设剧团在青岛，无锡，杭州的演出时间是14天，在其余六个城市的演出时间均为7天。为简化分析，假设每个演出团体都能按时到达指定剧场完成演出任务。
由于每家剧场每天均需安排一场演出，一共11家剧场，每天就有11场演出。则一轮巡回演出时间内，一共需要演出：
青岛、杭州、无锡三地5家剧场在一轮时间内，来每个剧场演出的演出团体有：
一共演出。考虑每个演出团体尽可能去11家剧场，则个演出团体在东阳、嘉兴、青岛、衢州、绍兴、温州、扬州等城市的剧场演出。
个演出团体一共表演了，则还需要补充个演出团体，负责余下的，那么对于一轮巡回演出，需要。
加盟的演出团体负责演出任务。
且为了使每个加盟的演出团体获得的收入尽可能多，则可将11家剧场场演出任务平均安排给每个加盟的演出团体，从而可以到达公司与剧团的双赢。
3.考虑到使每个演出团体尽可能收益均达到最大，用平均法将场演出任务平均分配个各个演出团体，则每个演出团体可获得场演出，再平均分配给11家剧场，那么演出团体在每家剧场演出时间均为。又同一演出团体在同城的两家剧场（杭州或无锡）演出的间隔（指自一家剧场演出结束至另一家剧场演出开始）不能小于天。
对于同一演出团体同城的两家剧场至少需要经过场演出。
由每个演出团体演出固定路线可以算出公司应承担的交通费用，从而得到目标函数：
另给剧场编号，0-杭州①，1-杭州②，2-无锡①，3-无锡②，4-扬州，5-嘉兴，6-温州，7-绍兴，8-东阳，9-衢州，10-青岛。
又公司支付给加盟的演出团体的固定费用和每场演出的演出费为常数，演出团体个数与一轮巡回演出的时间有关，可简化目标函数为：
其中为的一个随机排列，为0-1变量，取值如下：
其满足的约束条件为：
用数学软件解出得到一组关于0—11的排列，即为巡回演出的路线：
4.按3.得出的路线对演出团体进行演出方案的安排：
表一。到为最佳路径，m为最大剧团数。
则有m-10个剧场可一次沿路径循环完毕，无间隔时间。
剧场演出安排问题
中南民族大学2010年数学建模竞赛。承诺书。我们仔细阅读了数学建模竞赛的竞赛规则。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料 包括网上查到的资料 必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正 公平...
体能测试时间安排模型
摘要。以动态规划为理论基础，根据问题的背景，建立了周期性循环模型。根据本文所给条件分析后，把测试项目分成两大模块，第一个测试模块为台阶测试，第二大模块为立定跳远 肺活量 握力和身高与体重的测试。如此设定测试方式之后，可知两大模块测试所需要的时间大致相同，因此我们设定 20人为一个大组，一个大组又分成...
数学建模铺路问题的最优化模型
铺路问题的最优化模型。摘要。本文采用了两种方法，一种是非线性规划从而得出最优解，另一种是将连续问题离散化利用计算机穷举取最优的方法。根据a地与b地之间的不同地质有不同造价的特点，建立了非线性规划模型和穷举取最优解的模型，解决了管线铺设路线花费最小的难题。问题一 在本问题中，我们首先利用非线性规划模型...