Кафедра летательных аппаратов. Задача динамического программирования. Самара 2012. Транспортная задача с оптимизацией плана перевозок. По критерию времени

Министерство образования и науки

Российской Федерации

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО

ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ

УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА С.П. КОРОЛЕВА

(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)»

(СГАУ)

____________________________________________________

Кафедра летательных аппаратов

Лабораторная робота по предмету

 Исследование операций

ЗАДАЧА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Выполнила:

Ст. группы 1308

Гурьянова М.И.

Проверил:

Кучеров А.С.

                                                                Самара 2012

1 Транспортная задача с оптимизацией плана перевозок

по критерию времени

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

          (5.1)

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

               (5.2)

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

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

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

,    

                                     (5.3)

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

При этом .

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

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

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

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

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

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

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

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

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

Познавательные статьи:



Алгоритмические операторы Matlab

Конструирование и порядок расчёта дорожной одежды

Исследования учёных: почему помогают молитвы?

Почему терпят неудачу многие предприниматели?