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

Специфика задач целочисленного программирования заключается в том, что на переменные x_i и функцию цели F(x) налагается дополнительное ограничение – условие целочисленности. Целочисленное программирование иногда называют дискретным программированием. Если требование целочисленности распространяется не на все переменные, а только на часть из них, то задача называется частично целочисленной.

В большинстве случаев целочисленные задачи сильно отличаются от своих непрерывных аналогов и требуют для решения специальных методов. Условно методы решения задач целочисленного программирования можно разделить на три основных группы: методы отсечения; комбинаторные методы; приближенные методы.

Процедура решения задачи методом отсечения осуществляется следующим образом:

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

2. Строятся дополнительные линейные ограничения, отсекающие от ОДЗП ту её часть, в которой содержится оптимальное решение и не содержится ни одного целочисленного решения.

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

Способы построения дополнительных линейных ограничений известны как алгоритмы Гомори. Они различны для полностью и частично целочисленных задач и обеспечивают решение задачи за конечное число шагов.