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

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

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

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

Відео: Метод Гоморі - Cutting-plane method

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

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

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

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

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

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

Відео: Рішення задачі цілочислового програмування методом гілок і меж

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

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

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

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