ЗА Д А Ч И О Н А ЗН А Ч ЕН И Я Х
Презентацию подготовил Минаев А.А.
О бщ ая ф ормулировка
Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.
Венгерский метод
Применяется для решения транспортных задач, в которых количество пунктов производства и потребления равны, т.е транспортная таблица имеет форму квадрата, а объем потребления и производства в каждом пункте равен 1.
3 этапа
Венгерский
метод
Нахождение |
Нахождение |
максимально |
минимальног |
го значения |
о значения. |
Умножаем
первоначальные значение на -1, используем алгоритм нахождения минимального значения.
1этап
1 Формализация проблемы в виде транспортной таблицы
База |
Потребител Потребител |
Потребитель |
Потребител |
|
|
ь |
ь |
|
ь |
|
1 |
2 |
3 |
4 |
A |
68 мин. |
72 мин. |
75 мин. |
83 мин. |
B |
56 мин. |
60 мин. |
58 мин. |
63 мин. |
C |
38 мин. |
40 мин. |
35 мин. |
45 мин. |
D |
47 мин. |
42 мин. |
40 мин. |
45 мин. |
Компания имеет 4 сбытовых базы и 4 заказа, которые необходимо доставить потребителям. Складские помещения каждой из баз достаточны для размещения любого из этих заказов. Нужно найти минимальное время осуществления всех перевозок.
2. В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной
строки1 |
2 |
3 |
4 |
|
A |
68-68 |
72-68 |
75-68 |
83-68 |
B |
56-56 |
60-56 |
58-56 |
63-56 |
C |
38-35 |
40-35 |
35-35 |
45-35 |
D |
47-40 |
42-40 |
40-40 |
45-40 |
A |
1 |
2 |
3 |
4 |
0 |
4 |
7 |
15 |
|
B |
0 |
4 |
2 |
7 |
C |
3 |
5 |
0 |
10 |
D |
7 |
2 |
0 |
5 |
3. Повторить ту же процедуру для столбцов.
A |
1 |
2 |
3 |
4 |
0 |
2 |
7 |
10 |
|
B |
0 |
2 |
2 |
2 |
C |
3 |
3 |
0 |
5 |
D |
7 |
0 |
0 |
0 |
2 этап
1.Рассматриваем столбцы матрицы сверху вниз поочередно, подчеркиваем нули таким образом,
чтобы они не лежали в одной строке или одном
столбце - отмечается первый попавшийся в
столбце ноль, находящиеся с ним на одной строке или в одном столбце нули - вычеркиваем. Если
выяснится, что таблица содержит неучтенные нули
– повторяем 2 этап. |
2 |
3 |
4 |
|
A |
1 |
|||
0 |
2 |
7 |
10 |
|
B |
0 |
2 |
2 |
2 |
C |
3 |
3 |
0 |
5 |
D |
7 |
0 |
0 |
0 |
Если решение является допустимым, оно
оптимально. Если нет - переходим к этапу 3.
3 этап
1.Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице.
2.Найти наименьший из элементов, через которые не проходит ни одна прямая (обозначен звездочкой).
3.Вычесть его из всех элементов, через которые не проходят прямые.
4.Прибавить его ко всем элементам, лежащим на пересечении прямых.
5.Элементы, через которые проходит только одна прямая,
|
оставить неизменными |
3 |
4 |
|
A |
1 |
2 |
||
0 |
2*-2 |
7 |
10-2 |
|
B |
0 |
2-2 |
2 |
2-2 |
C |
3 |
3-2 |
0 |
5-2 |
D |
7+2 |
0 |
0+2 |
0 |
В результате в таблице появится как минимум одно новое нулевое значение. Вернуться к этапу 2 и повторить решение заново.
A |
1 |
2 |
3 |
4 |
0 |
0 |
7 |
8 |
|
B |
0 |
0 |
2 |
0 |
C |
3 |
1 |
0 |
3 |
D |
7 |
0 |
2 |
0 |
A |
1 |
2 |
3 |
4 |
0 |
0 |
7 |
8 |
|
B |
0 |
0 |
2 |
0 |
C |
3 |
1 |
0 |
3 |
D |
7 |
0 |
2 |
0 |
Решения является допустимым, а значит оно оптимально.
A |
1 |
2 |
3 |
4 |
0 |
0 |
7 |
8 |
|
B |
0 |
0 |
2 |
0 |
C |
3 |
1 |
0 |
3 |
D |
7 |
0 |
2 |
0 |
В результате в начальной таблице суммируются клетки, соответствующие выбранным элементам итоговой таблицы: 68+60+35+45=208 мин.
Это и будет минимальное время решения данной задачи.