Метод Гомори

Применяется этот метод для решения задачи целочисленного программирования общего вида. В основе метода лежит симплекс метод(С-М) и решение начиняется с определения симплекс-методом оптим-ного опорного плана задачи без учета целочисленного решения. Имеется 2е интерпретации данного метода:1-при решении полностью целочисленных задач-назыв.»первым алгоритмом Гомори»,2- при решении частично целочисленных задач «2й алгоритм Гомори»

Рассмотрим задачу Линейного программирования (ЛП) в канонич. форме, при целых значениях

(1)

(2)

(3)

x_j-целые, (4)

Итак, решение начин-тся с опред-ния С-оМоптим0ного опорного плана задачи(1)-(4).Если среди элементов оптим-ного опорного плана нет дробных чисел, то найденный план явл.оптимальным з-чи цел-ного прог-ния.(1-4).Если же в оптим-ном плане з-чи (1-4)переем-я x_j принимает дробное знач-е, то к с-ме ур-ний(2) добавляется нер-во:

(5)

и находят оптим-ное реш-е з-чи(1-3),(5).Вид доп-ного огран-ния (5) опред-ет необ-ть использ-ния двойственного С-М для решения этой задачи.

Где

и -дробные части числовых знач-ний коэф-тов и , взятых из строки, содержащей выбранную базисную переменную x_j из помледней С- таблицы.

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

Если требование цело-сти(4) относится лишь к некоторым перем-ным, такие задачи назыв. частично целочисленными.

Алгоритм метода Гомори:

1)Опред-ние оптим решения исходной задачи без учета требований целочисл-ных переем-ных

2)Составление доп-ного ограничения для базисной переменной, кот-я в оптим-ном плане з-чи имеет макс дробное значение, а оптим-ом опорном плане исходной з-чи должна быть целочисленной.

3)Опред-ние оптим-ного опорного плана з-чи с учетом присоединного доп-ного ограничения. При этом используя двойт-ный С-М.

4)Анализ полученного рез-та. Процесс решения заканчивается, если получено оптим решение, или ее неразрешимость.в противном случае процесс родолжается,начиная с п.2

Это метод, как показала практика, не обеспечивает высокой эф-ти вычислит-ных процедур для решения задач большой размерности.