4551
правка
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 12:34, 5 октября 2018
, 5 октября 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
'''Определения и нотация''' | '''Определения и нотация''' | ||
Для параметра ошибки " > x0 точка x 2 P является "-приближенным решением для дробно-линейной задачи упаковки (или покрытия), если Ax < (1 + ")b (или Ax > (1 — ")b, соответственно). С другой стороны, если x 2 P удовлетворяет условию Ax < b (или Ax > b), то x является точным решением. Для общей задачи GENERAL, параметра ошибки " > 0 и положительного вектора отклонения d значение x 2 P является "-приближенным решением, если Ax < b + "d, и точным решением, если Ax < b. "-ослабленная разрешающая процедура для этих задач либо находит "-приближенное решение, либо обоснованно сообщает о том, что точного решения не существует. В общем случае в задаче минимизации (максимизации) алгоритм (1 + ")-аппроксимации ((1 - ")-аппроксимации) возвращает значение, не более чем в (1 + ") (не менее чем в (1 - ")) раз отличающееся от оптимального. | |||
Время выполнения разработанных алгоритмов полиномиально зависит от e"1 для любого параметра ошибки " > 0, а также от ширины p выпуклого множества P, родственного множеству неравенств Ax < b или Ax > b, определяющему решаемую задачу. Более точно ширина p определяется следующим образом для каждой из рассматриваемых задач: | |||
• PACKING (упаковка): p := maxi maxx2P abi | |||
• RELAXED PACKING (упаковка с ослабленными ограничениями): p := maxi maxx2P ^. | |||
• COVERING (покрытие): p := maxi maxx2P abi | |||
• SIMULTANEOUS PACKING AND COVERING (одновременные упаковка и покрытие): p := r maxfmaxi ^, max, + 1, где d | |||
• GENERAL (общая задача): p := maxi maxx2P jaix . bij+1 – вышеупомянутый вектор отклонения. | |||
== Основные результаты == | |||