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

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

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

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

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

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

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

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

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

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

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

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

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

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