Page 83 - 4719

ПРАКТИЧНЕ ЗАНЯТТЯ 14

Тема: МЕТОДИ РОЗВ’ЯЗКУ ЦІЛОЧИСЛОВИХ
ОПТИМІЗАЦІЙНИХ ЗАДАЧ

Мета заняття: ознайомити студентів з існуючими
методами розв’язку цілочислових оптимізаційних задач

1. Основні теоретичні положення

Для розв’язку цілочислових оптимізаційних задач
застосовують такі методи: метод Гоморі (відсікань), метод
віток і меж, метод Беллмана тощо.

Метод Гоморі

За допомогою відсікань виділяють цілочислові частини
області допустимих значень (ОДЗ). Існує можливість
розв'язати дану задачу у певному розумінні частково,
послідовно відсікаючи від множини ОДЗ деякі її частини за
допомогою так званих відсікаючих площин. Ідея методів
відсікання полягає в наступному: розв'язується ЗЛП, одержана
з цілочислової відкиданням умови цілочисловості змінних.
Якщо її розв'язок є цілочисловим, то він же є і розв'язком
цілочислової задачі. Якщо ж задача розв'язку не має, то і
ЦЗЛП розв'язку не має. Якщо розв'язок ЗЛП не є
цілочисловими, то від розв'язаної ЗЛП переходять до нової
допоміжної ЗЛП шляхом додавання лінійного обмеження, яке
задовольняє усі цілочислові розв'язки ЦЗЛП, але не
задовольняє одержаний нецілочисловий розв'язок початкової
ЗЛП. Це додаткове лінійне обмеження визначає деяку
відсікаючу площину і називається правильним відсіканням.
Додавання нових правильних відсікань до початкової
допоміжної ЗЛП здійснюється доти, поки на деякому кроці не
буде одержаний цілочисловий розв'язок допоміжної задачі,
який, очевидно, буде оптимальним розв'язком вихідної ЦЗЛП.

82