20. Особенности задач целочисленного программирования

Решение целочисленных задач намного сложнее, чем обычных задач линейного программирования.

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

Требование целочисленности ухудшает значение целевой функции:

- Значение целевой функции в целочисленной задачи минимизации меньше, чем в той же задаче без требования целочисленности.

- Значение целевой функции в целочисленной задачи минимизации больше, чем в той же задаче без требования целочисленности.

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

Целевая функция может иметь локальные минимумы (максимумы) не являющиеся глобальными.

Отсутствуют простые способы позволяющие определить, является ли данное допустимое решение оптимальным.

Методы решения задач дискретного программирования.