01 - Лекция

Введение

Механизм принятия решений

- Подготовка решения Анализ ситуации, определение проблемы - Принятие решения Выдвижение альтернативных способов решения, определение критериев выбора, взвешивание альтернатив, выбор необходимого - Реализация решения Осуществление намеченного, корректировка

!Pasted image 20240904195123.png

Это не наша область, наша справа
Мы будем принимать решения математических моделей
Сюда относится несколько классов. С некоторыми вы уже знакомы:
Игровые модели и Оптимизационные модели

А начнем мы с оптимизационных моделей

А оптимизационные делятся на 2 класса: непрерывные и дискретные

Методы принятия решений:
!Pasted image 20240904195228.png
Эта табличка уже относится не к теории принятия решений, а уже к методам
Математические методы тоже делятся на свои классы: Формализованный и неформализованные
Формализованные:
1. Аналитические
2. Статистические
3. Математического программирования
4. Теоретико-игровые
Неформализованные:
1. Мозговой штурм
2. Метод Дельфы
3. Метод сценариев
4. Метод дерева решений
Мы будем заниматься аналитическими и статистическими методами. Но основное у нас будет мат. программирование и теория игр.

Этапы работы
А теперь мы будем рассматривать этапы работы
Эти этапы придется проделывать. Если говорить о самом алгоритме принятия решений, то он поэтапный
!Pasted image 20240904195419.png
У вас первые 3 пункта будут даны, чаще всего (выявление, диагностика и формулирование проблемы)
То есть вам будет дана постановка задачи
А вот формулировку проблемы, то есть что вы хотите улучшить или увеличить - будете делать сами. Определять что лучше.
Теперь четвертый пункт: Всегда есть ограничения и сдерживающие факторы. Нужно определить ограничения, записать что нас сдерживает.
Пятый пункт: Почему мы принимаем решения? Потому что у нас всегда есть альтернативы, а мы стремимся к выбору оптимального решения.
Пункты 5-7: Проблемы решаются не однозначно. Мы ставим свои критерии и выбираем метод решения.

!Pasted image 20240904195516.png

Первая тема: Задачи линейного программирования. Графический метод
Мы будем рассматривать левую часть и чуть правой

Несколько базовых терминов: целевая функция, поля решений, альтернативы решений, результаты, состояния среды

!Pasted image 20240904195540.png

анализ проблемы и среды
постановка задачи
выбор метода решения задачи
решение задачи (математическая и компьютерная обработка данных, имитационных и экспертные оценки, уточнение и модификация, если это необходимо)
анализ и интерпретация результатов.

Теперь мы с вами приступаем к математическому аппарату. Вы должны знать как выглядит общая задача

$f (x) = c_{1} x_{1} + c_{2} x_{1} + . . . + c_{n} x_{n} \to m a x / m i n$ - целевая функция

Но в этих задачах есть системы ограничений
$a_{11} x_{1} + a_{12} x_{2} + . . . + a_{1 j} x_{j} + a_{1 n} x_{n} \leq b_{1}$
$a_{21} x_{2} + a_{22} x_{2} + . . . + a_{2 j} x_{j} + a_{2 n} x_{n} \leq b_{2}$
$. . . . . . .$
$a_{i 1} x_{1} + a_{i 2} x_{2} + . . . + a_{i j} x_{j} + a_{m n} x_{n} \leq b_{i}$
$x 1, x 2, x 3, x 4, . . ., x n \geq 0$

Сейчас мы будем рассматривать графический метод

Графический метод решения задачи

Графический метод решения задач линейного программирования используется для решения задач с двумя переменными, когда ограничения выражены неравенствами, а также задач, которые могут быть, сведены к таким задачам.

Следующий термин: множество допустимых решений
Как может выглядеть это множество. Оно может быть пустым, многоугольником (причем в таком многоугольнике может быть частный случай: точка, отрезок), неограниченным.

Множество допустимых решений для данной задачи может быть:

пустая область
выпуклый многоугольник, включая вырожденные случаи - отрезок и единственную точку
- выпуклая многоугольная неограниченная область включая вырожденные случаи - луч и прямую

Алгоритм решения
1. Построить прямые
2. Определить полуплоскости
3. Определить ОДР (область допустимых решений)
4. Построить вектор-градиент
5. Построить линии уровня

И теперь начинается блок анализ результатов. Мы смотрим достигла ли функция максимума. Если да - мы счастливы, если нет - перемещаем линии уровня до вектора-градиента

Пример:
$F (x) = 5 x_{1} + 4 x_{2} \to m a x$
$6 x_{1} + 4 x_{2} \leq 24$ (1)
$x_{1} + 2 x_{2} \leq 6$ (2)
$x_{2} \leq 2$ (3)
$x_{2} - x_{1} \leq 1$
$x_{1, 2} \geq 0$

Словесный алгоритм графического метода
1. Неравенство превращаем в равенство и строим прямые
2. Заштриховываем полуплоскость для каждого ограничения неравенства
3. Определяем ОДР
4. Строим вектор-градиент (по частным производным целевой функции)
$f = c_{1} x_{1} + c_{2} x_{2} \to m a x$
$a_{11} x_{1} + a_{12} x_{2} \leq b_{1}$
$a_{21} x_{1} + a_{22} x_{2} \leq b_{2}$
$x_{1} \geq 0; x_{2} \geq 0$
5. Строим линию уровня
6. Перемещаем линию уровня вдоль градиента (рисуем несколько)
7. Определяем координаты точки

Шаг 1. Определим множество решений
Для того чтобы найти множество точек, координаты которых удовлетворяют первым четырем неравенствам системы ограничения, нужно построить граничные прямые

$6 x_{1} + 4 x_{2} = 24$
$x_{1} + 2 x_{2} = 6$
$x_{2} = 2$
$x_{1} + x_{2} = 1$

!Pasted image 20240904200608.png
!Pasted image 20240904200638.png

Шаг 2. Вектор-градиент
Для определения направления движения к оптимуму построим вектор-градиент C. координаты которого являются частными производными целевой функции.
!Pasted image 20240904200657.png

Шаг 3. Линия уровня
Приравниваем целевую функцию к постоянной величине $a$ :
Это уравнение является множеством точек, в котором целевая функция принимает значение $a$ , Меняя значение $a$ , получим семейство параллельных прямых, каждая из которых называется линией уровня.
Линия уровня $F$ задается уравнением $$5x_1 + 4x_2 = const$$На рисунке построены линии уровня, соответствующие значениям 10, 12 и 21
!Pasted image 20240904201023.png

Шаг 4. Найдем решение
Найдем значения переменных $X_{1}$ и $X_{2}$ , при которых целевая функция принимает максимальное значение.
Поэтому перемещаем $F$ по направлению вектора С, до линии уровня, являющейся границей полуплоскости, целиком содержащей ОДР.
При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, при минимизации - в противоположном направлении.

Шаг 5.
Решая систему уравнений, состоящую из уравнений прямых $6 x_{1} + 4 x_{2} \leq 24$ и $x_{1} + 2 x_{2} \leq 6$ В результате получим значение для $X_{1}$ и $X_{2}$ равные 3 и 1.5 соответственно. Следовательно, целевая функция имеет максимальное значение в точке (3;1.5), при этом $F m a x = 3 * 5 + 1.5 * 4 = 21$

Частные случаи.
!Pasted image 20240904201334.png
!Pasted image 20240904201345.png!Pasted image 20240904201351.png