Метод Гомори. Американским ученым Р.Гомори был разработан первый точный метод решения линейных задач целочисленного и частично целочисленного программирования

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

Однако эту идею можно видоизменить следующим образом. Пусть Q – многогранное множество, внутри которого располагается R. Будем последовательно сужать множество Q до многогранников Q ₁, Q ₂, …, причем так, чтобы Процесс этот будем повторять до тех пор, пока не получится целочисленное решение соответствующей задачи линейного программирования. Оно и будет решением исходной задачи ЦП.

Переход от многогранника Q_k к многограннику Q_{k +1} можно осуществлять различными способами. Например, получив нецелочисленное решение задачи ЛП на множестве Q_k, можно отсечь это решение подходящей гиперплоскостью так, чтобы сохранить все допустимые целочисленные точки. Такой переход от Q_k к Q_{k +1} называется правильным отсечением. На использовании правильных отсечений и основан метод Гомори.

Дата добавления: 2014-01-06