Метод Гоморі. Розв "язання завдань цілочисельної програми

Метод Гоморі. Розв "язання завдань цілочисельної програми

Маса завдань економічного характеру, проблем планування і навіть вирішення питань з інших сфер людської життєдіяльності пов 'язано зі змінними, що відносяться до цілих числах. В результаті їх аналізу та пошуку оптимальних способів вирішення з 'явилося поняття екстремальної задачі. Її особливостями є вищевказана особливість приймати ціле значення, а саме завдання розглядається в математиці, як цілочисельне програмування.                 


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


Метод Гоморі отримав свою назву на ім 'я математика, першим розробив у 1957-1958 роках алгоритм, який досі широко використовується для вирішення цілочисельних завдань лінійного програмування. Канонічна форма завдання цілочисельного програмування дозволяє доступно і в повному обсязі розкрити переваги цього методу.

Метод Гоморі до лінійного програмування істотно ускладнює завдання знаходження оптимальних значень. Адже цілочисельність є основною умовою, додатково до всіх параметрів завдання. Нерідкі випадки, коли завдання, маючи допустимі (цілочисельні) плани, при наявності у цільової функцій обмежень на допустимій безлічі, у рішенні не приходить до досягнення максимуму. Це відбувається через відсутність саме цілочисельних рішень. Без цієї ж умови, як правило, у вигляді рішення знаходиться відповідний вектор.

Для обґрунтування численних алгоритмів при вирішенні завдань виникає необхідність здійснювати накладання різних додаткових умов.

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

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

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


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

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

При побудові обмеження слід вибирати компоненту оптимального плану з найбільшою дробовою частиною. Саме це обмеження буде додано до вже наявної симплексної таблиці.

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

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