已知某传送网的网络拓扑、链路容量和端到端需求。每个需求对都有相应的候选路径列表,且需求可以分流。若每条候选路径的传输成本固定为该路径包含的链路数量,与该路径承载的流量无关,且为了限制参与分流的候选路径数量,要求参与分流的候选路径所承载的流量必须超过某门限E。请建立一个旨在最小化此传送网传输总成本的网络优化模型。无需求解,但必须指明模型中的每个符号(下标、常量、变量)和每个方程、不等式的含义。(写计算答案)
时间: 2024-04-07 14:29:34 浏览: 109
假设该传送网的网络拓扑表示为有向图$G=(V,E)$,其中$V$为节点集合,$E$为边集合。链路容量表示为$c_{ij}$,表示节点$i$到节点$j$的链路容量。端到端需求表示为$d_{s,t}$,表示源节点$s$到目标节点$t$的需求。每个需求对都有$k_{s,t}$条相应的候选路径列表,其中第$j$条候选路径的传输成本为$p_{s,t,j}$,表示该路径包含的链路数量。
我们定义决策变量$x_{s,t,j}$表示选择第$j$条候选路径承载源节点$s$到目标节点$t$的需求,若选择该路径,则$x_{s,t,j}=1$,否则$x_{s,t,j}=0$。
则该传送网传输总成本的网络优化模型为:
\begin{aligned}
\text{minimize} \quad & \sum_{s,t}\sum_{j}p_{s,t,j}x_{s,t,j} \\
\text{subject to} \quad & \sum_{j}x_{s,t,j} \geq \frac{d_{s,t}}{E}, \quad \forall s,t \\
& \sum_{j}x_{s,t,j}c_{ij} \leq d_{s,t}, \quad \forall s,t,i \\
& x_{s,t,j} \in \{0,1\}, \quad \forall s,t,j
\end{aligned}
其中第一个约束条件表示选择的所有候选路径的流量之和必须超过门限$E$,第二个约束条件表示选择的所有候选路径的流量不能超过某个链路的容量。
阅读全文