Участник:Kirillskor/minimum-multicover-approx-with-linear-relaxation — различия между версиями

Версия 00:14, 14 декабря 2017

Сведем задачу к задаче линейного программирования:

@@ Строка 2: / Строка 2: @@
-Сведем задачу к задаче линейного программирования.
+Сведем задачу к задаче линейного программирования:
 <latex>
-$\min_x \sum_{i=1}^{m} \omega_i x_i$, при ограничениях $0 \leq x_i \leq 1, \sum_{i=1}^{m} a_ij x_j \geq b_i$
+$\min_x \sum_{i=1}^{m} \omega_i x_i$, при ограничениях $x \in \{0, 1\}, \sum_{i=1}^{m} a_{ij} x_j \geq b_i$
+Релаксация этой задачи:
+$\min_x \sum_{i=1}^{m} \omega_i x_i$, при ограничениях $0 \leq x_i \leq 1, \sum_{i=1}^{m} a_{ij} x_j \geq b_i$
+Решаем
 <\latex>