排队系统中流量分布的优化
在当今的数字世界中，从全球数据网络到物流链和交易处理系统，我们不断面临有效的流量管理需求。 如何确保在高峰负载期间互联网连接不间断运行？ 如何优化特大城市的货物交付路线？ 如何设计呼叫中心，使客户不必等待响应？ 这些问题的答案在于排队理论领域，这是一门数学学科，研究请求（数据包，客户，车辆）到达服务的系统，形成队列。
排队服务系统(qms)它是由服务设备(通道、服务器、节点)和这些设备处理的应用程序流组成的数学模型。 特别感兴趣的是M/M/1系统，这是一个基本模型，其中传入的请求流具有泊松特性（具有恒定平均强度的随机，独立事件），并且服务时间受到指数分布（特征 这个简单但深入的模型揭示了队列的矛盾性质：随着负载接近100％，队列长度以双曲线而不是线性增加，使得优化不仅是可取的，而且是非常必要的。
网络首席财务官是下一个复杂级别，其中许多服务节点连接到网络。 这样的系统自然由有向图描述，其中节点表示处理点，分支表示带宽有限的通信信道。 对于网络结构的数学表示，使用邻接矩阵（描述节点之间存在连接）和入射矩阵（固定这些连接的方向）。 正是这些数学对象成为设置优化问题的构建块。
但如何在复杂网络中找到流的最佳分布？ 如何引导信息流或车辆，以尽量减少系统中的平均等待时间，同时避免个别通道超载？ 这个问题是使用非线性优化来解决的，其中目标函数是所有通道中平均请求数的总和（从M/M/1的公式得出），并且约束包括节点中的流的平衡和吞吐量的物理限制。
在本文中，我们提出了一个完整的网络CFM分析和优化周期，从理论基础到在AnyMath环境中的实际实现。 你会看到如何:
*将有关吞吐量和流量的真实数据转换为数学模型;
*使用图形可视化复杂的网络结构;
*制定一个包含数百个变量和约束的优化问题;
*使用现代非线性优化算法求解;
*通过交互式可视化和量化指标分析结果。
在这个例子中，我们并不局限于理论计算，而是贯穿整个过程--从Excel格式的源数据到网络优化的现成建议，每个步骤都附有可视化的图表和详细的解释。 使用Julia，一种结合了C的速度和Python的表现力的语言，使解决方案既高效又透明。
我们将附加必要的库。
import Pkg
neededLibs = ["XLSX", "JuMP" ,"Ipopt","Graphs", "SimpleWeightedGraphs" , "Colors", "Printf", "LinearAlgebra", "GraphPlot"]
for lib in neededLibs
try
eval(Meta.parse("using $lib"))
catch ex
Pkg.add(lib)
eval(Meta.parse("using $lib"))
end
end
我们将附加必要的功能文件。
foreach(include, ("opti1.jl", "opti2.jl", "opti3.jl", "opti4.jl", "opti5.jl", "opti6.jl", "opti7.jl", "opti8.jl", "opti9.jl", "flowDir.jl", "optiwrite.jl", "lfwrite.jl"))
foreach(include, ("readqs.jl", "flowGraph.jl", "flGplot.jl", "netGraph.jl", "simpGraph.jl", "sGplot.jl","nGplot.jl"))
CFR结构
排队系统的结构可以表示为对角线大小为零的正方形网络矩阵 :
哪里 -网络中的节点数, -连接节点的通信信道（图分支）的总带宽，并从具有编号的节点定向 到编号的节点 ，而零对角线意味着没有从节点寻址到自身的信息流的通道。
排队系统中的流向也可以表示为大小为零的对角线的方阵。 :
哪里 -网络中的节点数, -从带编号的节点引导的流量 到编号的节点 . 矩阵中的零对角线意味着没有流从节点寻址到自己。
流量和吞吐能力可以用排队系统中使用的任何计量单位来表示，例如：Mbit/s，每小时的产品数量;每天运输的货物数量;每小时驱动的车辆数量，每天的请求.
初始数据
在我们的示例中，源数据以xlsx表的形式呈现。 NetMatrix的。xlsx-通信线路的带宽和方向，FlowMatrix。xlsx-流动的强度和方向。
让我们阅读源数据。
СМО = readqs("NetMatrix.xlsx", 1);
Потоки = readqs("FlowMatrix.xlsx", 1);
让我们将通信线路的容量显示为矩阵。
display(СМО)
让我们将流显示为矩阵。
display(Потоки)
根据初始数据，我们将确定所研究的CFR中的节点，流和通信线路的数量。
узлов = size(СМО, 1);
линий = count(!iszero, СМО);
потоков = count(!iszero, Потоки);
println("В системе массового обслуживания\n\nузлов: $узлов\nпотоков: $потоков\nлиний связи: $линий")
CFR的可视化
让我们将CFR结构显示为图形。 为了清楚起见，我们将不考虑此图中通信线路的方向和强度。
и, п = simpGraph(СМО);
Граф = sGplot(и, п)
display(Граф)
.png)
通过指定节点编号、强度值和箭头，我们将显示流向。
nfl, nl, flG, flI = flowGraph(Потоки);
ГрафПотоков = flGplot(flG, flI, nl, "Направления потоков");
display(ГрафПотоков)
.png)
现在我们将以有向图的形式显示CFR的完整结构，其中包含通信线路的节点编号，方向和容量。
s, t, bW = netGraph(СМО);
ГрафСМО = nGplot(s, t, bW, "Структура системы массового обслуживания");
display(ГрафСМО)
.png)
M/M/1系统
考虑M/M/1系统，其中应用程序的传入流具有泊松分布，并且服务时间的分布是指数的，那么系统中的平均应用程序数由公式确定:
哪里 -收到的申请强度, -通信线路的带宽。 这个公式是由于应用程序到达和服务时刻的随机性而产生的。 当系统运行接近其容量限制（负载接近100％）时，即使是很小的随机延迟也会开始累积，从而导致双曲线而不是线性队列增长。 在数学上，这是系统中应用程序数量的几何分布的结果，其平均值由该表达式确定。 将来，基于该公式，将形成用于优化的目标函数。
源数据的转换
对于进一步的解决方案，我们将带宽矩阵转换为3个向量。:
*资料来源一览表;
*接收者名单;
*吞吐能力列表。
источник, приёмник, ёмкость = opti1(СМО, узлов, линий);
在绕过繁忙通信线路的优化过程中，流可能会分裂成分数。 流分数的结构可以表示为矩阵的数量的系统 大小 :
哪里 -节点数, -流数, -流量分数的值 通过从节点编号指向的线 到节点号 .
入射矩阵
基于邻接矩阵，我们将创建一个入射矩阵。
每列对应于图形的一个分支：源线包含 -1，在接收器线 — +1. 矩阵具有大小 узлов × линий 并描述了哪些节点由每条边和线的方向连接。
МатрицаИнцидентности = opti2(узлов, линий, источник, приёмник);
display(МатрицаИнцидентности)
流量限制
让我们将流矩阵转换为3个向量:
*寄件人名单;
*收件人名单;
*流动强度列表。
исток, приток, интенсивность = opti3(Потоки, узлов, потоков);
让我们创建一个矩阵，指示从源节点流出的流和流入到接收节点的流的强度。 行数等于节点数，列数等于线程数。 负值表示来自源节点的传出流，正值表示到接收器节点的传入流。 行号与节点号相对应。
исток_приток = opti4(узлов, потоков, исток, приток, интенсивность);
display(исток_приток)
让我们创建一个三维数组，指示每条通信线路中的流向。 行数为两个（源和流入），列数对应于通信线路数量 линий，且二维矩阵的个数对应于流的个数 потоков. 此阵列将用于阻止流向源节点的传入流和来自接收器节点的传出流。
ограничения = opti5(линий, потоков, источник, приёмник, исток, приток);
display(ограничения)
方程和不等式
基于入射矩阵和流向阵列，我们将创建一个三维阵列，指示CFR优化约束方程的流分数的符号（-1或0或+1）。 线路的数量对应于节点的数量加上两个，因为等于节点数量的数量指示中间通信线路中的限制，以及终端中的最后两个，其阻止流入源节点和从接收器节 这些数组将用于创建优化约束方程。
Уравнения = opti6(узлов, МатрицаИнцидентности, линий, потоков, ограничения, исток_приток);
display(Уравнения)
通过将得到的数组元素乘以指示流量分数的变量，我们得到了一个方程组。
让我们考虑方程是如何形成的节点1，流 . 将流的分数表示为矩阵:
让我们用索引取矩阵的一个元素 其等于零。 第行的元素用减号代入方程，第列的元素用加号代入方程。 我们得到方程:
对于以下节点，取索引 ，并重复方程的组成。 这些方程引入了约束，意味着中间节点处的流入和流出流的总和为零。
为了清楚起见，我们将使用节点示例以一般方式绘制优化约束方程系统。: 和流 :
哪里 -节点数, -线程数。
除了方程组之外，必要的限制是通信线路中流量的最大强度，不应超过其带宽。 对于由8个节点和24条通信线组成的CFR，此约束将由以下不等式系统表示:
我们将获得的结果转换为用于执行优化任务的初始数据。
А, Б, λ0, а, б = opti7(узлов, потоков, линий, Уравнения, исток_приток, ёмкость);
display(А)
display(Б)
目标功能
基于带宽矩阵和流量矩阵的结构，我们将创建一个目标函数。 对于由8个节点，24条通信线路和3条流组成的CFR，目标函数将具有以下形式:
目标函数可以用一般的方式表示:
在哪里 -排队系统中平均请求数的值, -通讯线路数目 -流数, -从节点定向的通信线路的带宽量 到节点 , -从节点引导的流的分数的期望的最佳强度 到节点 ，这是流的一部分 .
优化任务归结为以下目标：找到这样的值 ，其下 它将取最小值。
优化设计
让我们创建目标函数并完成优化任务。
T, λ, нагрузка = opti8(А, Б, λ0, а, б, ёмкость, потоков);
优化结果
我们将数据转换为图形显示，并将其输出为xlsx表。 在优化成功的情况下，我们将输出最优流量分布矩阵。
Оптимальные, НагрузкаСистемы = opti9(потоков, линий, λ, узлов, источник, приёмник, ёмкость);
if T # 负荷>0
display(Оптимальные)
end
让我们输出优化结果。
nl = flowDir(Потоки);
if T
optiwrite(Оптимальные, потоков)
println("\nОптимизация выполнена.\n")
println("\nСреднее количество заявок в системе: $нагрузка\n")
else
println("\nОптимизация невыполнима при данных интенсивностях потоков и ёмкостях линий связи.\n")
end
让我们创建一个xlsx文件并输出一个包含通信线路负载系数的矩阵。
lfwrite(НагрузкаСистемы)
display(НагрузкаСистемы)
最佳流的可视化
如果进行优化，我们将以图形的形式显示流动强度的最佳分布。
if T
fnums = reshape(nl, (2, потоков));
for m in 1:потоков
optiname = "Распределение потоков от узла $(fnums[1, m]) к узлу $(fnums[2, m])"
и, п, ё = netGraph(readqs("OptiFlows.xlsx", m));
ОптГраф(m) = nGplot(и, п, ё, optiname);
display(ОптГраф(m))
end
else
println("\nНеобходимо увеличить пропускные линий связи или уменьшить интенсивность потоков.\n")
end
.png)
.png)
.png)
线路拥堵的可视化
让我们以图表的形式显示通信线路的负载系数。 基于该图，可以分析某些通信线路是否需要增加带宽。 如果在给定带宽的通信线路中优化是不可行的，则负载因子超过一表示需要将此通信线路增加多少次以使优化成为可能。
lM = readqs("LoadFactors.xlsx", 1);
s1, t1, bW1 = netGraph(lM);
ГрафНагрузки = nGplot(s1, t1, bW1, "Загруженность линий связи");
display(ГрафНагрузки)
.png)
除了给出的图形外，我们还获得了具有最优流量分布矩阵的xlsx表作为计算结果（OptiFlows。xlsx)和通信线路的负载在通信线路的流量和容量(LoadFactors)的这些值处，这将便于用于进一步的计算和研究。
优化您自己的系统
在所提出的算法的帮助下，您可以优化自己的排队系统，为此:
-
准备两个标准化的Excel文件。:
-
NetMatrix.xlsx-通信线路的方向和传输能力矩阵 -
FlowMatrix.xlsx-服务流的方向和强度矩阵
-
-
将它们上传到交互式计算环境
-
启动分析过程以获得综合结果。:
*每个流的最佳分布矩阵
*通道加载系数的图形表示
*网络拓扑和流配置的可视化
*系统参数的定量指标
无论系统的规模和具体情况如何，无论是市政运输基础设施，企业计算机网络还是生产和物流综合体，所呈现的工具都根据提供的数据提供自适应分析。 该方法可以识别在容量限制下运行的关键元件，识别过载路径，并确定最佳流量分配方案。
应该指出的是，网络结构的优化不再是能够访问专门软件的专家的专有能力。 目前，这正在成为一个标准化的过程，其中复杂的计算算法在直观的界面中实现，分析的深度与视觉呈现有机地结合在一起。
建议在当前数据上测试方法。 将特定系统的矩阵上传到AnyMath环境将允许您观察排队理论原理的实际实现，检测现有配置中的隐藏储备，并为优化问题找到有效的解决方案。
优化不应被视为一次性事件，而应被视为持续改进过程。 所提出的工具包确保了其一致性，可见性和有效性，形成了在复杂网络系统的动态环境中做出明智管理决策的基础。
结论
本研究证明了从排队理论的基本原理到网络结构集成优化的实际实现的方法学过渡。 以一个包括8个节点、24个通信信道和3个服务流的系统为例,说明了将数学概念——泊松流、指数分布、邻接和发生率矩阵--转化为解决应用问题的有效工具。 作为理论考虑的经典对象的M/M/1模型已被成功地应用为构建最小化分布式网络中平均请求数的目标函数的基础。
所进行的工作的中心结果是证明网络结构的优化是一个系统的过程，具有明确定义的阶段：数学建模，可视化表示，约束形式化，数值解和结果的分析解释。 已经通过实验证实，即使在中等复杂度的网络中，信息流也沿着替代路线自然分布，显示出对关键元素潜在过载的适应性。 通过有向图可视化结果不仅提供了最终值的表示，而且还提供了对系统中因果关系的理解。
最重要的方面是所提出的方法的实际可及性。 为解决设计电信网络、优化物流路线、分配计算资源或管理信息流等问题的专家提供了一个现成的工具解决方案。