- •1. Основные понятия тпр. Основные модели и методы тпр. Основные этапы процесса пр. Основные понятия тпр
- •Основные методы и модели тпр
- •Этапы принятия решений
- •2. Классификация задач пр
- •3. Принятие решений Типы задач, критериев и общая схема решения. Общие группы методов решения многокритериальных задач принятия решений. Типы зпр
- •Типы критериев
- •Общие группы методов решения многокритериальных задач принятия решений
- •Исходная информация
- •Метод группировки критериев – нормализация функции полезности
- •1. Метод равномерной оптимальности
- •2. Метод справедливого компромисса
- •3. Метод свертывания критериев (аддитивный критерий)
- •4. Метод главного критерия
- •5. Метод идеальной точки (метод равномерного сжатия, минимального отличия от идеала)
- •Матрица отклонений
- •6. Метод последовательных уступок
- •Метод последовательных уступок
- •5. Нормализация критериев в условиях полной определенности. Принципы максимальной эффективности и минимизации рисков.
- •Исходная информация
- •6. Постановка задач линейного программирования. Примеры, различные формы задач и подходы решения. Постановка задач линейного программирования
- •Примеры, различные формы задач и подходы решения
- •7. Множества решений неравенств, уравнений и их систем в задачах линейного программирования. Допустимые решения. Допустимые базисные решения.
- •8. Сведения из теории выпуклых множеств. Выпуклые множества в n-мерном пространстве.
- •9. Задача линейного программирования в канонической форме. Основные теоремы о множествах оптимальных решений этой задачи.
- •10. Геометрический метод решения задачи линейного программирования m X n. Пример для задачи m X 2 (на максимум и минимум).
- •11. Аналитический метод решения задачи линейного программирования m X n (симплекс-метод). Для задач на максимум и минимум.
- •16. Ситуации равновесия в игре. Понятие седловой точки. Чистые стратегии двух игроков.
- •17. Смешанные стратегии двух игроков в матричной игре. Выигрыши игроков в игре. Теорема Дж. Фон Неймана о ситуации равновесия.
- •18. Аналитическое решение игры 2´2. Геометрическое решение игры 2´2.
- •Решение игры в смешанных стратегиях геометрическим методом
- •Решение игры 2×2
- •Решение игр вида 2хn и mх2
- •19. Лемма о масштабе. Условия эквивалентности смешанных стратегий двух игр.
- •20. Свойства оптимальных смешанных стратегий в матричной игре.
- •25. Вполне смешанная игра. Решение матричной игры n´n методом обратной матрицы.
- •26. Сведение матричной игры n´m к двойственной задаче линейного программирования. Общий подход. Методика решения матричной игры n´m симплекс-методом.
- •27. Неантагонистические игры. Биматричные игры. Постановка задачи. Функции выигрышей.
- •28. Примеры биматричных игр: дилемма узников, семейный спор, перекресток, ястребы-голуби и др.
- •36. Принятие решений в статистических играх в условиях полной определенности. Статистические методы принятия решений. Критерии Вальда, Сэвиджа, Гурвица, мм-критерий.
- •37. Принятие решений в статистических играх в условиях неопределенности. Статистические методы принятия решений. Критерии Байеса, Лапласа, Ходжа-Лемана.
- •38. Планирование эксперимента в статистических играх в условиях неопределенности.
- •39. Позиционные игры. Дерево решений. Позиционные игры с полной и неполной информацией. Информационное множество.
- •40. Нормализация позиционной игры. Привести общий пример для двухходовой позиционной игры с полной информацией.
- •41. Сведение позиционной игры к матричной в условиях неполной информации. На примере двухходовых и трехходовых игр.
- •42. Сведение позиционных игр к матричным и биматричным в условиях полной информации о стратегиях противника.
- •43. Позиционные игры со случайными ходами.
7. Множества решений неравенств, уравнений и их систем в задачах линейного программирования. Допустимые решения. Допустимые базисные решения.
8. Сведения из теории выпуклых множеств. Выпуклые множества в n-мерном пространстве.
9. Задача линейного программирования в канонической форме. Основные теоремы о множествах оптимальных решений этой задачи.
Канонической задачей линейного программирования называется задача, в которой, как было показано выше, требуется найти максимум целевой функции при ограничениях, заданных системой линейных уравнений.
Математическая модель называется канонической, если ее система ограничений представлена в виде системы m линейно независимых уравнений (ранг системы r=m), в системе выделен единичный базис, определены свободные переменные и целевая функция выражена через свободные переменные. При этом правые части уравнений неотрицательны (bi ≥ 0).
Переменные, входящие в одно из уравнений системы с коэффициентом один и отсутствующие в других уравнениях называются базисными неизвестными, а все другие – свободными.
Решение системы называется базисным, если в нем свободные переменные равны 0, и оно имеет вид: Xбаз = (0, 0; b1, …, bm), f(Xбаз) = c0
Базисное решение является угловой точкой множества решений системы, т.е. определяет вершину многоугольника решений модели. Среди таких решений находится и то, при котором целевая функция принимает оптимальное значение.
Базисное решение называется опорным, если оно допустимо, т.е. все правые части уравнений системы (или неравенств) положительны bi ≥ 0.
Компактная форма канонической модели имеет вид: AX = b X ≥ 0 Z = CX(max)
10. Геометрический метод решения задачи линейного программирования m X n. Пример для задачи m X 2 (на максимум и минимум).
Графоаналитический (графический) способ решения задач линейного программирования обычно используется для решения задач с двумя переменными, когда ограничения выражены неравенствами, а также задач, которые могут быть сведены к таким задачам.
Пусть задача линейного программирования имеет вид:
L = c1*x1 + c2*x2 → max(min) (2.1)
{ 𝑎11𝑥1 + 𝑎𝑎12𝑥𝑥2 ≤ (≥)𝑏1,
{ … … … … … …
{ 𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 ≤ (≥)𝑏𝑚, (2.2)
Где с1, с2, аi1, аi2, bi - заданные действительные числа; знаки в неравенствах произвольны; целевая функция либо максимизируется, или минимизируется.
Каждое из неравенств (2.2) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми i i bi a 1 x1 + a 2 x2 = ; i=1,…,m. В том случае, если система неравенств (2.2) совместна, допустимая область решений задачи есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых значений является выпуклое множество, которое называют многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств.
Множеством допустимых решений для данной частной задачи может быть:
• пустая область;
• выпуклый многоугольник, включая вырожденные случаи - отрезок и единственную точку;
• выпуклая многоугольная неограниченная область, включая вырожденные случаи - луч и прямую.
Практическая реализация решения задачи линейного программирования (2.1) – (2.2) на основе ее геометрической интерпретации включает следующие этапы:
1. Построить прямые, уравнения которых получаются в результате замены в ограничениях (2.2) знаков неравенств на знаки равенств.
2. Найти полуплоскости, определяемые каждым из ограничений. Соответствующая полуплоскость может быть найдена подстановкой в неравенство координат какой-нибудь «простой» точки - (0,0), (0,1) или (1,0). Главное - чтобы эта точка не принадлежала границе полуплоскости. Если после подстановки неравенство окажется справедливым, то выбирается та полуплоскость, где содержится эта точка. Если неравенство не справедливо, то выбирается альтернативная полуплоскость.
3. Определить многоугольник решений как пересечение найденных полуплоскостей.
4. Построить градиент целевой функции, т.е. вектор ( ) ( , ) 1 2 grad L = с с , координатами которого служат коэффициенты целевой функции L. Этот вектор определяет направление наискорейшего возрастания целевой функции.
5. Построить ряд линий уровня целевой функции L, т.е. прямых, перпендикулярных градиенту L. При этом построение линий уровня следует вести в направлении градиента, если решается задача на максимум, и в противоположном направлении (в направлении «антиградиента»), если решается задача на минимум. В результате отмечается точка (точки), в которой линии уровня в последний раз касаются допустимого множества.
Пример: