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

Страницы работы

Содержание работы

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

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

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

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

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

                  j=- инд. раб.

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

2.  Модель

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

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

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

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

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

   xij – целое

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

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

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

2.  Модель


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

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

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

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

Похожие материалы

Информация о работе

Тип:
Ответы на экзаменационные билеты
Размер файла:
33 Kb
Скачали:
0