44
правки
Изменения
sta
{{Определение
|definition =
Для двух матроидов <tex>M_1 = (S, \mathcal{I}_1) </tex> и <tex>M_2 = (S, \mathcal{I}_2) </tex> '''многогранником пересечения''' (англ. ''intersection polytope'') называется ''выпуклая оболочка'' (англ. ''convex hull'') инцидентных векторов общего независимого множества:
<tex>Conv\{\mathcal{X}(I), I \in \mathcal{I}_1 \cap \mathcal{I}_2 \} (1)</tex>
}}
{{Теорема
|statement =
Пусть <tex>r_1</tex> и <tex>r_2 : 2^S \mapsto Z_{+}</tex> ранговые функции матроидов <tex>M_1 = (S, \mathcal{I}_1) </tex> и <tex>M_2 = (S, \mathcal{I}_2) </tex> соответсвенно. Тогда многогранник пересечений <tex>(1)</tex> эквивалентен множеству <tex>\mathit{x} \in R^{S}</tex> , определенным следующей системой ''общего двойного интегралоа'' (англ. ''totally dual integral (TDI)'') <tex>(2)</tex> :
<tex>x(u) := \sum\limits_{e \in U} x_e \leqslant r_i(U) \mid \forall U \subseteq S , i = 1, 2</tex>
<tex> x \ge 0</tex>
|proof =
Достаточно показать, что эта система (2) является TDI , так как тогда все точки экстремума будут целыми, и тогда множество вершин будет являться набором инцидентных векторов общего независимого множества для двух матроидов .
Для доказательства TDI, рассмотрим следующее двойное линейное программирование для взвешенного вектора <tex> \mathit{w} \in Z^{S} (3)</tex>:
<tex>\max_{x \ge 0: x(u) \leqslant r_i(U), i = 1, 2 } </tex> <tex>\mathbf\mathit{w^Tx} = </tex> минимизировать <tex> \sum\limits_{U \subseteq S} r_1(U)u_1(U) + \sum\limits_{U \subseteq S} r_2(U)y_2(U)</tex>
С учетом того, что <tex>\sum\limits_{e \in U} [y_1(U) + y_2(U)] \ge w_e \mid \forall e \in S</tex>
и так же <tex>y_1, y_2 \ge 0</tex>
Заметим, что мы можем предположить <tex>w \ge 0</tex> , так как любое отрицательное значение может быть удалено, поскольку оно никак не влияет на целостность двойственности.
}}
{{Утверждение
|statement = Существуют оптимальные решения <tex>(y_1^*, y_2^*)</tex> для системы <tex>(3)</tex> , которое удовлетворяет свойствам <tex>(4) </tex>:
<tex> y_1^*(U) = 0</tex> <tex>\forall U \notin \mathcal{C}_1 </tex>
<tex> y_2^*(U) = 0 </tex> <tex>\forall U \notin \mathcal{C}_2 </tex>
для каких-то цепочек <tex>\mathcal{C}_1 , \mathcal{C}_2 \subseteq 2^S </tex>
|proof =
Пусть <tex>(y_1^*, y_2^*) </tex> будет оптимальным решением для <tex>(3)</tex>. Зафиксируем <tex> y_2 = y_2^* </tex>, и получаем:
минимизируем <tex> \sum\limits_{U \subseteq S} (r_1(U)y_1(U) + r_2(U)y_2(U)) </tex>
при условии <tex>\sum\limits_{e \in U} y_1(U) \ge w_e - \sum\limits_{e \in U} y_2^*(U)</tex> <tex> \forall e \in S</tex>
с учетом того, что <tex> y_1 \ge 0 </tex>
Это сводится к двойному линейному программированию задачи о максимальном независимом множестве с весом <tex>w</tex>. Таким образом, оптимальное решение <tex>y_1^*</tex> может быть выбрано для цепочки. Аналогично, делая замену <tex>y_1 = y_1^*</tex> , оптимальное решение <tex>y_2^*</tex> также может быть выбрано для цепочки. Более того, эти решения удовлетворяют
<tex> \sum\limits_{U \in \mathcal{C}_1 : e \in U} y_1^*(U) = w_e^{(1)}</tex>
<tex> \sum\limits_{U \in \mathcal{C}_2: e \in U} y_2^*(U) = w_e^{(2)}</tex>
и поэтому
<tex> \sum\limits_{i = 1}^{2} \sum\limits_{U \subseteq S} y_1^*(U) = w_e </tex> для всех <tex>e \in S</tex>
}}
==Источники информации==
* [http://math.mit.edu/~goemans/18438F09/lec12.pdf Advanced Combinatorial Optimization, lecture 12]
[[Категория:Матроиды]]
|definition =
Для двух матроидов <tex>M_1 = (S, \mathcal{I}_1) </tex> и <tex>M_2 = (S, \mathcal{I}_2) </tex> '''многогранником пересечения''' (англ. ''intersection polytope'') называется ''выпуклая оболочка'' (англ. ''convex hull'') инцидентных векторов общего независимого множества:
<tex>Conv\{\mathcal{X}(I), I \in \mathcal{I}_1 \cap \mathcal{I}_2 \} (1)</tex>
}}
{{Теорема
|statement =
Пусть <tex>r_1</tex> и <tex>r_2 : 2^S \mapsto Z_{+}</tex> ранговые функции матроидов <tex>M_1 = (S, \mathcal{I}_1) </tex> и <tex>M_2 = (S, \mathcal{I}_2) </tex> соответсвенно. Тогда многогранник пересечений <tex>(1)</tex> эквивалентен множеству <tex>\mathit{x} \in R^{S}</tex> , определенным следующей системой ''общего двойного интегралоа'' (англ. ''totally dual integral (TDI)'') <tex>(2)</tex> :
<tex>x(u) := \sum\limits_{e \in U} x_e \leqslant r_i(U) \mid \forall U \subseteq S , i = 1, 2</tex>
<tex> x \ge 0</tex>
|proof =
Достаточно показать, что эта система (2) является TDI , так как тогда все точки экстремума будут целыми, и тогда множество вершин будет являться набором инцидентных векторов общего независимого множества для двух матроидов .
Для доказательства TDI, рассмотрим следующее двойное линейное программирование для взвешенного вектора <tex> \mathit{w} \in Z^{S} (3)</tex>:
<tex>\max_{x \ge 0: x(u) \leqslant r_i(U), i = 1, 2 } </tex> <tex>\mathbf\mathit{w^Tx} = </tex> минимизировать <tex> \sum\limits_{U \subseteq S} r_1(U)u_1(U) + \sum\limits_{U \subseteq S} r_2(U)y_2(U)</tex>
С учетом того, что <tex>\sum\limits_{e \in U} [y_1(U) + y_2(U)] \ge w_e \mid \forall e \in S</tex>
и так же <tex>y_1, y_2 \ge 0</tex>
Заметим, что мы можем предположить <tex>w \ge 0</tex> , так как любое отрицательное значение может быть удалено, поскольку оно никак не влияет на целостность двойственности.
}}
{{Утверждение
|statement = Существуют оптимальные решения <tex>(y_1^*, y_2^*)</tex> для системы <tex>(3)</tex> , которое удовлетворяет свойствам <tex>(4) </tex>:
<tex> y_1^*(U) = 0</tex> <tex>\forall U \notin \mathcal{C}_1 </tex>
<tex> y_2^*(U) = 0 </tex> <tex>\forall U \notin \mathcal{C}_2 </tex>
для каких-то цепочек <tex>\mathcal{C}_1 , \mathcal{C}_2 \subseteq 2^S </tex>
|proof =
Пусть <tex>(y_1^*, y_2^*) </tex> будет оптимальным решением для <tex>(3)</tex>. Зафиксируем <tex> y_2 = y_2^* </tex>, и получаем:
минимизируем <tex> \sum\limits_{U \subseteq S} (r_1(U)y_1(U) + r_2(U)y_2(U)) </tex>
при условии <tex>\sum\limits_{e \in U} y_1(U) \ge w_e - \sum\limits_{e \in U} y_2^*(U)</tex> <tex> \forall e \in S</tex>
с учетом того, что <tex> y_1 \ge 0 </tex>
Это сводится к двойному линейному программированию задачи о максимальном независимом множестве с весом <tex>w</tex>. Таким образом, оптимальное решение <tex>y_1^*</tex> может быть выбрано для цепочки. Аналогично, делая замену <tex>y_1 = y_1^*</tex> , оптимальное решение <tex>y_2^*</tex> также может быть выбрано для цепочки. Более того, эти решения удовлетворяют
<tex> \sum\limits_{U \in \mathcal{C}_1 : e \in U} y_1^*(U) = w_e^{(1)}</tex>
<tex> \sum\limits_{U \in \mathcal{C}_2: e \in U} y_2^*(U) = w_e^{(2)}</tex>
и поэтому
<tex> \sum\limits_{i = 1}^{2} \sum\limits_{U \subseteq S} y_1^*(U) = w_e </tex> для всех <tex>e \in S</tex>
}}
==Источники информации==
* [http://math.mit.edu/~goemans/18438F09/lec12.pdf Advanced Combinatorial Optimization, lecture 12]
[[Категория:Матроиды]]
