Постановка задачи целочисленного программирования (ЗЦП)

ЗЦЛП формируется следующим образом:

Найти такое решение (план) Х=(х₁х₂… х_n), при котором линейная ф-ция:

_n

Z=∑c_jx_j принимает max или min значение, при ограничениях:

_j=1

_n

∑ a_ijх_j=b_i, i=1,2, …m;

_j=1

x_j≥0, j=1,…n; x_j- целые числа.

По смыслу решение экономических задач должны выражаться в целых числах (кол-во единиц неделимой продукции, станков, судов). Для решения ЗЦП используется ряд методов. Самый простой - обычный метод линейного программирования. В случае, если компоненты оптимального решения нецелочисленные, их округляют до ближайших целых чисел, однако округление может привести к далекому от оптимального решению, поэтому используют следующие методы:

- методы отсечения;

- комбинаторные;

- приближенные;