В своей практической деятельности человек часто встречается с задачами, в которых переменные по своему физическому или экономическому смыслу могут принимать только целочисленные значения. Например, в задачах о выпуске неделимой продукции, которая не может выражаться дробными числами. В мат. моделях таких задач необходимо вводить дополнительные условия, требования цело численности переменных. Если все остальные ограничения и целевая функция задачи является линейными, то мы имеем задачу линейного целочисленного программирования (ЗЛЦП).

Эти задачи являются частным случаем дискретного программирования. ЗЛЦП бывают двух типов:1)задачи с не делимостями 2) задачи выбора варианта или экстремальные комбинаторные задачи.

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

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

Второй тип задач часто встречается в планировании и управлении. Планирование варианта переменных могут принимать только два значения. Пример задач второго типа это задачи о назначениях.

Модели целочисленных задач исследования операций.

1.Задачи, сводящиеся к целочисленности. Такой задачей является транспортная задача.

2.Задача о ранце. Для перевозки m-видов неделимых предметов используется m-видов транспортных средств – ресурсов заданных в количестве

Известны стоимость одного предмета вида j, а также расход i-го ресурса необходимого для транспортировки одного предмета вида j это

Необходимо определить количество предметов каждого вида которые необходимо перевести с помощью имеющихся средств, чтобы стоимость всех перевезённых предметов была максимальной.

Обозначим через количество перевезённых предметов вида j. это задача с не делимостями.

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

1-если переменная j выбирается для транспортировки, 0- в противном случае.

Задачи о назначениях.

Имеется n работ и n исполнителей. Известны затраты № на выполнение i-м исполнителем j-й работы №

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

Введем переменные

1-если i-й исполнитель направлен на работу, 0 –в противном случае.

В этой задаче условие (1’) можно заменить на и получить мат модель транспортной задачи, в которой запасы и потребности.