Целочисленное программирование.

Метод Гомори

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

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

при ограничениях:

,

.

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

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

Напомним, что целой частью числа а называется наибольшее целое число, не превышающее а. Дробной частью числа а называется разность между числом а и его целой частью. Целую часть числа обозначают [а], а дробную часть – {а}, т.е. а = [а]+{а}.

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

1. Отбросив условие целочисленности, решить исходную задачу симплексным методом. Если получится целочисленное оптимальное решение, то задача решена.

2. Если в оптимальном решении не все переменные целочисленные, составить дополнительное ограничение (сечение Гомори). Сечение строится по базисной переменной, имеющей наибольшую дробную часть. Пусть в оптимальном решении базисная переменная, имеющая наибольшую дробную часть x_t,

(1)

,

где J - множество индексов свободных переменных.

Разбить все коэффициенты и свободный член (1) на два слагаемых - целую и дробную часть.

Неравенство

(2)

называется сечением Гомори. Дополнительное ограничение имеет вид

(3)

,

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