Задача о распределении сырья

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