Лабораторная работа № 5.
Метод динамического программирования для задачи оптимального распределения трудовых ресурсов»
Цель работы: С помощью модели динамического программирования составить оптимальный план регулирования численности рабочих.
Исходные данные: Предпринимателю необходимо составить план регулирования численности рабочих на последующие 7 недель. Минимальные потребности в рабочей силе bi на каждую из 7 недель известны.
Предприниматель имеет возможность регулировать количество имеющихся в наличие рабочих путем найма и увольнения.
Пусть yj – количество рабочих, имеющихся в наличии на j –й неделе, превышает заданное значение bj. Определим C1(yj – bj) как величину убытков, связанных с тем, что yj превышает заданное значение bj, а C2(yj – yj-1) – как величину накладных расходов по найму новых рабочих(yj > yj-1). Предприниматель располагает следующими данными:
C1(yj – bj) = 2*(yj – bj), j = 1, 2, 3, 4, 5, 6, 7.
Необходимо составить оптимальный план регулирования численности рабочих для 7-недельного периода планирования при условии, что исходное количество рабочих, имеющихся в наличие к началу первой недели, составляет b0 человек.
Методические указания к выполнению лабораторной работы
Предпринимателю необходимо составить план регулирования численности рабочих на последующие пять недель. Он оценивает минимальные потребности в рабочей силе bi на каждую из пяти недель следующим образом: 5, 7, 8, 4 и 6 рабочих для i = 1, 2, 3, 4 и 5 соответственно.
Предприниматель имеет возможность регулировать количество имеющихся в наличие рабочих путем найма и увольнения. При найме рабочих предприниматель терпит убытки в виде накладных расходов по найму. С другой стороны, сохранение в течение какой-либо недели количества рабочих, которое превышает минимальную потребность, приводит к убыткам, связанным с простоями рабочих на этой неделе.
Пусть yj – количество рабочих, имеющихся в наличии на j –й неделе. Определим C1(yj – bj) как величину убытков, связанных с тем, что yj превышает заданное значение bj, а C2(yj – yj-1) – как величину накладных расходов по найму новых рабочих(yj > yj-1). Предприниматель располагает следующими данными:
C1(yj – bj) = 3*(yj – bj), j = 1, 2, 3, 4, 5,
Из определения C2 следует, что увольнение(yj £ yj-1) не требует накладных расходов.
Необходимо составить оптимальный план регулирования численности рабочих для 5-недельного периода планирования при условии, что исходное количество y0 рабочих, имеющихся в наличие к началу первой недели, составляет пять человек.
Этапы определяются очевидным образом: каждой неделе j соответствует некоторый этап j. Информация о количестве рабочих, имеющихся к концу текущей недели, оказывается достаточной для принятия допустимых решений в течение оставшихся недель. Следовательно, состояние на этапе можно определить как yj-1. Величина yj выражает количество рабочих, имеющихся на этапе. Таким образом, определены все основные элементы модели динамического программирования:
1) Этап j ставится в соответствие j –й неделе.
2) Состояние yj-1 на этапе j выражает количество рабочих, имеющихся к концу этапа j - 1.
3) Варианты решения yj описываются количеством рабочих, имеющихся на этапе j.
Обозначим через fj(yj-1) минимальную величину расходов, осуществленных в течение периодов времени j, j + 1, …, 5, при заданном yj-1. Рекуррентное соотношение записывается в следующем виде
.
Перед тем как приступить к вычислениям с использованием таблиц, необходимо определить границы для значения переменных y1, y2, y3, y4 и y5. Так как j = 5 соответствует последнему периоду времени, а увольнение не требует накладных расходов, то значение y5 должно равняться минимальной потребности в рабочей силе, т. е. y5 = b5 = 6. С другой стороны, поскольку b4 < b5, предприниматель может рассматривать ситуации y4 = 4, 5 или 6 в поисках варианта с минимальными расходами. Аналогичные рассуждения приводят к заключению, что y3 = 8, y2 = 7 или 8 и y1 = 5, 6, 7 или 8. Из условий задачи следует, что исходное количество рабочих y0 равно 5.
Этап 5. b5 = 6.
| y4 | C1(y5 – 6 )+C2(y5 – y4) | Оптимальное решение | |
| y5 = 6 | f5(y4) | y*5 | |
| 3*(6-6)+4+2*2=8 | |||
| 3*(6-6)+4+2*1=6 | |||
| 3*(6-6)+0=0 |
Этап 4. b4 = 4.
| y3 | C1(y4 – 4 )+C2(y4 – y3)+f5(y4) | Оптимальное решение | |||
| y4 = 4 | y4 = 5 | y4 = 6 | f4(y3) | y*4 | |
| 0+0+8=8 | 3*1+0+6=9 | 3*2+0+0=6 |
Этап 3. b3 = 8.
| y2 | C1(y3 – 8) +C2(y3– y2)+f4(y3) | Оптимальное решение | |
| y3 = 8 | f3(y2) | y*3 | |
| 0+4+2*1+6=12 | |||
| 0+0+6 |
Этап 2. b2 = 7.
| y1 | C1(y2 – 7) +C2(y2– y1)+f3(y2) | Оптимальное решение | ||
| y2 = 7 | y2 = 8 | f2(y1) | y*2 | |
| 0+4+2*2+12=20 | 3*1+4+2*3+6=19 | |||
| 0+4+2*1+12=18 | 3*1+4+2*2+6=17 | |||
| 0+0+12=12 | 3*1+4+2*1+6=15 | |||
| 0+0+12=12 | 3*1+0+6=9 |
Этап 1. b1 = 5.
| y0 | C1(y1 – 5) +C2(y1– y0)+f2(y1) | Оптимальное решение | ||||
| y1 = 5 | y1 = 6 | y1 = 7 | y1 = 8 | f1(y0) | y*1 | |
| 0+0+19=19 | 3*1+4+2*1+17=26 | 3*2+4+2*2+12=26 | 3*3+4+2*3+9=28 |
Оптимальное решение задачи находится последовательно:
.
Полученному решению соответствует следующий план:
| Неделя, j | bj | yj | Решение |
| Никого не нанимать и не увольнять | |||
| Нанять трех рабочих | |||
| Никого не нанимать и не увольнять | |||
| Уволить двух рабочих | |||
| Никого не нанимать и не увольнять |