- •Тема 1. Теория графов
- •1. Понятие графа. Основные элементы и свойства графов.
- •Типы графов
- •Матричные способы задания графов
- •Упорядочение элементов орграфа. Алгоритм Фалкерсона
- •Тема 2. Сетевое планирование и управление в.1. Сетевая модель и её основные элементы
- •В.2. Порядок и правила построения сетевых графиков
- •В.3. Временные параметры сетевых графиков Временные параметры сетевых графиков Параметры событий:
- •Параметры работ:
- •Тема 3. Динамическое программирование (дп)
- •В.1. Общая постановка задачи дп
- •В.2. Принцип оптимальности и уравнения Беллмана
- •В.3. Общая схема применения метода дп (алгоритм метода дп):
- •Тема 4. Теория массового обслуживания в.1. Основные понятия теории массового обслуживания
- •В.2. Марковские случайные процессы
- •В.3. Графы состояний
- •В.4. Потоки событий
- •В .5. Законы распределения для важнейших потоков.
- •В.6. Уравнения Колмогорова в системах массового обслуживания. Уравнения Колмогорова для вероятностей состояния
- •В.7. Схема гибели и размножения
- •В.8. Основные модели систем массового обслуживания
- •8.1. Смо с отказами
- •8.1.1. Одноканальная система с отказами
- •8.1.2. Многоканальная смо с отказами
- •8.2. Смо с ожиданием (очередью)
- •8.2.1. Одноканальная смо с неограниченной очередью
- •8.2.2. Многоканальная смо с неограниченной очередью
- •8.2.3. Смо с ограниченной очередью
- •Примеры задач смо
Тема 3. Динамическое программирование (дп)
ДП – метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на шаги (этапы). Такие операции называются многошаговыми.
Модели динамического программирования применяются при разработке правил управления запасами, при разработке принципов календарного планирования производства и т.д.
В.1. Общая постановка задачи дп
Рассмотрим управляемый процесс (например, экономические процессы распределения средств между предприятиями, использования ресурсов в течение ряда лет, замены оборудования, пополнения запасов …).
В результате управления система (объект управления) S переводится из начального состояния S0 в состояние S.
Пусть управление можно разбить на п шагов, а управление, переводящее систему S из состояния S0 в состояние S, представляет собой совокупность п пошаговых управлений.
Обозначим его Х = (Х1, Х2, …, Хп), где Хk – управление на k – ом шаге ( ).
Хk удовлетворяют некоторым ограничениям.
Sk – состояние системы после k – го шага управления.
Получаем последовательность состояний:
X1 X2 Xk-1 Xk Xk+1 Xn
S0 S1 … Sk-1 Sk … Sn
Показатель эффективности управляемой операции – целевая функция – зависит от начального состояния и управления: .
Предположим:
1) Состояние Sk – системы в конце k – го шага зависит только от предшествующего состояния Sk-1 и управления Хk на k – ом шаге («отсутствие последействия»):
(1) – уравнения состояний.
2) Целевая функция является аддитивной от показателей эффективности каждого шага, которые обозначим
(2)
Т.о. получаем задачу пошаговой оптимизации (задачу ДП):
Определить такое допустимое управление Х, переводящее систему S из состояния S0 в состояние S, при котором целевая функция Z принимает наибольшее (или наименьшее значение).
Особенности задачи ДП:
Задача интерпретируется как n шаговый процесс управления.
Целевая функция равна сумме целевых функций каждого шага.
Выбор управления на каждом шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги.
Состояние системы после k – го шага Sk зависит только от предшествующего состояния Sk-1 и управления Хk на k – ом шаге.
На каждом шаге управление Хk зависит от конечного числа переменных, а Sk – от конечного числа параметров.
В.2. Принцип оптимальности и уравнения Беллмана
Принцип оптимальности: Каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.
Беллманом были четко сформулированы и условия, при которых этот принцип верен. Основное требование – процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.
Введем обозначения: - максимум целевой функции – показателя эффективности п-го шага при условии, что к началу последнего шага система S была в произвольном состоянии Sn-1, а на последнем шаге управление было оптимальным. называется условным максимумом целевой функции на n-ом шаге.
(3).
Решение Xn, при котором достигается , также зависит от Sn-1 и называется условным оптимальным управлением на шаге. Оно обозначается .
Обозначим – условный максимум целевой функции, полученный при оптимальном управлении на n – k +1 шагах, начиная с k – го шага до конца, при условии, что к началу k – го шага система находилась в состоянии Sk-1.
, . (4)
Управление Хk на k–ом шаге, при котором достигается максимум (4), обозначается и называется условным оптимальным управлением на k – ом шаге (в правую часть выражения (4) следует вместо Sk-1 подставить выражение , найденное из уравнения состояния (1)).
Уравнения (3)-(4) называются уравнениями Беллмана.
Они позволяют найти предыдущее значение функции, зная последующие. Процесс решения уравнений называется условной оптимизацией.