В работе решаем задачу. Три рабочих бригады должны выполнить демонтаж, установку и наладку водной турбины в машинном зале. Необходимо назначить бригады на работы методом динамического программирования, ветвей и границ так, чтобы затраты труда были минимальными.

Матрица затрат

Шаг 1. Затраты труда для выполнения демонтажа всеми бригадами:

Шаг 2. Сравнивя установку первой бригады со всеми остальными:

,

Получаем

;

;

Шаг 3. Сравниваем наладку первой бригады со всеми остальными:

И получаем:

.

Минимальному значению соответствует С3,1, поэтому назначаем 3 бригаду на установку турбины. В обратную сторону: 1 бригада исполняет наладку турбины, 2 бригада – демонтаж турбины

Сделаем попытку назначить 1 бригаду на каждую работу. Для этого вычеркнем 1 строку и столбец в матрице затрат, в зависимости от того, на какую работу назначена бригада:

Так как минимальное значение достигается в случае φ1,3 = [C1,3 =2]=7, назначаем первую бригаду на наладку водной турбины. Остальные ветви 1 уровня отсекаем.

Минимальное значение φ2,1=10, поэтому назначаем вторую бригаду на демонтаж, а остальные ветви отсекаем.

Третья бригада назначается на оставшуюся работу, в данном случае, на установку турбины:

φ 3,2 = C1,3+ C2,1 + С3,3= 2+3+4=9.

Окончательный результат:

3 бригада – установка турбины

2 бригада – демонтаж турбины

1 бригада – наладка турбины