- •Введение
- •1.Основные понятия и принципы моделирования Определение моделирования
- •1.1. Принципы построения математических моделей
- •Обобщенная математическая модель
- •1.2. Оценка эффективности стратегий
- •1.3. Классификация задач исследования операций
- •1.4. Модели выбора решений в условиях определенности
- •2. Математическое программирование
- •Формы записи задач линейного программирования
- •2.1. Постановка задачи линейного программирования.
- •Решение задачи лп графическим методом :
- •Геометрическая интерпретация и графический метод решения задачи линейного программирования
- •3. Геометрическая интерпретация задач линейного программирования
- •2.1.1 Симплексный метод решения задач линейного программирования
- •2.1.2Алгоритм симплекс метода отыскания оптимального решения задачи линейного программирования
- •2.1.3Примеры решения задач симплексным методом Пример 1. Найти максимум целевой функции
- •§4. Решение задачи лп двухфазным симплекс-методом
- •2.1.4 Задачи для закрепления полученных знаний
- •2.1.5. Двойственная задача
- •2.1.6Основные теоремы двойственности
- •2.1.7. Транспортная задача
- •2.1.8. Первоначальное распределение поставок
- •2.1.9. Правило "Северо-западного угла"
- •2.1.11. Метод потенциалов.
- •2.2. Модели динамического программирования
- •2.2.1. Постановка задачи динамического программирования
- •2.2.2. Принцип оптимальности и математическое описание динамического процесса управления
- •2.2.3. Оптимальное распределение инвестиций
- •2.2.3. Выбор оптимальной стратегии обновления оборудования
- •2.3. Сетевое моделирование. Методы и модели теории графов и сетевого моделирования
- •2.3.1. Элементы теории графов
- •2.3.2. Сетевое планирование и управление
- •2.3.3. Основные понятия и терминология, используемые в сетевом планировании
- •2.3.4. Порядок построения сетевых графиков
- •2.3.5. Правила построения сетевого графика.
- •2.3.6. Основные понятия сетевого графика
- •2.3.7. Временные параметры сетевых графиков
- •3. Задачи в условиях неопределенности
- •3.1. Системы массового обслуживания
- •3.1.1. Структура простейшей системы массового обслуживания.
- •3.1.2. Система массового обслуживания с отказом. Одноканальная система.
- •3.1.3. Системы массового обслуживания с ожиданием.
- •Имитационное моделирование
- •3.2.1. Основы имитационного моделирования
- •3.2.2. Метод статистических испытаний
- •3.2.3. Формирование случайных чисел на эвм
- •3.3. Модели прогнозирования. Задачи управления запасами
- •3.3.1.Основные понятия управления запасами
- •3.3.2. Классификация моделей управления запасами
- •3.3.3. Складская система
- •3.3.4. Спрос на товары
- •3.3.5. Возможность пополнения запасов
- •3.3.6. Затраты на функционирование системы управления запасами
- •3.3.7. Стратегия управления запасами
- •3.3.8. Основные детерминированные модели. Простейшая модель управления запасами ( модель 1)
- •3.3.9. Модель с учетом дефицита (модель 2)
- •С помощью этих соотношений исключим т1, т2, т и получим
- •Оптимальное значение
- •График зависимости уровня запаса на складе от времени
- •Методы и модели теории игр
- •3.4.1. Основные понятия теории игр
- •3.4.2. Постановка игровых задач
- •3.4.3. Методы решения игровых задач
- •3.4.4. Метод линейного программирования
- •Литература
3.4.4. Метод линейного программирования
Матричную игру можно свести к паре двойственных задач линейного программирования.
Рассмотрим игру, заданную платежной матрицей А:
а11 а12 …. а1n
а21 а22 …. a2n
A= ……………
аm1 аm2 …. amn
Пусть платежная матрица не содержит седловой точки, т.е. игра решается в смешанных стратегиях.
Если игрок В применяет свою чистую стратегию Вj , а игрок А – свою оптимальную стратегию, то средний выигрыш игрока равен:
j= а1jp1 + а2jp2+…+ аmjpm
(j=1…n)
Если игрок A применяет свою чистую стратегию Ai , а игрок B – свою оптимальную стратегию, то средний выигрыш игрока равен:
i= аi1q1 + аi2q2+…+ аinqn
(i=1…m)
Учитывая, что j не может быть меньше для игрока А, а j не может быть больше для игрока В.
Двойственную задачу можно записать следующим образом:
для игрока А :
m
аijpi> = (>0) (j=1…n)
i=1
m
pi=1
i=1
для игрока В :
n
аijqj< = (>0) (i=1…m)
j=1
n
qi=1
j=1
Разделив левую и правую части неравенств на >0, получим:
m
аijpi/> =1 (j=1…n)
i=1
n
аiiqj/< =1 (i=1…n)
j=1
Введем обозначения:
xi= pi/ (xi>=0)
yj= qj/ (yj>=0)
Из выше написанных выражений переменные xi и yj удовлетворяют условиям:
m
xi =1/
i=1
n
yj =1/
j=1
Учитывая, что игрок А стремиться максимизировать , а игрок В стремиться минимизировать , переменные xi и yj должны быть выбраны так, чтобы целевые функции F(x) и Ф(х)
m
F(x) = xi min
i=1
m
аijxi> =1 (j=1…n)
i=1
n
Ф(x)= yjmax
j=1
n
аijyi< =1 (i=1…m)
j=1
Эти задачи могут быть решены симплексным методом, т.е. найдены xi и yj.
m
=1/ xi
i=1
или n
=1/ yj
j=1
m
pi = xi / xi (i=1…m)
i=1
n
qj =yj./ yj (j=1…n)
j=1
Таким образом, можно принимать обоснованные, близкие к оптимальным решениям управления в условиях неопределенности.
Что Вы должны знать:
(вопросы для самоконтроля)
Каковы основные термины и определения теории игр?
Что из себя представляет платежная матрица?
Какая пара стратегий определяет седловую точку7
Каков принцип минимакса?
Пример для закрепления:
Определите оптимальные стратегии игроков, верхнюю и нижнюю цену игры
-
В1
В2
В3
В4
В5
А1
5
8
7
6
3
А2
10
12
4
7
2
А3
15
10
8
7
4
А4
10
7
8
12
6
А5
7
10
11
3
5
А6
7
2
3
12
4