Задача о назначении, задача коммивояжера. Постановка, модель, методы решения

51. Задача о назначении, задача коммивояжера. Постановка, модель, методы решения.

Задача о назначении

1.  Постановка задачи

Имеется ряд исполнителей для работ, известна эффективность применения каждого исполнителя для каждой работы

{a_ij}             i= - инд. исп.

                  j=- инд. раб.

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

2.  Модель

(p+q)´(p*q) – размерность модели

3.  Методы решения

·  Венгерский метод (Эгевара)

·  Метод потенциалов для решения транспортной задачи пригоден для решения задачи о назначении, хотя и менее эффективен

·  Такая модель достаточно легко сводится к задаче линейного программирования

   x_ij – целое

Задача коммивояжера

1.  Постановка задачи

Коммивояжеру необходимо объехать n городов не заезжая ни в один город дважды с минимальными затратами на переезд. Известна матрица затрат на переезд из одного города в другой {C_ij}_n´n C_ij=¥ для запрета

2.  Модель

3.  Методы решения

·  Метод ветвей и границ для задачи коммивояжера

·  Сведение задачи к задаче линейного целочисленного программирования (недостаток: большая модель)

·  Модификация венгерского метода, предусматривает появление окончательного решения в виде замкнутого цикла