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

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

Основным методом, позволяющим найти целочисленное решение за конечное число шагов являетсяметод отсечения плоскостей (метод Гомори).

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

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

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

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

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

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

Z = (1)

При ограничениях неравенств:

(2)

При условиях:

(3)

Симплексная таблица:

Σ						Q

Составляем дополнительное ограничение:

Пусть не является целым числом

=