4446
правок
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
м
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 21:23, 20 декабря 2018
, 20 декабря 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 20: | Строка 20: | ||
• '''Дробно-линейная задача о покрытии''' и ее оракул определяются следующим образом. | • '''Дробно-линейная задача о покрытии''' и ее оракул определяются следующим образом. | ||
COVERING (покрытие): Даны матрица A размера <math>m \times n</math>, b > 0 и выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0 | 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-мерный вектор <math>y \ge 0 \;</math> и вышеописанное множество P. Вернуть <math>\bar{x} := arg \; max \{ y^T Ax : x \in P \}</math> | COVER _PACK_ORACLE (оракул покрытия): Даны m-мерный вектор <math>y \ge 0 \;</math> и вышеописанное множество P. Вернуть <math>\bar{x} := arg \; max \{ y^T Ax : x \in P \}</math> | ||
| Строка 27: | Строка 27: | ||
• '''Задача об одновременных упаковке и покрытии''' и ее оракул определяются следующим образом. | • '''Задача об одновременных упаковке и покрытии''' и ее оракул определяются следующим образом. | ||
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 | 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 и решение двойственной задачи <math>(y, \hat{y})</math>. Вернуть <math>\bar{x} \in P</math>, такое, что <math>A \bar{x} \le vb</math> и выполняется соотношение | |||
<math>y^T A \bar{x} - \sum_{i \in I(v, \bar{x})} \hat{y}_i \hat{a}_i \bar{x} = min \{ y^T Ax - \sum_{i \in I(v, x)} \hat{y}_i \hat{a}_i x</math> : x является вершиной P, такой, что <math>Ax \le vb \}</math>, где <math>I(v,x) := \{i : \hat{a}_i x \le v b_i \}</math>. | <math>y^T A \bar{x} - \sum_{i \in I(v, \bar{x})} \hat{y}_i \hat{a}_i \bar{x} = min \{ y^T Ax - \sum_{i \in I(v, x)} \hat{y}_i \hat{a}_i x</math> : x является вершиной P, такой, что <math>Ax \le vb \}</math>, где <math>I(v,x) := \{i : \hat{a}_i x \le v b_i \}</math>. | ||