2 страница. Отношение предпочтения следует считать центральным понятием теории выбора

Отношение предпочтения следует считать центральным понятием теории выбора. Задачи выбора с одним отношением предпочтения (выбор с унипредпочтением). Задачи выбора с многими отношениями предпочтения (выбор с мультипредпочтением). На практике все большее значение приобретают постановки задач многокритериальной или векторной оптимизации, являющихся одним из классов задач выбора с мультипредпочтением. В групповом выборе участвует группа лиц, каждое из которых имеет своё индивидуальное отношение предпочтения или вектор индивидуальных предпочтений. Теория группового выбора является научной основой развития метода экспертных оценок, который, в свою очередь, нашёл широкое применение при оценивании и выборе решений на различных этапах жизненного цикла сложных технико-экономических систем. Для каскадного (иерархического) выбора характерен упорядоченный выбор элементов сложной (составной) альтернативы. Задачи координационного выбора. При этом задачи координационного выбора с одной стороны могут рассматриваться как подкласс задач каскадного выбора, а с другой стороны - как подкласс задач игрового выбора. Наиболее важными факторами, характеризующими и сам процесс и ситуацию выбора, являются следующие элементы, составляющие концептуальную модель принятия решений. S–субъект, принимающий решение и ответственный за последствия принятого решения. Субъектом может быть как отдельный человек, лицо, принимающее решение (ЛПР), так и группа лиц, или коллективный орган принятия решений. В соответствии с этим и задачи принятия решений принято подразделять на индивидуальные и групповые (коллективные).-множество допустимых решений. Множество допустимых альтернатив может быть конечным и бесконечным (счётным, концептуальным и т.п.), детерминированным, случайным, нечётким, задаваться в явном и неявном виде с помощью системы линейных и нелинейных ограничений. R–множество отношений предпочтения, заданных либо непосредственно в виде отношений, либо в виде функций, функционалов, операторов в неявном виде F–множество решающих правил (правил согласования), представляющих из себя, в общем случае, операторы, позволяющие формировать на множестве отношений предпочтений ЛПР результирующее отношение предпочтения. Перечисленные элементы концептуальной модели принятия решений можно записать в виде следующего кортежа <S, , R, F>.

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-й вид задач, в которых качество решения необходимо оценивать с нескольких точек зрения ‑ по отдельным компонентам качества. Некорректность задач многокритериального выбора обуславливает необходимость использования для ее решения соответствующих этапу классу задач методов. Известно, что основу таких методов составляет регуляризация-доопределение (уточнение) задачи путем привлечения дополнительной качественной и количественной информации о свойствах критериальных функций, об альтернативах, о принципах оптимальности и т.п. Вторая особенность задач многокритериального выбора состоит в том, что основным источником дополнительной информации при поиске наилучших альтернатив являются эксперты (Э), хорошо знающие заданную предметную область, и лицо, принимающее решение, преследующее определенную цель (цели), в интересах достижения которой и решается рассматриваемая задачаТретья особенность задач многокритериального выбора заключается в том, что в данных задачах множество допустимых альтернатив и множество частных отношений предпочтений может задаваться как непосредственно, так и с использованием соответствующих функций, функционалов, операторов и т.п. Обобщенная структура выбора с мультипредпочтением, описывающая задачи векторной оптимизации, имеет следующий вид: