Автор работы: Пользователь скрыл имя, 11 Декабря 2012 в 19:17, курсовая работа
В данной работе рассматривается один из методов математического программирования – динамическое программирование, позволяющий решать задачи оптимального управления различными процессами, которые возникают во всех сферах человеческой деятельности, например, при разработке правил управления запасами; при распределении дефицитных капитальных вложений между возможными новыми направлениями их использования; при разработке долгосрочных правил замены выбывающих из эксплуатации основных фондов и т. п.
Чтобы найти оптимальную стратегию управления, т. е. определить искомое решение задачи, нужно теперь пройти всю последовательность шагов, только на этот раз от начала к концу. На первом шаге в качестве оптимального управления x*1возьмем найденное условно оптимальное управление x01.На втором шаге найдем состояние S*1, в которое переводит систему управление x*1. Это состояние определяет найденное условно оптимальное управление x*2=x02, которое теперь будем считать оптимальным. Найти S*2 можно, учитывая x*2, а это, в свою очередь, позволяет определить x*3 и т.д. В итоге представляется возможным нахождение решения задачи, сущность которой — определение наибольшего дохода и оптимальной стратегии управления на конкретных этапах.
Рассмотрим несколько
Задача 12. Планируется деятельность группы филиалов F1, F2 …Fk на период хозяйственной деятельности из m лет. В начале периода на развитие всех филиалов выделены средства S, которые должны быть распределены между филиалами. В процессе работы вложенные средства частично расходуются, частично возвращаются в виде дохода и могут быть перераспределены.
Доход каждого филиала зависит от того, сколько средств в него вложено, средства перераспределяются в начале каждого года в периоде из m лет. Какое количество средств в начале года нужно вложить в каждый филиал, чтобы суммарный доход по k филиалам за m лет стремился к максимуму?
Задача 23. Пусть владелец автомобиля эксплуатирует его в течение m лет. В начале каждого года он может выполнить одно из указанных воздействий:
Нужно выбрать одно из решений на каждом из m годов (шагов).
Оптимальное управление получается из чередований определенных решений таким образом, чтобы минимизировать суммарные расходы за m лет.
Задача 3. Планируется распределение начальной суммы X0 млн. р. Между четырьмя предприятиями некоторого объединения. Средства выделяются только в размерах кратных a=80 млн. р. Функции прироста продукции от вложенных средств на каждом предприятии заданы таблично. Требуется так распределить вложения между предприятиями, чтобы общий прирост продукции (в млн. р.) был максимальным. Решить задачу на основе функционального уравнения Беллмана.
Задача 4. К началу текущей пятилетки на предприятии установлено новое оборудование. Зависимость производительности этого оборудования от времени его использования предприятием, а также зависимость затрат на содержание и ремонт оборудования при различном времени его использования приведены в таблице:
Время, в течении которого используется оборудование (лет) |
||||||||
0 |
1 |
2 |
3 |
4 |
5 | |||
Годовой выпуск продукции R в стоимостном выражении (тыс. руб.) |
80 |
75 |
65 |
60 |
60 |
55 | ||
Ежегодные затраты Z, связанные с содержанием и ремонтом оборудования(тыс. руб) |
20 |
25 |
30 |
35 |
45 |
55 | ||
Зная, что затраты, связанные с
приобретением и установкой нового
оборудования, идентичного с установленным,
составляют 40 тыс.руб., а заменяемое оборудование
списывается, составить такой план замены
оборудования в течение пятилетки, при
котором общая прибыль за данный период
времени максимальна4.
Рассмотрим решение задачи методом динамического программирования на примере задачи оптимального распределения ресурсов между отраслями.
Постановка задачи.
Найти оптимальное распределение средств между 5 отраслями на один год. Пусть общее количество средств, которые необходимо наилучшим образом распределить между рассматриваемыми производственными отраслями, равно 500 условным единицам. Шаг дискретизации для простоты ведения расчетов выбран равным 100ед.
|
X |
Отрасли производства | ||||
1 |
2 |
3 |
4 |
5 | |
0 |
0 |
0 |
0 |
0 |
0 |
100 |
2,5 |
1,5 |
2 |
2 |
2,2 |
200 |
3 |
3,5 |
3 |
2,5 |
2,5 |
300 |
3,5 |
4 |
4,5 |
4,5 |
3,5 |
400 |
4 |
5 |
6 |
5 |
6 |
500 |
5 |
6 |
7 |
6,5 |
6,5 |
Решение.
Введём обозначения:
количество средств,
Схема решения задачи методом ДП имеет следующий вид: процесс решения распределения средств = 5 рассматриваем как 5-шаговый, номера шагов совпадают с номерами предприятий, выбор , , , , - управления на 1, 2, 3,4,5 шагах. Конечное состояние равно нулю, так как все средства должны быть распределены.
Уравнения состояний в данной задаче имеют вид:
,
где - параметр состояния – количество средств, оставшихся после k-го шага, т.е. средства, которые осталось распределить между предприятиями.
Введем условную оптимальную прибыль, полученную от -го, +1-го, …,5-го предприятий, если между ними распределялись оптимальным образом средства . Допустимые управления удовлетворяют условию . Т.е. либо -му предприятию ничего не идет, либо не более того, что остается к -му шагу.
Уравнение Беллмана и
уравнение для максимума
Шаг 1. Предположим, что задача полностью решена и осталось распределить оставшийся ресурс Х12 между 1 и 2-й отраслями. Необходимо рассмотреть все возможные варианты и найти оптимальные сочетания между 1 и 2 отраслями.
Х1,2 |
Х1 |
Х2 |
V1,2 |
Возможное распределение ресурсов |
0 |
0 |
0 |
0 |
0 |
100 |
100 |
0 |
2,5* |
(100,0) |
0 |
100 |
1,5 |
||
200 |
200 |
0 |
3 |
|
0 |
200 |
3,5 |
||
100 |
100 |
2,5+1,5=4* |
(100,100) | |
300 |
300 |
0 |
3,5 |
|
0 |
300 |
4 |
||
200 |
100 |
3+1,5=4,5 |
||
100 |
200 |
2,5+3,5=6* |
(100,200) | |
400 |
400 |
0 |
4 |
|
0 |
400 |
5 |
||
200 |
200 |
3+3,5=6,5* |
(200,200) | |
300 |
100 |
3,5+1,5=5 |
||
100 |
300 |
2,5+4=6,5* |
(100,300) | |
500 |
500 |
0 |
5 |
|
0 |
500 |
6 |
||
300 |
200 |
3,5+3,5=7 |
||
200 |
300 |
3+4=7 |
||
400 |
100 |
4+1,5=5,5 |
||
100 |
400 |
2,5+5=7,5* |
(100,400) |
Шаг 2.
Рассматривая отрасли
1 и 2 как единый комплекс, необходимо
выполнить аналогичную
Х1,2,3 |
Х1,2 |
Х3 |
V1,2,3 |
Возможное распределение ресурсов | |
0 |
0 |
0 |
0 |
0 | |
100 |
100 |
0 |
2,5* |
(100,0,0) | |
0 |
100 |
2 |
|||
200 |
200 |
0 |
4 |
||
0 |
200 |
3 |
|||
100 |
100 |
2,5+2=4,5* |
(100,0,100) | ||
300 |
300 |
0 |
6* |
(100,200,0) | |
0 |
300 |
4,5 |
|||
200 |
100 |
4+2=6* |
(100,100,100) | ||
100 |
200 |
2,5+3=5,5 |
|||
400 |
400 |
0 |
6,5 |
||
0 |
400 |
6 |
|||
200 |
200 |
4+3=7 |
|||
300 |
100 |
6+2=8* |
(100,200,100) | ||
100 |
300 |
2,5+4,5=7 |
|||
500 |
500 |
0 |
7,5 |
||
0 |
500 |
7 |
|||
300 |
200 |
6+3=9* |
(100,200,200) | ||
200 |
300 |
4+4,5=8,5 |
|||
400 |
100 |
6,5+2=8,5 |
|||
100 |
400 |
2,5+6=8,5 |
|||
Шаг 3.
Теперь необходимо рассмотреть как единый комплекс отрасли 1,2 и 3 и провести аналогичную процедуру распределения ресурсов между этим комплексом и отраслью 4.
Х1,2,3,4 |
Х1,2,3 |
Х4 |
V1,2,3,4 |
Возможное распределение ресурсов |
0 |
0 |
0 |
0 |
0 |
100 |
100 |
0 |
2,5* |
(100,0,0,0) |
0 |
100 |
2 |
||
200 |
200 |
0 |
4 |
|
0 |
200 |
2,5 |
||
100 |
100 |
2,5+2=4,5* |
(100,0,0,100) | |
300 |
300 |
0 |
6 |
|
0 |
300 |
4,5 |
||
200 |
100 |
4,5+2=6,5* |
(100,0,100,100) | |
100 |
200 |
2,5+2,5=5 |
||
400 |
400 |
0 |
8* |
(100,200,100,0) |
0 |
400 |
5 |
||
200 |
200 |
4,5+2,5=7 |
||
300 |
100 |
6+2=8* |
(100,200,0,100) (100,100,100,100) | |
100 |
300 |
2,5+4,5=7 |
||
500 |
500 |
0 |
9 |
|
0 |
500 |
6,5 |
||
300 |
200 |
6+2,5=8,5 |
||
200 |
300 |
4,5+4,5=9 |
||
400 |
100 |
8+2=10* |
(100,200,100,100) | |
100 |
400 |
2,5+5=7,5 |