Метод відсікань Гоморі

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

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

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

Крок 1. Відшукати симплексним методом оптимальне рішення задачі лінійного програмування з цільовою функцією (6.1) та лінійними обмеженнями (6.2)
без урахування умови цілочисловості (6.3). Нехай воно має вид: . Якщо це оптимальне рішення цілочислове – обчислення припиняються. В противному разі треба перейти до кроку 2.

Крок 2. Обрати дробову компоненту оптимального рішення. Її вибір є достатньо довільним, але для підвищення збіжності обирається компонента з більшою дробовою частиною.

Нехай такою компонентою буде , тоді k - й рядок симплекс-таблиці звуть індексним. Рівняння цього рядка:

або

,

(6.4)

де – базисна змінна, – небазисні (вільні) змінні відповідного оптимального рішення.

Записати нерівність відсікання Гоморі:

,

(6.5)

де фігурні дужки означають дробову частину числа.

До лівої частини нерівності (6.5) додати додаткову невід’ємну змінну і записати таке рівняння

.

(6.6)

Ввести рівняння (6.6) в систему обмежень (6.2).

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

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

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

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

Наприклад,

1) , , ;

2) , , .

Задача 6.1. Для придбання обладнання для сортування зерна фермер виділяє 34 грош. од. Обладнання має бути розташовано на площі, що не перевищує 60 кв. м. Фермер може замовити обладнання двох видів: машини типу А вартістю 3 грош. од., що потребують площу 3 кв. м і забезпечують продуктивність за зміну 2 т зерна, і машини типу B вартістю 4 грош. од., що потребують площу 5 кв. м і забезпечують продуктивність за зміну 3 т зерна.

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

Дата добавления: 2014-11-06