22. Принципы динамического программирования. Иллюстрация на примере.

Введение в динамическое программирование.

(Принципы: разделения, оптимальности, многошаговости (-это Стась сказал))Динамическое программирование чаще всего занимается решением n-мерных задач исследования.В основе всех методов решения лежит принцип перехода от одной n-мерной задачи к n-одномерным задачам. Процесс решения задачи разбивается на этапы, на каждом этапе решается одна одномерная задача. Совокупность решений одномерных задач даст решение общей n-мерной задачи. В основе большинства методов динамического программирования лежат рекуррентные соотношения. Рекурсия проявляется в том, что для решения задачи на i-ом этапе используется решение полученное на (i-1)-ом этапе.

1. Задача о нахождении кратчайшего пути. Суть в том, что необходимо выбрать кратчайшее расстояние между 2-мя пунктами. При этом пункт назначения и пункт отправления связан сетью дорог проходящих через промежуточные пункты. Подобная задача может быть решена методом обычного перебора. Однако для больших сетей этот метод неэффективен, поэтому данная задача чаще всего решается методом динамического программирования. Для этого задача делится на этапы: 1_этап. На нем ищем кратчайшее расстояние до пунктов 2,3,4. 2_этап. На нем необходимо высчитать кратчайшее расстояние до пунктов 5 и 6. Рассмотрим пункт 5, минимальное расстояние до него = min расстояние по пунктам 2, 3, 4 - кратчайший путь к i-ому узлу + расстояние от i-ого узла до 5 узла =min(7+12;8+8;5+7)=12 (движение от 1 к 4 и к 5). Также ищем min расстояние и к пункту 6 = 17. 3_этап. Кратчайшее расстояние к п. 7 = min + расстояние от i-ого узла до п.7 кратчайшее = 21; маршрут : 1-4-5-7. Решение данной задачи позволяет вывести общую формулу, которую можно использовать при решении подобных задач. ; (x_i-1,x_i)- все допустимые маршруты от x_i-1 к x_i; f_i(x_i) – кратчайшее расстояние до узла x_i на этапе i; d(x_i-1,x_i)-расстояние от узла x_i-1 до x_i; f_i-1(x_i-1)-кратчайшее расстояние до узла x_i-1. При x=1, Данное выражение известно как метод прямой прогонки. В реальных задачах достаточно часто оказывается удобным двигаться не от 1-ого к последнему, а наоборот. Поэтому чаще применяется метод обратной прогонки: , при i=n

2. Задача о загрузке. Это задача о рациональном заполнении некоторого ограниченного объема. Например: имеется судно определенной грузоподъемности и имеется несколько категорий товара, каждое из которых приносит определенную прибыль. Тогда задача будет заключаться в том, чтобы загрузить судно. Выведем рекуррентное выражении обратной прогонки для подобной задачи. Пусть W –общая грузоподъемность; m_i- кол-во предметов i-ого наименования подлежащих загрузке; n- наименований предметов имеется; r_i- прибыль, которую приносит 1 загружаемый товар i- ого наименования; -вес одного предмета i-ого наименования. Мат. Модель задачи имеет след. вид: базовые элементы данной задачи: [1. i-ый этап соответсвует погрузке предметов i-ого наименования 2. Варианты решений на i-ом этапе описываются m_i, т.е. количеством предметов i-ого наименования подлежащих загрузке, соответствующая прибыль = r_im_i 3. Состоянием x_i на этапе i выражается суммарный вес предметов, решение о погрузке которых было принято на этапах i, i+1,…,n.]

3. Задача о планировании рабочей силы. Суть: имеется некоторый проект. В плане выполнения проекта число рабочих задействованных в нем путем найма или увольнения. Поскольку и найм и увольнение приводят к доп. затратам, необходимо определить каким образом должна регулироваться численность рабочих. В таких задачах в качестве интервалов рассматриваются временные интервалы.

Пусть n-количество временных интервалов, в течение которых выполняется проект; - минимальные потребности в рабочих на каждом этапе; x_i – кол-во работающих на i-ом этапе; Возможны затраты 2-х видов : 1.Затраты на содержание избыточного кол-ва рабочей силы C₁(x_i-x_i-1), 2.Затраты на найм рабочих C₂(x_i-x_i-1); Условия: 1. Этап i совпадает с порядковым номером временного интервала, 2.Варианты решений на i-ом этапе описываются x_i-ым, 3.Состоянием на i-ом этапе является x_i-1 т.е. кол-во работающих с 1-ого этапа. В рез-те получаем формулу: , при . Замечание: поскольку вычисления начинаются с n-ого этапа x_n полагают = b_n