5 Задача динамического программирования

5.1 Алгоритм решения

Задача. Для выполнения работы требуется набрать сотрудников при следующих условиях: продолжительность работы n=4 года; производственное задание каждого года известно и определяет необходимое число работников: m₁=2, m₂=5, m₃=3, m₄=1; число работников в начале работ x₀=2. Затраты по изменению численности работников (по найму дополнительных работников или увольнению их части) при переходе от j-1 – го к j– му году определяются функцией

(5.1)

где x_j, x_j-1 – соответствующее число работников. Отклонение численности работников от потребной (как в большую, так и в меньшую сторону) приводит к дополнительным затратам, выражаемым функцией

(5.2)

По окончании работ затраты а увольнение оставшихся работников не предусматриваются. Составить оптимальный план набора работников при следующих исходных данных: m₁=2, m₂=5, m₃=3, m₄=1, a=10, b=7, c=8, d=11.

Решение. Используем метод динамического программирования. Будем решать задачу в «обратном направлении», используя информацию о начальном состоянии системы (x₀=2).

Введем вспомогательную функцию S, определяющую суммарные затраты, начиная с текущего периода, и обозначим ее минимальное значение F:

, (5.3)

где z- вектор состояния системы (в данной задаче - количество работников) в начале текущего этапа операции.

При этом .

Шаг 1.Для отыскания необходимо рассчитать значения вспомогательной функции .

Для выполнения расчетов с использованием пакета Mathcad сформировать вектор M, компоненты которого M, равны потребным количествам работников m_j (в данном случае j=0,…,4, поскольку в Mathcad нумерация компонент начинается с нуля, при этом нулевая компонента может быть задана произвольно, т.к. в расчетах не используется):

.

Задать формулы для расчета функций затрат:

Очевидно, что ни в одном из периодов нецелесообразно набирать количество работников, превышающее максимально необходимое, которое в данной задаче равно 5. Поэтому будем варьировать значения z и x от 0 до 5.

Для этой цели удобно использовать индексированные переменные x_i, z_k, где индексы i, k будут в дальнейшем использоваться для нумерации элементов массивов. Поскольку z и x по смыслу задачи целочисленны, можно записать:

В

122

вести номер шага

j:=4

и присвоить переменной m значение соответствующей компоненты вектора M:

Рассчитать значения функций затрат и их сумму :

.

Сформировать матрицу С, содержащую значения функции T при различных значениях z, x:

.

При данной последовательности аргументов функции T строки матрицы С будут соответствовать переменной z, а столбцы - переменной x.

Получим:

.

Поскольку, по условию, (по окончании всех работ затраты не предусматриваются), то значение общих затрат S на данном, последнем, этапе будет равно C.

Далее нужно найти функцию F4. Для сохранения единообразия последующих вычислений удобно значения этой функции сохранить в виде вектора F, каждая компонента которого равна минимальному элементу из соответствующей строки матрицы С. Введем также вектор X4, компоненты которого – это номера столбцов, содержащих минимальные элементы (здесь необходимо помнить, что нумерация компонент матриц начинается с нуля!):

Шаг 2. Задать новое значение шага j:=3 и получить вновь значения матрицы С. Затем, используя соотношение (5.3), рассчитать значения вспомогательной функции (для этого к компоненте прибавляется значение F_k):

На основе значений матрицы S cформировать вектора F и X3:

Шаг 3. По аналогии для j=2 получим:

Шаг 4. На данном шаге нет нужды табулировать значение z, поскольку оно равно численности работников в начале работ, т.е. x₀=2 . Однако при расчетах на компьютере удобнее использовать стандартную процедуру, которая позволяет получить следующие результаты:

Можно видеть, что минимальное значение функции S=46 в заданном начальном состоянии z=x₀=2 достигается при x₁*=2.

Далее по значению можно найти оптимальную компоненту вектора X2: затем, по аналогии,

При этом минимальные суммарные затраты составят (2)=46.