VI Международная студенческая научная конференция Студенческий научный форум - 2014
РЕШЕНИЕ ЗАДАЧИ " О НАЗНАЧЕНИЯХ" МЕТОДОМ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
В работе решаем задачу:Три рабочих бригады должны выполнить демонтаж, установку и наладку водной турбины в машинном зале. Необходимо назначить бригады на работы методом динамического программирования, ветвей и границ так, чтобы затраты труда были минимальными.
Матрица затрат
|
7 |
7 |
2 |
|
3 |
9 |
5 |
|
4 |
5 |
4 |
Шаг 1. Затраты труда для выполнения демонтажа всеми бригадами:
|
i1 |
1 |
2 |
3 |
|
F1 |
6 |
3 |
4 |
Шаг 2. Сравнивя установку первой бригады со всеми остальными:
F2 (i1,i2) = min ,
Получаем
F2 (1,2) = min F2 (1,3) = min
Шаг 3. Сравниваем наладку первой бригады со всеми остальными:
F3 (i1,i2 ,i3) = min
И получаем: F3 (1,2,3) = min
Минимальному значению соответствует С3,1 , поэтому назначаем 3 бригаду на установку турбины. В обратную сторону :1 бригада исполняет наладку турбины,2 бригада – демонтаж турбины
Сделаем попытку назначить 1 бригаду на каждую работу. Для этого вычеркнем 1 строку и столбец в матрице затрат, в зависимости от того, на какую работу назначена бригада:φi,j= Ci,j + min=> φ1,2=[C1,1=7] + min φ1,3= [C1,2 =7] + min φ1,3 = [C1,3 =2] + min
Так как минимальное значение достигается в случае φ1,3 = [C1,3 =2]=7, назначаем первую бригаду на наладку водной турбины. Остальные ветви 1 уровня отсекаем.
φ 2,j = C1,3+C2,j+ min
φ2,1= 2+[C2,1 =3] + min φ2,2= 2+[C2,2 =9] + min
Минимальное значение φ2,1=10 , поэтому назначаем вторую бригаду на демонтаж, а
остальные ветви отсекаем.
Третья бригада назначается на оставшуюся работу, в данном случае, на установку турбины:
φ 3,2 = C1,3+C2,1 + С3,3= 2+3+4=9
Окончательный результат:
3 бригада – установка турбины
2 бригада – демонтаж турбины
1 бригада – наладка турбины
Литература: 1. Математические методы./ Попова Н.В., Родионова И.В. - Электронный учебник, ВТК 2005. – Тема 2.1.
2. Исследование операций в экономике. Модели, Задачи, Решения. /Афанасьев М.Ю., Суворов Б.П./2003. – Раздел 07. Задача о назначениях.
3. Методы принятия оптимальных решений./Д.К.Агишева, С.А.Зотова, В.Б.Светличная, Т.А. Матвеева- Волгоградский государственный технический университет, 2011. – Глава 4, 143с.