Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации
В статье предложены две модификации метода комбинаторных отсечений (МКО) решения линейных задач на вершинно расположенных комбинаторных множествах, основанные на построении ужесточенных отсечений по отношению к МКО отсечений. Данные модификации — метод отсечений комбинаторного многогранника (МОКМ) и...
Saved in:
| Date: | 2016 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Кам'янець-Подільський національний університет імені Івана Огієнка
2016
|
| Online Access: | http://mcm-math.kpnu.edu.ua/article/view/70278 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Mathematical and computer modelling. Series: Physical and mathematical sciences |
Institution
Mathematical and computer modelling. Series: Physical and mathematical sciences| _version_ | 1856543167336153088 |
|---|---|
| author | Пічугіна, Оксана Сергіївна |
| author_facet | Пічугіна, Оксана Сергіївна |
| author_sort | Пічугіна, Оксана Сергіївна |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2019-03-13T10:36:57Z |
| description | В статье предложены две модификации метода комбинаторных отсечений (МКО) решения линейных задач на вершинно расположенных комбинаторных множествах, основанные на построении ужесточенных отсечений по отношению к МКО отсечений. Данные модификации — метод отсечений комбинаторного многогранника (МОКМ) и метод поверхностных отсечений (МПО) — основаны на решении вспомогательной задачи поиска ближайшей точки поверхности к точке в заданном направлении. При этом в МОКМ в качестве поверхности выступает граница комбинаторного многогранника, в МПО — описанная вокруг него гладкая выпуклая поверхность. Последнее позволяет строить отсечения, являющиеся ужесточением как для МКО, так и для МОКМ. Для применения МПО необходимо решить задачу поиска полиэдрально-поверхностного представления комбинаторного множества, в то время как МОКМ использует только аналитический вид многогранника. |
| first_indexed | 2025-07-17T10:41:55Z |
| format | Article |
| id | mcm-mathkpnueduua-article-70278 |
| institution | Mathematical and computer modelling. Series: Physical and mathematical sciences |
| language | Russian |
| last_indexed | 2025-07-17T10:41:55Z |
| publishDate | 2016 |
| publisher | Кам'янець-Подільський національний університет імені Івана Огієнка |
| record_format | ojs |
| spelling | mcm-mathkpnueduua-article-702782019-03-13T10:36:57Z Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации Пічугіна, Оксана Сергіївна евклидово комбинаторное множество условная линейная комбинаторная оптимизация метод комбинаторных отсечений поверхностные отсечения полиэдральная и поверхностная релаксации полиэдрально-сферическое представление В статье предложены две модификации метода комбинаторных отсечений (МКО) решения линейных задач на вершинно расположенных комбинаторных множествах, основанные на построении ужесточенных отсечений по отношению к МКО отсечений. Данные модификации — метод отсечений комбинаторного многогранника (МОКМ) и метод поверхностных отсечений (МПО) — основаны на решении вспомогательной задачи поиска ближайшей точки поверхности к точке в заданном направлении. При этом в МОКМ в качестве поверхности выступает граница комбинаторного многогранника, в МПО — описанная вокруг него гладкая выпуклая поверхность. Последнее позволяет строить отсечения, являющиеся ужесточением как для МКО, так и для МОКМ. Для применения МПО необходимо решить задачу поиска полиэдрально-поверхностного представления комбинаторного множества, в то время как МОКМ использует только аналитический вид многогранника. Кам'янець-Подільський національний університет імені Івана Огієнка 2016-03-11 Article Article Рецензована Стаття application/pdf http://mcm-math.kpnu.edu.ua/article/view/70278 10.32626/2308-5878.2016-13.144-160 Mathematical and computer modelling. Series: Physical and mathematical sciences; 2016: Mathematical and computer modelling. Series: Physical and mathematical sciences. Issue 13; 144-160 Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки; 2016: Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки. Випуск 13; 144-160 2308-5878 10.32626/2308-5878.2016-13 ru http://mcm-math.kpnu.edu.ua/article/view/70278/65502 Авторське право (c) 2021 Оксана Сергіївна Пічугіна |
| spellingShingle | Пічугіна, Оксана Сергіївна Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации |
| title | Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации |
| title_full | Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации |
| title_fullStr | Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации |
| title_full_unstemmed | Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации |
| title_short | Поверхностные и комбинаторные отсечения в задачах Евклидовой комбинаторной оптимизации |
| title_sort | поверхностные и комбинаторные отсечения в задачах евклидовой комбинаторной оптимизации |
| topic_facet | евклидово комбинаторное множество условная линейная комбинаторная оптимизация метод комбинаторных отсечений поверхностные отсечения полиэдральная и поверхностная релаксации полиэдрально-сферическое представление |
| url | http://mcm-math.kpnu.edu.ua/article/view/70278 |
| work_keys_str_mv | AT píčugínaoksanasergíívna poverhnostnyeikombinatornyeotsečeniâvzadačahevklidovojkombinatornojoptimizacii |