Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации
В статье предложены две модификации метода комбинаторных отсечений (МКО) решения линейных задач на вершинно расположенных комбинаторных множествах, основанные на построении ужесточенных отсечений по отношению к МКО отсечений. Данные модификации — метод отсечений комбинаторного многогранника (МОКМ) и...
Збережено в:
| Опубліковано в: : | Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
|---|---|
| Дата: | 2016 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/133897 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации / О.С. Пичугина // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2016. — Вип. 13. — С. 144-160. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-133897 |
|---|---|
| record_format |
dspace |
| spelling |
Пичугина, О.С. 2018-06-08T19:58:04Z 2018-06-08T19:58:04Z 2016 Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации / О.С. Пичугина // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2016. — Вип. 13. — С. 144-160. — Бібліогр.: 14 назв. — рос. 2308-5878 https://nasplib.isofts.kiev.ua/handle/123456789/133897 519.85 В статье предложены две модификации метода комбинаторных отсечений (МКО) решения линейных задач на вершинно расположенных комбинаторных множествах, основанные на построении ужесточенных отсечений по отношению к МКО отсечений. Данные модификации — метод отсечений комбинаторного многогранника (МОКМ) и метод поверхностных отсечений (МПО) — основаны на решении вспомогательной задачи поиска ближайшей точки поверхности к точке в заданном направлении. При этом в МОКМ в качестве поверхности выступает граница комбинаторного многогранника, в МПО — описанная вокруг него гладкая выпуклая поверхность. Последнее позволяет строить отсечения, являющиеся ужесточением как для МКО, так и для МОКМ. Для применения МПО необходимо решить задачу поиска полиэдрально-поверхностного представления комбинаторного множества, в то время как МОКМ использует только аналитический вид многогранника. 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. ru Інститут кібернетики ім. В.М. Глушкова НАН України Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации |
| spellingShingle |
Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации Пичугина, О.С. |
| title_short |
Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации |
| title_full |
Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации |
| title_fullStr |
Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации |
| title_full_unstemmed |
Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации |
| title_sort |
поверхностные и комбинаторные отсечения в задачах евклидовой комбинаторной оптимизации |
| author |
Пичугина, О.С. |
| author_facet |
Пичугина, О.С. |
| publishDate |
2016 |
| language |
Russian |
| container_title |
Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| description |
В статье предложены две модификации метода комбинаторных отсечений (МКО) решения линейных задач на вершинно расположенных комбинаторных множествах, основанные на построении ужесточенных отсечений по отношению к МКО отсечений. Данные модификации — метод отсечений комбинаторного многогранника (МОКМ) и метод поверхностных отсечений (МПО) — основаны на решении вспомогательной задачи поиска ближайшей точки поверхности к точке в заданном направлении. При этом в МОКМ в качестве поверхности выступает граница комбинаторного многогранника, в МПО — описанная вокруг него гладкая выпуклая поверхность. Последнее позволяет строить отсечения, являющиеся ужесточением как для МКО, так и для МОКМ. Для применения МПО необходимо решить задачу поиска полиэдрально-поверхностного представления комбинаторного множества, в то время как МОКМ использует только аналитический вид многогранника.
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.
|
| issn |
2308-5878 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/133897 |
| citation_txt |
Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации / О.С. Пичугина // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2016. — Вип. 13. — С. 144-160. — Бібліогр.: 14 назв. — рос. |
| work_keys_str_mv |
AT pičuginaos poverhnostnyeikombinatornyeotsečeniâvzadačahevklidovoikombinatornoioptimizacii |
| first_indexed |
2025-12-07T20:10:11Z |
| last_indexed |
2025-12-07T20:10:11Z |
| _version_ |
1850881565312155648 |