Цілочислове математичне програмування

Мета роботи – навчитися розв’язувати задачі лінійного програмування за умови цілочисловості змінних.

У результаті виконання роботи студент повинен:

ЗНАТИ алгоритм методу Гоморі;

УМІТИ здійснювати перехід під одного плану до іншого;

МАТИ УЯВЛЕННЯ про правила побудови правильних відтинань.

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

Задача цілочислового програмування (ЦП) формулюється так:

(1)

(2)

(3)

(4)

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

1) повинне бути лінійним;

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

3) не повинне відтинати жодного цілочислового розв’язку.

Додаткове обмеження, яке має вказані властивості, називається правильним відтинанням.

Далі задача розв’язується з урахуванням нового обмеження.

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

Нехай є нецілочисловим. Тоді можна довести, що обмеження

(5)

має властивості правильного відтинання.

{ }- дробова частина числа.

Цілою частиною [ a ] числа а називається найближче ціле число до даного числа а,яке не перевищує а.

Дробовою частиною { a }числа а називається {a}=a-[a].

завжди.

Алгоритм методу Гоморі:

1 Симплекс-методом розв’язують задачу (1)-(3) без урахування цілочисловості. Якщо всі компоненти оптимального розв’язку – цілі числа, то цей розв’язок є оптимальним і для задачі (1)-(4).

Якщо перша задача не має розв’язку, то і цілочислова задача не має розв’язку.

2 Якщо серед компонент оптимального розв’язку є нецілі, то обирається компонента з найбільшою дробовою частиною і за відповідним рівнянням формується правильне відтинання (5).

3 Нерівність (5) введенням невід’ємної додаткової змінної перетворюється на рівносильне рівняння і включається до вихідних обмежень (1).

4 Одержану розширену задачу розв’язують симплекс-методом. Якщо розв’язок буде цілочисловим, то задача ЦП є розв’язаною. Якщо ж ні, то повертаються до пункту 2.

Якщо задача ЦП має розв’язок, то за скінчене число кроків знаходиться оптимальний розв’язок задачі.