Ольховський Д. М. Точні і наближені методи відсікання для розв'язування лінійних оптимізаційних задач на переставленнях

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