Динамическое программирование (ДП) – это метод нахождения оптимальных решений в задачах с многошаговой (многоэтапной) структурой.

Приведем общую постановку задачи ДП. Рассматривается управляемый процесс (распределение средств между предприятиями, использование ресурсов в течение ряда лет и т.п.). В результате управления система (объект управления) переводится из начального состояния в состояние. Предположим, что управление можно разбить на
шагов. На каждом шаге выбирается одно из множества допустимых управлений
, переводящее систему в одно из состояний множества
. Элементы множества
иопределяются из условий конкретной задачи. Последовательность состояний системы можно изобразить в виде графа состояний, представленного на рис. 3.1.

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

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

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

В принятых обозначениях принцип оптимальности Беллмана можно записать в математической форме следующим образом

Равенство (3.1) называется основным функциональным уравнением динамического программирования. Для каждой конкретной задачи уравнение имеет особый вид.

Вычислительная процедура метода ДП распадается на два этапа: условную и безусловную оптимизацию.

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

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

3.1. Задача оптимального распределения ресурсов

Пусть на реконструкцию и модернизацию основного производства объединению выделяется некоторый объем материальных ресурсов Х . Имеется N предприятий, между которыми нужно распределить данный ресурс. Обозначим через
прибыль, которому приносит народному хозяйству выделениеj -му предприятию
единиц ресурса. Предполагается, что размер прибыли зависит как от выделенного количества ресурса, так и от предприятия. Причем прибыль, получаемая предприятиями измеряется в одних и тех же единицах и общая прибыль объединения состоит из прибылей отдельных предприятий. Необходимо найти оптимальный план распределения ресурсов между предприятиями, при котором общая прибыль объединения будет максимальной.

Поставленную задачу нужно рассмотреть как многошаговую.

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

Воспользуемся рекуррентным соотношением Беллмана (3.1), которое для данной задачи приводит к следующим функциональным уравнениям при
:

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

На этапе безусловной оптимизации определяется оптимальный план распределения ресурсов между предприятиями.

Пример 3.1.

Для увеличения объемов выпуска пользующейся повышенным спросом продукции четырем предприятиям производственного объединения выделены средства в размере 50 млн. руб. Каждому из предприятий может быть выделено: 0, 10, 20, 30, 40 или 50 млн. руб. При этом ежегодный прирост выпуска продукции каждым из предприятий
в зависимости от капиталовложений известен и приведен в табл. 3.1.

Таблица 3.1

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

1. Основные понятия

1.1. Модель динамического программирования

1.2. Принцип оптимальности. Уравнение Беллмана

2. Оптимальное распределение ресурсов

2.1 Постановка задачи

2.2 Двумерная модель распределения ресурсов

2.3 Дискретная динамическая модель оптимального распределения ресурсов

2.4 Учет последействия в задачах оптимального распределения ресурсов

Заключение

Список используемых источников

Приложение 1. Листинг программы для решения задачи оптимального распределения ресурсов с заданными параметрами. Результаты работы программы

Введение

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

Большинство практических задач имеет несколько (а некоторые, возможно, даже бесконечное число) решений. Целью оптимизации является нахождение наилучшего решения среди многих потенциально возможных в соответствии с некоторым критерием эффективности или качества. Задача, допускающая лишь одно решение, не требует оптимизации. Оптимизация может быть осуществлена при помощи многих стратегий, начиная с весьма сложных аналитических и численных математических процедур и кончая разумным применением простой арифметики.

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

Как раздел математического программирования, динамическое программирование (ДП) начало развиваться в 50-х годах XX в. благодаря работам Р. Беллмана и его сотрудников. Впервые этим методом решались задачи оптимального управления запасами, затем класс задач значительно расширился. Как практический метод оптимизации, метод динамического программирования стал возможен лишь при использовании современной вычислительной техники.

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

1. Основные понятия

1.1 Модель динамического программирования

Дадим общее описание модели динамического программирования.

Рассматривается управляемая система, которая под влиянием управления переходит из начального состояния

Рисунок 1

Состояние

Предполагаем впредь, что состояние системы в конце k-го шага зависит только от предшествующего состояния системы

Равенства (1.1) получили название уравнений состояний. Функции

Варьируя управление U , получим различную «эффективность» процесса , которую будем оценивать количественно целевой функцией Z , зависящей от начального состояния системы

Показатель эффективности k-го шага процесса управления, который зависит от состояния

Если свойство аддитивности целевой функции Z не выполняется, то этого иногда можно добиться некоторыми преобразованиями функции. Например, если Z- мультипликативная функция, заданная в виде

Обычно условиями процесса на управление на каждом шаге

Задачу пошаговой оптимизации можно сформулировать так: определить совокупность допустимых управлении

Инструкция . Выберите количество предприятий.

Пример №1 . Планируется работа двух предприятий на n лет. Начальные ресурсы равны s0. Средства x, вложенные в 1-е предприятие в начале года, дают в конце года прибыль f1(x), и возвращаются в размере g1(x). Средства y, вложенные в 2-е предприятие в начале года, дают в конце года прибыль f2(y) и возвращаются в размере g2(y). В конце года возвращенные средства заново перераспределяются между отраслями. Определить оптимальный план распределения средств и найти максимальную прибыль.

Задачу решим методом динамического программирования. Операцию управления производственным процессом разобьём на этапы. На каждом из них управление выберем так, чтобы оно приводило к выигрышу как на данном этапе, так и на всех последующих до конца операции. В этом состоит принцип оптимальности , сформулированный американским математиком А. Беллманом.
Разобьём весь период на три этапа по годам и будем нумеровать их, начиная с первого.
Обозначим через x k и y k количество средств выделяемых каждому предприятию на k-ом этапе, а через x k + y k = a k - общее количество средств на этом этапе. Тогда первое предприятие приносит на этом этапе 3 x k , а второе 4 y k единиц дохода. Общий доход на k-ом этапе 3x k + 4y k .
Обозначим через f k (a k) - максимальный доход, который получает отрасль от обоих предприятий на k-ом и всех последующих. Тогда функциональное уравнение, отражающее принцип оптимальности Беллмана, принимает вид:
f k (a k)= max{3 x k + 4 y k + f k +1 (a k +1)}. (1)
Так как x k + y k = a k , то y k = a k - x k и 3x k + 4y k = 3x k + 4(a k - x k) = - x k + 4a k . Поэтому f k (a k) = max{-x k + 4a k + f k+1 (ak+1)} . (2)
0 ≤ x k ≤ a k
Кроме того, ak - это средства выделяемые обои предприятиям на k-ом этапе, и они определяются остатком средств, получаемых на предыдущем (k-1)-ом этапе. Поэтому по условию задачи оптимальное управление на каждом этапе
a k = 0,5 x k -1 + 0,2 y k -1 = 0,5 x k -1 +0,2(a k -1 - x k -1) = 0,3 x k -1 +0,2 a k -1 . (3)

I.Условия оптимизации
Планирование начинаем с последнего третьего этапа

При k = 3 получаем из (2)
f 3 (a 3) = max {- x 3 + 4a 3 + f 4 (a 4)}
0 ≤ x 3 ≤ a 3
Так как четвёртого этапа нет, то f 4 (a 4)=0 и
f 3 (a 3) = max {- x 3 + 4a 3 }=4a 3
0 ≤ x 3 ≤ a 3
(максимум выражения (- x 3 + 4 a 3 ) будет при x 3 =0)).

Итак, для третьего последнего этапа имеем: f 3 (a 3) = 4 a 3 , x 3 = 0, y 3 = a 3 - x 3 = a 3 ,
где a 3 = 0,3x 2 + 0,2a 2 , что следует из формулы (3).

При k = 2 из (2) и (3) получаем:
f(a 2) = max {-x 2 + 4a 2 + f 3 (a 3)}=
0 ≤ x ≤ a 2
= max {-x 2 + 4a 2 + 4a 3 }= max {-x 2 + 4a 2 + 4(0,3x 2 + 0,2a 2)} max{0,2x 2 + 4,8a 2 } 5a
0 ≤ x ≤ a 2
т. к. максимум выражения (0,2 x 2 + 4,8 a 2 ) будет при x 2 = a 2 .
То для второго этапа имеем: f 2 (a 2) = 5a 2 , x 2 = a 2 , y 2 = a 2 x 2 = 0 , при этом
a 2 = 0,3x 1 + 0,2a 1 с учетом (3).
При k = 1 с учетом (2) и (3) получаем:
f 1 (a 1) = max {-x 1 + 4a 1 + f 2 (a 2)}=
0 ≤ x ≤ a 1
= max {-x 1 + 4a 1 + 5a 2 }= max {-x 1 + 4a 2 + 5(0,3x 1 + 0,2a 2)}= max {0,5x 1 + 5a 1 }=5,5a 1
0 ≤ x ≤ a 1
при x 1 = a 1 .
Итак, для первого этапа f 1 (a 1) = 5,5 a 1 , x 1 = a 1 , y 1 = 0.
Процесс закончен. На первом этапе общее количество распределяемых средств известно -a 1 = 900 ед. Тогда максимальный доход, получаемый обоими предприятиями за три года составит f 1 (a 1) = 5,5*900 = 4950 ден. ед.

II. Безусловная оптимизация
Выясним, каким должно быть оптимальное управление процессом выделения средств между первым и вторым предприятиями для получения максимального дохода в количестве 4950 ден. ед.
1-й год. Так как x 1 = a 1 и , y 1 = 0, то все средства в количестве 900 ден. ед. отдаются первому предприятию.
2-й год. Выделяются средства a 2 = 0,3x 1 + 0,2a 1 = 0,5 a 1 =450 ед., x 2 = a 2 , y 2 = 0.
Все они передаются первому предприятию.
3-й год . Выделяются средства a 3 = 0,3x 2 + 0,2a 2 = 0,5 a 2 = 225 ед., x 3 = 0, y 3 = a 3 . Все они передаются второму предприятию.
Результаты решения представим в виде таблицы.

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

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

1. . Распределении инвестиций между предприятиями П 1 , П 2 ,..., П n . Инвестируемая сумма E усл. ден. ед.
2. Задача распределения ресурсов . Планируется работа двух предприятий на n лет. Начальные ресурсы равны s 0 .
3. Складская задача : составить оптимальную программу выпуска продукции X , которая минимизирует суммарные издержки предприятия.
4. Задача о рюкзаке (решение задачи о загрузке транспортного средства).

Задача распределения инвестиций

Таблицы могут иметь разный вид.
Таблица 1 - Первый вариант таблицы исходных данных

Таблица 2 - Второй вариант таблицы исходных данных

Пример задачи.
Для двух предприятий выделено A единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от x единиц средств, вложенных в первое предприятие, равен f 1 (х), а доход от y единиц средств, вложенных во второе предприятие, равен f 2 (y). Остаток средств к концу года составляет g 1 (x) для первого предприятия и g 2 (y) для второго предприятия. Задачу решить методом динамического программирования.

При вводе данных первую нулевую строку можно не заполнять.

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

Метод прогонки

В сервисе Метод прогонки необходимо также выбрать метод решения: процедура прямой или обратной прогонки.

Задача замены оборудования

Планирование производственной линии

План урока

Учебная дисциплина МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ В ЭКОНОМИКЕ

Тема урока Решение различных практических задач ДП с применением математических методов.

Цели урока

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

Развитие качества ума, внимания, умений учебного труда студентов.

Воспитание дисциплинированности, целеустремленности студентов.

Оснащение урока конспект лекций, В.П.Агальцов «Математические методы в программировании».

Ход урока:

Организационный момент:

проверка отсутствующих, заполнение журнала.

Актуализация опорных знаний : ответы на контрольные вопросы

Какие задачи называются многошаговыми?

При помощи какого математического аппарата решаются многошаговые задачи?

Что такое оптимальное управление u*?

Каков алгоритм метода последовательных приближений в два круга?

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

Изучение нового материала:

Классические задачи динамического программирования

• Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.

• Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.

• Задача о редакционном расстоянии (расстояние Левенштейна): даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.

• Задача о вычислении чисел Фибоначчи

• Задача о порядке перемножения матриц: даны матрицы, …, требуется минимизировать количество скалярных операций для их перемножения.

• Задача о выборе траектории

• Задача последовательного принятия решения

• Задача об использовании рабочей силы

• Задача управления запасами

• Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.

• Алгоритм Флойда - Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.

• Алгоритм Беллмана - Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.

• Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.

Пример: Оптимальное распределение ресурсов

Капитал 40 млн.руб. инвестор должен вложить в четыре инвестиционных проекта так, чтобы получить максимальный доход. Доходность проектов дана в таблице (вложения кратны 8 млн. руб.)

u

Прибыль от внедрения

f4 (u )

f3 (u )

f2 (u )

f1 (u )

55

39

120

115

10 0

120

135

134

14 0

145

158

147

Решение:

Это задача динамического программирования. Решение состоит из двух этапов. На первом этапе (от конца к началу) ищем условное оптимальное решение, на втором (от начала к концу) – ищем оптимальное решение задачи.

1 этап.

Распределяем капитал между четырьмя проектами и считаем получаемую прибыль L (i ), i = 8,16,24,32,40.

1 шаг : Денежные средства вкладываются в четвертый проект.

L (8)=55

L (16)=58

L (24)=90

L (32)=100

L (40)=140

2 шаг : Денежные средства вкладываются в четвертый и третий проекты.

u

Прибыль от внедрения

1 шаг

f3 (u )

55

39

10 0

120

14 0

145

3 шаг : Денежные средства вкладываются в четвертый, третий (2 шаг) и второй проекты.

u

Прибыль от внедрения

2 шаг

f 2(u )

94

108

120

135

135

175

158

175

134

214

147

2 этап:

На четвертом шаге выбираем максимальное из полученных значений прибыли L (40)=214.

И возвращаясь в обратном порядке от таблицы к таблице (от 4 шага к 1) выбираем такие значения доходов, при которых и получено значение 214.

Максимальный доход 214 млн. руб. от вложенных средств может быть получен при следующем распределении средств:

1 проект – 0 млн. руб.

2 проект – 24 млн. руб.

3 проект – 8 млн. руб.

4 проект – 8 млн. руб.

Закрепление нового материала:

5. Подведение итогов урока: выводы, оценки, домашнее задание:

(2) п.5.1

Ср12: формирование и усвоение содержания теоретического материала

Подпись преподавателя