Дробно-линейные задачи об упаковке и покрытии: различия между версиями

Перейти к навигации Перейти к поиску
Строка 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. Вернуть <math>\bar{x} := arg \; min \{ y^T Ax : x \in P \}</math>.
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 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>. Существует ли такое <math>x \in P \;</math>, что <math>Ax \le b \;</math>?


COVER _PACK_ORACLE (оракул покрытия): Даны m-мерный вектор y > 0 и вышеописанное множество P. Вернуть x := argmaxfyTAx: x 2 Pg:
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 (одновременные упаковка и покрытие): Даны матрицы A размера <math>m \times n</math> и A – размера <math>m \times n</math> (m — in) x n, b > 0 и b > 0, а также выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0, Ax \ge 0, \forall x \in P</math>. Существует ли такое x 2 P, что Ax < b и Ax > Ы?
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, такое, что
Источник — http://pco.iis.nsk.su/wega/index.php/Дробно-линейные_задачи_об_упаковке_и_покрытии