Доведемо виконання умови 2). Нехай x0 - допустимий розв’язок задачі (12.4-12.7), тобто усі координати x0 цілочисельні. Після підстановки x0 у рівняння (12.8) маємо

x⁰_k + a’_ij x⁰_j = b’_i,

j N

або

x⁰_k + ([a’_ij ] + {a’_ij }) x⁰_j = [ b’_i ] + { b’_i }.

j N

Можна зібрати дробові доданки у ліву частину рівняння, а цілі - у праву.

- { b’_i } + {a’_ij} x⁰_j = -x⁰_k - [a’_ij ] x⁰_j + [ b’_i ]. (12.10)

j N j N

Тому - { b’_i } + {a’_ij}x⁰_j – ціле число.

j N

Оскільки x⁰_j 0, {a’_ij} 0 j N, і 0 < { b’_i } <1, маємо

- { b’_i } + {a’_ij} x⁰_j > -1.

j N

Враховуючи, що ліва частина останньої нерівності – ціле число, остаточно отримуємо

- { b’_i } + {a’_ij} x⁰_j 0,

j N

що і треба було довести.

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

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

2. Якщо отриманий розв’язок цілочисельний, то він є розв’язком вихідної задачі – кінець алгоритму. Якщо отримано дробовий розв’язок, то згідно з обмеженням (12.9) у поточну симплекс-таблицю увести додаткове обмеження-рівняння, що є уявленням правильного відтинання у канонічній формі. На k-й ітерації це рівняння має вигляд

x_n+k + {a’_ij} x_j = - { b’_i }.

j N

3. Отримана симплекс-таблиця є двоїсто допустимою; застосувати до неї двоїстий симплекс-метод. Якщо розв’язок поточної задачі не існує, вихідна задача розв’язку не має – кінець алгоритму. Інакше перейти до кроку 2.

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

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

Дата добавления: 2014-01-13