- •Курс лекций по дисциплине
- •Для специальностей
- •Минск 2010
- •Тема 19. Динамическое программирование 73
- •Тема 20. Использование имитационного моделирования в процессе принятия управленческих решений 89
- •Тема 21. Многокритериальные задачи теории принятия решений 103
- •Тема 22. Экспертизы и обработка экспертных оценок как база решения сложных проблемных ситуаций. Методы дерева целей и анализа иерархий 117
- •Тема 11. Предмет, задачи и основные понятия теории принятия решений Основные понятия и определения
- •11.1. Объект и предмет исследования теории принятия решений. Назначение теории принятия решений и ее основные понятия
- •11.2. Этапы процесса моделирования.
- •11.3. Классификация задач принятия решений
- •Вопросы для самоконтроля
- •Тема 12. Использование целочисленной оптимизации в задачах теории принятия решений Основные понятия и определения
- •12.1. Сущность целочисленной оптимизации (целочисленного линейного программирования (цлп))
- •Задача о распределении бюджета
- •12.2. Использование логических условий и формирование зависимых решений с помощью целочисленных переменных
- •Вопросы для самоконтроля
- •Тема 13. Игровые модели теории принятия решений Основные понятия и определения
- •13.1 Теория игр как раздел теории принятия решений. Матричные игры с нулевой суммой
- •Решение парных матричных игр с нулевой суммой. Принцип минимакса.
- •13.2 Игры без седловых точек. Использование линейной оптимизации
- •Вопросы для самоконтроля
- •Тема 14. Игры с природой Основные понятия и определения
- •14.1 Игры с природой в условиях риска
- •14.2 Игры с природой в условиях неопределенности
- •14.3 Многоэтапные процессы принятия решений
- •Вопросы для самоконтроля
- •Тема 15. Сетевые модели теории принятия решений Основные понятия и определения
- •15.1. Понятие о методах сетевого планирования и управления (спу)
- •15.2. Понятие о сетевых моделях и правила построения сетевых графиков
- •15.3. Расчет критического пути сетевого графика
- •Тема 16. Оптимизация сетевых потоков Основные понятия и определения
- •16.1. Задача о максимальном потоке
- •16.2. Задача о потоке минимальной стоимости
- •16.3. Задача о кратчайшем маршруте
- •Тема 17. Сетевое планирование в условиях неопределенности Основные понятия и определения
- •17.1. Общая характеристика, область использования и алгоритм определения временных параметров проекта по методу pert
- •17.2. Обоснование и использование центральной предельной теоремы при расчетах вероятности выполнения проекта в директивный срок
- •17.3. Понятие о стохастических сетях
- •18.1. Характеристика стохастических задач, решаемых в условиях риска
- •18.2. Простейшие методы решения стохастических задач: мм-постановка, mp-постановка (задача с вероятностными ограничениями), pp-постановка
- •Вопросы для самоконтроля
- •Тема 19. Динамическое программирование Основные понятия и определения
- •19.1. Понятие о динамическом программировании.
- •19.2. Принцип оптимальности Беллмана и алгоритм решения задач динамического программирования
- •19.3. Вероятностное динамическое программирование и марковские процессы принятия решений
- •19.4. Определение оптимальной стратегии, максимизирующей ожидаемый доход в случае конечного горизонта планирования
- •19.5. Определение оптимальной стратегии для процесса с бесконечным числом этапов (оптимальная долгосрочная стратегия)
- •Вопросы для самоконтроля
- •Тема 20. Использование имитационного моделирования в процессе принятия управленческих решений Основные понятия и определения
- •20.1 Виды имитационного моделирования
- •1. Произошло ли событие a?
- •Какое из нескольких событий произошло?
- •Какое значение приняла случайная величина ?
- •Какую совокупность значений приняли случайные величины ?
- •20.2 Имитационное моделирование как метод анализа инвестиционных проектов
- •20.3 Имитационное моделирование денежных потоков проекта
- •20.4 Имитационное моделирование чистой приведенной стоимости проекта
- •Вопросы для самоконтроля
- •Тема 21. Многокритериальные задачи теории принятия решений Основные понятия и определения
- •21.1 Классификация многокритериальных задач
- •21.2 Принцип оптимальности Парето.
- •21.3 Принцип равновесия по Нэшу
- •21.4 Обзор методов решения задач векторной оптимизации
- •1. Методы свертки системы показателей эффективности
- •Вопросы для самоконтроля
- •Тема 22. Экспертизы и обработка экспертных оценок как база решения сложных проблемных ситуаций. Методы дерева целей и анализа иерархий Основные понятия и определения
- •22.1 Экспертное оценивание важности объектов
- •22.1.1 Усреднение экспертных оценок
- •22.1.2 Попарное сравнение объектов
- •22.2 Назначение сложных экспертиз
- •22.3 Экспертный анализ сложной проблемы с помощью дерева целей
- •22.4 Метод анализа иерархий: особенности и область применимости
- •Вопросы для самоконтроля
Тема 17. Сетевое планирование в условиях неопределенности Основные понятия и определения
Метод PERT. Бета-распределение. Оптимистическая, пессимистическая и наиболее вероятная оценки продолжительностей работ. Директивный срок выполнения проекта. Стохастические сети.
17.1. Общая характеристика, область использования и алгоритм определения временных параметров проекта по методу pert
При определении временных параметров сетевого графика мы предполагали, что время выполнения каждой работы является детерминированным. Однако СПУ часто применяется при планировании и реализации сложных проектов, не имевших аналогов в прошлом. В этих условиях продолжительность каждой работы заранее неизвестна и является случайной величиной с некоторым математическим ожиданием (средним значением) и дисперсией.
При планировании проектов с учетом фактора неопределенности предполагается, что плотность распределения продолжительности работ обладает следующими свойствами:
непрерывностью;
наличием единственного максимума у плотности распределения;
двумя точками пересечения кривой распределения с осью Ox.
В результате обработки многочисленных экспериментальных данных было установлено, что в качестве плотности вероятностей продолжительностей работ можно использовать - распределение.
Плотность вероятности - распределения имеет вид:
где
p,
q
– некоторые параметры, A
– константа, определяемая из условия
нормировки (интеграл от
должен
быть равен единице). Плотность
- распределения для
представлена ниже.
Рис. 17.1. Плотность бета-распределения
Для
определения математического ожидания
и
дисперсии
этого распределения на основании опроса
экспертов определяют три временные
оценки для каждой работы
:
оптимистическую оценку
,
т.е. продолжительность работы
при
самых благоприятных условиях;пессимистическую оценку продолжительности при самых неблагоприятных условиях
;наиболее вероятную оценку
-
продолжительность работы при нормальных
условиях.
При - распределении продолжительностей работ справедливы следующие оценки математического ожидания:
и дисперсии
В связи с тем, что часто даже специалистам трудно оценить наиболее вероятное время работы, в реальных проектах, как правило, используется упрощенная (и менее точная) оценка
Зная вероятностные характеристики продолжительностей работ, можно оценить временные параметры проекта.
17.2. Обоснование и использование центральной предельной теоремы при расчетах вероятности выполнения проекта в директивный срок
Оценку временных характеристик проекта в условиях неопределенности упрощает возможность применения центральной предельной теоремы (ЦПТ) в случае достаточно большого количества работ, принадлежащих пути L (десять и более).
В
соответствии с ЦПТ можно утверждать,
что общая продолжительность пути L
имеет нормальный закон распределения
со средним значением
,
равным сумме средних значений
продолжительностей составляющих его
работ
и
дисперсией
,
равной сумме соответствующих дисперсий
:
При малом числе работ применимость теоремы Ляпунова становится не столь хорошо обоснованной; тем не менее, и в этом случае предполагается нормальное распределение результирующих временных характеристик, т.к. отсутствуют какие-либо другие способы оценок.
Рассчитанные по методу PERT временные параметры являются по своей сути средними значениями соответствующих случайных величин. В каждом проекте возможны заметные отклонения продолжительности критического пути от среднего значения, - причем, чем больше суммарная дисперсия продолжительности работ, тем более вероятны значительные по абсолютной величине отклонения.
В
связи с этим, анализ сетей со случайными
продолжительностями работ не ограничивается
расчетами средних временных параметров
сети. Важным становится оценка вероятности
того, что срок выполнения проекта
не превзойдет заданного директивного
срока T.
Полагая случайной величиной, имеющей нормальный закон распределения, получим
где
- функция Лапласа,
,
а
-
среднее квадратическое отклонение
продолжительности критического пути.
Если рассчитанные по (6) значения вероятности выполнения проекта в срок окажутся малыми (меньше 0,3-0,5), необходимо принятие дополнительных мер (перераспределение материально-технических ресурсов по сети, пересмотр состава работ и т.п.). При значениях вероятности 0,8 и выше можно с достаточно высокой надежностью прогнозировать выполнение проекта в директивный срок.
Рассмотрим методику использования метода PERT на конкретном примере.
Пример
Руководство предприятия изучает возможности реализации новой модели холодильника. Результатом исследования должны стать рекомендации по организации производства и сбыта. Перечень работ и продолжительности их выполнения (в неделях) приводятся в таблице, а графическое представление проекта приведено на рисунке
Работа |
Содержание работы |
Непосредственно предшествующие работы |
Оптимистическое время выполнения работы |
Наиболее вероятное время выполнения
|
Пессимистическое время выпол-нения |
Ожидаемое время выполнения |
Дисперсия |
A |
Подготовка конструкторского проекта |
- |
4 |
5 |
12 |
6 |
1,78 |
B |
Разработка плана маркетинговых исследований |
- |
1 |
1,5 |
5 |
2 |
0,44 |
C |
Подготовка маршрутных карт |
A |
2 |
3 |
4 |
3 |
0,11 |
D |
Создание опытного образца |
A |
3 |
4 |
11 |
5 |
1,78 |
E |
Выпуск рекламных брошюр |
A |
2 |
3 |
4 |
3 |
0,11 |
F |
Подготовка оценок затрат |
C |
1,5 |
2 |
2,5 |
2 |
0,03 |
G |
Проведение предварительного тестирования |
D |
1,5 |
3 |
4,5 |
3 |
0,25 |
H |
Исследование рынка |
B, E |
2,5 |
3,5 |
7,5 |
4 |
0,69 |
I |
Подготовка доклада о ценах |
H |
1,5 |
2 |
2,5 |
2 |
0,03 |
J |
Подготовка заключительного доклада |
F,G,I |
1 |
2 |
3 |
2 |
0,11 |
Рис. 17.2. Сетевой график рассматриваемого проекта
Ожидаемые продолжительности работ проекта и их дисперсий рассчитаны по формулам (1) и (2), например, для работы A:
Полагая
время выполнения работы равным ожидаемому
времени ее выполнения, найдем критический
путь. При данных параметрах оказывается,
что он включает в себя работы
и равен
(ожидаемое время выполнения проекта 17
недель).
Предполагая, что распределение времени выполнения проекта является нормальным, можно определить вероятность того, что проект будет выполнен, например, не более чем за 20 недель. Дисперсия времени выполнения проекта равна сумме дисперсий работ критического пути:
Отсюда
,
и аргумент функции Лапласа равен
По
таблице функции Лапласа, найдем
,
откуда искомая вероятность равна
Для
рассмотренной сети мы можем найти лишь
приближенные оценки
и
,
так как на основании теоремы Ляпунова
вывод о нормальном законе распределения
случайной величины
правомерен
лишь для достаточно
большого
числа критических работ, а в нашем случае
их всего пять.
Важно
понимать, что метод PERT
не всегда дает надежные результаты даже
для сетей с большим числом работ.
Это связано с тем, что на практике
дисперсии некритических могут превышать
.
В этих случаях возможен переход к новым
критическим путям, которые в расчете
не учитываются.
