Принцип оптимальности и уравнения Беллмана

Принцип оптимальности.

На каждом шаге управление выбирается так, чтобы оно в совокупности со всеми оптимальными управлениями на всех последующих шагах приводило к наилучшему суммарному показателю эффективности. Т.е. управление должно выбираться исходя из оптимальности управления в целом, а не только на каком-то конкретном шаге. В основу этого принципа положены особенности модели ДП. На основе данного принципа были сформулированы рекуррентные формулы Беллмана. Применение данных формул возможно на базе обратной или прямой схемы Беллмана. В обоих случаях является показателем эффективности k -ого шага. На каждом шаге оптимальное управление выбирается из множества возможных управлений .

Обратная схема Беллмана.

При обратной схеме оптимизация осуществляется в результате обратного движения от последнего шага к первому. Сначала определяется оптимальная стратегия управления на n -ом шаге, затем на двух последних шагах, потом на трех последних шагах и т.д. до первого шага.

n -й шаг: состояние системы, зависящее от состояния , - управление на n -ом шаге, - целевая функция n -го шага.

Оптимальный показатель эффективности n –го шага , равный суммарному показателю эффективности всех предыдущих шагов на множестве всевозможных управлений всевозможных состояний системы.

(n-1)-ый шаг

к -ый шаг

………………

1 -ый шаг

Таким образом, в результате прохождения всех шагов от последнего к первому определяется оптимальное значение целевой функции. Чтобы найти оптимальную стратегию управления, т.е. определить решение задачи - , необходимо снова пройти всю последовательность шагов, только от начала к концу.

На первом шаге в качестве оптимального управления выбирается найденное условно оптимальное управление , характеризуемое показателем эффективности . Зная и , на втором шаге находится и управление и т.д.

Процесс решения можно представить в виде схемы:

Прямая схема Беллмана

При прямой схеме процесс поиска решения выполняется в направлении от первого шага к последнему. Сначала определяют оптимальную стратегию управления на первом шаге, затем на двух первых шагах, затем на трех первых шагах и т.д. до последнего шага.

1 шаг

На данном шаге состояние системы - , предыдущее состояние - . - множество управлений на первом шаге. Показатель эффективности 1-го шага - .

2 шаг

.

……………..

k – ый шаг

……………..

n- ый шаг

В результате прохождения всех шагов от первого к последнему определяется оптимальное значение целевой функции, которое приравнивается оптимальному показателю эффективности n -го шага . Чтобы найти оптимальную стратегию управления, т.е. определить решение задачи - , необходимо снова пройти всю последовательность шагов - от последнего к первому.

Поиск оптимальной стратегии можно представить в виде схемы:

Общая схема применения метода ДП

1. Выбирается способ деления процесса управления на шаги.

2. Определяются параметры состояния и переменные управления на каждом шаге.

3. Записываются уравнения состояний .

4. Вводится целевая функция.

5. Вводится в рассмотрение условные максимумы (минимумы) и условное оптимальное управление на k -м шаге: (в случае обратной схемы Беллмана), (при прямой схеме Беллмана).

6. Записываются основные уравнения для выбранной схемы Беллмана.

7. Последовательно решаются записанные уравнения Беллмана и получаются две последовательности функций: и .

8. После выполнения условной оптимизации определяется оптимальное решение поставленной задачи и .

Задача распределения средств между предприятиями

Задача распределения ресурсов между предприятиями является задачей динамического программирования.

Пусть имеется некоторая сумма средств, которую необходимо вложить в одно или несколько предприятий, чтобы получить максимальную прибыль от инвестирования. Предполагается, что в каждое из рассматриваемых предприятий может быть вложена как вся сумма инвестиций, так и частично, либо в предприятие может быть ничего не вложено, если инвестиции в него не эффективны. Для каждого предприятия должен быть рассчитан показатель эффективности инвестиций, который определяется в результате решения задачи ЛП о планировании производства.

Математическая модель для каждого вида предприятия имеет вид:

Целевая функция при ограничениях:

В модели использованы следующие обозначения:

- цена на j- ый вид товара для k -ого предприятия;

- оптимальный объем закупки i -ого вида ресурса k -ым предприятием;

- уровень запаса i -ого вида ресурса на k -ом предприятии;

- оптимальный план производства j -ого вида продукции на k -ом предприятии;

- норма расхода i -ого вида ресурса для производства единицы продукции j -ого вида на k -ом предприятии;

- рыночная цена i -ого вида ресурса для k -ого предприятия;

- объем финансовых средств, выделенных k -ому предприятию;

- минимальный объем заказов j -ого вида продукции на k -ом предприятии;

- предельная емкость рынка по j -ому виду продукции для k -ого предприятия.

В результате решения данной задачи будет получена величина дополнительного дохода от работы предприятия, которая представляет собой разницу прибыли при выделении инвестиций и прибыли, если инвестиции не производятся.

Вычисленные методами линейного программирования показатели эффективности деятельности каждого предприятия в зависимости от объема получаемых финансовых средств в дальнейшем используются для нахождения оптимального распределения средств между предприятиями методами динамического программирования.

Предполагается, что:

1. дополнительный доход каждого предприятия не зависит от объемов вложения средств в другие предприятия;

2. дополнительный доход каждого предприятия выражается в одних и тех же единицах;

3. совокупный дополнительный доход равен сумме дополнительных доходов, полученных каждым предприятием.

Для определения оптимальных средств инвестирования необходимо пройти следующие этапы:

1. интервал изменения выделяемых средств разбивается на элементарные отрезки;

2. для заданных значений выделяемых средств определяются показатели эффективности для всех предприятий;

3. по обратной (прямой) схеме используются уравнения Беллмана;

4. в обратной (прямой) последовательности, начиная от находятся оптимальные значения выделяемых средств .

Пример. Планируется деятельность 4 промышленных предприятий на очередной год. Необходимо между ними распределить 400 единиц ограниченного ресурса Q. Каждое предприятие i в зависимости от объема выделенных средств x получает дополнительный доход f_i(x). Распределение ресурсов производится с точностью 80 единиц. Необходимо определить оптимальное распределение средств между предприятиями, обеспечивающее максимальную эффективность деятельности всех предприятий.

Объемы получаемых дополнительных доходов в зависимости от выделенных ресурсов x представлены в таблице 1.

Таблица 1

Рассмотрим обратную схему Беллмана.

Согласно обратной схеме Беллмана начинаем с определения условно оптимальных капиталовложений, выделяемых для последнего четвертого (n -ого) предприятия. Для этого находим значения для каждого x, принимающего значения 0, 80, 160, 240, 320, 400.

4 шаг.

Показатель эффективности 4-ого предприятия, равный суммарному показателю эффективности на всех шагах определяется как .

3 шаг

Находим - суммарный показатель эффективности деятельности 3 и 4 предприятий .

2 шаг

Вычислим объединённый показатель эффективности деятельности 2, 3 и 4 предприятий - .

1 шаг

Объединённый показатель эффективности деятельности 4-х предприятий - .

Таблица 2

Чтобы найти оптимальную стратегию управления, необходимо рассмотреть всю последовательность шагов от последнего к первому.

В результате решения задачи распределения средств между предприятиями получили, что для обеспечения максимальной эффективности деятельности 4-х предприятий, равной 203 у.е., 1-ому и 2-ому предприятиям следует не выделять ресурсов, 3 предприятию необходимо выделить 240 единиц ресурса, 4-ому – 160 единиц.