Постановка задачи динамического программирования. - Лекция, раздел Науковедение, Курс лекций по дисциплине: МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ Рассматривается Управляемый Процесс. В Результате Управления Система (Объект ...
Рассматривается управляемый процесс. В результате управления система (объект управления) приводится из начального состояния S0 в конечное S(S0 → S). Предположим, что управление можно разбить на n шагов, то есть решение принимаются последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. Обозначим через Xk управление на k – ом шаге, k = 1,2,3…,n; Xk может быть числом, точкой в n-мерном пространстве или качественным признаком. Пусть X(X1, X2,..., Xn) – это управление, приводящее систему из S0 в S. Обозначим через Sk состояние системы после k-го шага управления. Получаем последовательность состояний:
S0, S1, S2,…, Sk-1, Sk,... Sn-1, Sn; которую изобразим кружками.
Показатель эффективности операции, целевая функция зависит от начального состояния S0 и управления X
Z=f(S0,x) (3.1)
Предположим:
1) Состояние системы Sk в конце k-го шага зависит от предшествующего состояния Sk-1 и управления на k-ом шаге Xk. Это требование называется отсутствием последствия:
Это положение записывают в виде уравнений
Sk = ϥk(S0,xk) k=1,2,3...n (3.2)
Которые называются уравнениями состояния.
2) Обозначим показатель эффективности k-го шага через
Zk=fk(Sk-1,xk) k=1,2,3...n (3.3)
тогда
Z=∑nk=1а(Sk-1, xk) (3.4)
Задача динамического программирования (пошаговой оптимизации) формируется так: определить такое управление X, переводящее систему S из состояния S0 в состояние S, при котором целевая функция (3,4) принимает наибольшее (наименьшее) значение.
Особенности модели динамического программирования:
1) Задача оптимизации интерпретируется как n-шаговый процесс управления;
2) Целевая функция равна сумме целевых функций каждого шага;
3) Выбор управления на k- ом шаге зависит только от состояния системы к этому шагу и не влияет на предшествующие шаги (нет обратной связи);
4) Состояние Sk после k-ого шага управления зависит только от предшествующего состояния Sk-1 и управления xk (отсутствия последствий).
5) На каждом шаге управления xk зависит от конечного числа управляющих переменных, а состояние Sk от конечного числа параметров.
Экономико-математическая модель. ТЗ
Транспортные задачи(ТЗ)- частный случай задачи линейного программирования.
В ТЗ существуют поставщики и потребители грузов. У каждого поставщика имеется определенное количест
Метод северо-западного угла.
С помощью метода северо-западного угла реализуется первоначальный план поставок.
Таблица 2.1
Nj
M
Метод потенциалов нахождения оптимального решения.
Введем показатель U1 для каждой строки и V1 для каждого столбца. Эти показатели называются потенциалами поставщиков и потребителей. Потенциалы подбираются так, чтобы для запол
Открытая (не сбалансированная) модель ТЗ.
Открытая модель сводится к закрытой. Если суммарная мощность поставщика больше суммарного спроса потребителей, то вводится фиктивный потребитель, к которому присваивается спрос равный разнице между
Принцип оптимальности.
Впервые был сформулирован Р. Беллманом в 1953 году.
Каково бы не было состояние системы в результате какого-либо числа шагов на ближайшем шаге нужно выбрать управление так, чтобы оно приво
Детерминированные задачи упорядочивания.
1) Постановка задачи:
Имеется несколько изделий, каждое из которых надо обработать на двух машинах последовательно (сначала на первой, потом на второй). Известны вре
Дублирование и доминирование стратегий.
Если матрица игры содержит несколько одинаковых строк или стобцов, то из них оставляют одну строку(столбец), а отброшенным стратегиям присваиваем нулевые вероятности.
Это дублирование с
Решение игры 2хn.
Самым удобным способом для определения оптимальной стратегии игроков в игре 2хn является графическим способом.
Пример:
Марковские процессы.
Для математического описания многих случайных процессов может быть применен аппарат, разработанный в теории вероятностей, для так называемых Марковских случайных процессов. Они обладают следующим с
Простейший пуассоновский поток событий.
Для простейшего потока справедливы три свойства:
1) Стационарность потока λ = const. Интенсивность λ – частота появления события или среднее число событий, поступающих в СМО в ед
Система дифференциальных уравнений Колмогорова.
Рассмотрим математическое описание процесса с дискретными состояниями системы и непрерывным временем на примере случайного процесса, размеченный граф которого размещен на рисунке:
Уравнение Колмогорова для простейшего потока событий.
Особый интерес представляют вероятности системы Рi(t) в предельном стационарном режиме, т.е. при t→∞, которые называются предельными вероятностями состояний.
Т.к. пр
Системы массового обслуживания с отказом.
В качестве показателей эффективности СМО с отказами будет рассматривать:
А – абсолютную пропускную способность СМО, т.е. среднее число заявок, обслуживаемых системой в единицу времени;
Системы массового обслуживания с ожиданием
В качестве показателей эффективности СМО с ожиданием, кроме уже известных показателей – абсолютной А и относительной Q пропускной способности, вероятности отказа ρотк, среднего числ
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов