Материал: Материалы по курсу (часть 2)

Оглавление

1.Методы принятия оптимальных решений. Математические модели операции: детерминированный случай, оптимизация решений в условиях неопределенности. 2

2.Методы принятия оптимальных решений. Оценка операции по нескольким показателям. 4

3.Основная задача линейного программирования (ОЗЛП). Допустимые решения и оптимальное решение задачи ЛП. 11

4.Геометрическая интерпретация ОЗЛП. 14

5.Задача ЛП с ограничениями-неравенствами. Переход от нее к основной задаче. 21

6. Симплекс-метод решения задачи ЛП 24

7. Табличный алгоритм замены переменных. 27

8. Отыскание опорного решения задачи ЛП на основе табличного алгоритма замены переменных. 38

9. Отыскание оптимального решения основной задачи линейного программирования на основе табличного алгоритма замены переменных. 42

10. Метод динамического программирования (ДП). Алгоритм решения задач управления состоянием организма в биотехнических системах. Основное рекуррентное уравнение ДП. 46

11. Управление переходом организма из исходного в конечное состояние методом ДП: использование ориентированного графа. 50

12. Управление переходом организма из исходного в конечное состояние в условиях неопределенности. 53

13. Игровые методы обоснования решений. Основные понятия теории игр. Платежная матрица. 59

14. Нижняя и верхняя цена игры. Принцип минимакса. Решение игры в чистых стратегиях. 60

15. Решение игры в смешанных стратегиях. 62

16. Игры 2х2 и их решение. 66

17. Геометрическая интерпретация решений игры 2х2. 67

18. Решение игр 2хn 72

19. Решение игр mx2 77

20. Решение игр mxn. 80

1. Методы принятия оптимальных решений. Математические модели операции: детерминированный случай, оптимизация решений в условиях неопределенности.

Операция  любое управляемое мероприятие (система действий), объединенное единым замыслом, направленное на достижение опред. цели.

Определенный выбор, зависящих от нас параметров, составляют решения.

Основная задача исследования операций  предварительное количественное обоснование оптимальных решений.

Функцию эффективности составляют операции.

Эффективность операции  степень приспособленности к стоящей задаче (чем лучше организована операция, тем она эффективнее).

В исследовании операций вводятся показатели эффективности или целевая функция.

Целевая функция определяется моделью операции.

Модель операции определяет круг методов оптимизации

Математические модели операции

Детерминированный случай

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

W – показатель эффективности

W=W(₁,₂,…;x₁,x₂…)

_i – некоторые известные факторы

x_i – элементы решения, которые зависят от нас, факторов

параметры  могут быть некоторые числа, функции, ограничения на элементы решения, x  числа или функции

Возникает класс вариационных задач

если известно аналитическое решение этой модели, используется поиск экстремумов функции;

если вид функции неизвестен  поисковый метод, пройдя пошагово по ф-и, или метод пропорционального поиска, градиентный поиск.

Если параметры   это линейная ф-я, используются методы линейного программирования.

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

Оптимизация решений в условиях неопределенности

W=W(₁, ₂,…;y₁,y₂…; x₁,x₂…)

y_i  неизвестные условия проведения операции

Применяемые методы зависят от природы y_i

Примеры:

1. если y_i параметры, обладающие статической устойчивостью, y_i заменяются в < y_i >и используются методы детерминирования случая, или используют оптимизацию в среднем W->max => <W>->max

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

3. y_i зависят не от объективных обстоятельств, а зависят от активного противодействия, противника (при боевых действиях, спортивных соревнованиях, конфликтные ситуации)

Для выработки тактики используют теорию игр

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

2. Методы принятия оптимальных решений. Оценка операции по нескольким показателям.

Оценка операции по нескольким показателям

Пусть есть несколько показателей эффективности W1, W2,…W_k

некоторые максимизируются, другие минимизируются

достижения максималного эффекта при минимуме затрат НЕКОРРЕКТНО

ПРАВИЛЬНО: достижения максимума эффективности при заданных затратах или наоборот

1. отбрасывание заведомо плохих вариантов

пусть операция оценивается по 2 показателям

2. использование составных критериев

U= Wi ->max, Wk ->min

не хорошо т. к. недостаток одного можно компенсировать другим показателем

3. составной критерий

U=a1W1+a2W2+…+a_kW_{k (}взвешенная сумма)

a_i> 0, если Wi ->max

a_i <0, если Wi -> min

a_i  коффициенты, которые связаны со степенью важности каждого веса

4. сведение к одному показателю с некоторыми ограничениями

многоэтапная процедура самый важный показатель впереди (ранжирование) нахождение максимума первого показателя при ограничениях на остальных

Любая задача линейного программирования (ЛП) может быть сведена к его основной задаче, формулируемой математически следующим образом. Имеется ряд переменных .Требуется найти такие неотрицательные значения этих переменных, которые бы удовлетворяли системе линейных уравнений:

……………………………………….

(1.1)

и, кроме того, обращали бы в минимум линейную функцию

(1.2)

Где заданные постоянные коэффициенты.

Допустимым решением основной задачи ЛП называют любую совокупность переменных

удовлетворяющую уравнениям (1.1).

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

Наконец, может оказаться, что допустимые решения основной задачи ЛП существуют, но среди них нет оптимального: функция L в области допустимых решений не ограничена снизу.

Матрицей системы линейных уравнений (1.1) называется таблица, составленная из коэффициентов при

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

Структура задачи линейного программирования существенно зависит от ранга системы ограничений (1.1). Рассмотрим прежде всего случай, когда r=n, т. е. когда число линейно независимых уравнений, входящих в систему (1.1), равно числу переменных n. Если отбросить уравнения, являющиеся линейными комбинациями других, система уравнений-ограничений основной задачи ЛП принимает вид

(1.3)

Так как r = n, то определитель, составленный из коэффициентов,

Если среди этих решений нет ни одного, для которого все неотрицательны, это значит, что основная задача ЛП не имеет допустимого, а следовательно, оптимального решения.

Если же существуют какие-то решения системы (1.1), для которых все

неотрицательны, то каждое из них допустимо. Возникает задача – найти среди допустимых решений оптимальное, т. е. такое решение для которого линейная функция (1.2) обращается в минимум.