мується нове додаткове обмеження і процес обчислень повторюється. p align="justify"> Алгоритм Гоморі дозволяє за кінцеве число кроків прийти до оптимального целочисленному рішенням, якщо воно існує.
З геометричної точки зору кожним додатковим лінійним обмеження в n-вимірному просторі відповідає певна гіперплощина, що відсікає від багатогранника рішень деяку його частину, включаючи і оптимальну на даному етапі нецілочисельне вершину. p align="justify"> При цьому всі точки з цілочисельними координатами, в тому числі і шукана оптимальна, залишаються в усіченому многограннике. Так як безліч цілих точок усіченого багатогранника збігається з безліччю цілих точок вихідного багатогранника, то зрозуміло, що якщо оптимальне рішення ЗЛП на усіченому многограннике задовольняє умові цілочисельності, то воно є оптимальним цілочисловим рішенням і вихідної задачі. Через кілька операцій відсікання шукана целочисленная крапка виявляється спочатку на кордоні, а потім стає оптимальною вершиною неодноразово усіченого багатогранника рішень. p align="justify"> Може виявитися, що багатогранник рішень не містить жодної целочисленной точки. У цьому випадку, скільки б не вводили додаткових обмежень, цілочисельного допустимого рішення отримати не можна. p align="justify"> Для кращого розуміння суті питання звернемося до наочної ілюстрації випадку п = 2 (рис. 4.1). Обмеження завдання визначають на площині x1Ox2 деякий багатокутник М, у вершині якого, якщо не враховувати умови цілочисельності, досягається максимум цільової функції. Усередині цього багатокутника є кінцеве безліч точок, яким відповідають рішення з цілочисельними значеннями змінних (на малюнку вони позначені кружечками). На малюнку показані три прямі l1, l2, l3 відповідні трьом додатковим лінійним обмеженням. Кожна з прямих відсікає частину області допустимих рішень. Так, після відсікання частини області прямої оптимальної виявляється вершина , і, нарешті, оптимальної стає целочисленная вершина . Основне в алгоритмі - складання додаткового обмеження, тобто відтинає гіперплощини, яка називається правильним відсіканням. Правильне відсікання повинно відповідати таким умовам: 1) бути лінійним, 2) відсікати знайдене оптимальне нецілочисельне рішення задачі (4.1) - (4.3); 3) не відсікати жодної з цілочисельних точок задачі (4.1) - (4.5).
Малюнок 4.1
В
Формування правильного відсікання. Після кожної ітерації система обмежень має вигляд
(4.5)
де {БП} - безліч базисних змінних.
Якщо виконується умова оптимальності задачі, то знаходимо оптимальне рішення. Якщо, всі компоненти оптимального плану цілочисельних, то задача вирішена. Припустимо, що деякі ( - нецілі. Нехай компонента i0 - неціла. Розг...
