Аноним

Ресинхронизация схемы: различия между версиями

Материал из WEGA
Строка 43: Строка 43:
Минимизировать <math>\sum_{v \in V} (in[v] - out[v]) * r[v]</math> так, чтобы выполнялись неравенства
Минимизировать <math>\sum_{v \in V} (in[v] - out[v]) * r[v]</math> так, чтобы выполнялись неравенства


<math>w[u, v] + r[v] - r[u] \ge 0 \; \forall (u, v) \in E</math>
<math>w[u, v] + r[v] - r[u] \ge 0 \; \; \forall (u, v) \in E</math>


<math>W[u, v] + r[v] - r[u] \ge 1 \; \forall u, v \in V: D[u, v] > \phi</math>
<math>W[u, v] + r[v] - r[u] \ge 1 \; \; \forall u, v \in V: D[u, v] > \phi</math>


<math>r[v] \in \mathbb{Z} \; \forall v \in V</math>
<math>r[v] \in \mathbb{Z} \; \; \forall v \in V</math>




Строка 53: Строка 53:




Теорема 1. Целочисленная линейная программа для задачи ресинхронизации с минимальной площадью является двойственной к задаче нахождения потока с минимальной стоимостью в сети.
'''Теорема 1. Целочисленная линейная программа для задачи ресинхронизации с минимальной площадью является двойственной к задаче нахождения потока с минимальной стоимостью в сети.'''
Minimize  У^  w[u;v] * f[u;v] (u;v)2E


'''Минимизировать <math>\sum_{(u, v) \in E} w[u, v] * f[u, v] + \sum_{D[u, v] > \phi} (W[u, v] - 1) * f[u, v]</math> так, чтобы выполнялись соотношения'''


<math>in[v] + \sum_{(v, w) \in E \vee D[u, v] > \phi} f[v, w] = out[v] + \sum_{(u, v) \in E \; \; D[u, v] > \phi} f[u, v] \; \; \forall v \in V</math>
(W[u,v]-l)*f[u,v]
 
s:t: in[v]
<math>f[u, v] \ge 0 \; \; \forall (u, v) \in E \; \; D[u, v] > \phi</math>
f[v;w] = out[v]
+ X        f[u;v]   8v 2 V
(K,V)€£D[K,V]>0
f[u; v] > 0   8(U; V) 2 ED[u; v]> ф




4551

правка