Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Методика решения задач на основе принципа оптимальности Беллмана

Читайте также:
  1. B. Принятия оптимального управленческого решения по наиболее важным вопросам деятельности на рынке.
  2. I. 1.1. Пример разработки модели задачи технического контроля.
  3. I. 3.1. Двойственная задача линейного программирования.
  4. I.2. Структура оптимизационных задач
  5. I.5.3. Подготовка данных для задачи линейного программирования.
  6. I.5.4. Решение задачи линейного программирования.
  7. I.5.5. Просмотр и анализ результатов решения задачи.

 

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

Для знакомства с методиками приведём примеры решения задач.

Рассмотрим пример геометрической интерпретации (рис.10.1) метода.

 

Рис. 10.1. Геометрическая интерпретация задачи

 

Смысл её состоит в следующем:

· Вертикальным линиям соответствуют моменты времени, в которые рассматривают исследуемую задачу.

· В начальный момент t0 = 0 процесс (система) находится в одном из возможных начальных состояний, множеству которых соответствует множество точек Аi.Начальное состояние может быть задано либо областью возможных состояний, либо одним конкретным значением, в нашем случае четырьмя А1 А2 А3 и А4. Будем также считать, для простоты, что в каждый момент времени система находится так же в одном из четырех возможных состояний, которые показаны точками на соответствующих вертикалях.

· Конечное состояние системы — одна из четырех точек В1 В2 В3 и В4

 

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

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

 

Каждая допустимая стратегия выражается ломаной линией, соединяющей вертикаль t= 0 с вертикалью tn = Т. Состоит она из набора управлений на каждом этапе, т. е. ей можно сопоставить число:

 

Оптимальной стратегии соответствует ломаная с наименьшим значением F.

Следовательно, исходную задачу можно сформулировать в следующем виде: требуется из всех допустимых ломаных, соединяющих вертикаль t0=0 c вертикалью tn = T выбрать такую, которой соответствует наименьшее значение F.

Решают задачу в таком порядке:

Для всех возможных состояний системы в начале последнего этапа х (n– 1) определяют оптимальное управление — выбирают функцию перехода в одно из конечных состояний с минимальным значением. Переходы, соответствующие минимальному значению Qn-1 для каждого состояния (n - 1), показаны на рис. 10.1 жирной линией. Таким образом, в какой бы точке не оказалась система в начале последнего этапа, всегда можно предложить оптимальную стратегию для перевода ее в конечное состояние, получить ряд условно-оптимальных решений. Условие оптимальности каждого такого решения - состояние системы в начале рассматриваемого периода.

Теперь для каждого состояния системы в начале предпоследнего этапа Х(n-2) можно определить условно-оптимальные стратегии для перевода в одно из конечных состояний уже по общему минимуму функций перехода на двух последних этапах: min

При этом значения Qn-1 уже известны в результате предыдущих вычислений. Затем аналогично определяют условно-оптимальные стратегии на трех последних этапах по условию min(Qn-2 + Qn-1), причем Qn-1 уже известна. Расчеты продолжают до тех пор, пока не будет пройден весь процесс в обратном направлении.

Каждая из полученных ломаных (жирная линия), соответствует условно-оптимальной стратегии для всего процесса. Поскольку множеству начальных состояний системы соответствует множество точек на вертикали, то каждой условно-оптимальной стратегии соответствует свое начальное состояние системы (точка, из которой она выходит). Таким образом, условно-оптимальная стратегия будет оптимальной, при условии, что начальное состояние системы находится в соответствующей точке. Каждая условно-оптимальная стратегия оценивается значением функции F:

 

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

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

Контрольные вопросы

1. В каких задачах транспорта применяется динамическое программирование?

2. В чем суть динамического программирования?

3. Опишите особенности алгоритма реализации метода.

4. Что необходимо учитывать при отыскании оптимального решения с помощью рассматриваемого метода?

5. Сущность принципа оптимальности Беллмана.

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

7. Поясните понятие «функция перехода».

 


Лекция 11


Дата добавления: 2015-10-29; просмотров: 160 | Нарушение авторских прав


Читайте в этой же книге: Описание алгоритма однократного замещения | Алгоритм решения | Основы теории графов | Алгоритм графоаналитического метода построения сетевых моделей | Методика оптимизации сетевых моделей | Непрерывная случайная величина | Постановка задач | Входящий поток | Постановка задачи | Разработка модели |
<== предыдущая страница | следующая страница ==>
Графоаналитическая модель имитации обслуживания.| Общее представление о теории игр

mybiblioteka.su - 2015-2024 год. (0.006 сек.)