4559
правок
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 11:46, 21 сентября 2018
, 21 сентября 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 7: | Строка 7: | ||
PACKING (упаковка): Даны матрица A размера <math>m \times n</math>, b > 0 и выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0, \forall x \in P</math>. Существует ли такое <math>x \in P \;</math>, что <math>Ax \le b \;</math>? | PACKING (упаковка): Даны матрица A размера <math>m \times n</math>, b > 0 и выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0, \forall x \in P</math>. Существует ли такое <math>x \in P \;</math>, что <math>Ax \le b \;</math>? | ||
PACK_ORACLE (оракул упаковки): Даны m-мерный вектор y > 0 и вышеописанное множество P. Вернуть x := | PACK_ORACLE (оракул упаковки): Даны m-мерный вектор y > 0 и вышеописанное множество P. Вернуть <math>\bar{x} := arg \; min \{ y^T Ax : x \in P \}</math>. | ||
• Ослабленная дробно-линейная задача об упаковке и ее оракул определяются следующим образом. | • '''Ослабленная дробно-линейная задача об упаковке''' и ее оракул определяются следующим образом. | ||
RELAXED PACKING (упаковка с ослабленными ограничениями): Даны <math>\varepsilon > 0 \;</math>, матрица A размера <math>m \times n</math>, b > 0 и выпуклые множества <math>P \in \mathbb{R}^n</math> и <math>\hat{P} \in \mathbb{R}^n</math>, такие, что <math>P \subseteq \hat{P}</math> и <math>Ax \ge 0, \forall x \in P</math>. Найти такое <math>x \in \hat{P}</math>, что <math>Ax \le (1 + \varepsilon)b \;</math>, или показать, что <math>\nexists x \in P</math>, такого, что <math>Ax \le b \;</math>. | |||
REL_PACK_ORACLE (оракул упаковки с ослабленными ограничениями): Даны m-мерный вектор y > 0 и вышеописанные множества P и P. Вернуть x € P, такое, что yTAx < minfyTAx: x 2 Pg. | REL_PACK_ORACLE (оракул упаковки с ослабленными ограничениями): Даны m-мерный вектор y > 0 и вышеописанные множества P и P. Вернуть x € P, такое, что yTAx < minfyTAx: x 2 Pg. | ||