Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении

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

Дискретное программирование также называется целочисленным.

Задача о контейнерных перевозках (о рюкзаке или о бомбардировщике).

Контейнер оборудован m отсеками, вместимостью (). Для перевозки n видов продукции. Виды продукции характеризуются свойствами неделимости. Пусть – расход i-того отсека для перевозки j-той продукции. Обозначим через полезность единицы j-й продукции. Требуется найти план перевозки, при котором прибыль от перевозки максимизируется:

при

Задача о назначении (проблема выбора, о женихах и невестах).

Имеется n исполнителей, которые могут выполнять n различных работ. Известна полезность , связанная с выполнением i-м исполнителем j-той работы (i,j= ). Нужно так назначить исполнителей на работы, чтобы добиться максимальной полезности при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должен быть закреплён только один исполнитель.

Для составления математической модели задачи обозначим через – факт назначения или не назначения i-того исполнителя на j-ю работу. Так как количество исполнителей равно количеству работ и каждый из них может быть назначен только на одну работу, то должны принимать только два значения 1 или 0. Такие переменные называются булевыми.

Так как нужно найти план назначения , который максимизирует суммарную полезность назначения

при

а) каждый исполнитель назначается только на одну работу:

б) на каждую работу назначается только один исполнитель:

, - ограничение неотрицательности и целочисленности.

Мы рассмотрели только два примера, можно еще рассмотреть задачу коммивояжера, транспортную задачу с фиксированными доплатами.