Практическое занятие № 10
Наименование работы: Решение простейших задач методом динамического программирования
Цель работы: научиться решать задачи методом динамического программирования
Подготовка к занятию: Повторить теоретический материал по теме «Динамическое программирование»
Литература:
Лобачева М.Е. Конспект лекций «Математические методы», 2013г.
Агальцов В.П. Математические методы в программировании, 2010г.
Перечень необходимых приборов, инструментов, материалов:ПЭВМ
Задание на занятие:
Выделены денежные средства S0=100 ден.ед. для вложения в инвестиционные проекты для реконструкции и модернизации производства на четырех предприятиях. По каждому предприятию известен возможный приростfi(х)(i=1, 2, 3, 4)выпуска продукции в зависимости от выделенной суммы. Требуется распределить средстваS0между предприятиями так, чтобы суммарный прирост продукции на всех четырех предприятиях достиг максимальной величины.
|
Параметр |
Номер варианта | |||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
0 | |
|
f1 (20) |
4 |
2 |
4 |
2 |
2 |
2 |
2 |
2 |
4 |
4 |
|
f2 (20) |
2 |
3 |
4 |
4 |
2 |
4 |
2 |
2 |
5 |
2 |
|
f3 (20) |
4 |
4 |
4 |
5 |
2 |
3 |
4 |
1 |
4 |
2 |
|
f4 (20) |
1 |
2 |
2 |
2 |
3 |
2 |
4 |
2 |
2 |
3 |
|
f1 (40) |
4 |
4 |
6 |
6 |
7 |
6 |
3 |
4 |
3 |
6 |
|
f2 (40) |
4 |
4 |
4 |
6 |
5 |
5 |
6 |
6 |
6 |
7 |
|
f3 (40) |
6 |
3 |
3 |
4 |
6 |
3 |
4 |
4 |
3 |
4 |
|
f4 (40) |
4 |
4 |
5 |
5 |
5 |
5 |
6 |
4 |
4 |
4 |
|
f1 (60) |
9 |
7 |
9 |
8 |
7 |
9 |
5 |
6 |
4 |
8 |
|
f2 (60) |
6 |
4 |
6 |
5 |
8 |
10 |
8 |
9 |
7 |
8 |
|
f3 (60) |
10 |
8 |
5 |
6 |
5 |
10 |
5 |
4 |
9 |
9 |
|
f4 (60) |
9 |
5 |
7 |
9 |
8 |
5 |
5 |
6 |
9 |
4 |
|
f1 (80) |
12 |
11 |
7 |
11 |
12 |
7 |
11 |
7 |
7 |
7 |
|
f2 (80) |
11 |
11 |
9 |
5 |
13 |
8 |
11 |
8 |
10 |
8 |
|
f3 (80) |
5 |
8 |
8 |
12 |
7 |
7 |
12 |
7 |
6 |
10 |
|
f4 (80) |
6 |
5 |
13 |
7 |
9 |
11 |
9 |
8 |
12 |
12 |
|
f1 (100) |
15 |
14 |
14 |
14 |
14 |
15 |
11 |
15 |
14 |
11 |
|
f2 (100) |
12 |
11 |
10 |
10 |
12 |
12 |
15 |
15 |
10 |
14 |
|
f3 (100) |
12 |
13 |
13 |
10 |
10 |
12 |
11 |
10 |
12 |
15 |
|
f4 (100) |
13 |
14 |
12 |
13 |
14 |
14 |
13 |
12 |
14 |
12 |
Порядок проведения занятия:
Получить допуск к работе.
Выполнить задание в соответствии с заданным вариантом.
Ответить на контрольные вопросы.
Содержание отчета:
Наименование, цель работы, задание;
Выполненное задание;
Выводы по результатам выполненного задания;
Ответы на контрольные вопросы.
Контрольные вопросы для зачета:
Какие задачи решаются методом динамического программирования?
Что означает понятие «шаговое управление»?
Как определяются шаги при решении задачи динамического программирования?
В чем суть принципа оптимальности Беллмана?
Каким образом проводится условная и безусловная оптимизация?
ПРИЛОЖЕНИЕ
Динамическое программирование – раздел оптимального программирования (оптимального управления), в котором процесс принятия решения и управления, может быть разбит на отдельные этапы (шаги). Все шаги могут быть уникальными или одинаковыми и чередоваться друг с другом. Некоторые задачи оптимизации легко разделяются на шаги естественным способом, а для других вводится искусственное разделение на шаги.
Динамическое программирование позволяет свести одну сложную задачу со многими переменными ко многим задачам с малым числом переменных. Это значительно сокращает объем вычислений и ускоряет процесс принятия управленческого решения.
Экономический процесс является управляемым, если можно влиять на ход его развития.
Управление – совокупность решений, принимаемых на каждом этапе для влияния на ход развития процесса.
Операция – управляемый процесс, т.е. мы можем выбирать какие-то параметры, влияющие на ход процесса и управлять шагами операции, обеспечивать выигрыши на каждом шаге и в целом за операцию.
Решение на каждом шаге называется «шаговым управлением». Совокупность всех шаговых управлений представляет собой управление операцией в целом.
Примерами задач, решаемых методом динамического программирования, могут быть: распределение ресурсов (финансовых, сырьевых, материальных и т.д.) между предприятиями, замена или ремонт промышленного оборудования, прокладка коммуникаций (трубопроводов, дорог и т.д.) и пр. В этих задачах, как правило, в качестве шагов выступают отрезки времени, которые явно задаются в условии задачи.
Требуется найти такое управление (х), при котором выигрыш обращался бы в максимум:
где F– выигрыш за операцию;
Fi(xi) – выигрыш наi-мшаге;
х – управление операцией в целом;
хi– управление наi-мшаге(i=1,2,…,m).В общем случае шаговые управления(х1, х2, … хm)могут стать числами, векторами, функциями.
То управление (х*), при котором достигается максимум, называется оптимальным управлением. Оптимальность управления состоит из совокупности оптимальных шаговых управленийх* = х*1, х*2, … х*m
F* = max {F*(х*)} –максимальный выигрыш, который достигается при оптимальном управлении х*.
Исходя из условий, каждой конкретной задачи длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений.
Принцип оптимальности Беллмана
Основным методом динамического программирования является метод рекуррентных соотношений; который основывается на использовании принципа оптимальности, разработанного американским математиком Р.Беллманом.
Суть принципа:
Каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться ОПТИМАЛЬНЫМИ относительно состояния, к которому придет система в конце каждого шага.
Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом.
Условная оптимизация
Безусловная оптимизация
Si – состояние системы наi-мшаге. Основная рекуррентная формула динамического программирования в случае решения задачи максимизации имеет вид:
,
где максимум в данной формуле берется
по всем возможным решениям в ситуации,
когда система на шагеmнаходится
в состоянииi.
Величина fm(i)– есть максимальная прибыль завершения задачи из состоянияi, если предположить, что на шагеm, система находится в состоянииi.
Максимальная прибыль может быть получена максимизацией суммы прибылей самого шага m и максимальной прибыли шага(m+1) и далее, чтобы дойти до конца задачи.
Планируя многошаговую операцию надо выбирать управление на каждом шаге с учетом всех его будущих последствий на ещё предстоящих шагах.
Управление на i-м шаге выбирается не так, чтобы выигрыш именно на данном шаге был максимальным, а так, чтобы была максимальна сумма выигрышей на всех оставшихся шагах плюс данный шаг.
Среди всех шагов последний шаг планируется без оглядки на будущее, т.е. чтобы он сам, как таковой принес наибольшую выгоду.
Задача динамического программирования решается в два этапа:
1 этап (от конца к началу по шагам):Проводится условная оптимизация, в результате чего находится условные оптимальные управления и условные оптимальные выигрыши по всем шагам процесса.
2 этап (от начала к концу по шагам):Выбираются (просчитываются) уже готовые рекомендации от 1-го шага до последнего и находитсябезусловное оптимальное управлениех*, равныйх*1, х*2, …, х*m.
Пример. Имеется запас средств, который нужно распределить между предприятиями, чтобы получить наибольшую прибыль. Пусть начальный капитал S0=100 д.ед. Функции дохода предприятий даны в матрице прибылей по каждому предприятию.
|
Х |
1 предприятие f (х1) |
2 предприятие f (х2) |
3 предприятие f (х3) |
4 предприятие f (х4) |
|
20 |
3 |
2 |
3 |
3 |
|
40 |
4 |
5 |
4 |
6 |
|
60 |
9 |
8 |
9 |
8 |
|
80 |
11 |
7 |
5 |
7 |
|
100 |
12 |
15 |
12 |
14 |
Схема решения:
Используем принцип Беллмана. Каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придет система в конце каждого шага.
Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом.
Математическая модель задачи:
Экономический смысл переменных:
xi – количество денег, вкладываемых в i предприятие.
Si– количество денег, оставшихся после вложения в i-предприятие (состояние системы на i-шаге);
F(xi)– прибыль от вложенной суммы денег;
S0– начальный капитал.
Рассмотрим 4-й шаг:
На 4-ом предприятии может остаться либо 0, либо 20, либо 40, либо 60, либо 80, либо 100 ден. ед. Тогда прибыль от вложения денег можно получить следующую.
-
S3
Х4
f (x4)
F4
0
0
0
0
20
20
3
3
40
40
6
6
60
60
8
8
80
80
7
7
100
100
14
14
Рассмотрим 3-й шаг:
На 3-ем и 4-ем предприятии может остаться либо 0, либо 20, либо 40, либо 60, либо 80, либо 100 ден. ед. Рассмотрим первую возможность. Если 3-му предприятию мы выдаем 20 ден. ед. то 4-му предприятию ничего не остается, и наоборот. Соответственно 40 ден. ед. можно поделить так (0;40), (20;20);
60 ден. ед. – (0;60), (20;40), (40;20), (60;0).
Прибыль от вложения денег в 3-е предприятие берется в исходной матрице прибылей, а прибыль от вложений, денег в 4-е предприятие берется из таблицы предыдущего шага
Прибыль на 3-м шаге берется максимальной по каждому вложению.
|
Вклад |
Проект |
Остаток |
Прибыль из матрицы |
Прибыль за шаг |
|
Прибыль на шаге |
|
S2 |
Х3 |
S3 |
f (x3) |
F4 |
f+F |
F3 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
20 |
0 |
20 |
0 |
3 |
3 |
3 |
|
20 |
0 |
3 |
0 |
3 | ||
|
40 |
0 |
40 |
0 |
6 |
6 |
6 |
|
20 |
20 |
3 |
3 |
6 | ||
|
40 |
0 |
4 |
0 |
4 | ||
|
60 |
0 |
60 |
0 |
8 |
8 |
9 |
|
20 |
40 |
3 |
6 |
9 | ||
|
40 |
20 |
4 |
3 |
7 | ||
|
60 |
0 |
9 |
0 |
9 | ||
|
80 |
0 |
80 |
0 |
7 |
7 |
12 |
|
20 |
60 |
3 |
8 |
11 | ||
|
40 |
40 |
4 |
6 |
10 | ||
|
60 |
20 |
9 |
3 |
12 | ||
|
80 |
0 |
5 |
0 |
5 | ||
|
100 |
0 |
100 |
0 |
14 |
14 |
15 |
|
20 |
80 |
3 |
7 |
10 | ||
|
40 |
60 |
4 |
8 |
12 | ||
|
60 |
40 |
9 |
6 |
15 | ||
|
80 |
20 |
5 |
3 |
8 | ||
|
100 |
0 |
12 |
0 |
12 |
Рассмотрим 2-й шаг:
|
Вклад |
Проект |
Остаток |
Прибыль из матрицы |
Прибыль за шаг |
|
Прибыль на шаге |
|
S1 |
Х2 |
S2 |
f (x2) |
F3 |
f+F |
F2 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
20 |
0 |
20 |
0 |
3 |
3 |
3 |
|
20 |
0 |
2 |
0 |
2 | ||
|
40 |
0 |
40 |
0 |
6 |
6 |
6 |
|
20 |
20 |
2 |
3 |
5 | ||
|
40 |
0 |
5 |
0 |
5 | ||
|
60 |
0 |
60 |
0 |
9 |
9 |
9 |
|
20 |
40 |
2 |
6 |
8 | ||
|
40 |
20 |
5 |
3 |
8 | ||
|
60 |
0 |
8 |
0 |
8 | ||
|
80 |
0 |
80 |
0 |
12 |
12 |
12 |
|
20 |
60 |
2 |
9 |
11 | ||
|
40 |
40 |
5 |
6 |
11 | ||
|
60 |
20 |
8 |
3 |
11 | ||
|
80 |
0 |
7 |
0 |
7 | ||
|
100 |
0 |
100 |
0 |
15 |
15 |
15 |
|
20 |
80 |
2 |
12 |
14 | ||
|
40 |
60 |
5 |
9 |
14 | ||
|
60 |
40 |
8 |
6 |
14 | ||
|
80 |
20 |
7 |
3 |
10 | ||
|
100 |
0 |
15 |
0 |
15 |
Рассмотрим 1-й шаг:
|
Вклад |
Проект |
Остаток |
Прибыль из матрицы |
Прибыль за шаг |
|
Прибыль на шаге |
|
S0 |
Х1 |
S1 |
f (x1) |
F2 |
f+F |
F1 |
|
100 |
0 |
100 |
0 |
15 |
15 |
15 |
|
20 |
80 |
3 |
12 |
15 | ||
|
40 |
60 |
4 |
9 |
13 | ||
|
60 |
40 |
9 |
6 |
15 | ||
|
80 |
20 |
11 |
3 |
14 | ||
|
100 |
0 |
12 |
0 |
12 |
Анализ результатов:
Максимальная прибыль равна 15 д.ед. Расположить денежные средства между проектами можно несколькими способами:
1 предприятие – 0ден. ед., 2 предприятие –0ден. ед., 3 предприятие – 60ден. ед., 4 предприятие т – 40ден. ед.
1 предприятие – 0ден. ед., 2 предприятие –100ден. ед., 3 предприятие – 0ден. ед., 4 предприятие – 0ден. ед.
1 предприятие – 20ден. ед., 2 предприятие –0ден. ед., 3 предприятие – 60ден. ед.., 4 предприятие – 20ден. ед.
1 предприятие – 60ден. ед., 2 предприятие –0ден. ед., 3 предприятие – 20ден. ед., 4 предприятие – 20ден. ед.
1 предприятие – 60ден. ед., 2 предприятие –0ден. ед., 3 предприятие – 0ден. ед., 4 предприятие т – 40ден. ед.