РЕШЕНИЕ ЗАДАЧИ " О НАЗНАЧЕНИЯХ" МЕТОДОМ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ. - Студенческий научный форум

VI Международная студенческая научная конференция Студенческий научный форум - 2014

РЕШЕНИЕ ЗАДАЧИ " О НАЗНАЧЕНИЯХ" МЕТОДОМ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

Славина С.С. 1, Светличная В.Б. 2
1Волжский политехнический институт (филиал) ВолгГТУ
2Волжский политехнический институт (филиал) ВолгГТУ, Волжский, Россия
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате 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с.

Просмотров работы: 1947