英语原文共 22 页，剩余内容已隐藏，支付完成后下载完整资料
社会划分问题的数学模型
瓦尔奇斯·梅尔科尼安
俄亥俄州大学数学系，美国
摘要
本文针对社会划分问题开发建模技术。流行病期间实行不同的社会互动条例，以防止疾病的传播。我们建议划分一组公司员工作为一种遏制传播的有效方法，并使用整数规划技术来建模。该模型的目标是最大限度地增加对公司工作至关重要的员工之间的直接互动次数，从而形成一种约束，即所有员工都应被划分为不超过法规所暗示的一定大小的组件。然后，我们进一步发展基本模型，以考虑到不同的限制和规定。我们还为解决问题提供启发性意见。我们的计算结果包括对一些模型和启发式性能分析的灵敏度分析。
关键字
医疗保健操作研究、流行病数学模型、图形分割、整数线性规划、启发式算法
1.介绍
背景和问题陈述
为了抗击Covid-19流行病，许多国家和州采取了限制社交聚会的措施。许多限制限制了允许参加集会的人数。例如，德国和英国在某些时候限制超过2人的社交聚会[1]，而在美国许多州，这个数字是10[2]。 虽然这类限制可能有助于防止疾病的传播，但它们有以下缺点。生病但无症状的人可以参加不超过10人的几次会议（每次会议有不同的人）。这些会议的人可能会携带病毒并参加其他不超过10人的会议。它可能会产生连锁反应，从而导致许多人被感染。
在本文中，我们提出了一种限制相互作用的替代方法以防止疾病传播。它解释在规范中小型公司的互动的例子，因为我们的方法最适合这类组织。
考虑一个公司拥有 N 名员工，他们应该在公司的日常运作中彼此直接互动。每一次直接互动都有可能将一种疾病从一个人传染给另一个人。为了遏制疾病的传播，我们建议将 N员工分成最多 M 人的较小群体。（编号M 可以根据州或公司法规确定）。员工只能与同一较小群体的人进行直接互动。在这种情况下，在同一组中，患有此病的人最多可能感染 M minus; 1 人。因此，连锁反应的影响是有限的。
N个员工的集合可以以许多不同的方式被划分为最多 M人的较小群体。划分的最佳方式是什么？虽然限制疾病在流行病期间的传播是首要目标，但另一个重要目标是保持尽可能多的经济活动。经济活动可以通过不中断公司内部重要的员工互动来促进。就我们的问题而言，目标如下：找到最多 M 人的分组，最大限度地增加不间断的员工互动次数。
相应的离散优化问题如下。我们有一个图形G，含有N个节点（员工）。目标是尽可能少地删除弧线（员工交互），以便将图形分割成最多 M 节点的连接组件。换句话说，图中保留的弧数应该最大化。
图1 中给出了一个N=11 名员工和 M = 4 最大组件大小示例。十条粗弧构成了示例的最佳解决方案。最佳解决方案中的组件为 {1, 2, 3, 4}, {5, 7, 8}, {6, 9, 10, 11}。
对公司来说，一些员工互动比其他员工更重要。因此，给弧分配权重是有意义的，将更高的权重分配给更重要的弧线。然后，目标是最大限度地提高解决方案中包含的弧线的总权重。
求解方法
我们给出了求解此问题的整数线性规划模型。该模型的主要特征是提供两个节点（员工）位于同一组件的一组约束条件。我们提供几种技术使模型的计算效率更高。这些技术包括减少变量的数量和放宽最大变量集的集成性要求 。我们还给出了解决问题的启发式方法来解决问题。启发式输出也可以作为整数规划模型的初始解决办法，以加速解决方案进程。
图一 社会划分问题的一个例子
主模型的变化
虽然社会划分问题的主要要求是不超过最大组成部分的大小，但在现实生活中，可能有其他限制和规定应予以考虑。例如，有些员工可能被要求在公司中直接互动;一些为公司从事同样重要任务的专家可能需要在不同的部门中工作;有时，如果对公司的工作非常重要，则可能会违反最大部门规模，但在这种情况下，对违规行为将处以处罚。我们提供主要整数规划模型的变化，以考虑上述每一项限制和规定。对于这些情况中的每一种，我们也给出了启发式算法的一个扩展。
其他图形分割问题的联系
图形分割问题以前曾被广泛研究过。[3] 对平衡图形分割问题的算法和应用进行调查。这里有多种解决问题的方法，从简单的启发式到复杂的组合优化方法。一些著名的应用是并行处理，道路网络，图像处理。 [4] 给出了一个最接近我们问题的平衡分割问题的近似算法。在大多数相关问题（包括 [4] ）中，组件的数量是固定的。在我们的问题中，组件的数量没有固定，这使得它更难解决。我们问题的主要特点是组件的最大尺寸。这一特点来源于我们问题的主要社会划分应用的性质。这也是与使用不同标准进行划分的相关问题的主要区别。与许多相关问题不同，我们考虑问题的加权版本，因为在社会分区问题的背景下，将不同的权重分配给弧线更为现实。我们的主要解决方法是整数规划，而近似算法或启发式算法用于许多相关问题。整数规划是小公司（最多50人）解决社会划分问题的合适方法。我们还给出了如何使模型更高效的方向，以便它能够解决更大的问题。整数规划也是在原始问题中增加不同额外要求的合适技术，使其在社会划分应用中更加现实。
计算结果
我们在优化建模语言AMPL（数学编程语言）上对模型进行了模拟[5]。这些模型经过了不同尺寸和性质的输入测试。对允许超过最大复合体积的模型进行了敏感性分析。启发式也在 AMPL 上实施和测试，并评估其性能的最佳解决方案。
论文的结构
论文的结构如下。第 2 节给出了主要整数规划模型、 提高其效率和实施 AMPL 的方向。第 3 节讨论了模型的不同变化和扩展。第4节为解决主要问题及其变化提供了启发式算法。第5节讨论计算结果，第6节给出了几个未来的方向。
2.主要模型
我们在第 2.1 节中开发了基本模型。在第 2.2 节中，我们讨论如何改进模型以使其计算效率更高。第 2.3 节给出了模型的 AMPL 实现。
2.1.基本模型
让节点成为公司内的一组 N 个员工。让弧成为节点中一对员工之间所有可能的直接互动（连接）的集合。规则要求将节点划分为组件，以便每个组件最多拥有 M 个员工。不同组件的员工之间不允许互动。每次直接互动对公司都有一定的价值。因此，公司希望在遵守规定的同时最大限度地增加可能的互动次数。
变量
我们有以下一组二进制变量：
如果将员工i和j之间的链接包含在解决方案中，则xij为1，否则为0。
如果员工i和j在解决方案中的同一组件中，则让yij为1，否则为0。
问题的加权与非加权版本
在问题的未加权版本中，公司希望最大限度地增加解决方案中包含的连接总数。但在现实中，对公司来说，有些环节比其他环节更重要。因此，我们为Arcs 设置的每种连接定义一个范围为 [0， 1]的参数权重。更高的权重意味着这种连接对公司具有更高的重要性。对于其他的文件， 我们考虑了问题的加权版本。请注意，当所有权重设置为 1 时，未加权版本是特例。
目标函数
客观功能最大化解决方案中包含的弧线的总权重。
最大sum;（ i ，j ）isin; 弧权重（i , j） lowast; xij （1）
约束
我们在模型中具有以下约束：
C1） 任何组件的大小不应超过M。为了提供它，我们要求对于任何节点i， 与i在同一组件中的节点数不超过 M minus; 1。
sum; j isin;节点 yij le; M-1 （2）
变量xij 和 yij 应相互连接。我们需要以下两套约束来提供它。
C2）如果连接（i，j）包含在解决方案中，则节点i和j应位于同一组件中。
象征性地，如果xij=1然后yij=1。. 相应的线性约束是
yij ge;xij （3）
C3） 传递性。如果节点i 和 j 位于同一组件中，并且节点 j 和 k 位于相同的组件中，则节点 i 和 k 也应位于同一组件中。
象征性地，如果yij=1和yjk=1然后yik=1.。同样，如果yij yjk=2然后yik=1。
实现上述条件约束的线性约束是
yik=yij yjk-1 （4）
约束的工作原理如下。如果yij yjk=2，那么右侧是1，yik需要至少1：因为yik是一个二进制变量，它将必须精确到1。另一方面，如果，那么右边是le;0;因此，它无法强迫yik。
2.2.基本模型的计算改进版本
在本节中，我们给出了如何改进模型以使其计算效率更高的几个方向。主要的想法是减少yij变量的数量和放宽 yij 变量的集成性。
通过只定义一次对称变量来减少变量的数量
在我们的模型中，节点按词典顺序给出：节点等于1，...，N 。对于每一对节点i和j如ilt;j，我们定义只有一个连接（i，j）和相应的变量xij和yij。由于i和j之间的关系是对称的，相反的连接也含蓄地出现在解决方法中。此方法明显减少了变量的数量。
不定义不是1的变量来减少变量数量
请注意，在输入问题时，节点可能已经被分割成几个连接的组件。我们的模型打算将这些组件分成更小的不超过大小为M的零件。我们将区分这些组件，称它们为输入组件和输出组件。例如，请考虑图 2中的未加权网络，包括 N = 10 和 M = 3。它有两个输入组件：{1, 2, 3, 6, 7}和{4, 5, 8, 9, 10}.。最佳解决方案中的输出组件为 {1, 2}, {3, 6, 7}, {4, 5}, {8, 9, 10}，解决方案中总共包含 6 条弧线。
如果节点i 和j 不在同一输入组件中，则 i 和 j 也不能在同一输出组件中，并且变量yij 不能在最佳解决方案中考虑值 1。因此，没有定义相应的变量 yij 的点。例如，在图 2的实例中无需定义变量y3，8，因为节点 3 和 8 位于不同的输入组合中。这对于相对稀疏的网络尤其有意义。
排除变量yij的另一个考虑因素如下。假设节点i和j位于相同的输入组件中，但i和j之间的最短距离大于Mminus;1。如果i和j也在同一个输出组件中，那么该组件将包括有M 1节点的一个路径连接i和j（包括i和j）。但一个输出组件不能超过 M 节点。因此，i 和 j 不能在同一输出组件中，并且没有定义相应变量 yij的点。例如，由于节点 1 和之间的距离是3，3大于2=Mminus;1，因此无需在图 2 的实例中定义变量y1，6；有1和6在同一放组件将意味着连接路径1-2-7-6上的所有节点应在该输出组件中，从而违反M=3。
为了实现上述变量的减少，我们使用广度优先搜索 （BFS） 查找每个节点的输入组件。来自 BFS 计算的信息用于计算来自同一输入计算机的任何两个节点之间的最短距离。然后变量yij被定义只有在1）i和j位于相同的输入组件中;2）i和j之间的最短距离不超过Mminus;1。这些计算的AMPL实现在第2.3节中给出。
放宽yij 变量的集成性
定理 1.假设yij变量的二进制要求放宽到 0 le; yij le; 1。然后将有一个最佳的解决方案，其中yij将只取值0或1。
图2 输入和输出组件示例
证明
让C1，C 2，hellip;，Cm 是由包括弧 （i， j）与 xij = 1 在解决方案中形成的输出组件。假设节点u和v位于同一组件中。然后有一个路径P在u和v之间，以至于对于所有的弧（i，
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[405766]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
