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

Задача состоит в том, что требуется найти такое множество назначений i-х исполнителей (претендентов) на j-е работы K_ij (i=1, 2,..., n; j=1, 2,...n), при которых достигается максимум эффекта

и выполняются ограничения

, j=1, n;

, i=1, n;

1, если i-й объект назначен на j-ю работу

K_ij=

0, в противном случае.

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

118. Алгоритм метода ближайшего соседа (один из вариантов):

1) создается рабочий массив , i=1, 2,..., n; j=1, 2,..., n;

2) текущее множество перемещений коммивояжера L задается нулевым (число переходов m=0). В итоге решения элементы массива L будут представлять перечень пунктов l_k, k=1, 2, …, m (m=n+1);

3) находится звено максимальной стоимости из массива как (i¹ j);

4) изменяется m (m=m+1) и один из пунктов r или s, например, пункт r вводится во множество L (l_m=l₁=r);

5) составляется путь перемещений коммивояжера:

5.1) рассматривается множество M звеньев массива, соединенных с пунктами l₁ и l_m (т.е. рассматриваются звенья и );

5.2) находится звено минимальной стоимости из массива М как . Если c_rs=1Е12, то решение закончено (переход на 7). Иначе переход на 5.3;

5.3) изменяется m (m=m+1);

5.4) текущее множество перемещений коммивояжера L дополняется звеном rs. Если l₁=r, то l_k=l_k-1, k=m, m-1,..., 2 и l₁= s, а если l_m-1=r, то l_m= s;

5.5) заменяются элементы = = 1Е12;

5.6) если l₁ = l_m-1 , то переход на пункт 6 и если иначе, то заменяются элементы = = 1Е12;

5.7) если l₂= r, то = = 1Е12, k= 1, 2,..., n или если l_m-1=r, то = = 1Е12, k=1, 2,..., n;

6) возврат на 5.1.

7) контур перемещений замыкается путем введения еще одного перехода (m=m+1 и l_m= l₁).

119. Алгоритм простейшей реализации метода ветвей и границ следующий:

1) принимается один из пунктов за начальный пункт ветвления, например, один из пунктов, принадлежащих звену (переходу) с наибольшей стоимостью (длиной). Стоимость (длина) ветвления у начального пункта принимается равной нулю;

2) из пункта с минимальной стоимостью ветвления (минимальной текущей оценкой границы ветвления) производятся ветвления (включение звеньев переходов), не дающие замкнутого цикла (в ветви отсутствуют пункты с одинаковыми номерами кроме последнего n-го шага ветвления по каждой ветви) и рассчитываются стоимости ветвления у вновь включенных в ветви пунктов; каждая ветвь на n-м шаге замыкается на начальный пункт. Стоимость у вновь включенных в ветвление пунктов рассчитывается по формуле Z_ji=Z_{j, i -1} + c_i, где Z_ji и Z_{j, i-1}– соответственно оценка стоимости j-й ветви на шаге i и i-1; c_i – стоимость звена (перехода), включаемого в ветвь на i-м шаге;

3) находится минимальное значение из всех рассчитанных стоимостей дерева ветвления. Если какая-то ветвь имеет число переходов (звеньев) n и минимальное значение стоимости ветвления, то оптимальное решение получено, а иначе необходимо продолжать ветвление (переход на п. 2).

Одна из ветвей с минимальным значением стоимости ветвления у конечного пункта и включающая все n пунктов, дает решение.

120. Имеется n пунктов, в которых должен побывать коммивояжер. Задана матрица стоимостей (расстояний, времени и т.п.) на переход между пунктами c_ij , i=1, 2,..., n и j=1, 2,..., n. Коммивояжер должен выйти из одного из пунктов, побывать во всех остальных пунктах по одному разу и вернуться в начальный пункт.

Необходимо найти порядок обхода, дающий минимальную суммарную стоимость посещения всех пунктов.

Введем переменную K_jj

K_ij = 1, при переходе между пунктами i и j, 0, если нет перехода между пунктами i и j

Необходимо найти множество {K_ij }, i=1, 2,..., n и j=1, 2,..., n, дающее минимум

и выполнение ограничений

; (*)

; (**)

U_i -U_j +nK _ij £ n-1, i ¹ j, (***)

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

Условие (*) означает, что коммивояжер выходит из каждого пункта один раз, а условие (**) – что он входит в каждый пункт только один раз. Условие (***) обеспечивает замкнутость цикла (контура) только на n-м этапе решения задачи.

Задача без учета условия (***), представляет постановку, аналогичную задаче о назначениях и отличается тем, что целевая функция стремится к минимуму (Z→ min). Если при ее решении получен замкнутый контур, то это оптимальное решение, а иначе полученное значение целевой функции является той оценкой, которая всегда меньше или равна целевой функции (длине пути) с учетом условия (***).

Точное решение задачи дает метод ветвей и границ, а приближенные – метод ближайшего соседа, метод сумм (изложен ранее для составления сборочно-развозочных маршрутов), метод Кларка-Райта.