Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Лекции. Оптимизация систем управления. Оптимальное управление и оптимальные мехатронные системы - файл ЛЕКЦИЯ 16.doc


Загрузка...
Лекции. Оптимизация систем управления. Оптимальное управление и оптимальные мехатронные системы
скачать (1529.3 kb.)

Доступные файлы (22):

desktop.ini
ЛЕКЦИЯ 10.doc410kb.15.06.2000 16:50скачать
ЛЕКЦИЯ 11.doc186kb.15.06.2000 16:51скачать
ЛЕКЦИЯ 12.doc241kb.15.06.2000 16:53скачать
ЛЕКЦИЯ 13.doc256kb.15.06.2000 16:54скачать
ЛЕКЦИЯ 14.doc2611kb.15.06.2000 16:56скачать
ЛЕКЦИЯ 15.doc239kb.15.06.2000 16:56скачать
ЛЕКЦИЯ 16.doc250kb.15.06.2000 16:58скачать
ЛЕКЦИЯ 17.doc218kb.15.06.2000 16:59скачать
ЛЕКЦИЯ 18.doc333kb.15.06.2000 17:00скачать
ЛЕКЦИЯ 19.doc255kb.15.06.2000 17:00скачать
ЛЕКЦИЯ 1.doc44kb.29.06.2000 15:08скачать
ЛЕКЦИЯ 20.doc277kb.15.06.2000 17:01скачать
ЛЕКЦИЯ 21.doc133kb.29.06.2000 15:02скачать
Лекция 2.doc343kb.15.06.2000 16:38скачать
ЛЕКЦИЯ 3.doc2930kb.15.06.2000 16:40скачать
ЛЕКЦИЯ 4.doc5790kb.15.06.2000 16:42скачать
ЛЕКЦИЯ 5.doc244kb.15.06.2000 16:43скачать
ЛЕКЦИЯ 6.doc4878kb.15.06.2000 16:44скачать
ЛЕКЦИЯ 7.doc204kb.15.06.2000 16:45скачать
ЛЕКЦИЯ 8.doc245kb.15.06.2000 16:46скачать
ЛЕКЦИЯ 9.doc474kb.15.06.2000 16:49скачать

ЛЕКЦИЯ 16.doc

Реклама MarketGid:
Загрузка...






ЛЕКЦИЯ 16
План лекции

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

  2. Функциональное уравнение Беллмана.

  3. Пример решения основного функционального уравнения Беллмана.

  4. Три варианта оптимальных стратегий.

  5. Кратчайшие пути через сети.

  6. Функциональное уравнение Беллмана и его решение в задаче о кратчайших путях через сети.


Пример 1. Задача о замене оборудования. Пусть имеется некоторый комплект оборудования, который характеризуется покупной ценой p и функцией ежегодного дохода n(t). Функция n(t) задает доход от работы оборудования в течение одного года от момента t до момента t+1, здесь t - возраст оборудования в годах: t=0,1,2,... Будем, далее, предполагать, что оборудование является специальным и не имеет продажной цены. Требуется определить оптимальную политику замены оборудования, которая дает максимальный доход для k-летнего производственного процесса.

Обозначим максимальный доход, который можно получить от k-летнего производственного процесса, если к началу этого процесса имеется оборудование, возраст которого t лет (t=0,1,2,...). В начале каждого года можно принять одно из следующих двух решений: заменить оборудование или оставить старое оборудование. Принцип оптимальности Беллмана приводит к функциональному уравнению

(4.11)

К равенству (4.11) следует присоединить уравнение для однолетнего производственного процесса

(4.12)

В равенстве (4.11) выражение, стоящее в квадратной скобке до точки с запятой, задает доход, который можно получить от k-летнего производственного процесса, если на первом году этого процесса принять решение оставить старое оборудование при применении в дальнейшем оптимальной политики замены оборудования. Выражение, стоящее после точки с запятой, задает доход от k-летнего производственного процесса, если на первом году принять решение заменить оборудование при применении в дальнейшем оптимальной политики замены оборудования.

Положим p=4, n(t)=4-t. Тогда уравнения (4.12) и (4.11) примут вид

(4.13)

Из первого уравнения (4.13) находим



Функция задает оптимальное решение, здесь C - оставить старое оборудование, H - заменить оборудование.

Подставим функцию во второе уравнение (4.13). Получим



Перепишем это уравнение в виде

(4.14)

Из (4.14) находим, что



Продолжим этот процесс. Запишем второе уравнение (4.13) для трехлетнего производственного процесса:

(4.15)

Из уравнения (4.15) следует, что



Для четырехлетнего производственного процесса второе уравнение (4.13) принимает вид



или

(4.16)

Из (4.16) следует



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

Пусть, например, к началу четырехлетнего производственного процесса имеется оборудование, возраст которого три года. Максимальный доход, который можно получить от производственного процесса, равен 6 ( ). Оптимальная стратегия, которая обеспечивает этот доход, не является однозначной, а имеет следующие варианты:

а) первый вариант

Год от начала процесса

1

2

3

4

Оптимальное решение

C

H

С

С

Доход за год

1

0

3

2

б) второй вариант

Год от начала процесса

1

2

3

4

Оптимальное решение

H

C

С

С

Доход за год

0

3

2

1

в) третий вариант

Год от начала процесса

1

2

3

4

Оптимальное решение

H

C

H

С

Доход за год

0

3

0

3

Все три варианта оптимальной стратегии эквивалентны между собой, если интересоваться только четырехлетним производственным процессом, так как они обеспечивают один и тот же доход, равный 6. Однако они не эквивалентны, если принимать во внимание состояние оборудования в конце производственного процесса. В первом варианте по окончанию производственного процесса оборудование имеет возраст 3 года, во втором - 4 года, в третьем - 2 года.

Пример 2. Кратчайшие пути через сети [11]. Рассмотрим сеть, состоящую из N узлов, занумерованных 1,2,...,N, и взаимосвязанных звеньев. Обозначим () время прохождения звена (i,j). Будем решать задачу о нахождении пути через сеть, который соединяет два заданных узла и время движения вдоль которого минимально.

Данная задача имеет важное значение при выборе маршрутов движения автомобилей, самолетов по транспортным сетям, передачи сообщений по сетям связи и т.п. Числа могут необязательно означать время прохождения звена (i,j), а, например, задавать расход топлива.

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

Обозначим время перевода системы из узла i в узел N по кратчайшему пути (i=1,2,...,N-1). Принцип оптимальности Беллмана приводит к функциональному уравнению

(4.17)

Покажем, что уравнение (4.17) имеет единственное решение.

Пусть и - два различных решения уравнения (4.17). Пусть, далее, m является индексом, для которого разность Um-um достигает максимального значения. Покажем, что эта разность равна нулю.

В соответствии и с (4.17) запишем



Очевидно



Тогда из соотношений



следует неравенство



Поскольку для индекса m разность достигает максимального значения, поэтому



причем .

Далее, рассмотрев разность , подобным образом найдем узел , для которого



Поскольку число узлов конечно, то перебрав все узлы, окончательно получим



Полученное равенство доказывает единственность решения уравнения (4.17).

Остановимся теперь на численном решении уравнения (4.17). Воспользуемся методом последовательных приближений.

В качестве начального приближения положим



что соответствует времени прохождения звена (i,N), т.е. непосредственному переводу из узла i в узел N (минуя другие узлы). Если звено (i,N) отсутствует или, вообще, отсутствует какое-либо звено (i,j), то можно в качестве взять подходящее большое число. Таким образом удается очень просто решить трудные вопросы связей между узлами.

Следующее приближение получим по формуле

(4.18)

Предусмотренную равенством (4.18) минимизацию следует выполнять путем непосредственного сравнения встречающихся сумм, что быстро выполняется на ЭВМ. Переход от k-го приближения к k+1 осуществляется с помощью соотношений



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



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


Скачать файл (1529.3 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru