Компьютер
<<  Задача о назначениях Компьютер в жизни школьника  >>
Задача о назначениях
Задача о назначениях
Возможные варианты задачи о назначениях:
Возможные варианты задачи о назначениях:
Задача о назначениях
Задача о назначениях
Строим первое опорное решение:
Строим первое опорное решение:
1)
1)
Для заполненных клеток выполняется соотношение: ui + vj = Cij
Для заполненных клеток выполняется соотношение: ui + vj = Cij
Подсчитаем оценки
Подсчитаем оценки
Вывод: первый план не является оптимальным
Вывод: первый план не является оптимальным
Таблица со вторым решением
Таблица со вторым решением
Проверяем решение на оптимальность
Проверяем решение на оптимальность
Цикл для
Цикл для
Найденный план является оптимальным: x13=1;x22=1;x34=1;x41=1 L(x) =
Найденный план является оптимальным: x13=1;x22=1;x34=1;x41=1 L(x) =
Венгерский метод решения задачи о назначениях
Венгерский метод решения задачи о назначениях
2. Если после выполнения первого шага можно произвести назначения, то
2. Если после выполнения первого шага можно произвести назначения, то
Пример:
Пример:
2.Назначение сотрудников провести нельзя
2.Назначение сотрудников провести нельзя

Презентация на тему: «Задача о назначениях». Автор: user. Файл: «Задача о назначениях.ppt». Размер zip-архива: 107 КБ.

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

содержание презентации «Задача о назначениях.ppt»
СлайдТекст
1 Задача о назначениях

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

Венгерский метод решения задачи о назначениях.

Малофеевой Екатерины гр. ММ-61

2 Возможные варианты задачи о назначениях:

Возможные варианты задачи о назначениях:

Ресурсы

Потребители

Критерий эффективнос-ти

Рабочие

Работа (рабочие места)

Время выполнения (мин)

Автомобили

Маршруты

Объём перевозимой продукции

Станки

Работа (участки)

Мин. время или макс. производительность

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

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

Решим задачу как транспортную:

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

4 Строим первое опорное решение:

Строим первое опорное решение:

b1=1

b2=1

b3=1

b4=1

a1=1

2 1

10

9

7 1

a2=1

15

4 1

14

8

a3=1

13

14 0

16

11 1

a4=1

4 0

15

13 1

19

5 1)

1)

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

6 Для заполненных клеток выполняется соотношение: ui + vj = Cij

Для заполненных клеток выполняется соотношение: ui + vj = Cij

u1 + v1=2 u1 =0 u1 + v4=7 u2= -6 u2 + v2=4 u2= -6 u3 + v2=14 u3 = 4 u3 + v4=11 u4 = 2 u4 + v1 =4 v1 = 2 u4 + v3=13 v2 = 10 u1 =0 v3 = 11 v4 = 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) = 15 + 4 = 19 >0 ?23 = 14 – (-6 + 11) = 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: После перераспределения груза строим новую таблицу с найденным вторым решением.

+ 1-

1- +

1

1

9 Таблица со вторым решением

Таблица со вторым решением

b1=1

b2=1

b3=1

b4=1

a1=1

2

10

9 1

a2=1

15

4 1

14

a3=1

13

14 0

a4=1

4 1

7

8

16

11

15

13

19

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 <0, =>составляем цикл для ?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 – (-17 + 10) = 15 + 7 = 22 > 0 ?43 = 13 – (-17 + 9) = 13 + 8 = 23 > 0 ?44 = 19 – (-17 + 7) = 19 +10 = 29 > 0

11 Цикл для

Цикл для

11 :

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

12 Найденный план является оптимальным: x13=1;x22=1;x34=1;x41=1 L(x) =

Найденный план является оптимальным: x13=1;x22=1;x34=1;x41=1 L(x) =

9+4+11+4=28 y.e.

Таблица с третьим решением.

b1=1

b2=1

b3=1

b4=1

a1=1

2 0

10

9 1

7

a2=1

15

4 1

14

8

a3=1

13

14

16

11 1

a4=1

4 1

15

13

19

13 Венгерский метод решения задачи о назначениях

Венгерский метод решения задачи о назначениях

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

14 2. Если после выполнения первого шага можно произвести назначения, то

2. Если после выполнения первого шага можно произвести назначения, то

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

15 Пример:

Пример:

Дана матрица: 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 19

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

2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 19

0 8 7 5 11 0 10 4 2 3 5 0 0 11 9 15

Получим матрицу:

16 2.Назначение сотрудников провести нельзя

2.Назначение сотрудников провести нельзя

Выберем в каждом столбце матрицы минимальный элемент и вычтем его из каждого элемента данного столбца:

0 8 7 5 11 0 10 4 2 3 5 0 0 11 9 15

0 8 2 5 11 0 5 4 2 3 0 0 0 11 4 15

3.Назначение провести нельзя. Минимальным числом прямых вычеркнем все нули в матрице. Среди не вычеркнутых элементов выберем минимальный. Прибавим его к элементам, стоящим на пересечении прямых и вычтем из всех не вычеркнутых элементов. Получим матрицу:

Назначения проведены: 1й сотрудник выполняет 3ю работу; 2й-выполняет 2ю работу; 3й-выполняет 4ю работу; 5й-выполняет 1ю работу.

0 8 2 5 11 0 5 4 2 3 0 0 0 11 4 15

0 8 0 3 11 0 3 2 4 5 0 0 0 11 2 13

«Задача о назначениях»
http://900igr.net/prezentacija/informatika/zadacha-o-naznachenijakh-260666.html
cсылка на страницу
Урок

Информатика

130 тем
Слайды