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

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

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

Повний опис

Збережено в:
Бібліографічні деталі
Видавець:Інститут кібернетики ім. В.М. Глушкова НАН України
Дата: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
id irk-123456789-133897
record_format dspace
spelling irk-123456789-1338972018-06-09T03:05:02Z Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации Пичугина, О.С. В статье предложены две модификации метода комбинаторных отсечений (МКО) решения линейных задач на вершинно расположенных комбинаторных множествах, основанные на построении ужесточенных отсечений по отношению к МКО отсечений. Данные модификации — метод отсечений комбинаторного многогранника (МОКМ) и метод поверхностных отсечений (МПО) — основаны на решении вспомогательной задачи поиска ближайшей точки поверхности к точке в заданном направлении. При этом в МОКМ в качестве поверхности выступает граница комбинаторного многогранника, в МПО — описанная вокруг него гладкая выпуклая поверхность. Последнее позволяет строить отсечения, являющиеся ужесточением как для МКО, так и для МОКМ. Для применения МПО необходимо решить задачу поиска полиэдрально-поверхностного представления комбинаторного множества, в то время как МОКМ использует только аналитический вид многогранника. The article presents two improvements of the method of combinatorial cuttings (MCC) for linear problems over vertex located combinatorial sets based on the construction of tightening cuttings to MCC ones. These modifications are a method of combinatorial polyhedron cuttings (MCPC) and the method of surface cuttings (MSC). They are based on solving an auxiliary problem of finding the nearest point on a surface to a point in a given direction. In the MCPC the surface is a boundary of the corresponding combinatorial polytope; in the MSC — it is a smooth convex surface circumscribed around the combinatorial set. The last one allows construction cuttings that are tighter than MSC-ones as for the MCC, as for the MCPC. To apply the MSC, a problem of constructing a polyhedron-surface representation of the combinatorial set needs to be solved, whilst the MOKM utilises only the analytical description of the poly tope. 2016 Article Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации / О.С. Пичугина // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2016. — Вип. 13. — С. 144-160. — Бібліогр.: 14 назв. — рос. 2308-5878 http://dspace.nbuv.gov.ua/handle/123456789/133897 519.85 ru Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description В статье предложены две модификации метода комбинаторных отсечений (МКО) решения линейных задач на вершинно расположенных комбинаторных множествах, основанные на построении ужесточенных отсечений по отношению к МКО отсечений. Данные модификации — метод отсечений комбинаторного многогранника (МОКМ) и метод поверхностных отсечений (МПО) — основаны на решении вспомогательной задачи поиска ближайшей точки поверхности к точке в заданном направлении. При этом в МОКМ в качестве поверхности выступает граница комбинаторного многогранника, в МПО — описанная вокруг него гладкая выпуклая поверхность. Последнее позволяет строить отсечения, являющиеся ужесточением как для МКО, так и для МОКМ. Для применения МПО необходимо решить задачу поиска полиэдрально-поверхностного представления комбинаторного множества, в то время как МОКМ использует только аналитический вид многогранника.
format Article
author Пичугина, О.С.
spellingShingle Пичугина, О.С.
Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации
Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки
author_facet Пичугина, О.С.
author_sort Пичугина, О.С.
title Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации
title_short Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации
title_full Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации
title_fullStr Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации
title_full_unstemmed Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации
title_sort поверхностные и комбинаторные отсечения в задачах евклидовой комбинаторной оптимизации
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2016
url http://dspace.nbuv.gov.ua/handle/123456789/133897
citation_txt Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации / О.С. Пичугина // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2016. — Вип. 13. — С. 144-160. — Бібліогр.: 14 назв. — рос.
series Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки
work_keys_str_mv AT pičuginaos poverhnostnyeikombinatornyeotsečeniâvzadačahevklidovojkombinatornojoptimizacii
first_indexed 2023-10-18T21:06:53Z
last_indexed 2023-10-18T21:06:53Z
_version_ 1796151961032065024

Схожі ресурси