Метод Гомори

Нахождение решения задачи целочис­ленного программирования методом Гомори начинают с опреде­ления симплексным методом оптимального плана задачи (1) — (3) без учета целочисленности переменных. После того как этот план найден, просматривают его компоненты. Если среди компо­нент нет дробных чисел, то найденный план является оптималь­ным планом задачи целочисленного программирования (1) — (4). Если же в оптимальном плане задачи (4) — (3) перемен­ная X] принимает дробное значение, то к системе уравнений (3) добавляют неравенство

∑ f (a^*_ij) x_j ≥ f (b^*_i ) (5)

j

и находят решение задачи (1) —(3), (5).

В неравенстве (5) a^*_ijи b^*_i — преобразованные исходные ве­личины a_ijи b_i, значения которых взяты из последней симплекс-таблицы, a f (a^*_ij) и f (b^*_i) — дробные части чисел (под дробной частью некоторого числа а понимается наименьшее неотрица­тельное число b такое, что разность между а и b есть целое). Если в оптимальном плане задачи (1) — (3) дробные значения

принимают несколько переменных, то дополнительное неравен­ство (5) определяется наибольшей дробной частью.

Если в найденном плане задачи (1) —(3), (5) перемен­ные принимают дробные значения, то снова добавляют одно до­полнительное ограничение и процесс вычислений повторяют. Проводя конечное число итераций, либо получают оптимальный план задачи целочисленного программирования (1) — (4), либо устанавливают ее неразрешимость.

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

∑ y_ijx_j ≥ f (b^*_i),

^j

где y_ij определяются из следующих соотношений:

1) для x_j которые могут принимать нецелочисленные зна­чения,

f (b^*_i) a^*_ij при a^*_ij< 0;

1- f (b^*_i)

2) для X_j, которые могут принимать только целочисленные значения,

f

f (b^*_i) 1-f ( a^*_ij) при f ( a^*_ij)> f (b^*_i)

1- f (b^*_i)

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

1. Используя симплексный метод, находят решение задачи (1)-(3) без учета требования целочисленности переменных.

2. Составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (1)—(3) имеет макси­мальное дробное значение, а в оптимальном плане задачи (1)—(4) должна быть целочисленной.

3. Используя двойственный симплекс-метод, находят реше­ние задачи, получающейся из задачи (1)—(3) в результате присоединения дополнительного ограничения.

4. В случае необходимости составляют еще одно дополни­тельное ограничение и продолжают итерационный процесс до получения оптимального плана задачи (1)—(4) или установ­ления ее неразрешимости.

Контрольные вопросы

1. Какие задачи относятся к задачам целочисленного программирования?
2. В чем сущность метода Гомори?
3. Каким образом строится сечение Гомори?
4. Сколько сечений Гомори можно построить?
5. Чему равна дробная часть положительного числа?
6. Чему равна дробная часть отрицательного числа?
7. Определить дробную часть следующих чисел:

4/5; 8/3; -12/7; 65/57; -4/7; - 8/3

1. Перечислить этапы алгоритма метода Гомори.

9. Тест на тему «Метод Гомори»

1.Задача целочисленного программирования - это……

а) разновидность транспортных задач.

б) экстремальная задача, переменные которой принимают лишь целочисленные значения.

в) вспомогательная задача, получаемая с помощью определенных правил непосредственно из условия исходной.

2. В математической модели задачи целочисленного программирования целевая функция и функция в системе ограничений могут быть:

а) линейными, нелинейными, смешенными.

б) только линейными.

в) нелинейными и смешенными.

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

а) определения симплексным методом оптимального плана задачи без учета целочисленности переменных.

б) построение двойственной к ней задачи.

в) приведение исходной системы к единому базису.

4. План считается оптимальным, если…

а) несколько переменных имеют дробное значение.

б) нет переменных с дробным значением.

в) все переменные имеют дробное значение.

5. В каком случае строится сечение Гомори?

а) если в оптимальном плане задачи нет дробных значений переменных.

б) все переменные имеют дробное значение.

в) если одна или несколько переменных принимают дробное значение.