Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации
В статье предложены две модификации метода комбинаторных отсечений (МКО) решения линейных задач на вершинно расположенных комбинаторных множествах, основанные на построении ужесточенных отсечений по отношению к МКО отсечений. Данные модификации — метод отсечений комбинаторного многогранника (МОКМ) и...
Збережено в:
Видавець: | Інститут кібернетики ім. В.М. Глушкова НАН України |
---|---|
Дата: | 2016 |
Автор: | |
Формат: | Стаття |
Мова: | Russian |
Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
Назва видання: | Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/133897 |
Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
Цитувати: | Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации / О.С. Пичугина // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2016. — Вип. 13. — С. 144-160. — Бібліогр.: 14 назв. — рос. |
Репозиторії
Digital Library of Periodicals of National Academy of Sciences of UkraineРезюме: | В статье предложены две модификации метода комбинаторных отсечений (МКО) решения линейных задач на вершинно расположенных комбинаторных множествах, основанные на построении ужесточенных отсечений по отношению к МКО отсечений. Данные модификации — метод отсечений комбинаторного многогранника (МОКМ) и метод поверхностных отсечений (МПО) — основаны на решении вспомогательной задачи поиска ближайшей точки поверхности к точке в заданном направлении. При этом в МОКМ в качестве поверхности выступает граница комбинаторного многогранника, в МПО — описанная вокруг него гладкая выпуклая поверхность. Последнее позволяет строить отсечения, являющиеся ужесточением как для МКО, так и для МОКМ. Для применения МПО необходимо решить задачу поиска полиэдрально-поверхностного представления комбинаторного множества, в то время как МОКМ использует только аналитический вид многогранника. |
---|