Вектор методы оптимальных решений

В упрощенном виде задача векторной оптимизации формируется следующим образом:

Имеется n конкурирующих решений:

<S_i> = <S₁, S₂, . S_n>, т.е. стратегий, структур, проектов, плакатов и т.д. и m частных критериев

<K_j> = <K₁, K₂, . K_m>, не всегда согласованных между собой и противоречивых.

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

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

E = opt_Sj <[k_ji], система предпочтений ЛПР> следовательно S_rat

opt — некоторый оператор векторной оптимизации.

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

Использование субъективной информации ЛПР позволяет преодолеть принципиальные трудности и выбрать рациональный критерий.

Все множество методов векторной оптимизации можно разбить на 5 классов.

1. Методы, основанные на формализации, в виде задач математического программирования.
2. Методы, основанные на реинжинировании критериев и их последовательном применении.
3. Методы, использующие обобщенный критерий для сравнительной оценки альтернатив.
4. Методы, не использующие обобщенный критерий для сравнительной оценки альтернатив.
5. Методы, реализующие процессы структуризации и адаптации при выборе рациональных решений.

Методы расположены в порядке возрастания их потенциальной характеристики (классификационный признак — полнота реализации принципа системности). Методы 1-го и 2-го класса не реализуют в полной мере принцип системности. Методы 3-го класса достаточно конструктивны (их легко использовать), однако не всегда удается обосновать и построить обобщенный критерий. Методы 4-го класса более прогрессивны, т.к. они предусматривают активное использование ЛПР в процессе анализа альтернатив. Методы 5-го класса отражают современные тенденции в области векторной оптимизации и находят применение в современных перспективных интерактивных автоматизированных системах.

АСНИ, САПР, АСЛПР, . поддержки принятия решений.

4-5 — разрабатывают (в том числе и на нашей кафедре).

Принцип согласованного оптимума В.Парето

В.Парето обосновал принцип согласованного оптимума, ориентируясь на конфликтную ситуацию между несколькими субъектами с пересекающимися интересами (1870 г). Согласованный оптимум означает преобразование конфликтной ситуации в такую ситуацию, в которой ни один из участников конфликта не может улучшить свое состояние, не причинив своими действиями вреда партнерам. Состояние согласованного оптимума является наилучшим для всех взаимодействующих субъектов. Леонард Заде распространил принцип согласованного оптимума на технические системы (1963 г).

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

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

1. Выполняется обоснование способа свертки частных критериев в обобщенный критерий.
2. Учитывается важность частных критериев.
3. Векторные оценки приводятся к безразмерному виду.
4. Для всех конкурирующих решений вычисляются обобщенные скалярные оценки.
5. Определяется область компромисса, содержащая парето-оптимальные решения (т.е. такие решения, когда улучшения состояния по каждым из критериев ухудшает состояние по другим критериям).
6. Выбирается рациональное решение в области компромиссов с учетом системы предпочтений ЛПР.

Приемы поиска Парето-оптимальных решений

Пример 1: определить Парето-оптимальные варианты системы

Явно видно, что вариант S₁₀ можно выбросить, т.к. S₂ — дешевле. S₆ — можно забраковать и оставить первый вариант, а остальные сравниваем с оптимальными (т.е. 3, 4 и т.д. с 1 и 2). Найдем граничные варианты в области компромисса: S₁ и S₂, причем варианты S₆ и S₁₀ необходимо отбраковать как худшие.

Определим Парето-оптимальные варианты системы.

Произвести дальнейший отбор.

Пример 2: Определить парето-оптимальные варианты системы, которая состоит из блоков А и В

Определим Порето-оптимальные варианты системы S₁, S₃, S₄

Пример 3: выбрать рациональный вариант системы в условиях, когда ЛПР применяет минимальный критерий

Этап 4:

Составляется матрица бинарных предпочтений ЛПР, которое содержит результаты попарных сравнений критериев по важности. 1 — если критерий строки считается более важным, чем критерий столбца. 0 — в противном случае. 0,5 — если критерии не сравнимы по важности.

Суммирование оценок по строке определяет цену критерия.

Вылавливаем, что у ЛПР «в голове»

Этап 5:

Находятся веса частных критериев, отражающие неформальное отношение ЛПР

Этап 6:

Находятся веса частных критериев, исходя из разброса векторных оценок

Этап 7:

Находятся обобщенные веса частных критериев в классе линейных функций

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

В частном случае, когда a = b = 0,5

Этап 8:

Оценки матрицы критериев структуры приводятся к безразмерному виду.

Δk_j значение-кванты по частному критерию K_j, причем под квантой понимается мера разумной точности измерения соответствующей характеристики.

Этап 9:

Формируется матрица взвешенных оценок

Этап 10:

Вычисляются обобщенные скалярные оценки

т.е. находится разность суммарных взвешенных оценок по критериям, подлежащим соответственно, минимизации и максимизации.

Этап 11:

при оценке структур в диапазоне условий осуществляется η-кратное повторение этапов 3-10. В результате получаем матрицу структуры условий.

Для первого варианта воздействия

Этап 12

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

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

Структурная оптимизация локальной информационно-вычислительной сети

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

Необходимо на реальных данных определить число процессоров.

Этап 1: Множество конкурирующих структур

S₁ — структура с одним процессором;

S₂ — структура с двумя процессорами;

S₃ — структура с тремя процессорами.

Этап 2: Совокупность частных критериев

K₁ — время реакции системы;

K₂ — коэффициент загрузки процессора;

K₃ — пропускная способность системы;

K₄ — вероятность правильного ответа;

K₅ — стоимость процессорных устройств.

Этап 3: Матрица критерии структуры:

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

Покажем расчеты для N = 20

Этап 6: Веса частных критериев исходя из разброса векторных оценок для N = 20

суммируем по строке 3

0,34 = (/5,7 — 3,77/ + /2,89 — 3,77/ + /2,71 — 3,77/3,77)/3

Наибольший вес в формальном способе расчета имеет время реакции системы. Далее — все наоборот (не так, как дал человек).

Этап 7: Усредненные веса частных критериев для N = 20

ω₁ = 0,27( = 0,265) а = b = 0,5

ω₂ = 0,18 Наиболее важным получился критерий K₁

Этап 8: Матрица безразмерных векторных оценок для N = 20

т.е. делим на кванту то число, которое стоит в таблице матрицы критериев структуры

Кванта — это тот «кирпичик», через который человек чувствует этот критерий 0,5 — т.е. через 0,5 сек человек начинает чувствовать эту характеристику.

Этап 9: Матрица взвешенных векторных оценок для N = 20

Эти веса умножаем на столбик прошлой матрицы

Этап 10: обобщенные скалярные оценки для N = 20

Этап 11: матрица структуры условия:

Мы провели расчеты для случая гот.

1,74 — наиболее предпочтителен для случая с 20-тью терминалами.

Этап 12: Эффективность конфигурирующих структур в диапазоне условий

Суммируем по строке — т.е. эффективность в данном диапазоне условий;

Умножаем вероятности на прошлую матрицу

Р(10) — т.е. вероятность подключения 10-ти терминалов

Видим, что 2-й вариант системы является предпочтительнее

Это решение дают ЛПР.

Вывод: в заданных условиях рациональной является структура S₂

Видео:Графический метод решения задачи линейного программирования (ЗЛП)Скачать

Постановка задачи векторной оптимизации

1. Постановка задачи векторной оптимизации

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

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

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

Многокритериальные задачи широко распространены в техническом проектировании, например, задача проектирования компьютера с максимальным быстродействием, максимальным объемом оперативной памяти и минимальным весом или задача проектирования электрического двигателя с максимальной мощностью, максимальным коэффициентом полезного действия, минимальным весом и минимальными затратами электротехнической стали (естественно, при ограничениях на необходимые параметры проектируемых устройств). Реальные многокритериальные управленческие задачи также широко распространены, лозунг экономики СССР 80-х гг. — «максимум качества при минимуме затрат», несмотря на его одиозность, выражал сущность большинства проблем управления.

Под многокритериальной задачей зачастую понимают не собственно вербальное описание задачи, а ее модель, а именно: «многокритериальная задача – математическая модель принятия оптимального решения по нескольким критериям. Эти критерии могут отражать оценки различных качеств объекта или процесса, по поводу которых принимается решение».

Формально многокритериальная задача как модель задается в виде:

, (5.1)

где D — множество допустимых решений. F(x) – векторная функция векторного аргумента x, которую можно представить как F(x)=, где f1(x), f2(x), … , fk(x) – скалярные функции векторного аргумента x, каждая их которых является математическим выражением одного критерия оптимальности. Так как в данной модели используется векторная целевая функция, ее зачастую называют задачей векторной оптимизации. Очевидно, что задача (5.1) не принадлежит классу задач математического программирования, т. к.модели этого класса задач содержат всегда только одну целевую функцию векторного аргумента.

Иначе задачу (5.1) можно переписать в виде:

Сущность поставленной задачи состоит в нахождеии такого ее допустимого решения, т. е. >, которое в том или ином смысле максимизирует (минимизирует) значения всех целевых функций fi(x), i=1,k. Существование решения, буквально максимизирующего все целевые функции, является редким исключением. (Если вспомнить пример о поиске одновременно очень качественной и очень дешевой покупки, то становится понятным, что нахождение такого решения – редкая удача, но, гораздо более часто, это неразрешимая задача).

Отсюда следует, что принципиальным моментом при решении такого рода задач является предварительная договоренность, а что считать самым предпочтительным решением, т. е. надо договориться об используемом принципе оптимальности. Ранее используемый принцип оптимальности «хорошо то, что доставляет наибольшее (наименьшее) значение имеющемуся единственному критерию оптимальности» в многокритериальных задачах очевидно «не работает».

Задача векторной оптимизации в общем случае не имеет строго математического математического решения. Для получения того или иного ее решения необходимо использовать дополнительную субъективную информацию специалиста в данной предметной области, которого принято называть лицом принимающим решение (ЛПР), в английском языке — decision maker. Это означает, что при решении задачи разными специалистами с привлечением различных источников информации, скорей всего будут получены различные ответы.

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

2. Основные определения теории векторной оптимизации. Принцип Парето

Введем несколько определений.

Пусть решается задача (6.1) и есть x‘, x» — допустимые решения данной задачи. Говорят, что x‘ более предпочтительное решение по сравнению с x», если f i (x‘) ≥ f i (x») i=1,k), причем i0, такой, что f i (x‘) > f i (x»). Другими словами, будем считать, что решение x’ более предпочтительно по сравнению с решением x» , если оно не хуже x» по всем рассматриваемым критериям, причем среди всех критериев есть хотя бы один критерий с номером i0, для которого решение x‘ лучше, чем x»

Некоторое решение x* задачи (5.1) называется эффективным решением данной задачи, если для него не существует более предпочтительных решений. Иначе можно сказать, что эффективным решением называется такое решение x*, которое нельзя улучшить по какому-либо из критериев, не ухудшив при этом значения других критериев.

Множество эффективных решений называется множеством Парето и обозначается P(D). Очевидно, множество Парето является подмножеством множества допустимых решений, которое, в свою очередь принадлежит n-мерному векторному пространству, т. е. P(D) D En.

Вектор значений критериев, вычисленных для эффективного решения F(x*), называется эффективной оценкой. Совокупность всех эффективных оценок, т. е. образ множества Парето в пространстве критериев, называется множеством эффективных оценок и, как правило, обозначается как F (P). Множество эффективных оценок является подмножеством образа множества допустимых решений в пространстве критериев F(D), которое, в свою очередь, является подмножеством k-мерного векторного пространства, т. е. F(P) F(D) Ek. Т. е. можно сказать, что множеству Парето P, принадлежащему множеству допустимых решений D, с помощью векторной функции F сопоставлется множество эффективных оценок F(P)

Решение xl называется слабоэффективным решением задачи (6.1), если для него не существует решения xll такого, что i=1,k f(xl) > f(xll), другими словами, слабоэффективное решение – решение, которое не может быть улучшено одновременно по всем критериям.

P(D)En.

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

Субоптимальное решение (по критерию fi(x) – оптимальное решение многокритериальной задачи, найденное по какому-либо одному критерию (i-ому) без учета остальных критериев.

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

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

Рассмотрим введенные понятия на примере.

С помощью графического метода найдем субоптимальные решения (см рис. 5.1). По критерию f1 — это точка Е(2,0), f1(Е)=6.

По критерию f2 субоптимальные точки — это точки отрезка, соединяющего точки С(0,4) и В(1,4),], при этом f2(С) = f2(В)=4

Таблица 5.1 – Анализ точек множества D примера 6.1 на принадлежность множеству Парето

Не улучшаемые точки

Улучшаемая по 1-му критерию

Одновременно улучшаемая по

В таблице 5.1 приведены значения целевых функций f1(x)= 3x1—x2 и f2(x)= x2 для всех точек, обозначенных на рис. 5.1. На основании этих данных построен рис. 5.2. Полученный многоугольник F(C) F(K) F(E) F(A) F(G) F(B) является отображением многоугольника допустимых решений примера C K E A G B в пространсте критериев.

3. Нормализация критериев

Зачастую целевые функции fi(x) имеют различную размерность и их необходимо свести к безразмерному виду с помощью какого-нибудь преобразования. Это преобразование должно удовлетворять по крайней мере следующим критериям:

· иметь общее начало отсчета и один порядок изменения значений на всем множестве допустимых решений

· быть монотонным преобразованием, т. к. должно сохранять отношение предпочтения на множестве D, т. е. не менять множество Парето

· учитывать необходимость минимизации отклонения от оптимальных значений по каждой целевой функции.

Обыкновенно для получения нормализованных критериев в качестве таких преобразований используют следующие:

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

Пример 5.1 (продолжение 1)

Если принять преобразование для нормализации критериев вида:

то первый нормализованный критерий получается в виде:

.

И тогда можно рассчитать значение первого нормализованного критерия в наилучшей и наихудшей точках по критерию f1:

Второй нормализованный критерий получается в виде: . А значение второго нормализованного критерия в наилучшей и наихудшей точках по критерию f2:

.

График, построенный по значениям нормализованных критериев, вычисленных для выше перечисленных точек (см табл. 5.1) представлен на рис. 5.3. Нижняя ломаная полученного многогранника есть множество нормализованных эффективных оценок.

Рисунок 5.3- Иллюстрация процесса решения примера 5.1 в пространстве нормализованных критериев.

4. Решение многокритериальных задач методом ограничений. Компромиссное решение

Недостаток принципа Парето в том, что он предлагает в качестве решения – множество решений, что не всегда приемлемо. Для того, чтобы выбрать из этого множества единственное решение нужны какие-то дополнительные сведения, предположения, договоренность о том, что же считать наилучшим решением (некоторая дополнительная неформальная информация).

Естественно, следует считать наилучшим такое решение, при котором величина отклонений от оптимальных значений по каждой целевой функции достигает своего минимального значения, т. е. для преобразованных функций – такое решение, при котором . Но наименьшие значения величин или (x) , как правило, не достигаются одновременно ни для какого решения из D (т. е. нельзя подобрать x, чтобы (x) max или min min .

Поэтому нужны какие-то дополнительные процедуры для отыскания какого-то единственного представителя из множества Парето. Специфика решения таких задач состои в том, что сам выбор такой процедуры, метода нахождения окончательного решения в какой-то степения основан на предположениях ЛПР, т. е. на субъективной информации.

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

Метод ограничений основан на теореме: если x0 – эффективное решение для данного вектора предпочтений , то ему соответствует наименьшее значение , при котором система равенств

= выполняется для всех i=1,k (5.2)

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

Например, если принять и , то это означает, что по информации ЛПР первый критерий в 2 раза значимее по сравнению со вторым.

Тогда в качестве решения задачи (5.1) можно принять компромиссное решение с заданным вектором предпочтений. Очевидно, что компромиссное решение – это такое эффективное решение x0, которое обеспечивает одинаковые минимальные значения параметра , при котором система (5.2) совместна.

Таким образом, компромиссное решение может быть найдено как единственное решение системы неравенств вида

для минимального значения параметра , при котором эта система совместна.

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

(5.3)

Для того, чтобы избежать необходимости использовать минимаксный (нелинейный) критерий, вспомогательную задачу (5.3) можно преобразовать в адекватную задачу (5.4), но уже с линейной целевой функцией.

(5.4)

Если исходная задача (5.1) является задачей представлена с помощью линейных целевых функций и функций-ограничений, то вспомогательная задача (5.4)является задачей ЛП:

(5.5).

Пример 5.1 (продолжение 2)

Выше были построены нормализованные критерии для целевых функций примера 5.1: 1(x)=0.6-0.3+0.1, 2(x)=1-0.25. Тогда система вновь введенных ограничений вспомогательной задачи (5.5) при будет выглядеть как:

.

Вспомогательная задача для этого примера представляет собой задачей ЛП с тремя неизвестными и функциональными ограничениями:

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

—

—

—

—

—

—

=

=

=

=

=

=

=

=

=

=

Видео:Вектор. Сложение и вычитание. 9 класс | МатематикаСкачать

Векторные интерпретация и метод решения задачи линейного программирования Текст научной статьи по специальности « Математика»

Видео:Cимплексный метод решения задачи линейного программирования (ЗЛП)Скачать

Аннотация научной статьи по математике, автор научной работы — Щеглов А. Ю.

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

Видео:Высшая математика. Линейные пространства. Векторы. БазисСкачать

Похожие темы научных работ по математике , автор научной работы — Щеглов А. Ю.

Видео:Как выражать вектор? Как решать задачу с вектором? | TutorOnlineСкачать

Текст научной работы на тему «Векторные интерпретация и метод решения задачи линейного программирования»

Федеральный портал «Инженерное образование»

Электронный журнал и

#3 март 2006 Ред. совет Специальности Рецензентам Авторам English Koi-8 Win

Векторные интерпретация и метод решения задачи линейного программирования #3 март 2006

А. Ю. Щеглов, д-р техн. наук проф., СПб ГИТМО (ТУ)

Векторные интерпретация и метод решения задачи линейного программирования

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

Интерпретация задачи линейного программирования как пошаговойзадачи

Задача линейного программирования в общем виде может быть представлена следующим образом: найти X n = 1, . N, такие, что

при условии, что

при Хп ^ 0, п = 1, . N. При необходимости дополняется условие целочисленности всех Хп.

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

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

где дпт — по какому-либо правилу нормированные (приведенные к безразмерному виду)

значения разнородных параметров. В случае необходимости учета различной относительной важности параметров в формуле (1) используются коэффициенты относительной важности параметров (или весовые коэффициенты) вт, где 0 ^ вт ^ 1,

тах, —>тт з что имеет физический

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

Данный подход, наряду с методом Паретто, представляет чисто теоретический интерес, так как на практике использование обоих критериев оптимальности существенно усложняет задачу оптимизации и, как правило, позволяет найти множество «нехудших решений», практически не уступающему по величине исходному множеству сравниваемых альтернатив. В [4—9] в качестве критерия оптимальности нами предлагается использовать параметр «длина проекции вектора качества варианта на идеальный вектор» Хп0, который

позволяет одновременно учитывать оба параметра X и , т. е. свести задачу

оптимизации к однокритериальной

при условии выбора оптимального варианта Хц

* глах . В [4] строго доказывается, что в

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

Действительно, с учетом того, что в ортонормированном базисе нормированные значения параметров идеального вектора = 1, т = 1. М, подставляя (2) и (3) в (4),

соответственно из (1) имеем

откуда следует, что аддитивная свертка параметров представляет собой приведенную или

умноженную на коэффициент (М) длину проекции вектора качества варианта на вектор

качества идеального варианта в ортонормированном пространстве критериев ЕМ. Так как

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

Теперь остановимся на вопросах синтеза ортонормированного базиса и векторной интерпретации использования весовых коэффициентов вт. При объективном способе

нормирования параметров [4, 9] в качестве идеальных выбираются лучшие значения параметров на сравниваемом множестве вариантов п = 1. N, задаваемые в рассматриваемом случае формулой

причем на сравниваемом множестве вариантов п = 1. N корректируются значения параметров, качество которых превосходит задаваемое (или требуемое) идеальное — приравнивается задаваемому идеальному. Нормированные значения параметров задаются формулами

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

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

плоскости (в пространстве Ям = 2) проиллюстрирована на рис. 1.

Рис. 1. Иллюстрация векторной интерпретации задачи линейного программирования

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

, образующий идеальное направление «продвижения в пространствеев» для выполнения заданных ограничений (идеальность направления соответствует равенству Qm

в исходной системе ограничений). Два возможных плана (Ы = 2) отображаются в рассматриваемом пространстве векторами, например и . Метод поэтапного

получения оптимального плана (векторный метод планирования) состоит в выборе на каждом этапе оптимизации лучшего вектора по критерию длины проекции вектора варианта на идеальный вектор (00′) с переносом системы координат в направлении и на величину выбранного на очередном этапе оптимизации вектора. В частности, на рис. 1 лучшим для рассматриваемого этапа составления плана при наличии двух вариантов будет вариант, отображаемый вектором . Отложив этот вектор, получим новую систему

координат и соответствующий ей новый идеальный вектор (0*0′), который примем в качестве вектора, задающего идеальное направление для следующего этапа. Многоэтапная процедура завершается при выполнении ограничений по всем видам задач. Набор отложенных векторов на всех этапах оптимизации (и соответственно отображаемые ими возможные частные планы) и составляют оптимальный план.

Замечание. При альтернативной постановке задачи линейного программирования — найти Х п = 1. N, такие, что

при условии, что

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

оптимального плана уже будет —>min min для каждого этапа оптимизации, причем

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

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

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

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

Очевидно, что приоритет планов здесь определяется приоритетами (в данном случае — значениями) ограничений и значениями коэффициентов Сп в целевой функции.

Предположим, что величины Сп = 1 для всех N рассматриваемых вариантов. В данных

предположениях имеем следующую формулу для расчета весовых коэффициентов:

Именно это условие нами рассматривалось при использовании предлагаемого подхода для решения систем линейных уравнений большой размерности [2] и для приложений задач линейного программирования, используемых для решения задачи распределения работ в мультипроцессорных системах, решаемых в рамках теории расписаний [1]. При различии значений С;? аддитивным критерием ^ должно учитываться и различие величин Сп в том смысле, в какой мере по сравнению с вариантом,

увеличит значение целевой функции любой иной п-й вариант. С

учетом сказанного имеем

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

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

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

Скажем несколько слов относительно вычислительной сложности предлагаемого метода. Следуя тому, что решаемая задача может быть отнесена к N^,-полным, сложность методов, предназначенных для ее решения, оценивается из следующих соображений. Если обозначить через О сложность отдельных операций (вычитание, сложение, деление и т. д.), реализуемых на каждом шаге оптимизации I, I = 1. Ь, причем на каждом шаге требуется выполнить О< операций, вычислительная сложность £ численного метода определяется по

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

Утверждение 1. Предлагаемый метод позволяет проводить оптимизацию за минимальное число шагов Ь.

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

Замечание. Возможность уменьшения числа шагов состоит в том, чтобы не исходно задавать дискретное значение параметра Х например, принимать для каждого шага Хп =

1, а выбирать Хп таким, при котором п-решение для рассматриваемого шага остается

оптимальным. Эта идея заложена, например, в симплекс — алгоритме, что не позволяет рассматривать этот метод как метод комбинаторного программирования. Аналогичный подход может быть применен и в рамках предложенного нами векторного метода [2]. Однако данные подходы приводят к резкому увеличению О, а как следствие, что видим из

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

Утверждение 2. Предлагаемый метод позволяет проводить сравнительный анализ вариантов на каждом 1-м шаге с минимальной вычислительной сложностью О

Доказательство этого утверждения, рассматриваемое в [4—9], основано на том, что, во-первых, опарное сравнение вариантов на каждом шаге осуществляется только по одному параметру (а не по М), что существенно снижает трудоемкость каждого шага О,,

во-вторых, именно сравнение по одному параметру позволяет выбирать на каждом шаге не ограниченное множество «нехудших решений», а лучший вариант (в противном случае выражение (6) должно было бы учитывать, что на каждом шаге сложность вычислений не О1, а г О, где г, — число «нехудших решений» на 1-м шаге, причем значение г, должно в

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

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

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

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

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

Численный метод точного решения задачи

Некоторые из приложений рассматриваемой задачи требуют либо точного ее решения, либо решения с заданной точностью. Для точного решения задачи и решения ее с заданной погрешностью результата может быть предложен двухэтапный подход (предложенный для решения системы линейных уравнений большой размерности в [2]). На первом этапе задача решается целочисленно, где оптимальные векторы откладываются полностью. На втором этапе реализуется точное решение. При этом решение получается уже в системе координат, получаемой для противоположного квадранта, вершиной которой будет точка пересечения последнего отложенного на первом этапе вектора с допустимой областью. Идеальный вектор получаем, соединяя вершину координат с точкой т = 1. М). Повторяем процедуру оптимизации, но уже откладываем некоторые

части к, к . Совместим области

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

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

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

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

Рис. 3. Иллюстрация векторной интерпретации многокритериальной задачи линейного программирования на плоскости

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

векторов, что проиллюстрировано на рис. 4. Вместе с тем на рис. 3 и рис. 4 явно выделяется один вектор — вектор , характеризуемый тем, что если его

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

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

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

Рис. 4. Иллюстрация задания идеального вектора для многокритериальной задачи

Таким образом, многокритериальная задача линейного программирования решается так же, как и однокритериальная, с использованием пошагового метода. Отличие состоит исключительно в способе задания идеального вектора. Равноидеальный вектор определяется по следующей формуле:

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

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

1. Щеглов А. Ю. Методика планирования распределения ресурсов вычислительной сети // Автоматика и вычислительная техника, 1989. № 1. С. 39—41.

2. Щеглов А. Ю. Векторная интерпретация и численный метод решения системы линейных уравнений // Изв. ВУЗов. Приборостроение, 1993. № 9—10. С. 36—44.

3. Кузьмин Б. И., Русин Ю. С. Векторная оптимизация систем и аппаратуры радиосвязи // Электросвязь, 1986. № 5. С. 30-32.

4. Щеглов А. Ю. Методика векторной оптимизации сложных подсистем информационно-вычислительных сетей // Автоматика и вычислительная техника, 1988. № 5. С. 14—19.

5. Щеглов А. Ю. Дополнительный критерий для формального выбора оптимального варианта ЛВС из множества «нехудших решений» // Автоматика и вычислительная техника, 1991. № 4. С. 39—41.

6. Щеглов А. Ю. Метод многокритериальной оптимизации сложных систем с экспертным заданием гипотетически идеального вектора качества // Изв. ВУЗов. Приборостроение, 1994. Т. 37. С. 21-23.

7. Щеглов А. Ю. Метод ограничений для оптимизации сложных систем // Радиотехника, 1993. № 4. С. 9—13.

8. Щеглов А. Ю. Метод поинтервального учета неравнозначности разнородных параметров альтернативных вариантов сложных систем вычислительной техники //

Автоматика и вычислительная техника, 1990. № 6. С. 10—13.

9. Щеглов А. Ю. Статистический метод нормирования и учета относительной важности разнородных параметров для многокритериальной оптимизации сложных радиотехнических систем // Радиотехника, 1995. № 3. С. 7—8.

МЕТОДЫ ОПТИМИЗАЦИИ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, № 8, 1998

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

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

Публикации со словами: Линейное программирование -многокритериальная оптимизация — векторное планирование — пошаговые методы См. также:

■ Векторный метод решения задачи линейного программирования; с пошаговым усечением множества «нехудших решений» Написать комментарий >>

📸 Видео

Транспортная задача (закрытая, с циклом). Метод потенциалов - подробно и понятноСкачать

Векторы. Метод координат. Вебинар | МатематикаСкачать

vector | Библиотека стандартных шаблонов (stl) | Уроки | C++ | #1Скачать

Урок 1.Поиск решения, оптимизация, оптимальный план производстваСкачать

ПРОСТОЙ СПОСОБ, как запомнить Векторы за 10 минут! (вы будете в шоке)Скачать

Реальность (2 день 1 часть)Скачать

Векторы для чайников (что потребуется знать при решении физических задач)Скачать

🎙 Бесконечное откладывание и отказ от принятия решений. Почему мы тормозим?Скачать

Выразить векторы. Разложить векторы. Задачи по рисункам. ГеометрияСкачать

8 класс, 48 урок, Применение векторов к решению задачСкачать

ВЫЧИТАНИЕ ВЕКТОРОВ ЧАСТЬ I #егэ #огэ #математика #геометрия #профильныйегэСкачать

Векторы и действия над ними, проекция вектора на координатные оси. 9 класс.Скачать