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

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

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

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

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

при

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

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

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

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

при

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

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

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

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

3.9. Сущность методов дискретной оптимизации

В первом приближении методы целочисленной оптимизации можно разделить на две группы: точные и приближённые. К точным относятся методы отсечения и комбинаторные (метод ветвей и границ). Однако точные методы имеют слабую сходимость. Многие экспериментальные и прикладные задачи не удалось решить за десятки и тысячи итераций. Общая идея решения задачи дискретного программирования методами отсечения состоит в следующем: исходная задача решается сначала без учёта ограничения целочисленности. Если полученный оптимальный план удовлетворяет условиям целочисленности, то задача решена, в противном случае к ограничениям исходной задачи добавляются новые, обладающие следующими свойствами:

• Полученный нецелочисленный план нарушает это ограничение.

• Любой целочисленный допустимый план исходной задачи заведомо удовлетворяет и новому ограничению.

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

Для решения задачи дискретного программирования получили широкое распространение комбинаторные методы направленного частичного перебора допустимых планов. Из них наиболее универсален метод ветвей и границ. Для выявления сущности этого момента воспользуемся известной задачей об отыскании фальшивой монеты. Пусть в мешке с монетами одинакового достоинства имеется одна фальшивая, отличающаяся бόльшим весом, которую будем искать по средствам взвешивания на рычажных весах без гирь. Поступим так: Разделим содержимое мешка на 2 равные по количеству монет части. В случае, если число n монет – нечётное – разделим n-1 монет на 2 равные части. Положим на чашки весов равные по количеству монет части. Если чашки весов уравновесятся, то отложенная монета – фальшивая, в противном случае она находится в более тяжёлой части, с которой поступим аналогичным образом. Так до тех пор, пока не найдём фальшивую монету. Здесь деление мешка есть деление множества на подмножества, т.е. разбиение области допустимых решений на непересекающиеся подмножества. Взвешивание каждой части соответствует оценке целевой функции на подмножестве (оценке верхней или нижней границы). Если при этом удастся найти некоторый план, для которого верхняя (нижняя) оценка на множестве плана одного из подмножеств равна значению функции в этой точке и не меньше (не превосходит) оценок сверху (снизу) на всех подмножествах, то этот план оптимальный. Если такой план не обнаружен, то продолжается процесс разбиения, начиная его с подмножества, имеющего самую высокую (низкую) оценку и т.д. Поскольку множество всех планов задачи конечно, то в конце концов план будет оптимальный.