Е. Н. Живицкая
↑ | Оглавление | ||
← | Лекция 18, «Методология решения слабо структуризованных проблем» | Лекция 20, «Принятие решений в процессе системного проектирования» | → |
В упрощенном виде задача векторной оптимизации формируется следующим образом:
Имеется n конкурирующих решений:
{Si} = {S1, S2, ..., Sn}, т.е. стратегий, структур, проектов, плакатов и т.д. и m частных критериев
{Kj} = {K1, K2, ..., Km}, не всегда согласованных между собой и противоречивых.
Для оценки конкурирующих решений по частным критериям используются различные средства: экспертные процедуры, мат. моделирование, натуральные эксперименты. При этом множество конкурирующих решений отображается в матрицу векторных оценок:
S1 | S2 | ... | Sn | |
---|---|---|---|---|
[kji] = | k11 | k12 | ... | k1n |
k21 | k22 | ... | k1n | |
... | ... | ... | ... | |
km1 | km2 | ... | kmn |
Исходя из матрицы векторных оценок и системы предпочтений ЛПР выбирается рациональное решение.
E = optSj {[kji], система предпочтений ЛПР} следовательно Srat
opt — некоторый оператор векторной оптимизации.
Выбор рационального решения связан с преодолением неопределенностей, которые имеются в связи с наличием многих критериев. Эта неопределенность является принципиальной. Для ее компенсации есть лишь одна единственная возможность: использование системы предпочтений ЛПР (т.е. дополнительной, субъективной информации).
Использование субъективной информации ЛПР позволяет преодолеть принципиальные трудности и выбрать рациональный критерий.
Все множество методов векторной оптимизации можно разбить на 5 классов.
Методы расположены в порядке возрастания их потенциальной характеристики (классификационный признак — полнота реализации принципа системности). Методы 1-го и 2-го класса не реализуют в полной мере принцип системности. Методы 3-го класса достаточно конструктивны (их легко использовать), однако не всегда удается обосновать и построить обобщенный критерий. Методы 4-го класса более прогрессивны, т.к. они предусматривают активное использование ЛПР в процессе анализа альтернатив. Методы 5-го класса отражают современные тенденции в области векторной оптимизации и находят применение в современных перспективных интерактивных автоматизированных системах.
АСНИ, САПР, АСЛПР, ... поддержки принятия решений.
1-3 — используют;
4-5 — разрабатывают (в том числе и на нашей кафедре).
В.Парето обосновал принцип согласованного оптимума, ориентируясь на конфликтную ситуацию между несколькими субъектами с пересекающимися интересами (1870 г). Согласованный оптимум означает преобразование конфликтной ситуации в такую ситуацию, в которой ни один из участников конфликта не может улучшить свое состояние, не причинив своими действиями вреда партнерам. Состояние согласованного оптимума является наилучшим для всех взаимодействующих субъектов. Леонард Заде распространил принцип согласованного оптимума на технические системы (1963 г).
В процессе их проектирования стремятся оптимизировать систему по многим, часто противоречивым критериям. Однако оптимизация системы по одному из критериев практически исключает возможность оптимизации по другим критериям. Поэтому важно найти согласованный оптимум для всех используемых критериев.
Если векторная оптимизация осуществляется с использованием обобщенного критерия, то реализуются обычно следующие процедуры:
{Kj} | Единица измерения | Направление экстремума | S1 | S2 | S3 | S4 | S5 | S7 | ||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
K1 — масса | K2 | min | 13 | 5 | 11 | 2 | 10 | 16 | 12 | 15 | 9 | 5 |
K2 — стоимость | рубли | min | 200 | 900 | 400 | 800 | 700 | 200 | 500 | 500 | 1100 | 1100 |
Явно видно, что вариант S10 можно выбросить, т.к. S2 — дешевле. S6 — можно забраковать и оставить первый вариант, а остальные сравниваем с оптимальными (т.е. 3, 4 и т.д. с 1 и 2). Найдем граничные варианты в области компромисса: S1 и S2, причем варианты S6 и S10 необходимо отбраковать как худшие.
Определим Парето-оптимальные варианты системы.
S1, S2, S3, S4, S5, S7
S8, S0 выбросим
Произвести дальнейший отбор.
{Kj} | Единица измерения | Направление экстремума | Блок A | Блок B | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
A1 | A2 | A3 | A4 | A5 | A6 | B1 | B3 | B4 | B5 | ||||
K1 — масса | K2 | min | 6 | 7 | 5 | 17 | 14 | 15 | 10 | 6 | 6 | 15 | 17 |
K2 — стоимость | рубли | min | 800 | 600 | 500 | 300 | 200 | 250 | 500 | 400 | 300 | 200 | 300 |
Определим Порето-оптимальные варианты системы S1, S3, S4
{Kj} | Единица измерения | Направление экстремума | {Si} | |||||
---|---|---|---|---|---|---|---|---|
S1 | S2 | S3 | S4 | S5 | S6 | |||
K1 — вероятность отказа | — | min | 1,2⋅10-2 | 0,5⋅10-2 | 0,3⋅10-2 | 0,1⋅10-2 | 0,08⋅10-2 | 0,05⋅10-2 |
K2 — затраты ресурсов | тысячи рублей | min | 200 | 400 | 600 | 900 | 1200 | 1500 |
Ограничения для системы K1 ≤ 1⋅10-2, K2 < 1 млн. руб. |
Определим Парето-оптимальные варианты системы и матрицу потерь
Zji | S2 | S3 | S4 |
---|---|---|---|
K1 | 0,5 | 0,3 | 0,1 |
K2 | 0,4 | 0,6 | 0,9 |
minSi(maxKj(Zji)) = min{0,5; 0,6; 0,9} = 0,5
Т.е. рациональным является вариант системы S2.
Принятие решений является наиболее массовой операцией в процессе создания некоторой АСУ практически на всех ее этапах.
См. общее системное проектирование АСУ реального времени. Под редакцией В. А. Шабалина, М., радио и связь, 1984 г, стр.34-44.
Принятие решений при многих критериях базируются на принципе согласованного оптимизма В.Парето и представляет собой многошаговый интеративный процесс, который начинается с появлением проблемы и заключается реализацией решений.
Рис. 19.1 — Принятие решения
Сбор исходных данных и структуризация проблемы:
а) ограничение сложности
б) отображение ситуации
г) оценка ресурса
д) выявление взаимосвязей
Выбор рационального решения, которые должны быть:
а) единственным
б) своевременным
в) реализуемым
г) устойчивым
д) перспективным
В настоящее время в стадии становления находится новое научное направление, а именно т-я качества сложных систем, в частности АСУ различных уровней и назначения. В проблематику данного направления входят вопросы обеспечения качества систем на всех этапах их создания и развития. Современное представление о процессе проектирования сложных технических систем включает 3 характерных цикла:
Первый цикл представляет конкретизацию целей и функций системы, а также представление требований к ее характерам качества.
Второй цикл служит для корректной увязки требований внешнего проектирования с конструкторскими и технологическими возможностями внутреннего проектирования и состоит в выборе рациональной структуры из некоторого множества конкурирующих структур.
Третий цикл предполагает разработку выбранной структуры и ее реализацию в виде комплекса технических ф-в, принадлежащих системе требуемое качество.
Рис.19.2 — Циклы проектирования технических систем
Циклам проектирования соответствуют следующие уровни оптимизации систем:
Оптимизация системы последовательно на всех 3-х уровнях приводит к синтезу структуры, удовлетворяющей заданным требованиям по качеству.
Наибольший эффект в обеспечении качества системы дает глобальная оптимизация (Глушков, Мясников, Половинкин) 30-50%, наименьший эффект — параметрическая оптимизация 10-15%, структурная оптимизация занимает промежуточное положение 20-30%. Причем, степень оптимизации зависит весьма существенно от множества конкурирующих структур и их проработки по векторному критерию качества.
Необходимость структурной оптимизации обусловлена наличием сравнительно большой номенклатуры технических средств и способов, объединяя их в различные структуры, которые отличаются друг от друга рядом признаков, а именно, составом структурных элементов, технологией переработки информации, пространственным распространением элементов и др.
Анализ конкурирующих структур неизбежно связан с использованием многих критериев и выполняется в условиях неопределенности, т.е. в условиях неполноты информации в отношении создаваемой системы и внешней среды, взаимодействующей с ней. По этой причине проблема структурной оптимизации формируется как проблема многокритериального выбора рациональной структуры из некоторого множества конкурирующих структур в условиях неопределенности. Проблема структур оптимизации в такой постановке решается на основе методологии системного анализа.
Рис.19.3 — Уровни оптимизации систем
В процессе структурной оптимизации необходимо осуществлять целенаправленный поиск альтернативных структур, т.к. их случайный перебор обычно не приводит к успеху. При этом, чем больше альтернативных структур, тем с большей вероятностью можно гарантировать конечный результат, т.е. выбор наиболее рациональной структуры. Вместе с тем, большой объем альтернативных структур порождает проблему отсева (отбраковки) неперспективных структур, исходя из тех или иных ограничений и требований к системе.
Таким образом процесс структурной оптимизации — это процесс систематизации альтернативных структур с отсевом неперспективных структур и определение множества конкурирующих структур, из числа которых выбирается рациональная структура.
Метод предусматривает 2-хкритериальную оценку вариантов системы и включает в себя 5 основных операций:
Поясним сущность метода на примере ВЦ с распределенной сетью терминалов. В этом случае возможно построить следующие модели:
При построении моделей используется вся доступная объективная и субъективная информация. Выходные данные модели в соответствии с методом синтезируются в обобщенный критерий, позволяющий анализировать варианты системы. Базируясь на обобщенных оценках, ЛПР выбирает рациональный вариант системы.
Сложно в ФСА построить модель эффективности. В качестве обобщенного критерия Е можно использовать:
Выбор обобщенного критерия Е осуществляется, как правило, на основе субъективных суждений ЛПР. 3 — применяется на практике наиболее часто (т.к. наиболее понятно; получаем число, которое никакого смысла не имеет; выбираем число с максимальным значением).
Метод служит для решения задач структурной многокритериальной оптимизации систем в процессе их проектирования или модернизации. Базируется на методологии системного анализа и представляет собой многошаговый итерактивный процесс, который начинается с формулировки целевого назначения системы и заканчивается выбором рациональной структуры. Этот процесс не поддается полной математической формализации и поэтому представляет собой сложную цель эвристических и формальных процедур. Сочетание эвристики и формализма образует системный метод, дисциплинирующий решение проектировщика и позволяющий решать широкий класс задач многокритериального выбора рациональной структуры.
Рис.19.4 — Комплексная оценка структур
Концептуальная схема метода включает следующие операторы:
Z — цель системы достигается в процессе функционирования при взаимодействии с внешней средой;
S — конкурирующие структуры, выявляемые в результате морфологического анализа;
K — частные критерии, характеризующие качество конкурирующих структур;
М — совокупность моделей, позволяющих оценить отдельные свойства конкурирующих структур;
W — векторные оценки, получаемые для конкурирующих структур по частным критериям;
Р — процедуры скаляризации, направленные на свертку векторных оценок по каждой из структур;
А — анализ структур, осуществляемый на основе обобщенных скалярных оценок в диапазоне условий;
R — решающее правило, определяющее выбор рациональной структуры в заданном классе условий.
Практическое применение метода требует расшифровки операторов с учетом особенностей конкретной системы. При этом выполняется 6 основных операций:
Рассмотрим методику, которая реализует все операторы метода комплексной оценки структур (т.е. более подробно, чем сам метод).
Операторы метода | Z, F, S | K | M, W | P | A | R |
---|---|---|---|---|---|---|
Этапы методики | 1 | 2 | 3 | 4-10 | 11 | 12 |
Определяется множество конкурирующих структур {Si} = {S1, S2, ..., Sn}, из числа которых выбирается в дальнейшем рациональная структура. Для поиска структур могут быть использованы различные методы: мозговой атаки; дерево целей; морфологического ящика и др. На практике закрепился метод морфологического ящика (анализа). Морфологический анализ создаваемой системы позволяет систематизировать потенциально возможные структуры и определить множество конкурирующих структур.
Рис.19.5 — Множество конкурирующих структур
Вводятся ограничения
а) экономические
б) технические
в) эксплуатационные
Отбирается совокупность частных критериев {Ki} = {K1, K2, ..., Km}, которые служат для оценки качества конкурирующих структур.
Набору критериев предъявляется ряд требований:
Противоречивость требований заставляет искать компромисс при построении набора критериев.
Рис.19.6 — Набор критериев
1 — формируется полный перечень частных критериев;
3 — выполняется отбор критериев и их обоснование.
Выполняется оценка конкурирующих структур по частным критериям для М-ого варианта условий
Для оценки структур используются все возможные средства, которые имеются в наличии на данный момент эволюции систем: аналитические, имитационные, полунатурные модели, полунатурные испытания, проведение экспертиз.
Получаемые оценки Kji(M) образует матрицу критерии структуры
{Kj} | Единицы измерения | Направление экстремума | {Si} | |||||
---|---|---|---|---|---|---|---|---|
S1 | S2 | ... | Sn | |||||
K1 | ... | ... | K11(M) | K12(M) | ... | K1n(M) | ||
K2 | ... | ... | K21(M) | K22(M) | ... | K2n(M) | ||
... | ... | ... | ... | ... | ... | ... | ||
Km | ... | ... | Km1(M) | Km2(M) | ... | Kmn(M) |
Составляется матрица бинарных предпочтений ЛПР, которое содержит результаты попарных сравнений критериев по важности. 1 — если критерий строки считается более важным, чем критерий столбца. 0 — в противном случае. 0,5 — если критерии не сравнимы по важности.
Суммирование оценок по строке определяет цену критерия.
{Ki} | K1 | K2 | ... | Km | Cj(M) |
---|---|---|---|---|---|
K1 | ... | ... | ... | ... | ... |
K2 | ... | ... | ... | ... | ... |
... | ... | ... | ... | ... | ... |
Km | ... | ... | ... | ... | ... |
Вылавливаем, что у ЛПР «в голове»
Находятся веса частных критериев, отражающие неформальное отношение ЛПР
ϑ1j = Cj(M)/∑rj(M), j = 1,m
Находятся веса частных критериев, исходя из разброса векторных оценок
ϑ2j = Zj(M)/∑rj(M), j = 1,m
rj(M) = 1/n⋅(∑(-[kji(M) - kji(M)^]/kji(M)^))
kji(M) = ∑kji(M)/n
Находятся обобщенные веса частных критериев в классе линейных функций
ωj(M) = a⋅ϑ1j(M) + b⋅ϑ2j(M), j = 1,m
где а и b — это коэффициенты, характеризующие степень доверия к соответствующим весам.
a + b = 1
В частном случае, когда a = b = 0,5
ωj(M) = 0,5⋅(ϑ1j(M) + ϑ2j(M)), j = 1,m, ∑ωj(M) = 1
Оценки матрицы критериев структуры приводятся к безразмерному виду.
ρji(M) = kji(M)/Δkj
Δkj значение-кванты по частному критерию Kj, причем под квантой понимается мера разумной точности измерения соответствующей характеристики.
Формируется матрица взвешенных оценок
Eji(M) = ωj(M)⋅ρji(M) (j = 1,m, i = 1,n)
Вычисляются обобщенные скалярные оценки
qi(M) = ∑lji(max) - ∑lji(min) (i = 1,n)
т.е. находится разность суммарных взвешенных оценок по критериям, подлежащим соответственно, минимизации и максимизации.
при оценке структур в диапазоне условий осуществляется η-кратное повторение этапов 3-10. В результате получаем матрицу структуры условий.
{Si} | {M} | |||
---|---|---|---|---|
1 | 2 | ... | η | |
S1 | q1(1) | q2(1) | ... | q1(2) |
S2 | q2(1) | q2(2) | ... | q2(2) |
... | ... | ... | ... | ... |
Sn | qn(1) | qn(2) | ... | qn(2) |
Для первого варианта воздействия
На основе матрицы структуры условия выбирается рациональная структура системы. Эта структура должна обладать приемлемой эффективностью для всех вариантов условий, возникающих с вероятностями pM. Для известных вероятностей pM, имеющих частотную или субъективную трактовку, целесообразно использовать критерий максимума средней эффективности в диапазоне условий.
E = maxSi(∑qi(M)⋅pM) ⇒ Srat
На практике типичной является ситуация, когда вероятности pM не известны. В данном случае используются критерии для выбора решений в условиях неопределенности.
Применим методику многокритериального выбора рациональных структур, для структурной оптимизации локальной информационно-вычислительной сети (ИВС). Локальная ИВС содержит вычислительную систему, которая может включать несколько однотипных процессоров (на сколько процессоров?) и N распределенных по региону терминалов пользователей, имеющих теледоступ к ИВ ресурсам этой системы.
Необходимо на реальных данных определить число процессоров.
{Si} = {S1, S2, S3}, где S1, S2, S3 имеют следующий смысл:
S1 — структура с одним процессором;
S2 — структура с двумя процессорами;
S3 — структура с тремя процессорами.
{Kj} = {K1, K2, K3, K4, K5}, где
K1 — время реакции системы;
K2 — коэффициент загрузки процессора;
K3 — пропускная способность системы;
K4 — вероятность правильного ответа;
K5 — стоимость процессорных устройств.
{Kj} | Единицы измерения | Направление экстремума | N = 10 | N = 20 | N = 30 | N = 50 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
S1 | S2 | S3 | S1 | S2 | S3 | S1 | S2 | S3 | S1 | S2 | S3 | |||
K1 | Сек | min | 2,89 | 2,08 | 2,05 | 5,7 | 2,89 | 2,71 | 11,5 | 4,38 | 3,38 | 25,8 | 9,64 | 0,99 |
K2 | % | max | 55 | 30 | 20 | 91 | 55 | 37 | 99,8 | 75 | 51 | 100 | 91 | 63 |
K3 | Задач/сек | max | 0,78 | 0,83 | 0,83 | 1,27 | 1,55 | 1,57 | 1,4 | 2,09 | 2,15 | 1,4 | 2,55 | 2,69 |
K4 | — | max | 0,85 | 0,95 | 0,99 | 0,85 | 0,95 | 0,99 | 0,85 | 0,95 | 0,99 | 0,85 | 0,95 | 0,99 |
K5 | Тыс. руб. | min | 340 | 490 | 640 | 340 | 490 | 640 | 340 | 490 | 640 | 340 | 490 | 640 |
Чтобы получить количественные средства, нужно использовать все возможные средства (например, аналитические вычисления).
Покажем расчеты для N = 20
{Ki} | K1 | K2 | K3 | K4 | K5 | Cj |
---|---|---|---|---|---|---|
K1 | 1 | 0,5 | 0 | 0,5 | 2 | |
K2 | 0 | 0,5 | 0 | 0 | 0,5 | |
K3 | 0,5 | 0,5 | 0 | 0 | 1 | |
K4 | 1 | 1 | 1 | 0,5 | 3,5 | |
K5 | 0,5 | 1 | 1 | 0,5 | 3 |
∑Cj = 10
суммируем по строке 3
{Ki} | Kji^ | rj | ϑ2j |
---|---|---|---|
K1 | 3,77 | 0,34 | 0,33 |
K2 | 61 | 0,33 | 0,32 |
K3 | 1,46 | 0,09 | 0,09 |
K4 | 0,93 | 0,06 | 0,06 |
K5 | 490 | 0,2 | 0,2 |
0,34 = (/5,7 - 3,77/ + /2,89 - 3,77/ + /2,71 - 3,77/3,77)/3
Наибольший вес в формальном способе расчета имеет время реакции системы. Далее — все наоборот (не так, как дал человек).
ω1 = 0,27( = 0,265) а = b = 0,5
ω2 = 0,18 Наиболее важным получился критерий K1
ω3 = 0,09
ω4 = 0,21
ω5 = 0,25
{Kj} | ΔKj | Единица измерения | {Si} | ||
---|---|---|---|---|---|
S1 | S2 | S3 | |||
K1 | 0,5 | Сек | 11,4 | 5,78 | 5,42 |
K2 | 5 | % | 18,2 | 11 | 7,4 |
K3 | 0,25 | Задач/сек | 5,08 | 6,2 | 6,28 |
K4 | 0,1 | — | 8,5 | 9,5 | 9,9 |
K5 | 100 | Тыс. руб. | 3,4 | 4,9 | 6,4 |
т.е. делим на кванту то число, которое стоит в таблице матрицы критериев структуры
Кванта — это тот «кирпичик», через который человек чувствует этот критерий 0,5 — т.е. через 0,5 сек человек начинает чувствовать эту характеристику.
{Kj} | ωj | Направление экстремума | {Si} | ||
---|---|---|---|---|---|
S1 | S2 | S3 | |||
K1 | 0,27 | min | 3,08 | 1,57 | 1,46 |
K2 | 0,18 | max | 3,28 | 1,98 | 1,33 |
K3 | 0,09 | max | 0,46 | 0,51 | 0,57 |
K4 | 0,21 | max | 1,78 | 1,99 | 2,03 |
K5 | 0,25 | min | 0,85 | 1,22 | 1,6 |
Эти веса умножаем на столбик прошлой матрицы
= 0,27⋅11,4
q1 = 1,59; q2 = 1,74; q3 = 0,92.
{Si} | {M} | |||
---|---|---|---|---|
N = 10 | N = 20 | N = 30 | N = 50 | |
S1 | 2,75 | 1,59 | -3,27 | -12,27 |
S2 | 1,63 | 1,74 | 0,81 | -1,9 |
S3 | 0,3 | 0,92 | 0,24 | -2,29 |
Мы провели расчеты для случая гот.
1,74 — наиболее предпочтителен для случая с 20-тью терминалами.
{Si} | {M} | E | |||
---|---|---|---|---|---|
P(10) = 0,1 | P(20) = 0,5 | P(30) = 0,3 | P(50) = 0,1 | ||
S1 | 0,27 | 0,79 | -0,98 | -1,23 | -1,15 |
S2 | 0,16 | 0,87 | 0,24 | -0,19 | 1,08 |
S3 | 0,08 | 0,46 | 0,07 | -0,23 | 0,38 |
Суммируем по строке — т.е. эффективность в данном диапазоне условий;
Умножаем вероятности на прошлую матрицу
Р(10) — т.е. вероятность подключения 10-ти терминалов
Видим, что 2-й вариант системы является предпочтительнее
Это решение дают ЛПР.
Вывод: в заданных условиях рациональной является структура S2
↑ | Оглавление | ||
← | Лекция 18, «Методология решения слабо структуризованных проблем» | Лекция 20, «Принятие решений в процессе системного проектирования» | → |
© Виктор Сафронов, 2006–2017
Пользовательское соглашение | RSS | Поддержать проект | Благодарности