Главная | Обратная связь | Поможем написать вашу работу!

Метод відтинання. Додаткове обмеження

Якщо розв’язувати лінійну цілочислову задачу методами лінійного програмування, не враховуючи цілочисловості змінних, а потім усім дробовим змінним привласнювати найближчі цілі числа, то такий розв’язок у багатьох випадках не буде оптимальним, особливо, коли числа мають малі значення. Крім того, якщо вибрати за оптимальну найближчу точку з цілочисловими координатами, то вона може вийти за межі області допустимих розв’язків.

Поява умови цілочисловості геометрично відображує область допустимих розв’язків як сукупність дискретних точок, тобто цілочислову решітку.

Найпоширенішими методами розв’язування цілочислових задач є підхід, який використовує метод послідовного відтинання частини області допустимих розв’язків, яка не має цілочислових точок. Типовим методом, який використовує таку ідею, є алгоритм Гоморі.

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

Відтинання повинно задовольняти таким властивостям:

– проходити принаймні через одну цілочислову точку;

– повинно бути лінійним;

– має відтинати оптимальний розв’язок з не цілочисловою точкою;

– не повинно виключати цілочислових точок.

Відтинання, що має такі властивості, називається правильним.

Після доповнення таким обмеженням математичної моделі задачі отримується нова модель з рівняннями, тобто складається розширена модель початкової задачі.

Розглянемо область допустимих розв’язків, яка відображена на рис.7.2 трикутником АВС.

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

Нехай не цілочислова точка

А А відповідає максимуму . Щоб

І знайти цілочислову точку, вво-

С ІІ дять додаткові обмеження І та ІІ

В один за одним так, щоб найближ-

ча точка області допустимих роз-

в’язків мала цілочислові корди-

Рис.7.2 нати. Такі послідовні відтинання

будуються доки не знайдеться оптимальна цілочислова точка.

Найпоширенішим методом, основаним на методі відтинання, є алгоритм Гоморі, який має кілька модифікацій і дозволяє:

– розв’язувати як часткові, так і повністю цілочислові задачі лінійного програмування (І - ІІ алгоритм Гоморі);

– знаходити розв’язок за кінцеве число кроків розв’язування;

– використовувати алгоритм у випадку, коли значення цільової функції повинно теж бути цілочисловим.

Ідея методу Гоморі базується на симплексному методі. Пошуки оптимального розв’язку ведуться без урахування цілочисловості змінних і у випадку, коли розв’язок нецілочисловий, вводять додаткове лінійне обмеження.

Модель з додатковим обмеженням знову розв’язується симплекс-методом (розширена математична модель) і такий процес пошуку ведеться до знайдення оптимальної цілочислової точки або доводиться відсутність такого розв’язку.

Розглянемо вигляд додаткового обмеження для такої математичної моделі:

– цільова функція