Файл: Материалы по курсу (часть 1).docx

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

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

– всегда управляемое мероприятие (т.е. от нас зависит, какие параметры выбрать и как организовать).

– определенный выбор параметров составляет решение

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

Раз мы говорим об оптимизации, то необходимо операции сопоставить функцию эффективности.

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

В исследовании операций вводят показатель эффективности или целевую функцию (ЦФ). Как правило, ЦФ определяется моделью операции, а модель операции, в свою очередь, определяет круг методов оптимизации.

Основные математические модели операций.

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

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

w = w (α₁, α₂, …, x₁, x₂, …), где α_i – некоторые известные факторы, на которые мы влиять не можем;

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

Параметры α могут быть числа, функции, различные ограничения, которые накладываются на x.

Параметры x могут быть либо числа, либо функции.

Для такой модели возникает класс вариационных задач.

– Если известно аналитическое выражение w, то используются поисковые методы для обнаружения экстремумов функции.

– Если вид функции не известен (т.е. нет формулы), то используются следующие поисковые методы:

– метод перебора;

– метод пропорционального поиска;

– градиентный метод.

Если α – линейные ограничения на элементы решения x_i, то чаще используют методы линейного программирования.

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

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

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

w = w (α₁, α₂, …, y₁, y₂, …, x₁, x₂, …),

где α_i – некоторые известные факторы, на которые мы влиять не можем;

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

y_i – неизвестные фактора (условия) проведения операции.

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

– Если y_i – параметры, обладающие статистической устойчивостью (подчиняются некоторым статистическим законам распределения), тогда

y_i заменяются на средние и применяются методы, что и в детерминированных случаях или используют оптимизацию в среднем.

Оптимизация в среднем – процедура нахождения w_max заменяется на нахождение _max.

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

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

Начало из вопроса 1 (от начала до основные математические модели.

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

Пусть у нас имеется несколько показателей эффективности (группа целевых функций): w₁, w₂, …, w_k. Одни из них нужно максимизировать, а другие минимизировать.

Достижение МАКСИМАЛЬНОГО ЭФФЕКТА при МИНИМАЛЬНЫХ ЗАТРАТАХ – некорректная формулировка задачи, так как практически невозможна.

Поэтому, мы достигаем МАКСИМАЛЬНОГО ЭФФЕКТА при ЗАДАННЫХ ЗАТРАТАХ (т.е. мы фиксируем затраты)

или

достигаем ЗАДАННОГО ЭФФЕКТА при МИНИМАЛЬНЫХ ЗАТРАТАХ (т.е. параметры ограничиваются).

Пути решения:

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

Пусть дано 2 показателя: s – стоимость лекарств, w – вероятность раннего выздоровления.

Нам нужно МИНИМИЗИРОВАТЬ s и МАКСИМИЗИРОВАТЬ w.

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

, но это не очень хороший показатель, т.к. если знаменатель устремить к 0, то числитель роли играть не будет.

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

в) Использование составных критериев в виде взвешенной суммы.

u = a₁*w₁ + a₂*w₂ + … + a_k*w_k, где a_i – коэффициенты, которые связаны со степенью важности.

При этом естественно задать коэффициенты следующим образом:

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

Многоэтапная процедура. Показатели эффективности (ПЭф) ранжируются по весу.

Задача: нахождение max первого показателя при ограничении оставшихся.

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

ВСТУПЛЕНИЕ (вдруг нужно будет для полноты ответа)

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

1. Показатель эффективности (w) – представляет собой линейную функцию от элементов решения (x_i).

2. Ограничительные условия (элементы α) имеют вид линейных равенств или линейных неравенств.

Такие задачи оптимизации – задачи линейного программирования.

Рассмотрим задачу, где ограничительные условия (элементы α) имеют вид линейных равенств – ОСНОВНУЮ ЗАДАЧУ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ОЗЛП).

Формулировка основной задачи линейного программирования.

Имеется ряд переменных х₁, х₂, …, х_n. Требуется найти такие неотрицательные (≥0) значения этих переменных, которые бы удовлетворяли системе линейных уравнений (СЛУ) следующего вида:

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

В некоторых задачах функция L может максимизироваться. Ее также можно привести к стандартному виду, поменяв знак.

Допустимое решение основной задачи (ДРОЗ) – любая совокупность решений х_j ≥ 0, j = . Которая удовлетворяет (*).

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

Основная задача ЛП необязательно должна иметь решение.

СЛУ (*) может как иметь так и не иметь решений.

Может оказаться так, что допустимые решения основной задачи (ДР ОЗ) существуют, но среди них нет оптимального: функция L в области допустимых решений не ограничена сверху.

Рассмотрим вопрос о существовании оптимальных решений.

Рассмотрим вопрос о существовании допустимых решений.

При рассмотрении данного вопроса можно не рассматривать линейную функцию L.

В линейной алгебре доказывается, что для совместимости системы линейных уравнений (СЛУ) необходимо и достаточно, чтобы ранг матрицы системы (r_c) был равен рангу расширенной матрицы (r_р).

СЛУ имеет решение при r_c = r_p.

Очевидно, что r ≤ m (число уравнений) и r ≤ n (число неизвестных).

Мы это писали на паре (скорее всего, пригодится).

Матрица СЛУ – таблица, составленная из коэффициентов при неизвестных х₁, х₂, …, х_n.

Расширенная матрица – матрица системы, дополненная столбцом свободных членов.

Ранг – наибольший порядок отличного от нуля определителя, который можно получить, исключая, строки и столбцы, чтобы перейти к квадратной матрице.