Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации

• Видавець: Кам'янець-Подільський національний університет імені Івана Огієнка
• Дата: 2016
• Автор: Пічугіна, Оксана Сергіївна
• Формат: Стаття
• Мова: rus
• Опубліковано: Кам'янець-Подільський національний університет імені Івана Огієнка 2016
• Теми: евклидово комбинаторное множество; условная линейная комбинаторная оптимизация; метод комбинаторных отсечений; поверхностные отсечения; полиэдральная и поверхностная релаксации; полиэдрально-сферическое представление
• Онлайн доступ: http://mcm-math.kpnu.edu.ua/article/view/70278

В статье предложены две модификации метода комбинаторных отсечений (МКО) решения линейных задач на вершинно расположенных комбинаторных множествах, основанные на построении ужесточенных отсечений по отношению к МКО отсечений. Данные модификации — метод отсечений комбинаторного многогранника (МОКМ) и метод поверхностных отсечений (МПО) — основаны на решении вспомогательной задачи поиска ближайшей точки поверхности к точке в заданном направлении. При этом в МОКМ в качестве поверхности выступает граница комбинаторного многогранника, в МПО — описанная вокруг него гладкая выпуклая поверхность. Последнее позволяет строить отсечения, являющиеся ужесточением как для МКО, так и для МОКМ. Для применения МПО необходимо решить задачу поиска полиэдрально-поверхностного представления комбинаторного множества, в то время как МОКМ использует только аналитический вид многогранника.