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

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

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

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

_m

F=∑ c_jx_i (1)

^j=1

при условиях

_m

∑ a_ij=b_j (j=1,m),

ⁱ⁼¹ (2)

Xj≥0(j=1, n), (3)

Xj — целые (j= 1, п). (4)

Если найти решение задачи (1) —(4) симплексным мето­дом, то оно может оказаться как целочисленным, так и нет (при­мером задачи линейного программирования, решение которой всегда является целочисленным, служит транспортная задача). В общем же случае для определения оптимального плана задачи (1) — (4) требуются специальные методы. В настоящее время существует несколько таких методов, из которых наиболее из­вестным является метод Гомори, в основе которого лежит описанный выше симплексный метод.