ПРОГРАМНИЙ КОМПЛЕКС ДЛЯ РОЗВ’ЯЗУВАННЯ ЕВКЛІДОВИХ КОМБІНАТОРНИХ ОПТИМІЗАЦІЙНИХ ЗАДАЧ ТОЧНИМИ ТА НАБЛИЖЕНИМИ МЕТОДАМИ

Анотація

Задачі комбінаторної оптимізації набувають усе більшого поширення на практиці. Це зумовлено тим, що велика кількість прикладних задач описується моделями, в яких розв’язок визначений на комбінаторних множинах. Розв’язування таких задач вимагає розробки нових або модифікації вже наявних методів, написання алгоритмів та їх програмної реалізації. Мета роботи – створити програмний продукт для розв’язування евклідових комбінаторних оптимізаційних задач точними та наближеними методами. При цьому важливим є врахування структури комбінаторних конфігурацій, зокрема, із застосуванням теорії графів. Важливим, окрім розробки нових математичних підходів, є врахування сучасного стану обчислювальної техніки – наявність потужних багатопроцесорних систем. Методологія. Для розробки програми було вибрано мову програмування високого рівня Object Pascal середовища програмування Delphi. Наукова новизна. У роботі проведено опис розробленого програмного комплексу, який реалізує методи для розв’язування задач комбінаторної оптимізації різними методами. Представлений програмний продукт дає змогу розв’язувати задачі лінійного програмування методом комбінаторного відсікання на основі алгоритму Кармаркара для умовних лінійних задач комбінаторної оптимізації на переставленнях. На відміну від відомих методів комбінаторного відсікання для задач на вершинно розташованих множинах, тут допоміжна задача лінійного програмування розв’язується не певною різновидністю симплекс-методу, а поліноміальним алгоритмом Кармаркара. Розроблений програмний продукт реалізує також другий метод комбінаторного відсікання в умовних лінійних задачах на вершинно розташованих множинах з виключенням виродженості в допоміжних задачах лінійного програмування. Також знайдено розв’язок задачі комбінаторної оптимізації модифікованим методом з можливістю приєднання необхідних обмежень та відкидання зайвих. Такий підхід дозволив значно збільшити вимірність задач, що можуть бути розв’язані. Висновки. Завдяки програмному комплексу стало можливим розв’язування комбінаторних задач оптимізації із застосуванням представлення комбінаторного многогранника у вигляді графа значних вимірностей. Створений програмний продукт дозволив провести чисельні експерименти всіма вище зазначеними методами для підтвердження їх практичної ефективності та коректності.