ГОМОРИ МЕТОД

— метод решения задачи линейного программирования целочисленного, сводящий ее решение к решению последовательности задач линейного программирования путем отсечения на каждом шаге оптимального нецелочисленного решения. Метод предложил амер. математик Р. Гомори.

Пусть задача целочисленного линейного программирования записана в виде:

где все — заданные целые числа, — переменные задачи и базис оптим. плана задачи линейного программирования — знак транспонирования. Умножив ур-ния (2) на перепишем их в виде:

или

где N — множество индексов векторов не принадлежащих базису; все преобразованные значения соответствующих коэффициентов Подставляя ур-ние (5) в выразим линейную форму через небазисные переменные

где значение линейной формы, оценки небазисных векторов (см. Симплекс-метод) на оптим. плане. Если все соответствующие данному плану целые числа, то решение задачи (1—4). Если же некоторые из дробные, выберем одно из них, напр., и, отправляясь от строки системы (5), построим дополнительное ограничение, которому не удовлетворяет полученное нецелочисленное решение но удовлетворяют все целочисленные планы (1—4). Обозначим через наибольшее целое число, не превосходящее тогда дробная часть Искомое ограничение записывается в виде:

План ему не удовлетворяет, т. к. для пего левая часть неравенства (7) равна нулю, а правая — дробная часть нецелой величины больше нуля. В качестве I можно выбрать и 0, т. е. строить дополнительное ограничение по ур-нию (6). Действительно, целочисленность всех гарантирует целочисленность на всех целочисленных планах. Ограничение (7) переписывается в виде:

и добавляется к условиям (2).

Матрица

получаемая расширением при добавлении к системе (2) строки (8) и переменной является псевдобазисом расширенной задачи. Для решения этой задачи пользуются двойственным симплекс-методом, начиная решение с псевдобазиса А. Процесс добавления новых ограничений продолжается до тех пор, пока на одном из шагов не будет получен оптим. целочисленный план или не выявится неразрешимость задачи. В первом случае полученный план является решением задачи (1—4), во втором — задача (1—4) не имеет целочисленных планов. Г. м. сходится к решению за конечное число шагов, если выполнено хотя бы одно из условий: существует решение задачи (1—4) или значение линейной формы (1) ограничено снизу. Если ограничения целочисленности (4) наложены лишь на часть переменных, описанное правило построения дополнительного ограничения (8) неприменимо. Однако известно видоизменение этого правила (разработанное также Р. Гомори) и для такой задачи. Г. м. обобщен на задачи выпуклого целочисленного программирования, дискретного программирования и в некоторых других направлениях.

Лит. см. к ст. Программирование целочисленное.

В. А. Трубин.