4551
правка
Ресинхронизация схемы: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 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. Целочисленная линейная программа для задачи ресинхронизации с минимальной площадью является двойственной к задаче нахождения потока с минимальной стоимостью в сети.''' | ||
'''Минимизировать <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> | |||
<math>f[u, v] \ge 0 \; \; \forall (u, v) \in E \; \; D[u, v] > \phi</math> | |||
f[v | |||
+ | |||
f[u | |||
