Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
В данной статье приводится обзор быстрых алгоритмов, дающих приближенные решения для задач, которые могут быть сформулированы в виде задач линейного программирования (LP) и, следовательно, могут быть решено точно, хотя это потребует большего времени выполнения. Общий формат семейства таких задач имеет следующий вид. Дано множество из m неравенств с n переменными и оракул, который выдает решение подходящей задачи оптимизации над выпуклым множеством <math>P \in \mathbb{R}^n</math>. Найти решение <math>x \in P \;</math>, удовлетворяющее неравенствам, или | В данной статье приводится обзор быстрых алгоритмов, дающих приближенные решения для задач, которые могут быть сформулированы в виде задач линейного программирования (LP) и, следовательно, могут быть решено точно, хотя это потребует большего времени выполнения. Общий формат семейства таких задач имеет следующий вид. Дано множество из m неравенств с n переменными и оракул, который выдает решение подходящей задачи оптимизации над выпуклым множеством <math>P \in \mathbb{R}^n</math>. Найти решение <math>x \in P \;</math>, удовлетворяющее неравенствам, или определить, что такого решения x не существует. Принципиальная идея алгоритма заключается в следующем. Алгоритм всегда начинает работу с недопустимого решения x и использует оракул оптимизации для поиска направления, в котором степень нарушения неравенств может быть уменьшена; это выполняется при помощи расчета вектора y, представляющего собой ''решение двойственной задачи относительно x''. После этого x аккуратно изменяется в этом направлении, и процесс повторяется до тех пор, пока x не становится «приближенно» допустимым. Далее будут рассмотрены конкретные задачи и соответствующие им оракулы оптимизации, а также определены другие нотации используемой «аппроксимации». | ||
• '''Дробно-линейная задача об упаковке''' и ее оракул определяются следующим образом. | • '''Дробно-линейная задача об упаковке''' и ее оракул определяются следующим образом. | ||
PACKING (упаковка): Даны матрица A размера <math>m \times n</math>, b > 0 и выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0 | 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-мерный вектор <math>y \ge 0 \;</math> и вышеописанное множество 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>. | ||
| Строка 12: | Строка 12: | ||
• '''Ослабленная дробно-линейная задача об упаковке''' и ее оракул определяются следующим образом. | • '''Ослабленная дробно-линейная задача об упаковке''' и ее оракул определяются следующим образом. | ||
RELAXED PACKING (упаковка с ослабленными ограничениями): Даны <math>\varepsilon > 0 \;</math>, матрица A размера <math>m \times n</math>, b > 0 и выпуклые множества <math>P | RELAXED PACKING (упаковка с ослабленными ограничениями): Даны <math>\varepsilon > 0 \;</math>, матрица A размера <math>m \times n</math>, b > 0 и выпуклые множества <math>P, \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-мерный вектор <math>y \ge 0 \;</math> и вышеописанные множества <math>P, \hat{P}</math>. Вернуть <math>\bar{x} \in \hat{P}</math>, такое, что <math>y^T | REL_PACK_ORACLE (оракул упаковки с ослабленными ограничениями): Даны m-мерный вектор <math>y \ge 0 \;</math> и вышеописанные множества <math>P, \hat{P}</math>. Вернуть <math>\bar{x} \in \hat{P}</math>, такое, что <math>y^T A \bar{x} \le min \{y^T Ax : x \in P \}</math>. | ||