4554
правки
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 11:55, 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 > | PACK_ORACLE (оракул упаковки): Даны m-мерный вектор <math>y \ge 0 \;</math> и вышеописанное множество P. Вернуть <math>\bar{x} := arg \; min \{ y^T Ax : x \in P \}</math>. | ||
| Строка 20: | Строка 20: | ||
• '''Дробно-линейная задача о покрытии''' и ее оракул определяются следующим образом. | • '''Дробно-линейная задача о покрытии''' и ее оракул определяются следующим образом. | ||
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 | 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>. Существует ли такое <math>x \in P \;</math>, что <math>Ax \le b \;</math>? | ||
COVER _PACK_ORACLE (оракул покрытия): Даны m-мерный вектор y > | COVER _PACK_ORACLE (оракул покрытия): Даны m-мерный вектор <math>y \ge 0 \;</math> и вышеописанное множество P. Вернуть <math>\bar{x} := arg \; max \{ y^T Ax : x \in P \}</math> | ||
• Задача об одновременных упаковке и покрытии и ее оракул определяются следующим образом. | • '''Задача об одновременных упаковке и покрытии''' и ее оракул определяются следующим образом. | ||
SIMULTANEOUS PACKING AND COVERING (одновременные упаковка и покрытие): Даны матрицы | SIMULTANEOUS PACKING AND COVERING (одновременные упаковка и покрытие): Даны матрицы <math>\hat{A}</math> и <math>A \;</math> размера <math>\hat{m} \times n</math> и <math>(m - \hat{m}) \times n</math>, соответственно, <math>b > 0 \;</math> и <math>\hat{b} > 0 \;</math>, а также выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0, \hat{A}x \ge 0, \forall x \in P</math>. Существует ли такое <math>x \in P \;</math>, что <math>Ax \le b \;</math> и <math>\hat{A}x \ge \hat{b}</math>? | ||
SIM_ORACLE (оракул упаковки и покрытия): Даны вышеописанное множество P, константа v и решение двойственной задачи (у, у). Вернуть x € P, такое, что | SIM_ORACLE (оракул упаковки и покрытия): Даны вышеописанное множество P, константа v и решение двойственной задачи (у, у). Вернуть x € P, такое, что | ||