Досліджуються області визначення задач евклідової комбінаторної оптимізації на переставних множинах, зокрема, розглядаються системи обмежень загального переставного, загального поліпереставного многогранників і многогранника - області допустимих розв'язків задачі з лінійною функцією цілі, до якої зводиться задача з дробово-лінійною функцією цілі на загальній множині переставлень. Встановлено незвідні системи лінійних обмежень зазначених многогранників та викладено деякі їх нові властивості. а також новий метод знаходження точного розв'язку задачі мінімізації зваженої довжини зв'язучої сітки при лінійному розташуванні прямокутних елементів.

Розглянуто задачу визначення ряду домінантності для заданої множини властивостей у двох аспектах: встановлення допустимої множини розв'язків (рядів домінантності) та визначення оптимального з них. Формально задачі представлені як розмиті оптимізаційні задачі на просторі виборок. Розглянуто один клас комбінаторних оптимізаційних задач для формалізації, розв'язку і дослідження яких застосовуються поняття теорії нечітких множин Заде.

Розглянуто метод побудови точних і наближених рішень задачі (0,1)-рюкзак на основі рангового підходу та оптимізації за напрямком у дискретному просторі станів. Показано, що цей метод дозволяє будувати точні рішення задачі (0,1)-рюкзак протягом поліноміального часу з довірчою вірогідністю 0,95.

Описано нову форму квадратичної задачі про призначення. На основі властивостей цієї форми задачі отримано нові межі цільової функції.

Запропоновано монотонну покрокову процедуру для наближеного розв'язку адитивної задачі про розподіл завдань між виконавцями з можливим дублюванням деяких завдань. Постановка такого роду виникає, зокрема, під час дослідження задачі кількох комівояжерів, для якої на розподільному рівні оптимізації у класі покриттів вона може дати кращий результат, ніж у розбиттях. Наведено результати числових розрахунків.

У поданій статті запропонована нова методика статистичного дослідження ПДС-алгоритмів для важковирішуваних комбінаторних задач, на підставі якої визначається статистична значимість поліноміальних підкласів, що виділяються поліноміальною складовою ПДС-алгоритмів, та галузь їх ефективного застосування. Визначаються статистичні параметри, що дозволяють знаходити умови застосування ПДС-алгоритму, який був побудований для однієї важковирішуваної комбінаторної задачі, як ефективний засіб розв'язання інших задач з класу NP.

Запропоновано алгоритми, які дозволяють підвищити точність розв'язання задачі 0,1-рюкзак, і паралельні обчислювальні структури для їхньої реалізації в масштабі реального часу.

Работа посвящена актуальной проблеме нахождения и обоснования полиномиальной оптимизации, которая является труднорешаемой. Выявлен нетривиальный полиномиально разрешимый класс двукритериальной задачи о сочетаниях. Осуществлено конструктивное доказательство теоремы, т.е. построен соответствующий алгоритм, который гарантирует нахождение искомого множества альтернатив с полиномиальной вычислительной сложностью.

Запропоновано новий метод генерування комбінаторних конфігурацій різних типів (перестановок, розбиття множини на підмножини, розбиття числа), який базується на властивості періодичності цього процесу. Застосування методу показано на прикладі упорядкування перестановок та розбиття числа.

Розглянуто задачу комівояжера, її застосування та деякі алгоритми її реалізації. Наведено результати проведеного числового експерименту з дослідження методу локальних оптимальних послідовностей.

Рассмотрена задача коммивояжера, ее применение, некоторые алгоритмы, решающие ее. Приведены результаты проведенного вычислительного эксперимента по исследованию метода локальных оптимальных последовательностей.

In the given article the traveling salesman problem and its applications are reviewed. Some algorithms solving it are reviewed. There are presented results of the computing experiment held as a part of research of the method of optimal local sequences.

Наведено загальну характеристику оптимізаційних задач розміщення геометричних об'єктів, розглянуто методи пошуку екстремумів функцій мети, розкрито суть багатоекстремальних комбінаторних задач. Описано існуючі методи розв'язання задач розміщення прямокутних об'єктів, які визначені на множині перестановок.

Приведена общая характеристика оптимизационных задач размещения геометрических объектов, рассмотрены методы поиска экстремумов функций цели, раскрыта сущность многоэкстремальных комбинаторных задач. Описаны существующие методы решения задач размещения прямоугольных объектов, определенные на множестве перестановок.

Наведено результати дослідження властивостей задач комбінаторної оптимізації з дробово-лінійними цільовими функціями на переставних множинах. Вперше побудовано алгоритми розв'язування таких задач, удосконалено метод комбінаторного відсікання. Здійснено перехід від задачі з дробово-лінійною функцією цілі до задачі з лінійною функцією цілі. Визначено властивості області допустимих розв'язків задачі, опукла оболонка є многогранником. Сформульовано та доведено теорему про грані многогранника, визначено критерії вершини та суміжності граней. Побудовано незвідну систему лінійних обмежень даного многогранника. Запропоновано моделі прикладних задач у вигляді багатокритеріальних задач оптимізації з допустимою областю, що має переставні властивості й обгрунтовано підхід щодо їх розв'язання.

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

Розглянуто полікомбінаторні множини, їх опуклі оболонки та задачі оптимізації на них. Для багатогранників поліпереставлень і полірозміщень доведено властивості невиродженості й еквівалентності. На підставі застосування методів динамічного програмування, гілок і меж розв'язано задачу розміщення об'єктів обслуговування як задачу евклідової полікомбінаторної оптимізації. Проведено аналіз застосованих алгоритмів і доведено їх ефективність.

Рассмотрены поликомбинаторные множества, их выпуклые оболочки и задачи оптимизации на них. Для многогранников полипереставлений и полиразмещений доказаны свойства невырожденности и эквивалентности. На основе применения методов динамического программирования, ветвей и границ решена задача размещения объектов обслуживания как задача евклидовой поликомбинаторной оптимизации. Проведен анализ примененных алгоритмов и доказана их эффективность.

Рассмотрены узловые вопросы и изложены основные результаты, касающиеся проблемы коммивояжера, объединяющей многочисленные задачи комбинаторной математики. Показана взаимосвязь проблем оптимизации циклических процессов с фундаментальными положениями теории вычислительной сложности и вопросами применения компьютерных технологий. Представлены модели и методы решения задач типа коммивояжера, сопровождаемые числовыми примерами и практическими приложениями.

Введено новое комбинаторное множество - композиция перестановок. Решена задача оптимизации линейной функции на композиции перестановок с использованием введенного отношения линейного порядка.

Введено нову комбінаторну множину - композицію перестановок. Розв'язано задачу оптимізації лінійної функції на композиції перестановок з використанням введеного відношення лінійного порядку.

Розглянуто опис системою лінійних нерівностей опуклої оболонки множини полірозміщень - багатогранника полірозміщень. Висвітлено структуру даного багатогранника. Наведено розв'язок безумовної лінійної задачі оптимізації на полірозміщеннях. Обгрунтовано оцінки та достатні умови мінімумів у безумовних задачах на полірозміщеннях для опуклих та сильно опуклих цільових функцій. Розглянуто метод відсікання для одного класу лінійних частково комбінаторних задач евклідової комбінаторної оптимізації. Обгрунтовано алгоритм даного методу.

Рассмотрено описание системой линейных неровностей выпуклой оболочки множества полиразмещений - многогранника полиразмещений. Освещена структура данного многогранника. Приведено решение безусловной линейной задачи оптимизации на полиразмещениях. Обоснованы оценки и достаточные условия минимумов в безусловных задачах на полиразмещениях для выпуклых и сильно выпуклых целевых функций. Рассмотрен метод отсекания для одного класса линейных частично комбинаторных задач евклидовой комбинаторной оптимизации. Обоснован алгоритм данного метода.

Проанализированы разновидности методов муравьиных колоний. На основании проведенного анализа предложены рекомендации, касающиеся возможности применения конкретной разновидности такого метода для решения определенного класса оптимизации задач.

Проаналізовано різновиди методу мурашиних колоній. На підставі проведеного аналізу запропоновано рекомендації щодо можливості застосування конкретного різновиду такого методу для вирішення визначеного класу оптимізаційних задач.

Приведены результаты исследования методов и алгоритмов решения оптимизационных задач на размещениях с дополнительными ограничениями. Рассмотрены два подхода к решению данных задач: метод комбинаторного отсечения, идейно близкий методам отсечения в дискретной оптимизации, и метод построения лексикографической эквивалентности, основанный на направленном переборе классов эквивалентности.

Індекс рубрикатора НБУВ: В173.112.1

Рубрики:

Комбінаторне програмування

Шифр НБУВ: Ж15477 Пошук видання у каталогах НБУВ 

Наведено повний опис простору лінійності конуса матриць Монжа та всіх його мінімальних граней. На підставі даного опису надано повну характеризацію матриць Монжа. Обговорено можливі застосування одержаних результатів.