4555
правок
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
м
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 11:48, 21 сентября 2018
, 21 сентября 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
REL_PACK_ORACLE (оракул упаковки с ослабленными ограничениями): Даны m-мерный вектор y > | REL_PACK_ORACLE (оракул упаковки с ослабленными ограничениями): Даны m-мерный вектор <math>y \ge 0 \;</math> и вышеописанные множества <math>P, \hat{P}</math>. Вернуть <math>\bar{x} \in \hat{P}</math>, такое, что <math>y^T Ax \le min \{y^T Ax : x \in P \}</math>. | ||
• Дробно-линейная задача о покрытии и ее оракул определяются следующим образом. | • '''Дробно-линейная задача о покрытии''' и ее оракул определяются следующим образом. | ||
COVERING (покрытие): Даны матрица A размера <math>m \times n</math>, b > 0 и выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0, \forall x \in P</math>. Существует ли такое x 2 P, что Ax > b? | COVERING (покрытие): Даны матрица A размера <math>m \times n</math>, b > 0 и выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0, \forall x \in P</math>. Существует ли такое x 2 P, что Ax > b? | ||