Задачи целочисленного (дискретного) ЛП

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

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

,

, , (6.1)

, ,

.

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

Методы целочисленной оптимизации можно разделить на три основные группы: 1) методы отсечения; 2) комбинаторные методы; 3) приближенные методы.