Краткое знакомство

3. 1) Функциональная схема интегрированной системы поддержки принятия решений по управлению структурной динамикой СОТС.

2) Интегрированная экспертная система поддержки принятия решений.

3) Инструментальные CASE-системы

4) Обобщенная структура имитационной системы.

5) Имитационная система для комплексного моделирования АСУ АПО.

4. Значительная часть задач принятия решения – это задачи распределения ресурсов между объектами. Цель задачи распределения ресурсов устанавливается какой-либо одной из двух взаимоисключающих постановок:

1) при заданных ресурсах максимизировать получаемый результат;

2) при заданном результате минимизировать потребные ресурсы.

Задачи, в которые переменные x_j входят в виде линейных зависимостей, называют задачами ЛП. Каждая задача ЛП содержит ЦФ, ограничения, граничные условия.Для решения задач ЛП используют графический и аналитический методы.Всистеме неравенства, устанавливающие зависимости для ресурсов – ограничения, а предельно допустимые значения переменных – граничные условия. В ограничениях левые части неравенства – потребные ресурсы, а правые–располагаемые. В системе дополнительные переменные–это разность между располагаемым ресурсом и потребным и, следовательно, равные неиспользуемому ресурсу, т.е. это резервы каждого вида ресурсов. Если получить оптимальное решение очень важно, то иметь допустимое решение – необходимо.

5. Если линейное уравнение с двумя переменных может быть представлено прямой на плоскости, то неравенство изображается как полуплоскость. Решение системы неравенств – координаты всех точек, принадлежащих ОДР. Так как в ОДР бесчисленное множество точек, значит рассматриваемая задача имеет бесчисленное множество допустимых решений. Не любая система линейных неравенств имеет ОДР, т.е. допустимые решения.

С увеличением числа переменных выше трёх, геометрическая интерпретация невозможна, но система неравенств – ОДР в k -мерном пространстве. Оптимальное решение – координаты вершины ОДР. Метод решения задач ЛП. 1. Найти вершины ОДР как точки пересечения ограничений. 2. Определить последовательно значения ЦФ в вершинах.

3. Вершина, в которой ЦФ приобретает оптимальное (max или min) значение, является оптимальной вершиной.4. Координаты оптимальной вершины есть оптимальные значения искомых переменных.

6. Каждой задаче ЛП можно некоторым образом сопоставить другую задачу ЛП, называемую двойственной по отношению к исходной (прямой). ДЗ по отношению к прямой составляют согласно правилам: 1) ЦФ ПЗ задаётся на max, тогда ЦФ ДЗ – на min, и наоборот; 2) матрица, составленная из коэффициентов в системе ограничений ПЗ, и аналогичная матрица в ДЗ получаются друг из друга транспонированием; 3) число переменных в ДЗ (т) равно числу соотношений (ограничений) в ПЗ, а число ограничений ДЗ (п) – числу переменных в ПЗ; 4) коэффициенты при неизвестных в ЦФ ДЗ – свободные члены (b _i), а правые части в ограничениях ДЗ (c_j) – коэффициенты при неизвестных в ЦФ ПЗ; 5) если переменная x_j ПЗ может принимать только положительные значения (x_j ³ 0), то j -е условие ПЗ – условие неравенства вида «³». Если i -е соотношение в ПЗ – неравенство, то i -я переменная ДЗ z_i ³ 0. Если ПЗ имеет решение, то и ДЗ тоже имеет решение. Поэтому достаточно для отыскания оптимума решить одну какую-либо из задач двойственной пары, обычно решают ту, которая проще. Оптимальный план двойственной задачи позволяет оценить степень дефицитности ресурсов, потребляемых при выполнении оптимального плана исходной задачи. Свойства двойственной задачи ЛП. 1. max(min) L ₁ = min(max)L ₂ 2. При подстановке оптимальных значений двойственных переменных в систему ограничений двойственной задачи возможны следующие ситуации: 3. Как и в прямой задаче в двойственной задаче должны вводиться дополнительные (вспомогательные) переменные 4.

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

7. Рассмотрим неравенство ах £ b. Если от неравенства мы хотим перейти к уравнению, то введём дополнительную переменную у и запишем ах + у = b, т.е. получим одно уравнение с двумя неизвестными. В этой системе общее число неизвестных N = n + m, где п – число основных неизвестных x_j; т – число дополнительных неизвестных y_i, которое равно числу уравнений. Возможны три варианта соотношения величин N и т.

1. Число неизвестных меньше, чем число уравнений: N < m. Е сли число неизвестных N меньше числа уравнений т, то система решения не имеет и является несовместной. 2. Число неизвестных равно числу уравнений: N = m. Линейная система, в которой число неизвестных N равно числу уравнений т, имеет одно решение. 3. Число неизвестных больше числа уравнений: N > m. Если в системе число неизвестных N больше числа уравнений т, то такая система имеет бесчисленное множество решений.

В случае, когда система имеет более одного возможного решения, может быть поставлена задача оптимизации. При этом суть такой задачи в том, чтобы из всех допустимых решений, удовлетворяющих ограничениям и граничным условиям, выбрать такое, которое придаёт ЦФ оптимальное, т.е. максимальное или минимальное значение. Если все ограничения и ЦФ линейны, задача оптимизации, как нам известно, является задачей ЛП. Выводы:1. Если оптимальным решением являются координаты вершины ОДР, то это значит, что сколько вершин имеет ОДР, столько оптимальных решений может иметь задача. 2.Поскольку чем больше ограничений, тем больше вершин, то, следовательно, чем больше ограничений, тем больше оптимальных решений.3.Дополнительные ограничения в задачах ЛП не улучшаются ранее полученных оптимальных решений.

8.Транспортная модель является частным случаем общей сетевой модели оптимизации. Представим транспортную модель в следующем виде. Имеется:- множество поставщиков A = {A_i, i = 1,…, m}; - множество потребителей B = {B_j, j = 1,…, n}. Каждому поставщику соответствует объем имеющегося у него ресурса a_i, а каждому потребителю сопоставляется объем необходимого для него ресурса b_j. Предполагается, что каждый поставщик соединен с каждым потребителем, т.е. множество дуг такой сети E = A ´ B. Задана функция c: E ® R¹, характеризующая некоторое качество (время, стоимость, и т.п.) перевозки по дуге
e_ij = (A_i, B_j) Î E. В этом случае математической конструкцией, описывающей решение, может являться вектор x = (x₁₁, x₁₂,....,x_1n, x₂₁,....,x_2n,...., x_mn)^т = ║x_ij║,

компоненты которого x_ij характеризуют объем перевозок от поставщика A_i к потребителю B_j. Ограничения накладываются на объем продукции, вывозимой от i -го поставщика, и количество продукции, которую необходимо завести j -му потребителю. Целевая функция характеризует суммарные расходы на все такие перевозки. Транспортная задача (6)–(9) описывается линейными ограничениями и линейной целевой функцией, следовательно, для ее решения могут использоваться стандартные методы линейного программирования (симплекс-метод, например).

9. Частным случаем классической транспортной задачи является задача о назначениях. Практическая суть задачи, из которой и возникло ее название, заключается в том, что имеется (n) должностей, на которые могут быть назначены (n) кандидатов, причем назначение некоторого i –го кандидата на j -ю должность связано с расходами равными c_ij. Необходимо так распределить кандидатов на должности, чтобы суммарные расходы были минимальны. Такая задача относится к классу задач линейного дискретного (целочисленного, булевого) программирования.

10. 1. Задача выбора, в которой зависимости между переменными в целевой функции и/или в ограничениях являются нелинейными, называется задачей нелинейного программирования. 2. Множество (область) R ⁿ называется выпуклым, если с каждыми двумя точками (альтернативами) и , ему принадлежащими, оно включает весь отрезок, соединяющий данные точки. Глобальным максимумом (минимумом) называют такой максимум (минимум), который больше (меньше) всех остальных. Наибольшее или наименьшее значение функции без учета того, где находится такое значение, — внутри заданного интервала или на его границе — называют оптимумом. Оптимум — более широкое понятие, чем экстремум. Если экстремум есть не у всех функций, то в практических задачах оптимум, как правило, есть всегда. Так же как и экстремумы, оптимумы могут быть локальными и глобальными. Задачи нелинейной оптимизации с точки зрения методов решения делятся на два класса:

r задачи безусловной оптимизации;

r задачи условной оптимизации.

11. Под эффективностью того или иного алгоритма, как правило, понимается объем вычислений, необходимый для получения приемлемого решения, который складывается из трудоемкости отдельной итерации и общего количества итераций вычислительного процесса. В настоящее время для решения различных задач нелинейного программирования разработано большое количество алгоритмов, построенных на использовании тех или иных методов, обладающих различными характеристиками и областью эффективной применимости. Общей особенностью указанных алгоритмов является то, что все они, как правило, для поиска оптимального решения в той или иной степени используют следующую итерационную схему:

x^k+1 = x^k + h_k r(x^k), k = 0,1,....Здесь k - номер итерации; x^k - решение на k-ой итерации; r(x^k) - направление, в котором изменяется значение x^k; h_k - переменная, показывающая величину изменения (длину шага) вектора x^k в направлении r(x^k); h_k ≥ 0. В алгоритмах подобного типа необходимо анализировать (доказывать) сходимость (и скорость сходимости) последовательности {x^k, k=0,1,...} к оптимальному решению x*. Критерием окончания итерационного процесса служит выполнение неравенства

║ x^k – x*║ ≤ e. Для реализации итерационного процесса (1) необходимо:а) задавать начальное значение x^o;б) на каждом k-ом шаге уметь вычислять направление r(x^k), и величину шага h_k; в) задавать критерий окончания итерационного процесса e. С точки зрения области применимости алгоритма различают универсальные (широкоспециализированные) и специализированные (узкоспециализированные) алгоритмы. У н и в е р с а л ь н ы е алгоритмы предназначены для решения широкого класса задач нелинейного программирования. При построении этих алгоритмов используются самые общие свойства задач; выпуклость функций, дифференцируемость функций, замкнутость множества допустимых альтернатив и т. п.С п е ц и а л и з и р о в а н н ы е алгоритмы в той или иной степени учитывают специфику функций, описывающих множество допустимых альтернатив и целевой функции. Прежде всего, такая специфика выражается в линейности этих функций. В зависимости от вида целевой функции различают задачи:

– к в а д р а т и ч н о г о программирования; целевая функция имеет вид:
f(x) = c^тx + x^тDx, где D — неположительно определенная матрица;

– б и л и н е й н о г о программирования; целевая функция имеет вид:
f(x) = c^тx + d^тy + x^тG y; – д р о б н о - л и н е й н о г о программирования. С точки зрения особенностей математических методов оптимизации, используемых при построении алгоритмов, можно различать:1) алгоритмы, использующие методы приведения исходной задачи нелинейного программирования с ограничениями к задаче оптимизации некоторой функции в условиях отсутствия ограничений;2) алгоритмы прямого решения исходной задачи;3) специальные алгоритмы, использующие методы преобразования функций, процедуры случайного поиска и другие.

13. Аналитические методы решения задач НЛП. Обобщенный алгоритм решения задачи НЛП включает в себя следующие этапы:

1.Формирование функции Лагранжа 2. Вычисление производныхСоставление системы нелинейных алгебраических уравнений. 3. Поиск решений указанной системы уравнений (поиск экстремумов функции Лагранжа). 4. Поиск вторых производных функции Лагранжа, определение вида экстремума.Численные методы решения задач НЛП: Суть метода состоит в последовательном приближении к оптимальному решению x^* на основе проведения ряда итераций вида x^k+1 = x^k + h_k ÑF(x^k), k = 0,1,.... Алгоритмы, построенные на основе градиентного метода, носят итерационный характер; итерация состоит в выполнении ряда шагов.

0. Исходное состояние. Задается начальная точка x^o, некоторое малое
e ≥ 0; k = 0.1. Рассчитывается градиент в точке x^k; ÑF(x^k).2. Задается шаг h_k.3. Находится x^k+1 = x^k + h_k ÑF(x^k).4. Проверяется условие ║x^k+1 - x^k║ ≤ e, или ║ÑF(x^k)║ ≤ e.В зависимости от способа выбора h_k на каждой итерации выделяют различные модификации алгоритма.1. Постоянный шаг. Задается h_k = h = const, при этом должно выполняться условие F(x^k+1) = F(x^k + h_kÑF(x^k)) > F(x^k). 2. Наискорейший подъем. Если подставить в выражение для F(x) значение x=x^k+1 в соответствии с (1), то получим выражение F(x^k+h_kÑF(x^k)), как функцию от величины шага. Следовательно, можно выбирать величину шага h_k на каждой итерации, исходя из условия максимизации функции, т.е.

h_k = max F(x^k+hÑF(x^k)).Метод покоординатной (покомпонентной) оптимизации. Сущность метода заключается в том, что в качестве направления r(x^k) последовательно выбираются направления изменения координат (компонент) вектора x. Функции Лагранжа.Исторически первым способом сведения задачи с ограничениями к задаче безусловной оптимизации явилось использование функции Лагранжа L(x,m)

L(x, m) = f(x) + m^т(b - j(x)) = f(x) + m_i (b_i - j _i(x)),

где m_i ≥ 0, i=1,...,m - множители Лагранжа.

В соответствии с теоремой Куна-Таккера необходимым и достаточным условием оптимальности является то, что точка (x^*,m^*) седловая точка функции Лагранжа, т.е. удовлетворяет условию

max min L(x, m) = L(x*, m*) = min max L(x, m).Штрафные функцииЪ

Исходная задача условной оптимизации сводится к последовательности задач безусловной оптимизации функцийF_k(x, m) = f(x) - S_k(x, m_k),

k = 1,2,3,....Здесь S_k(x,m_k), k = 1,2,3,... - штрафные функции, задаваемые таким образом, чтобы обеспечить выполнение условия xÎD. Различают три основных способа формирования штрафных функций:

- внешние штрафные функции;

- внутренние штрафные (барьерные) функции;

- комбинированный метод.

14. Методы прямой условной оптимизации предназначены для непосредственного решения задачи выпуклого программирования в условиях ограничений, описывающих множество допустимых решений D.Итак, пусть решается задача нелинейного программирования f(x) ® max

Использование прямых методов условной оптимизации строится на основе использования итеративной схемы x^k+1 = x^k + h_k r(x^k), k = 0,1,....Метод условного градиента.

15. Задача целочисленного программирования не всегда имеет решения, т.е. она не совместна. Под целочисленным или дискретным программированием понимают такие задачи (обычно линейные), в которых искомые переменные по смыслу могут принимать только целые значения: число рабочих, разделяемых по рабочим местам, количество единиц оборудования, устанавливаемых на заданной площади и т.п. Задачи оптимизации, в которых решение должно быть в целых числах, называют задачами целочисленного программирования. Если в этой задаче целевая функция и ограничения–линейные зависимости, то её называют целочисленной задачей линейного программирования; если же хотя бы одна зависимость будет нелинейной, то такая задача формулируется как целочисленная задача нелинейного программирования. Большинство практических задач принятия решения сводятся, как правило, к целочисленным задачам линейного программирования. Непрерывные задачи решают симплекс-методом с применением так называемых симплекс-таблиц. Каждой итерации соответствует своя симплекс-таблица. Есть признаки, с помощью которых по симплекс-таблицу можно получить ответы на вопросы: имеет ли вообще задача допустимое решение; является ли решение на данной итерации допустимым; является ли решение на данной итерации оптимальным. Если задача имеет решения, то она решается до тех пор, пока не будут удовлетворены признаки этих решений. При этом решение является допустимым, если удовлетворяется один признак, и оптимальным, если удовлетворяются оба признака. К сожалению, для целочисленных задач таких признаков нет. Поэтому по задаче нельзя судить, во-первых, имеет ли она вообще допустимое решение и, во-вторых, является ли полученное допустимое решение оптимальным. Графическое решение целочисленной задачи включает следующие этапы: графическое решение непрерывной задачи; наложение требований целочисленности; анализ полученных результатов. Для нахождения оптимального решения целочисленных задач применяют специальные методы, в которых учитывается, что число возможных решений любой целочисленной задачи является конечным.

16. 1. Исходная ЗЦП решается как задача линейного программирования (ЗЛП) (снимаем ограничения вида (г)). При этом за «рекорд» в ЗЦП принимают значение целевой функции, полученное при решении ЗЛП . 2. Если все переменные приняли целочисленные значения, то получено оптимальное решение в ЗЦП, уход на шаг 8. Если нет, то в решенной на шаге 1 ЗЛП выбирают одну из переменных, которая приняла нецелочисленное значение. Пусть это будет переменная . Для нее вводят следующие два дополнительных ограничения. , ,где — целая часть нецелочисленного значения переменной , полученной при решении ЗЛП.

3. Решаются уже две новые ЗЛП вида (а)–(в) п. 3.5, в каждой из которых введены по одному дополнительному ограничению (1) и (2). Другими словами, исходная задача ЛП разбивается на две новые ЗЛП (происходит ветвление). Обозначим их соответственно ЗЛП–II и ЗЛП–III. Результаты решения получает , .4. Если в ЗЛП–II получаем целочисленное значение всех переменных, то .5. Если в ЗЛП–III получаем целочисленное значение всех переменных, то .В том случае, когда в ЗЛП–II и ЗЛП–III получены целочисленные решения, то происходит их сравнение. , выбирается то решение, которому соответствует максимальное значение целевой функции. Переход на шаг 8.

6. Если в сформированных на шаге 3 решения не являются целочисленными, то происходит проверка следующих двух условий , .

Если указанные ограничения выполняются, то дальнейшее ветвление в ЗЦП прекращается, т. к. введение дополнительных ограничений на целочисленность переменных будет только ухудшать значения ЦФ.Если , , то уход на шаг 7, а ЗЛП вида (II) дальше не решается.

Если , , то уход на шаг 7, а ЗЛП вида (III) дальше не решается.

7. Осуществляется проверка все ли нецелочисленные переменные, полученные на шаге 2, просмотрены. Если нет, то формирование новых условий вида (6) в ЗЛП–II и III и переход на шаг 3, если да, то переход на шаг 8.

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

17. Перейдем теперь к частному случаю задач целочисленного программирования. В этом частном случае искомая переменная в результате решения может принимать не любое целое значение, а только одно из двух: либо 0,
либо 1. Значит, если обозначить — соответствует «быть», — «не быть», то вопрос «быть или не быть» может быть записан следующим образом: В этом случае есть два допустимых решения: ; — означает «быть»; ; — означает «не быть». Так как целевая функция не сформулирована, то дать оптимальный ответ на этот извечный вопрос невозможно. Чтобы принять решение, необходимо знать, чего мы хотим.

18. Существует два метода решения задач с булевыми переменными. Во-первых, их можно решать как обычные задачи целочисленного программирования, т. е. методом ветвей и границ. При этом на каждую переменную накладывается два требования: они должны быть в пределах ; должны быть целыми. Совершенно очевидно, что выполнение этих двух требований обеспечивает получение в решении значений , т. е. равных либо 0, либо 1.Вторым методом является метод сплошного перебора.. Работа при полном переборе выполняется в такой последовательности.1. Заполнить все возможные варианты сочетаний допустимых значений , , .2. Определить значения левых частей ограничений и целевой функции и записать их.3. Вычеркнуть те варианты, в которых не удовлетворяется хотя бы одно ограничение. 4. Из оставшихся вариантов принимается тот, в котором целевая функция приобретает максимальное значение. В общем случае число вычислительных процедур при полном переборе ,где — число переменных; — число ограничений.

19. Для поиска альтернатив в задачах выбора необходимо задать соответствующие критерии, под которыми в дальнейшем понимаются и правила (признаки), позволяющие сопоставлять и сравнивать допустимые альтернативы друг с другом для выбора наилучшей из них. При этом оценивание альтернатив в сложных инженерно-технических задачах, как правило, осуществляется с использованием нескольких критериальных функций. Данные функции в научно-технической литературе часто называют еще целевыми функциями, показателями качества, показателями эффективности.Можно указать на 4 основных вида задач выбора, при решении которых необходимо использовать многокритериальный подход. Перечислим указанные виды задач многокритериального выбора:1-й вид задач, в которых окончательное решение, определяет порядок совместных действий нескольких объектов, эффективность функционирования каждого из которых оценивается отдельными критериальными функциями (например, совместная деятельность СТС при выполнении общей задачи);2-й вид задач, в которых качество принимаемого решения необходимо оценивать для нескольких вариантов условий воздействия среды на СТС и для каждого варианта вводится отдельная оценка;3-й вид задач, в которых принятие решения осуществляется поэтапно с использованием на каждом этапе своих критериальных функций (например, оценка эффективности жизненного цикла СТС);4-й вид задач, в которых качество решения необходимо оценивать с нескольких точек зрения ‑ по отдельным компонентам качества. Некорректность задач многокритериального выбора обуславливает необходимость использования для ее решения соответствующих этапу классу задач методов. Известно, что основу таких методов составляет регуляризация-доопределение (уточнение) задачи путем привлечения дополнительной качественной и количественной информации о свойствах критериальных функций, об альтернативах, о принципах оптимальности и т.п. Вторая особенность задач многокритериального выбора состоит в том, что основным источником дополнительной информации при поиске наилучших альтернатив являются эксперты (Э), хорошо знающие заданную предметную область, и лицо, принимающее решение, преследующее определенную цель (цели), в интересах достижения которой и решается рассматриваемая задачаТретья особенность задач многокритериального выбора заключается в том, что в данных задачах множество допустимых альтернатив и множество частных отношений предпочтений может задаваться как непосредственно, так и с использованием соответствующих функций, функционалов, операторов и т.п. Обобщенная структура выбора с мультипредпочтением, описывающая задачи векторной оптимизации, имеет следующий вид:

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

20. 1. Альтернативы удовлетворяют отношению доминирования по Парето , тогда и только тогда, когда хотя бы по одному входному отношению предпочтения имело место доминирование (, где ‑ отношение строгого порядка), а по остальным ‑ безразличие или доминирование.

Данное определение можно задать в виде единого соотношения вида:

.

2.. Альтернативы удовлетворяют отношению сильного доминирования по Парето тогда и только тогда, когда по каждому входному отношению предпочтения имеет место доминирование: .

Данное определение также можно задать с использованием единого соотношения вида:

.

Замечательное свойство множества Парето состоит в том, что если это множество не пусто, то всякая альтернатива, лежащая вне множества Парето, доминируется альтернативой, принадлежащей последнему множеству. Следовательно, рационально поиск наилучших, в том или ином смысле, альтернатив сосредоточить именно в области Парето.

Таким образом, окончательный выбор во множестве Парето связан с достижением определенного компромисса. Поэтому данное множество получило также название множества (области) компромиссов.

3. Альтернатива называется эффективной (недоминируемой), если во множестве допустимых альтернатив не существуют решения, которое доминирует по Парето альтернативу .Важным практическим результатом выделения области компромиссов (множества Парето) является существенное сужение области поиска оптимальных решений. При этом, как и ранее будем предполагать, что все целевые функции максимизируются. 1. Никакие альтернативы, принадлежащие множеству допустимых альтернатив , не доминируют (не превосходят) альтернативы, принадлежащие множеству Парето. 2. При переходе от одной точки (альтернативы) множества Парето к другой точке множества Парето происходит увеличение значений одних критериальных функций и уменьшение значений других критериальных функций. 3. Множеству Парето принадлежат все альтернативы , при которых достигается единственные (или глобальные) экстремумы значений хотя бы одной из критериальных функций , как при отсутствии ограничений на значения остальных критериальных функций, так и при вводе (частичном вводе) таких ограничений. Другими словами, множеству Парето принадлежат альтернативы , для которых . 4. Множеству Парето принадлежат все точки , в которых достигается единственный (или глобальный) экстремум линейных форм. 5. Если множество альтернатив является выпуклым компактом и соответствующим требованиям вогнутости (выпуклости) удовлетворяют непрерывные функции , то решение совокупности указанных выше экстремальных задач вида (4.8) в принципе определяет все точки множества Парето. 6. Любая точка множества Парето, расположенного в строго положительном варианте, может быть представлена как решение задачи

,

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

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

22. На практике осуществляют переход к лексикографическим методам построения результирующих отношений предпочтения. Данное отношение предпочтения часто называют лексикографическим, а многокритериальные задачи со строго упорядоченными по важности критериями — лексикографическими задачами. Главное из этих отличий состоит в том, что в определении множества Парето и его последующих сужений обычно участвуют все отношения предпочтения , а при применении лексикографических методов предпочтения постепенно нарастает, и вся последовательность шагов направлена на отыскание ядра отношения предпочтения . В общем случае процедура лексикографической оптимизации может оказаться неустойчивой. Для расширения возможностей применения лексикографических методов многокритериальной оптимизации вводится интервальный лексикографический порядок. Метод последовательных уступок. Целесообразно применять для решения тех задач, в которых все показатели качества естественным образом упорядочены по важности, причем каждый показатель настолько более важен, чем последующий, что можно ограничиться только их попарной связью и выбирать величину допустимого снижения очередного показателя с учетом поведения лишь одного следующего показателя.

23. Сущность данных методов многокритериальной оптимизации состоит в построении такого результирующего отношения предпочтения, на основе которого возможно прямое выделение во множестве оптимальной в некотором смысле альтернативы . В связи с этим данные методы называют еще и прямыми методами векторной оптимизации. Принцип равномерной оптимальности. Основными недостатками данного варианта свертки являются:1) слабая связь весовых коэффициентов с действительной ролью частных критериальных функций при обобщенной оценке альтернатив с использованием . 2) трудность отыскания объективного способа нормирования частных критериальных функций для приведения их к безразмерному виду, т.к. значимость каждой определяется величинами и ;3) возможность компенсации недопустимо малых значений оценок альтернатив по некоторым критериальным функциям большими значениями по другим критериальным функциям. Выражение представляет собой свертку‑произведение оценок альтернатив по всем критериальным функциям. Принцип оптимальности, реализуемый с использованием данного варианта свертки, называется принципом справедливого компромисса и формулируется следующим образом: справедливым следует считать такой компромисс, когда суммарный уровень относительного снижения одной или нескольких критериальных функций не превышает суммарного уровня относительного увеличения остальных критериальных функций.При использовании (априорных) методов многокритериального принятия решений выбор соответствующего принципа оптимальности существенно зависит от типа и структуры конкретно решаемой задачи.

24. Решение задач выбора в реальных системах всегда связано с необходимостью учета факторов н е о п р е д е л е н н о с т и, в знании среды, которая влияет на формализованное описание системы (модель) и на способы принятия решений.В зависимости от степени имеющихся знаний о среде используется та или иная форма ее описания, при этом различают следующие варианты:- д е т е р м и н и р о в а н н а я среда, действие которой на систему полностью определено;- с т о х а с т и ч е с к а я среда, действие которой подчиняется известным (или неизвестным) вероятностным законам;- ц е л е н а п р а в л е н н а я среда, действие которой подчинено определенным целям;- н е и з в е с т н а я среда - среда, о которой в той или иной степени отсутствует информация.Последние три формы используются для описания среды с неопределенностью.Принятие решений в условиях с т о х а с т и ч е с к о й среды основывается на том, что объективно существующая неопределенность достаточно точно описывается вероятностными законами. Выбор в условиях ц е л е н а п р а в л е н н о г о воздействия среды связан с ситуациями, в которых сталкиваются интересы нескольких оперирующих сторон, преследующих различные цели. Н е и з в е с т н а я среда характеризуется индифферентным поведением по отношению к системе. Пути организации процесса принятия решения в случае неизвестной среды: а) ввод гипотез о направленности воздействия внешней среды на экономическую систему и, соответственно, на основе взаимодействия с лицом, принимающим решение, введение аксиом поведения (аксиом пессимизма, оптимизма, минимума риска и др.); б) использование экспертных знаний о возможных состояниях среды и формализация их в той или иной форме в моделях принятия решений. Для снятия неопределенности в моделях принятия решений широко используются д е к о м п о з и ц и я и а г р е г и р о в а н и е. Выделяется несколько взаимосвязанных управленческих задач. Прежде всего это задачи п е р с п е к т и в н о г о планирования,задача д о л г о с р о ч н о г о планирования, задача о п е р а т и в н о г о планирования. Развиваются многошаговые методы принятия решений для снятия неопределенности за счет сокращения интервала управления и, следовательно, сокращения времени поступления возмущений.

25. Постановка задач принятия решений в условиях стохастической среды имеет вид(D(w), f(w)), wÎW, где D(w) - множество допустимых альтернатив, f(w) - целевая функция. Методы решения задач выбора в условиях стохастической среды можно разделить на две большие группы: методы детерминизации и методы имитационной оптимизации.М е т о д ы д е т е р м и н и з а ц и и (непрямые методы) основаны на построении детерминированных эквивалентов задачи стохастического выбора. Исходной информацией для такого построения являются известные законы распределения случайных величин (состояний среды).М е т о д ы и м и т а ц и о н н о й о п т и м и з а ц и и (прямые методы) основаны на имитации случайных изменений среды в соответствии с известными законами распределения. Для фиксированного набора случайных параметров, характеризующих состояние среды, решается оптимизационная задача.

26. Принятие решений в условиях целенаправленной среды связано с тем, что известна цель среды, в соответствии с которой она выбирает свои состояния и которую преследует в своих действиях. Эти действия могут вступать в противоречия с нашими действиями, т.е. формируется конфликтная ситуация.К о н ф л и к т н о й с и т у а ц и е й назовем ситуацию, в которой сталкиваются интересы нескольких оперирующих сторон, преследующих различные цели.Конфликтная ситуация характеризуется: составом оперирующих сторон; целями, которые преследует каждая из сторон; способами участия оперирующих сторон в конфликте; возможными результатами разрешения (исходами) конфликта.Формализованную модель некоторой конфликтной ситуации называют и г р о й. Теория игр является математической теорией моделей принятия решений при целенаправленном воздействии среды. Эта теория создает формальную основу для анализа конфликтных и противоречивых ситуаций и, в конечном итоге, позволяет формулировать рекомендации о наилучшем поведении в таких ситуациях. Ее предназначение - выработка рекомендаций по рациональному поведению участников конфликта (оперирующих сторон - игроков). Теория игр является математической теорией моделей принятия решений при целенаправленном воздействии среды. Эта теория создает формальную основу для анализа конфликтных и противоречивых ситуаций и, в конечном итоге, позволяет формулировать рекомендации о наилучшем поведении в таких ситуациях. Ее предназначение - выработка рекомендаций по рациональному поведению участников конфликта (оперирующих сторон - игроков). П р а в и ла игры: - возможные действия игроков;- состав информации о действиях других игроков и об условиях, в которых происходит игра;- оценки качества действий каждого из игроков в ходе конфликта.Игры с различными правилами можно классифицировать: 1. Количество участников игры. По этому признаку различают игры двух игроков и игры n лиц.2. Мощность множеств выбора игроков (количество возможных вариантов действий каждого участника). Различают игры конечные и бесконечные.3. Суммарный выигрыш игроков: игры с нулевой (ненулевой) суммой.4. Количество розыгрышей игры. Различают одношаговые, многошаговые и дифференциальные (непрерывные) игры. 5. Информированность игроков Различают игры с полной информацией и игры с неполной информацией.6. Математико-психологические аспекты игры:- угрозы - информированность противника о возможных последствиях его хода;- блеф - ложная информация, сообщаемая противнику;- рефлексия - постановка себя на место противника.А н т а г о н и с т и ч е с к о й и г р о й называется игра n лиц (игроков) с нулевой суммой.

Игры n лиц в зависимости от характера взаимоотношений игроков могут быть б е с к о а л и ц и о н н ы м и и к о а л и ц и о н н ы м и. П а р т и я и г р ы представляет из себя фиксированный вариант реализации игры при неизменных правилах и складывается из отдельных х о д о в - решений, принимаемых противоположными сторонами.С т р а т е г и е й игрока называется совокупность правил, определяющих выбор варианта действий (принятия решения) при каждом личном ходе игрока в зависимости от ситуации, сложившейся в процессе игры. О п т и м а л ь н о й с т р а т е г и е й игрока принято называть такую стратегию, которая при многократном повторении партий игры обеспечивает ему максимально возможный выигрыш (или соответственно минимально возможный проигрыш). О с н о в н о й ц е л ь ю изучения игр является выявление оптимальной стратегии, приводящей к максимальному выигрышу игрока. М а т р и ч н о й и г р о й называется конечная игра двух лиц с нулевой суммой. В матричных играх, под стратегией понимается ход, приводящий к наибольшему выигрышу. Множество таких ходов у первого игрока равно X и его часто называют множеством ч и с т ы х с т р а т е г и й первого игрока. max min Это для первого игрока гарантированный выигрыш (при рациональном его поведении меньше этого значения он выиграть не может), который называется н и ж н е й ц е н о й и г р ы.min max,который называется в е р х н е й ц е н о й и г р ы. О с н о в н а я т е о р е м а т е о р и и и г р (теорема о минимаксе). Любая матричная игра разрешима в смешанных стратегиях. Процедура нахождения оптимальных чистых или смешанных стратегий соответствует выявлению рациональной линии поведения противников в конфликтной ситуации, описываемой игровой моделью. Поэтому такую процедуру часто называют р е ш е н и е м и г р ы (интерпретируя ее как процесс), а пару оптимальных стратегий (чистых или смешанных) называют решением игры, рассматривая ее как результат.Принятие решений в условиях неизвестной среды.1) для сбора и обработки статистики необходим ресурс времени, который на практике довольно часто отсутствует;2) изменение состояний среды должно обладать свойством статистической устойчивости. Модели типа "игра с природой". В этих играх в качестве второго игрока выступает "природа", которая не заинтересована в результатах игры и, следовательно, действует по своим законам, не противодействуя сознательно другой оперирующей стороне. К прикладным проблемам, использующим модели типа "игра с природой", можно отнести многие экономические задачи разработки систем, задачи планирования хозяйственных действий в различных условиях. Принцип равновероятных состояний среды (критерий Лапласа).Принцип гарантированного результата (критерий пессимизма, критерий Вальда).Принцип максимального оптимизма.Принцип пессимизма-оптимизма (критерий Гурвица).Принцип минимума максимальных потерь

(критерий минимизации риска, критерий Сэвиджа).

27. Обобщенную модель выбора, которая может быть представлена как(Q(s), D, { r_i, iÎC}, f). Q(s) — исходная структура выбора (модель) типа s. D — пространство альтернатив (решений). {r_i, iÎС} — множество отношений, ограничивающих выбор; С — множество индексов отношений, ограничивающих выбор.

f — отношение предпочтения, задаваемое на множестве альтернатив D и отражающее требования, предъявляемые к оптимальному решению.Для задач оптимального управления исходная структура выбора Q(s) задается системой дифференциальных уравнений = j (t, x, u),Пространство альтернатив D представляет собой декартово произведение базовых множеств D = T´X´U, где T — множество моментоввремени; X — множество состояний системы; U — множество управлений.

В постановке задачи оптимального управления присутствует четыре элемента.1) Функционал: J (x, u) ® min.2) Дифференциальные связи (динамическая система):

= j (t, x, u).3) Ограничения вдоль траектории: (t,x,u) Î G = G_t´G_x´G_u.4) Краевые условия: x(t_o) Î E_o, x(t_f) Î E_f. Способы задания функционала. З а д а ч а Л а г р а н ж а (интегральный функционал), качество управления характеризуется некоторыми интегральными на всем интервале управления характеристиками, тогда функционал имеет вид J(x,u) = F(t,x,u) dt ® min,где F — некоторая дифференцируемая функция своих аргументов. Простейшим видом задачи Лагранжа является задача, в которой F(t,x,u) = 1. ТогдаJ(x,u) = t_f – t_o ® min,т.е. задача становится задачей м а к с и м а л ь н о г о б ы с т р о д е й с т в и я.З а д а ч а М а й е р а (терминальный функционал), качество управления определяется значением фазовых переменных, которые достигаются на концах траектории.J(x,u) = Ф(t_o, x(t_o), t_f, x(t_f)) ® min. З а д а ч а Б о л ь ц а (смешанный функционал), качество управления определяется функционалом смешанного типа, который имеет интегральную и терминальную составляющиеJ(x,u) = Ф(t_o, x(t_o), t_f, x(t_f)) + F(t,x,u) dt ® min. Виды дифференциальных связей. Основные виды дифференциальных уравнений, соответственно, динамических систем (моделей). Ограничения вдоль траектории. Принято различать следующие способы задания ограничений вдоль траектории:а) Ограничения на управление. б) Ограничения на фазовые переменные. в) Совместные ограничения на управление и фазовые переменные. г) Интегральные ограничения (изопериметрические). Краевые условия. Содержание задач оптимального управления, как правило, состоит в переводе динамической системы из некоторого начального состояния в конечное при достижении определенных качественных характеристик управления. В этой связи для постановки задачи весьма важны начальное и конечное состояния системы, которые задаются краевыми условиями.а). Задача с ф и к с и р о в а н н ы м и концами

б). Задача со с в о б о д н ы м и концамив). Задача с п о д в и ж н ы м и концами

28. Программное управление ресурсами. Управление ресурсами заключается в изменении количества и скорости поступления ресурсов. В этих условиях необходимо найти управление, позволяющее изменить состояние ресурсов за минимальное время.Цель проводимой операции — изменение количества ресурсов. Задача 1. Функционал dt ® min.2. Дифференциальные связи = x₂, = u.3. Ограничения вдоль траектории u(t) Î [-U_o,+U_o] или ôu (t)ô £ U_o, tÎ(0,T].4. Краевые условия x(0) = ║r_o v_o║^т ; x(T) = ║ 0 0 ║^т . Оптимальное управление производством. необходимо найти программу управления выполнения операций, позволяющую минимизировать расход ресурсов. 1. Функционал u^т(t) R(t) u(t)dt ® min.2.Дифференциальные связи = e_ij(t) d_ij u_ij(t) Г¹_i(t) Г²_i(t), i = 1,…,n.3. Ограничения вдоль траектории u_ij(t) Î [0, 1], i = 1,…,n, j = 1,…, m.4. Краевые условия x_i(0) = 0; x_i(T) = x_i^зад, i = 1,…,n.

29. Исследование принципиальной разрешимости задачи оптимального управления, доказательство существования и единственности решения и является предметом качественного анализа. Основные группы вопросов.1. Исследование принципиальной возможности перевода динамической системы из одного заданного состояния в другое за конечное время с использованием некоторого программного управления, принадлежащего заданному классу функций (управляемость динамической системы).2. Анализ существования допустимого управления — управления, принадлежащего заданному классу функций, удовлетворяющего заданным ограничениям и переводящего динамическую систему из заданного начального состояния в заданное конечное состояние (достижимость состояний).3. Анализ существования в классе допустимых управлений оптимального управления и его единственность. Управляемость динамической системы. Динамическая система (t) = j (x, u) называется у п р а в л я е м о й в состоянии x₁=x(t₁) относительно состояния x₂=x(t₂), если существует кусочно-непрерывное управление u(t), tÎ(t₁,t₂], позволяющее перевести систему из состояния x₁ в состояние x₂.Если существует кусочно-непрерывное управление, позволяющее перевести динамическую систему из любого заданного состояния в любое желаемое состояние за конечное время, то система называется в п о л н е (полностью) управляемой.

30. Вопрос достижимости заданного состояния динамической системы из некоторого начального состояния заключается в существовании допустимого управления — управления, принадлежащего заданному классу функций и удовлетворяющего заданным ограничениям.Анализ достижимости состояний динамической системы задачи — построения областей достижимости или их аппроксимаций. Существование и единственность оптимального управления. В настоящее время отсутствуют универсальные критерии для оценки единственности решения в задачах оптимального управления динамическими системами.

31. Основное содержание этих условий заключается в формулировании свойств, присущих оптимальному управлению, т.е. свойств, которые имеют место, если оптимальное управление существует. Необходимые условия довольно часто используются при качественном анализе существования оптимального управления. Они позволяют выявить множество экстремальных управлений, т.е. подмножество допустимых управлений, содержащее оптимальное управление. Функция Гамильтона. H(t, ,u, ) = (, j) = j^т = ^т j = y_j j_j(t,x,u).. Принцип максимума Л.С.Понтрягина. Задачей Лагранжа со свободным временем и фиксированными концами. J(x,u) = F(t,x,u) dt ® min, (t) = j (t, x, u),

u(t) Î G_u Í R^m, tÎ(t_o, t_f],x(t_o) = x_o, x(t_f) = x_f.

Функция Гамильтона для задачи будет иметь вид H(t, ,u, ) = y_oF(t,x,u) + y^тj (t,x,u).

Утверждение (Принцип максимума Л.С.Понтрягина). Если управление u*(t) является оптимальным управлением в задаче, то существует ненулевая непрерывная векторная функция (y_o(t),y₁(t),...,y_n(t)), удовлетворяющая сопряженной системе дифференциальных уравнений и такая, что выполняются условия1) Для любого момента времени tÎ(t_o,t_f] функция Гамильтона (6.21) достигает максимума по u(t), т.е.

H(t, ,u*, ) = max H(t, ,u, ).uÎG_u2) Выполняются соотношенияy_o(t_f) £ 0; H(t_f, ,u*, ) = 0.Замечание 1.Условие 1 принципа максимума может служить основой для вычисления оптимального управления на основе решения некоторой специализированной краевой задачи. Замечание 2.Формулировки принципа максимума для различных задач оптимального управления отличаются видом функции Гамильтона (т.к. могут использоваться разные функционалы) и условиями 2 в формулировке принципа максимума. 2^¢). y_о(t_f) < 0; y_i(t_f) = 0, i=1,...,n.

условиями т р а н с в е р с а л ь н о с т и Условия трансверсальности. Поскольку состояние системы не фиксировано (x(t_f)ÎE_f), то условия трансверсальности позволяют сформировать дополнительные ограничения для однозначного решения задачи оптимального управления и нахождения оптимального состояния системы в конечный момент времени.

32. Динамические системы, состояние которых изменяется в дискретные моменты времени, называются р е к у р р е н т н ы м и динамическими системами или системами с дискретным временим. Процессы изменения состояния и управления в таких системах называются м н о г о ш а г о в ы м и процессами. Рекуррентные динамические системы. Изменение состояния непрерывной автономной динамической системы описывается системой дифференциальных уравнений вида = j (x, u), tÎ(t_o,t_f]. Задача оптимального управления,поставленная для непрерывных систем, может быть переписана для рекуррентных систем

J(x,u) = F(x(k),u(k)) ® min

x(k+1) = f(x(k),u(k)), k = 0,...,N-1,

u(k) Î G_u Í R^m, k = 0,...,N-1,

x(0) = x_o, x(N) = x_f. Дискретный принцип максимума. В задачах оптимального непрерывного управления решение в любой момент времени находится на основе поиска максимума функции Гамильтона. В задачах оптимизации управления рекуррентными динамическими системами можно показать, что функция Гамильтона вдоль оптимальной траектории отличается от своего максимального значения на величину порядка O(t), где t³ max(t_i -t_j),"_i,j Î {0,...,N}. Таким образом, при увеличении шага дискретизации значение функции Гамильтона все больше отличается от своего максимального значения, и естественно предполагать, что для произвольных разностных уравнений принцип максимума вообще не имеет места. В дискретном принципе максимума появляется дополнительное условие.

33. Эффективность различных вычислительных методов и алгоритмов оптимального управления, реализующих методы поиска оптимального решения, определяется, прежде всего, временем счета и потребным объемом памяти электронной вычислительной машины, необходимого для хранения промежуточных данных вычислений. Прямые методы. Под прямыми методами решения задач оптимального управления в настоящее время принято понимать методы, не использующие непосредственно необходимых или достаточных условий оптимальности.

Прямые методы можно разделить на три группы:1) Методы, основанные на редукции исходной задачи оптимального управления к некоторой задаче математического программирования2) Методы, основанные на использовании градиентных методов в функциональных пространствах3) Методы случайного поиска. Непрямые методы. Непрямые методы основаны на использовании необходимых или достаточных условий оптимальности.Наиболее развитыми в алгоритмическом смысле здесь являются методы, базирующиеся на необходимых условиях оптимальности, которые могут быть получены на основе вариационного исчисления или на основе принципа максимума Л.С. Понтрягина.Метод Ньютона.Метод Ньютона является исторически первым численным способом решения трансцендентного уравнения (6.45), который предназначен для поиска оптимального управления. Суть метода, носящего итеративный характер, состоит в уточнении значений a, проводимого с целью последовательного сокращения невязок d(a). Тогда на некоторой k-ой итерацииa^k+1 = a^k + d^k, k = 0,1,….