2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задача о назначении. Не уверен в правильности решения.
Сообщение12.05.2012, 21:12 
Здравствуйте! Стоит следующая задача.

В сельской местности работает N передвижных магазинов. По завершении
работы все они должны переехать из тех населенных пунктов, где они находятся в другие.
Обозначим за $A_{ij}$ расстояние от i-того исходного населенного пункта к j-тому населенному
пункту назначения. Составить план перемещения передвижных магазинов так, чтобы сум-
марное пройденное расстояние оказалось минимальным. В качестве демонстрационного
примера взять следующую матрицу A:


$\begin{array}{|l|c|r|l|}
\hline
- & 1 & 2 & 3 \\
\hline
A & 32 & 11 & 19 \\
\hline
B & 41 & 54 & 23 \\
\hline
C & 47 & 34 & 41 \\
\hline
\end{array}$

В матрице исходные населенные пункты обозначены буквами, пункты назна-
чения - цифрами.


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

Методом "вычитания" минимальных элементов получил следующую матрицу:

$\begin{array}{|l|c|r|l|}
\hline
- & 1 & 2 & 3 \\
\hline
A & 8 & 0 & 8 \\
\hline
B & 5 & 31 & 0 \\
\hline
C & 0 & 0 & 7 \\
\hline
\end{array}$

Венгерский алгоритм.

(Оффтоп)

1. Найти строку с наименьшим количеством нулей.
2. Знаком "+" отметить один из нулей этой строки. А знаком "-" все остальные нули этой строки и того столбца, в котором находится этот ноль.
3. Повторяем эту процедуру для остальных строк, пока есть неотмеченные нули.
4. Если число нулей со знаком "+" равно n, то получено оптимальное решение.


$\begin{array}{|l|c|r|l|}
\hline
- & 1 & 2 & 3 \\
\hline
A & 8 & 0^+ & 8 \\
\hline
B & 5 & 31 & 0^+ \\
\hline
C & 0^+ & 0^- & 7 \\
\hline
\end{array}$

Число нулей со знаком "+" равно n. Скажите, всё ли верно я сделал?
Заранее спасибо!

 
 
 
 Re: Задача о назначении. Не уверен в правильности решения.
Сообщение13.05.2012, 14:17 
A B C
1 2 3 (длина пути 127)
1 3 2 (89)
2 1 3 (93)
2 3 1 (81)
3 1 2 (94)
3 2 1 (120)


Можно же все простым перебором проверить - всего 6 вариантов выбора путей - минимальная длина 81.

 
 
 
 Re: Задача о назначении. Не уверен в правильности решения.
Сообщение13.05.2012, 14:43 
Да, все правильно вы сделали.

 
 
 
 Re: Задача о назначении. Не уверен в правильности решения.
Сообщение13.05.2012, 17:24 
Большое спасибо.

P.S. по заданию нужно было именно венгерским методом.

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group