Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Задача. Для выполнения работы требуется набрать сотрудников при следующих условиях: продолжительность работы n= 4 года; производственное задание каждого года известно и определяет необходимое число работников: m1=2, m2=5, m3=3, m4=1; число работников в начале работ x0=2. Затраты по изменению численности работников (по найму дополнительных работников или увольнению их части) при переходе от j-1 – го к j– му году определяются функцией
(5.1)
где xj, xj-1 – соответствующее число работников. Отклонение численности работников от потребной (как в большую, так и в меньшую сторону) приводит к дополнительным затратам, выражаемым функцией
(5.2)
По окончании работ затраты а увольнение оставшихся работников не предусматриваются. Составить оптимальный план набора работников при следующих исходных данных: m1=2, m2=5, m3=3, m4=1, a=10, b=7, c=8, d=11.
Решение. Используем метод динамического программирования. Будем решать задачу в «обратном направлении», используя информацию о начальном состоянии системы (x0=2).
Введем вспомогательную функцию S, определяющую суммарные затраты, начиная с текущего периода, и обозначим ее минимальное значение F:
, (5.3)
где z- вектор состояния системы (в данной задаче -количество работников) в начале текущего этапа операции.
При этом .
Шаг 1. Для отыскания необходимо рассчитать значения вспомогательной функции .
Для выполнения расчетов с использованием пакета Mathcad сформировать вектор M, компоненты которого M, равны потребным количествам работников mj ( в данном случае j=0,…,4, поскольку в Mathcad нумерация компонент начинается с нуля, при этом нулевая компонента может быть задана произвольно, т.к. в расчетах не используется):
.
Задать формулы для расчета функций затрат:
Очевидно, что ни в одном из периодов нецелесообразно набирать количество работников, превышающее максимально необходимое, которое в данной задаче равно 5. Поэтому будем варьировать значения z и x от 0 до 5.
Для этой цели удобно использовать индексированные переменные xi, zk, где индексы i, k будут в дальнейшем использоваться для нумерации элементов массивов. Поскольку z и x по смыслу задачи целочисленны, можно записать:
j:=4
и присвоить переменной m значение соответствующей компоненты вектора M:
Рассчитать значения функций затрат и их сумму :
.
Сформировать матрицу С, содержащую значения функции T при различных значениях z, x:
.
При данной последовательности аргументов функции T строки матрицы С будут соответствовать переменной z, а столбцы - переменной x.
Получим:
.
Поскольку, по условию, (по окончании всех работ затраты не предусматриваются), то значение общих затрат S на данном, последнем, этапе будет равно C.
Далее нужно найти функцию F4. Для сохранения единообразия последующих вычислений удобно значения этой функции сохранить в виде вектора F, каждая компонента которого равна минимальному элементу из соответствующей строки матрицы С. Введем также вектор X4, компоненты которого – это номера столбцов, содержащих минимальные элементы (здесь необходимо помнить, что нумерация компонент матриц начинается с нуля!):
Шаг 2. Задать новое значение шага j:=3 и получить вновь значения матрицы С. Затем, используя соотношение (5.3), рассчитать значения вспомогательной функции (для этого к компоненте прибавляется значение Fk):
На основе значений матрицы S cформировать вектора F и X3:
Шаг 3. По аналогии для j=2 получим:
Шаг 4. На данном шаге нет нужды табулировать значение z, поскольку оно равно численности работников в начале работ, т.е. x0=2. Однако при расчетах на компьютере удобнее использовать стандартную процедуру, которая позволяет получить следующие результаты:
Можно видеть, что минимальное значение функции S=46 в заданном начальном состоянии z=x0=2 достигается при x1*=2.
Далее по значению можно найти оптимальную компоненту вектора X2: затем, по аналогии,
При этом минимальные суммарные затраты составят (2)=46.
Варианты заданий
Решить задачу об оптимальном наборе сотрудников при следующих исходных данных.
Таблица 5.1 – Исходные данные
Дата публикования: 2015-02-22; Прочитано: 264 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!