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

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

;

Таблица 4.1

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

В качестве второго примера рассмотрим задачу распределения заказов между исполнителями, например, для случая, когда есть 4 заказа, и каждый из них может быть поручен любому из 7-и исполнителей. При этом каждый исполнитель может получить не более одного заказа и все заказы должны быть распределены.

План распределения работ по исполнителям должен минимизировать суммарные затраты на выполнение всех заказов, если ожидаемые затраты каждого исполнителя на любую из работ известны (приведены в табл. 4.2).

Переменные задачи, которые могут принимать значения только 1 или 0, в зависимости от того, поручена ли исполнителю соответствующая работа или нет, представим в виде аналогичной табл. 4.3.

Чтобы каждый заказ был выполнен, построчные суммы для переменных должны быть равны единице; а чтобы каждый исполнитель выполнял не более одного заказа, суммы по столбцам не должны превышать единицу. Некоторые исполнители (в этом примере 2, 3 и 4) заказов не получат. Критерием оптимизации будет минимум суммарных затрат.

Таблица 4.2

Таблица 4.3

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