§ 8. Задача целочисленного линейного программирования

8.1. Рассмотрим задачу линейного программирования с дополнительным условием целочисленности — задачу целочисленного линейного программирования. Максимизировать

при условиях

Если то задача называется полностью целочисленной задачей линейного программирования, если частично целочисленной задачей линейного программирования. Иногда условие (8.4) записывают в более общем виде:

Здесь

8.2. Введем для задачи целочисленного линейного программирования ряд понятий, аналогичных введенным выше для задачи линейного программирования. Напомним, что область определения задачи линейного программирования (8.1) — (8.3) была обозначена выше через , сама задача — через а ее оптимальный план — через Множество наборов удовлетворяющих условиям называется областью определения задачи целочисленного линейного программирования (8.1) — (8.4).

Вектор удовлетворяющий условиям (8.2) — (8.4), называется планом (или допустимым решением) задачи целочисленного линейного программирования

План обращающий в максимум линейную форму (8.1), называется оптимальным планом (или решением) задачи целочисленного линейного программирования (8.1) — (8.4).

Если -план (оптимальный план) и то вектор называется расширенным планом (расширенным оптимальным планом) задачи целочисленного линейного программирования

Иногда бывает удобно ввести следующие обозначения: область определения задачи (8.1) — (8.4); задача (8.1) — (8.4); - оптимальный план и — расширенный оптимальный план задачи (8.1) — (8.4). Задача целочисленного линейного программирования называется разрешимой, если существует оптимальный план

8.3. Многогранник все опорные планы (вершины) которого целочисленные (т. е. все компоненты каждого из опорных планов целые), называется целочисленным многогранником.

8.4. Симплексная таблица все элементы которой — целые числа, называется целочисленной симплексной таблицей.