Задача об оптимальном назначении

 

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

В наиболее общей форме задача формулируется следующим образом:

Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.

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

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

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

Если целевая функция выражается через квадраты, говорят о квадратичной задаче о назначениях.

Формальная постановка задачи о назначениях:

Даны два множества, A и T, одного размера и задана функция стоимости C: A × T → R.

Необходимо найти биекцию f: A → T, такую, что целевая функция:

минимальна.

Обычно функция стоимости задается как квадратная матрица C, состоящая из вещественных чисел, так что целевую функцию можно записать в виде:

Задача называется "линейной", поскольку и целевая функция, и ограничения содержат только линейные выражения.

Задачу можно представить как задачу линейного программирования c целевой функцией

и ограничениями

для ,

для ,

для .

Переменная представляет назначение исполнителя на работу , принимая значение 1 если исполнитель назначен на эту работу и 0 в противном случае. В этой формулировке решение может и не быть целым, но всегда существует оптимальное решение с целыми значениями. Этот факт следует из абсолютной унимодулярности матрицы. Первое ограничение требует, чтобы каждому исполнителю была назначена в точности одна задача, второе требует, чтобы для каждой зад задачи был назначен один исполнитель.

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

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

Общая постановка транспортной задачи. Алгоритм построения 1-го опорного плана

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.

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

Общая постановка транспортной задачи заключается в определении оптимального плана перевозок некоторого однородного груза из «m» пунктов отправления (А1, А2, …, Аm) в «n» пунктов назначения (В1, В2, …, Вn). При этом в качестве критерия оптимальности обычно берется:

- минимальная стоимость перевозки всего груза;

- минимальное время доставки груза.

1 оп.план. Метод северо-западного угла.

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

Таким же образом (вправо и вниз) производится распределение всего количества груза.

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

Пример.

Построить опорный план транспортной задачи для исходных данных, приведенных в таблице.

 

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4	В5
А1
А2
А3
Потребности

Определим тип задачи

140+180+160=480

следовательно, задача закрытого типа. Построим опорный план методом северо-западного угла.

 

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4	В5
А1
А2
А3
Потребности

 

Таким образом, опорный план имеет вид:

С0=2×60+3×70+4×10+1×110+7×60+2×100=1380

Определим стоимость перевозок:

С0=2×60+3×70+4×10+1×110+7×60+2×100=1380