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

Предметный указатель

Читайте также:
  1. D)Указательные местоимения имеют отдельные формы для единственного числа – this этот, эта, that тот, та, то – и множественного числа – these эти, those те.
  2. VI. Bыпишите из 3-ro aбзацa npeдложение с указательным местоимением. Предложение переведите.
  3. Алфавитно-предметный указатель
  4. Алфавитно-предметный указатель
  5. Алфавитный указатель
  6. АЛФАВИТНЫЙ УКАЗАТЕЛЬ ВЕНКОВ СОНЕТОВ
  7. База»,— понял Шефер и поднял указательный палец, что означало: «Залечь, вести наблюдение».

 

 

Глава 10. Многошаговая оптимизация

 

1. Основные понятия и постановка задачи

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

3. Модификации основной постановки

4. Предметный указатель

 

Основные понятия и постановка задачи

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

1. Рассматриваемой системе естественно сопоставляется некоторое множество S её состо-яний, так что функционирование системы фактически состоит в переходах из одних состояний в другие.

2. Для каждого состояния s Î S определено множество Qs возможных воздействий на рас-сматриваемую систему, находящуюся в данном состоянии s. Под воздействием частного уп-равления v Î Qs система переходит из состояния s в новое состояние s’ Î S, которое однозначно определяется «старым» состоянием s и частным управлением v Î Qs по формуле

s’ = φ (s, v), (1)

где φ (s, v) – так называемая функция перехода, определяющая переходы системы между состоя-ниями.

3. При переходе системы из состояния s в состояние s’ = φ (s, v) под действием частного управления v доход от функционирования системы равен ψ (s, v), где функция ψ (s, v) называется функцией дохода. Функция дохода, как и функция перехода, определена при всех s Î S и при всех v Î Qs при заданном состоянии s. При ψ (s, v) < 0 доход превращается в убыток.

4. Управление u = (v 1, v 2, …, vN) является последовательностью частных управлений v 1, v 2, …, vN, под действием которых система последовательно переходит из заданного начального состояния s 0 в состояния

s 1 = φ (s 0, v 1), s 2 = φ (s 1, v 2), …, sN = φ (sN −1, vN). (2)

При этом общий доход от управления u = (v 1, v 2, …, vN) является суммой доходов от частных управлений:

ψ (u) = ψ (s 0, v 1) + ψ (s 1, v 2) + … + ψ (sN −1, vN), (3)

где s 1, s 2, …, sN определяются формулами (2).

Таким образом, на первый план выходит многошаговость всех процессов и аддитивность доходов по шагам, выражаемая формулой (3).

Основная задача многошаговой оптимизации состоит в максимизации дохода ψ (u) при за-данном начальном состоянии s 0 и числе шагов N. Эта задача является дискретной при конечнос-ти множества S состояний и множеств управлений Qs при всех s Î S. Далее в главе будут рас-сматриваться только дискретные задачи многошаговой оптимизации.

Всякую дискретную задачу многошаговой оптимизации можно представить как задачу оп-тимизации на графе. Именно, определим орграф G следующим образом. Множеством вершин орграфа G является конечное множество состояний S. Рассмотрим любую вершину s Î S. Каждо-му управлению v Î Qs, под действием которого система переходит из состояния s в состояние s’ = φ (s, v), сопоставим дугу графа G с началом в вершине s и концом в вершине s’. За вес этой ду-ги примем величину ψ (s, v). При этом исходная задача многошаговой оптимизации перейдёт в задачу поиска ориентированного пути с максимальным суммарным весом при заданном началь-ном состоянии s 0 и числе шагов N. Именно последняя задача и рассматривается в настоящей главе.

В разделе 1 дано краткое описание и постановка задачи многошаговой оптимизации; в разделе 2 приведён общий метод решения общей задачи многошаговой оптимизации – динами-ческое программирование; в разделе 3 рассмотрены некоторые модификации общей задачи, ко-торые проиллюстрированы развёрнутыми примерами важных классов задач: о замене машины и о критическом пути в сетевом графике.


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


Читайте в этой же книге: Алгоритмтм Флёри. | Определение потоковой сети. | Модификация основной постановки | Поиск максимального потока. | Утверждение 5. | Понятие кратчайшего пути | Алгоритм Дейкстры | Алгоритм Флойда-Уоршолла | Минимаксная модификация задачи о кратчайших путях | Максимальные паросочетания |
<== предыдущая страница | следующая страница ==>
Задача назначения| Принцип оптимальности и метод динамического программирования

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