- •Федеральное агентство по рыболовству
- •2. Лекция. Экономико – математическое моделирование
- •3.Лекция. Линейное программирование
- •4.Лекция .Транспортная задача
- •5 .Лекция .Целочисленное программирование
- •6. Лекция. Динамическое программирование
- •1 Лекция. Основы теории принятия решений.
- •1.2. Основные понятия системного анализа
- •1.3. Основные понятия исследования операций
- •1.4. Постановка задач для принятия
- •1.5 Методология и методы принятия решений.
- •2.Лекция. Экономико - математическое моделирование
- •2.1 Основные понятия.
- •2. 2 Классификация моделей
- •2. 3 Классификация решаемых экономических задач.
- •3.Лекция . Линейное программирование.
- •3.1 Общая постановка задачи
- •3. 2 Двойственность в задачах линейного программирования
- •3.4 Решение задач линейного программирования
- •3. 5 Симплексный метод решения задач лп
- •4.Лекция . Транспортная задача
- •4. 1 Постановка задачи. Математическая модель
- •4. 2 Алгоритм решения транспортных задач.
- •4.2.1 Метод наименьшего элемента.
- •4. 3 Примеры решения транспортных задач.
- •1.Проверяем задачу на сбалансированность.
- •5.Лекция . Целочисленное программирование.
- •5. 1 Постановка задачи целочисленного программирования.
- •5. 2 Графический метод решения задач целочисленного программирования.
- •3 Пример решения задачи целочисленного программирования.
- •6.1. Постановка задачи.
- •6.2. Принцип оптимальности Беллмана.
- •6.3. Задача распределения средств на 1 год.
- •6.4. Задача распределения средств на два года
- •7.Лекция . Управление производством . Управление запасами.
- •7. 1 Задача о замене оборудования.
- •7. 2 Управление запасами. Складская задача.
- •8.Лекция. Теория игр.
- •8.1 Основные понятия.
- •8.2 Антагонистические игры.
- •8.3 Игры с « природой».
- •2. Критерий Гурвица.
- •3. Критерий Сэвиджа (критерий минимаксного риска).
- •4. Критерий Лапласа. N
- •8.Лекция. Системы массового обслуживания.
- •8.I. Формулировка задачи и характеристики смо
- •8.2 Смо с отказами.
- •8.3 Смо с неограниченным ожиданием
- •8.3.1 Основные понятия
- •8.3.2 Формулы для расчета установившегося режима
- •8.4 Смо с ожиданием и с ограниченной длиной очереди
- •8.4.1 Основные понятия
- •8.4.2Формулы для установившегося режима
- •10.Лекция . Сетевое планирование.
- •10.1 Основные понятия метода сетевого планирования
- •10.2 Расчет сетевых графиков
- •11.Лекция. Нелинейное программирование.
- •11.3. Условный экстремум
- •1 Тема. «линейное программирование».
- •2 Тема. «транспортная задача»
- •3 Тема .«целочисленное программирование»
- •4 Тема. Динамическое программирование.
- •5 Тема . Управление производством . Управление запасами.
- •6 Тема . Теория игр.
- •7 Тема . Системы массового обслуживания
- •8 Тема. Сетевое планирование.
- •10 Тема . Нелинейное програмирование.
6.1. Постановка задачи.
Динамическое программирование – раздел оптимального программирования (оптимального управления), в котором процесс принятия решения и управления, может быть разбит на отдельные этапы (шаги).
Динамическое программирование позволяет свести одну сложную задачу со многими переменными ко многим задачам с малым числом переменных. Это значительно сокращает объем вычислений и ускоряет процесс принятия управленческого решения.
Экономический процесс является управляемым, если можно влиять на ход его развития.
Управление – совокупность решений, принимаемых на каждом этапе для влияния на ход развития процесса.
Операция – управляемый процесс, т.е. мы можем выбирать какие-то параметры, влияющие на ход процесса и управлять шагами операции, обеспечивать выигрыши на каждом шаге и в целом за операцию.
Решение на каждом шаге называется «шаговым управлением».
Совокупность всех шаговых управлений представляет собой управление операцией в целом.
При распределении средств между предприятиями шагами целесообразно считать номер очередного предприятия; при распределении на несколько лет ресурсов деятельности предприятия – временной период. В других задачах разделение на шаги вводится искусственно.
Требуется найти такое управление (х), при котором выигрыш обращался бы в максимум:
F(x)=
Где F – выигрыш за операцию;
Fi(xi) – выигрыш на i-м шаге;
х – управление операцией в целом;
хi – управление на i-м шаге (i=1,2,…,m). В общем случае шаговые управления (х1, х2, … хm) могут стать числами, векторами, функциями.
То управление (х*), при котором достигается максимум, называется оптимальным управлением. Оптимальность управления состоит из совокупности оптимальных шаговых управлений х* = х*1, х*2, … х*m
F* = max {F*(х*)} – максимальный выигрыш, который достигается при оптимальном управлении х*.
Исходя из условий, каждой конкретной задачи длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений.
6.2. Принцип оптимальности Беллмана.
Основным методом динамического программирования является метод рекуррентных соотношений; который основывается на использовании принципа оптимальности, разработанного американским математиком Р.Беллманом.
Суть принципа:
Каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться ОПТИМАЛЬНЫМИ относительно состояния, к которому придет система в конце каждого шага.
Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом.
Условная оптимизация
Безусловная оптимизация
Si – состояние системы на i-м шаге. Основная рекуррентная формула динамического программирования в случае решения задачи максимизации имеет вид:
, где максимум в данной формуле берется по всем возможным решениям в ситуации, когда система на шаге m находится в состоянии i.
Величина fm(i) – есть максимальная прибыль завершения задачи из состояния i, если предположить, что на шаге m, система находится в состоянии i.
Максимальная прибыль может быть получена максимизацией суммы прибылей самого шага m и максимальной прибыли шага (m+1) и далее, чтобы дойти до конца задачи.
Планируя многошаговую операцию надо выбирать управление на каждом шаге с учетом всех его будущих последствий на ещё предстоящих шагах.
Управление на i-м шаге выбирается не так, чтобы выигрыш именно на данном шаге был максимальным, а так, чтобы была максимальна сумма выигрышей на всех оставшихся шагах плюс данный шаг.
Среди всех шагов последний шаг планируется без оглядки на будущее, т.е. чтобы он сам, как таковой принес наибольшую выгоду.
Задача динамического программирования начинает решаться с конца, т.е. с последнего шага. Решается задача в 2 этапа:
1 этап (от конца к началу по шагам): Проводится условная оптимизация, в результате чего находится условные оптимальные управления и условные оптимальные выигрыши по всем шагам процесса.
2 этап (от начала к концу по шагам): Выбираются (прочитываются) уже готовые рекомендации от 1-го шага до последнего и находится безусловное оптимальное управление х*, равный х*1, х*2, …, х*m.