Омарова М.Т., магистр математики, магистр

менеджмента, старший преподаватель кафедры ВМ

Абильмажинова М., студентка группы УА-12

Карагандинский экономический университет Казпотребсоюза

ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ И ПРИНЦИП ОПТИМАЛЬНОСТИ БЕЛЛМАНА

В последнее время особое развитие получили методы оптимального управления в задачах экономики, т.к. основной причиной такого процесса является все большее удорожание средств для решения задач управления и реализации полученных результатов. Оптимальным управлением называется выбор наилучшего среди множества всевозможных вариантов управления [1, стр. 39].

Динамическое программирование является одной из разновидностью подхода оптимизации в задачах математического программирования. Отличительной особенностью решения оптимизационных задач динамического программирования является сведение его к решению более простых «подзадач» и оптимизации целевой функции на каждом этапе. Поэтому нахождение оптимального решения (максимума или минимума функции) является задачей динамического программирования. Эта функция характеризует состояние системы, которая всегда меняется, при этом проходя этапы своего развития. Динамическое программирование позволяет выбор управления переходом от одного этапа к другому таким образом, чтобы на самом последнем этапе получить оптимум данной функции [2, стр. 57].

Таким образом, можно ввести следующее определение:

– динамическое программирование – это метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). Такие операции называют многошаговыми [3, стр. 245].

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

Во многих задачах и примерах, которые решаются данным методом, в процессе управления, как мы говорили ранее, происходит разбиение на некоторые шаги. Шагом можно считать, например, какой-то период времени, если мы распределяем ресурсы производственной деятельности на несколько лет. В другом же случае шагом будет, например, номер каждого предприятия, если будет распределение между этими предприятиями определенных средств. В некоторых же других задачах может вводиться искусственно разбивка на шаги. Например, процесс управления происходит непрерывно, и в то же время мы можем его представить в виде дискретного процесса, при этом разбивая условно этот процесс на определенные отрезки (шаги). Для конкретных условий задачи при этом нужно правильно выбирать длину каждого шага таким образом, чтобы было получено более простая задача по оптимизации на каждом конкретном шаге задачи и обеспечивать при этом необходимую точность вычислений [4, стр. 364].

Математическая постановка задачи динамического программирования состоит в определении наименьшего (наибольшего) значения функции:

при следующих условиях

Показателем эффективности управления является целевая функция F.

Для решения задач динамического программирования применяется принцип оптимальности, сформулированный Р. Беллманом в 1953 году и состоящий в следующем: В результате определенного количества шагов каково бы ни было состояние системы перед каждым шагом, необходимо на этом шаге выбрать такое управление, чтобы это решение и на данном шаге и на всех следующих шагах был оптимальным. И главное требование – этот процесс управления обязательно должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать никакого влияния на предшествующие шаги.

Алгоритм решения задач с помощью рекуррентных уравнений Беллмана:

Берем n=1,2,… последовательно, используем разные состояния s – одношаговую, двухшаговую и т.д. Выбираем решение X_k на каждом шаге состояния системы s_k-1 «с оглядкой», так как этот выбор влияет на следующее состояние s_k и дальнейший процесс управления, который зависит от s_k. Все эти условия берем из принципа оптимальности. И последний шаг для любого состояния s_n-1 планируется оптимальным, исходя только из соображений шага, что он является последним.

Рассмотрим n-й шаг: естественно, что для этого шага s_n-1 – состояние системы к началу n-го шага и – конечное состояние, X_n – управление на n-м шаге, а – целевая функция n-го шага. И согласно этому принципу решение X_n необходимо выбирать таким образом, чтобы для любых состояний s_n-1 надо получить минимум (максимум) целевой функции на данном шаге. Теперь обозначим через максимум целевой функции – показателя эффективности n-го шага при условии, что к началу последнего шага система S была в произвольном состоянии s_n-1, а на последнем шаге управление было оптимальным.

называется условным максимумом целевой функции на n-м шаге. Очевидно, что (1)

Максимизация проводится по всем допустимым управлениям X_n. Решение X_n, при котором достигается , также зависит от s_n-1 и называется оптимальным условным управлением на n-м шаге. Т.е. надо найти для всех возможных состояний s_n-1 две функции и , решив одномерную задачу локальной оптимизации [3, стр. 249-250].

Рассмотрим теперь двухшаговую задачу: для этого присоединим к n-му шагу (n-1)-й. Для любых состояний s_n-2, произвольных управлений X_n-1 и оптимальном управлении на n-м шаге значение целевой функции на двух последних шагах будет равно: (2)

Согласно принципу оптимальности для любых s_n-2 решение нужно выбирать так, чтобы оно вместе с оптимальным управлением на последнем шаге приводило бы к максимуму целевой функции на двух последних шагах. Следовательно, нужно найти максимум выражения (2) по всем допустимым управлениям X_n-1. Максимум этой суммы зависит от s_n-2, обозначается и называется условным максимумом целевой функции при оптимальном управлении на двух последних шагах. Соответствующее управление X_n-1 на (n-1)-м шаге обозначается через и называется условным оптимальным управлением на (n-1)-м шаге.

(3)

В результате максимизации только по одной переменной X_n-1 согласно уравнению (3) вновь получаются две функции: и .

Далее рассматривается трехшаговая задача: к двум последним шагам присоединяется (n-2)-й и т.д.

Целевая функция на n-k последних шагах при произвольном управлении X_k на k-м шаге и оптимальном управлении на последующих n-k шагах равна

Согласно принципу оптимальности, X_k выбирается из условия максимума этой суммы, т.е.

(4)

k = n-1, n-2, …, 2, 1.

Уравнения (4) называются уравнениями Беллмана или рекуррентными соотношениями, которые позволяют, зная последующие, найти предыдущее значение функции. Процесс решения этих уравнений называется условной оптимизацией [5, стр. 111].

Список использованной литературы:

1. Экономико-математические методы и модели: учебник для бакалавров / А.М. Попов, В.Н. Сотников; под ред. проф. А.М. Попова. – М.: Издательство Юрайт, 2011. – 479 с. – Серия; Бакалавр.

2. Элементы исследования операций: учебное пособие / Е.Г. Давыдов. – М.: КНОРУС, 2013. – 158 с.

3. Исследование операций в экономике: Учебное пособие для вузов / Н.Ш. Кремер, Б.А. Бутко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997. – 407 с.

4. Математика в экономике: математические методы и модели: учебник для бакалавров / М.С. Чупрынов; под ред. М.С. Красса. – 2-ое изд., испр. и доп. – М.: Издательство Юрайт, 2013. – 541 с. – Серия: Бакалавр. Базовый курс.

5. Методы принятия оптимальных решений: Учебно-практическое пособие / Н.К. Емелина – Караганда, Карагандинский экономический университет, 2015. – 165.