Задача динамического программирования. Распределение ограниченный запаса сырья на доли

Лекция №4 (20.04) Разберем еще одну задачу динамического программирования (последнюю в лекционном курсе). Задача похожа на задачу из предыдущей лекции, но функция прибыли задается подругому. И поэтому решение отличается от решения задачи из предыдущей лекции. Задача. Пусть требуется распределить ограниченный запас сырья на доли ( ) , между N предприятиями, каждое из которых приносит доход ( ) , где – количество сырья, которое выделяется i ому предприятию, а коэффициенты заданы. Найти оптимальное распределение ресурсов с точки зрения получения максимального суммарного дохода ∑ . Чтобы представить задачу в форме задачи динамического программирования, будем рассматривать задачу распределения сырья как процесс последовательного дележа. Будем выделять сырье сначала первому предприятию, затем второму и т.д. (а считать будем «с конца»). ( ) , т.е. Количество сырья, выделяемое каждому предприятию: количество сырья, выделяемое k–му предприятию, эту величину примем за управление. В качестве состояния выберем количество сырья, оставшееся после распределения сырья k–му предприятию. Тогда начальное состояние процесса , а закон изменения ( ) состояния процесса . Следовательно, , т.е. ) ⌊ ⌋ а множество допустимых управлений ( . Рис 1. Составим уравнения Беллмана. Пусть сырье распределено по всем предприятиям, кроме N-ого, и управляемый процесс находится в состоянии , тогда максимальный доход за счет выбора в оставшемся одношаговом процессе составит: ( ) ( ) (1) Т.к. на последнем шаге мы должны «отдать все, что есть», т.е. и фактически максимум на последнем шаге мы не находим, при этом, обозначим ) (зачем это сделали – увидим позднее) и ( – количество сырья, которое будет выделено N- ому предприятию. Пусть теперь сырье распределено по всем предприятиям, кроме двух последних: ) - максимальный доход, когда распределяется сырье между N-1-го и N-го, тогда ( двумя последними предприятиями, перед началом этого распределения имеется в распоряжении единиц сырья: ( = * ) ( * ( ) + )+ (2) Согласно уравнениям Беллмана вычисляем максимум суммарной прибыли – прибыль на ближайшем шаге + оптимальная прибыль на следующем, последнем шаге. Неравенство показывает, что мы не можем отдать сырья больше, чем имеем на данном шаге. ) заменяем по формуле (1), полученной для этой функции. Функцию ( Для того, чтобы найти максимум функции (формула (2)) и значение , при котором функция достигнет максимума, вычислим производную и приравняем ее нулю. Но для этого немного упростим описание функции (уберем индексы для простоты). ) ( ) . Рассмотрим функцию: ( (3) (Чтобы проще было рассуждать о нахождении максимума функции в (2) , заменили ). ), если , -, т.е. Итак, надо найти максимум функции ( ) как функцию одной переменной Зафиксируем = ̅ , рассмотрим функцию ( ( ̅ ) причем ̅. График такой функции представлен рисунке 2 (а,б). Это парабола, ветви которой направлены вверх (объясните, почему?). Это значит, что во внутренней точке интервала изменения , ̅ -, функция ( ̅ ) может принимать только минимальное значение (вершина параболы). Максимальное значение функция ( ̅ ) может принимать в одной из граничных точек интервала изменения переменной, т.е. или при или при ̅ (может случиться, что это одинаковые значения, подумайте, при каких условиях это возможно). ) задается формулой (3), тогда ( ) ( ) Функция ( . Итак ( ( ) ) ̃ ̃ { ̃ где ) при этом либо ( , либо Рис.2а Рис.2б Вернемся теперь к прошлым обозначениям. ( = ) * = * ( , ( )+ ) + = где * (2) +. Окончательно получили: ( ) если * + , причем, , то Рассуждая аналогично (выполните самостоятельно) получим ( ) причем, если , то В итоге надо вычислить ( * ) * + + Теперь нам понятно, что начинать надо с вычисления коэффициентов . Формулы для вычисления коэффициентов получены: * + * +… * + Делаем «обратный ход» , чтобы определить, сколько сырья надо выделять каждому предприятию. Итак * , то + (уже вычислено) причем, если Рассуждаем и далее таким образом вычислим все ( ) Это нужно проделать самостоятельно. Еще несколько задач будут разобраны на практических занятиях, после чего выданы индивидуальные задания по теме «Динамическое программирование».