Задача о назначениях. Венгерский метод решения задачи о назначениях. Малофеевой Екатерины гр. ММ-61. - презентация

1 Задача о назначениях. Венгерский метод решения задачи о назначениях. Малофеевой Екатерины гр. ММ-61

2 Возможные варианты задачи о назначениях: Ресурсы ПотребителиКритерий эффективности рабочие Работа (рабочие места) Время выполнения (мин) автомобили маршруты Объём перевозимой продукции станки Работа (участки)Мин. время или макс. производительность

3 Задача о назначениях. Решим задачу как транспортную: Пример : Пусть имеется 4 сотрудника фирмы, которых необходимо закрепить за выполнением 4 х работ. Известны производительности каждого из сотрудников по каждой работе:

4 строим первое опорное решение: b 1 =1b 2 =1b 3 =1b 4 =1 a 1 = a 2 = a 3 = a 4 =

5 1). Проверяем открытая или закрытая транспортная задача по формуле: 4=4 => транспортная задача закрытая 2). Проверяем первое опорное решение на оптимальность методом потенциалов. Количество заполненных клеток должно равняться выражению: m + n-1. если недостаёт заполненных клеток, то в 1 из пустых клеток вводим нулевую поставку груза =7

6 Для заполненных клеток выполняется соотношение: ui + vj = Cij u 1 + v 1 =2 u 1 =0 u 1 + v 4 =7 u 2 = -6 u 2 + v 2 =4 u 2 = -6 u 3 + v 2 =14 u 3 = 4 u 3 + v 4 =11 u 4 = 2 u 4 + v 1 =4 v 1 = 2 u 4 + v 3 =13 v 2 = 10 u 1 =0 v 3 = 11 v 4 = 7

7 Подсчитаем оценки Δij свободных клеток по формуле: Если все Δij не отрицательны, то план оптимален. Если же существуют Δij<0, то необходимо улучшить первый опорный план, перераспределив поставки. Δij= Cij – (ui + vj) Δ12 = 10 – (0 +10) = 10 – 10 = 0 Δ13 = 9 – (0 + 11) = 9 – 11 = -2 <0 Δ21 = 15 – (-6 +2) = = 19 >0 Δ23 = 14 – ( ) = 14 – 5 = 9 >0 Δ24 = 8 – (-6 + 7) = 8 – 1 = 7 >0 Δ31 = 13 – ( 4 + 2) = 13 – 6 = 7 >0 Δ33 = 16 – (4 + 11) = 16 – 15 = 1 >0 Δ42 = 15 – (2 + 10) = 15 – 12 = 3 >0 Δ44 = 19 – (2 + 7) = 19 – 9 = 10 >0

8 Вывод: первый план не является оптимальным. Для его улучшения найдём клетку с наибольшей по абсолютной величине отрицательной Δij и составим цикл перераспределения поставок. Составляем цикл для Δ13: После перераспределения груза строим новую таблицу с найденным вторым решением

9 Таблица со вторым решением b 1 =1b 2 =1b 3 =1b 4 =1 a 1 = a 2 = a 3 = a 4 =

10 Проверяем решение на оптимальность u1+v3=9 u1= 0 u1+v4=7 u2= -6 u2+v1=15 u3= 4 u3+v2=4 u4= -17 u3+v2=14 v1= 21 u3+v4=11 v2= 10 u4+v1=4 v3= 9 u1=0 v4= 7 Решение не оптимально, т.к. Δ 11 составляем цикл для Δ 11 Δ11 = 2 – (0 + 21) = 2 – 21 = - 19 < 0 Δ12 = 10 – (0 + 10) = 10 – 10 = 0 = 0 Δ23 = 14 – (-6 + 9) = 14 – 3 = 11 > 0 Δ24 = 8 – (-6 + 7) = 8 – 1 = 7 > 0 Δ31 = 13 – (4 + 21) = 13 – 25 = -12 < 0 Δ33 = 16 – (4 + 9) = 16 – 13 = 3 > 0 Δ42 = 15 – ( ) = = 22 > 0 Δ43 = 13 – ( ) = = 23 > 0 Δ44 = 19 – ( ) = = 29 > 0

11 Цикл для Δ 11 : После перераспределения груза строим новую таблицу с найденным решением.

12 Таблица с третьим решением. Найденный план является оптимальным: x 13 =1; x 22 =1; x 34 =1; x 41 =1 L(x) = =28 y.e. b 1 =1b 2 =1b 3 =1b 4 =1 a 1 = a 2 = a 3 = a 4 =

13 Венгерский метод решения задачи о назначениях. Алгоритм решения: 1. Решаем задачу на минимум. Цель данного шага – получение максимально возможного числа нулей в матрице С. Для этого находим в матрице С в каждой строке минимальный элемент и вычитаем его из каждого элемента соответствующей строки. Аналогично в каждом столбце вычитаем соответствующий минимальный элемент. Если задана не квадратная матрица, то делаем её квадратной, проставляя стоимости равными максимальному числу в заданной матрице.

14 2. Если после выполнения первого шага можно произвести назначения, то есть в каждой строке и столбце выбрать нулевой элемент, то полученное решение будет оптимальным. Если назначения провести не удалось, то переходим к третьему шагу. 3. Минимальным числом прямых вычёркиваем все нули в матрице и среди не вычеркнутых элементов выбираем минимальный, его прибавляем к элементам, стоящим на пересечении прямых и отнимаем от всех не вычеркнутых элементов. Далее переходим к шагу 2. Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления.

15 Пример: Решим её венгерским методом. 1.найдём в каждой строке минимальное значение и вычтем его из каждого элемента данной строки. Дана матрица: Получим матрицу:

16 2. Назначение сотрудников провести нельзя. Выберем в каждом столбце матрицы минимальный элемент и вычтем его из каждого элемента данного столбца: Назначение провести нельзя. Минимальным числом прямых вычеркнем все нули в матрице. Среди не вычеркнутых элементов выберем минимальный. Прибавим его к элементам, стоящим на пересечении прямых и вычтем из всех не вычеркнутых элементов. Получим матрицу: Назначения проведены: 1 й сотрудник выполняет 3 ю работу; 2 й-выполняет 2 ю работу; 3 й-выполняет 4 ю работу; 5 й-выполняет 1 ю работу.