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

Масса задач экономического характера, проблем планирования и даже решение вопросов из других сфер человеческой жизнедеятельности связано с переменными, относящимися к целым числам. В результате их анализа и поиска оптимальных способов решения появилось понятие экстремальной задачи. Её особенностями является вышеуказанная особенность принимать целое значения, а сама задача рассматривается в математике, как целочисленное программирование.

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

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

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

Метод Гомори применительно к линейному программированию существенно усложняет задачу нахождения оптимальных значений. Ведь целочисленность является основным условием, дополнительно ко всем параметрам задачи. Нередки случаи, когда задача, имея допустимые (целочисленные) планы, при наличии у целевой функций ограничений на допустимом множестве, в решении не приходит к достижению максимума. Это происходит по причине отсутствия именно целочисленных решений. Без этого же условия, как правило, в виде решения находится подходящий вектор.

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

Видео: Лекция 2 Симплекс-метод

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

Также для гарантированности целочислености функции предполагают, что коэффициенты значений также являются целыми числами. Невзирая на строгость таких условий, послабить их удаётся на немного.

Метод Гомори, по сути, предполагает построение ограничений, которые отсекают решения, не являющиеся нецелочисленными. При этом не происходит отсечения ни одного решения целочисленного плана.

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

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

При построении ограничения следует выбирать компоненту оптимального плана с наибольшей дробной частью. Именно это ограничение будет добавлено к уже имеющейся симплексной таблице.

Находим решение полученной задачи, используя обычные симплексные преобразования. Проверяем решение задачи на наличие целочисленного оптимального плана, если условие выполняется, то задача решена. Если опять был получен результат с наличием нецелочисленных решений, то вводим дополнительное ограничение, и повторяем процесс вычислений.

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