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

2.2.1. Определение
коэффициентов веса параметров

Постановка задачи

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

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

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

Предложено достаточно много методов определения экспертных оценок. Рассмотрим три из них.

2.1.2. Непосредственное назначение
коэффициентов веса

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

,

где n — число экспертов.

Алгоритм 7.1.1. Непосредственное назначение
коэффициентов веса

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

Сделать таблицу по форме, представленной на рис. 7.1.1, которую мы будем называть базовой.

Рис. 7.1.1

Ввести функции Excel, определяющие среднее значение, среднее квадратическое отклонение, дисперсию, как это показано в ячейках С8:F10.

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

Значения коэффициентов веса, назначаемые каждым экспертом, ввести в ячейки С4:F7.

На экране: результат экспертизы.

В ячейках С8:F8 находятся усредненные значения коэффициентов веса.

Значение коэффициента вариабильности показывает величину разброса экспертных оценок. При v Ј 0,2 оценки экспертов можно считать согласованными. В случае v > 0,2 целесообразно провести с экспертами содержательное обсуждение важности оцениваемых параметров, после чего повторить экспертизу. При сохранении величины разброса целесообразно учитывать вероятностный характер экспертных оценок по методам, приведенным ниже.

Пример заполнения таблицы приведен на рис. 7.1.2, в которой принято число параметров три: А, Б, В и число экспертов n = 8.

Рис. 7.1.2

Как показывает опыт, удовлетворение экспертами требования

при К > 3, вызывает затруднение.

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

2.1.3. Оценка важности параметров в баллах

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

Алгоритм 7.1.2. Определение коэффициентов веса оценки важности параметров в баллах

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

Рис. 7.1.3

В ячейках G6:G9 введены функции суммирования.

Составить базовую таблицу (рис. 7.1.4), аналогичную таблице, показанной на рис. 7.1.1, в ячейки J4:M7 которой ввести указанные функции.

Рис. 7.1.4

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

Пример исходных оценок в баллах по форме рис. 7.1.3 представлен на рис. 7.1.5, а результат определения экспертных оценок по форме рис. 7.1.4 — на рис. 7.1.6.

Рис. 7.1.5

Рис. 7.1.6

2.1.4. Метод парных сравнений

Если при k > 3 одновременная оценка всех параметров вызывает затруднения, их можно оценивать еще одним методом, который называется методом парных сравнений. Этот метод реализуется с помощью следующего алгоритма.

Алгоритм 7.1.3. Определение коэффициентов веса методом парных сравнений

Определить число оцениваемых параметров k и число экспертов n. В дальнейшем принимаем k = 5; n = 4.

Для каждого эксперта составить отдельную таблицу по форме, представленной на рис. 7.1.7.

Рис. 7.1.7

В этой таблице эксперт должен ввести оценку парных сравнений, которая заключается в следующем. Если k-ый параметр важнее j-го, то в ячейке, принадлежащей k-ой строке и j-му столбцу, указывается 1, в противном случае — 0.

Пример заполнения такой таблицы первым экспертом приведен на рис. 7.1.8, из которой видно, что по оценке этого эксперта параметр А менее важен, чем параметр Б (D16 = 0) и Д (G16 = 0), но более важен, чем В (Е16 = 1) и Г (F16 = 1).

Рис. 7.1.8

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

Рис. 7.1.9

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

Пример заполнения таблицы для 1-го эксперта по данным рис. 7.1.8 приведен на рис. 7.1.10 в ячейках C17:H17. Данные в ячейках C18:H20 из таблиц для остальных экспертов вводятся аналогично.

Рис. 7.1.10

В этой таблице в ячейках C21:G21 приведены окончательные результаты проведенной экспертизы.

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

2.2.1. Обобщенная целевая функция

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

, (7.2.1)

где F_k — k-ая целевая функция,

F_k^норм — нормирующее значение k-ой целевой функции,

s — число составляющих целевых функций,

a_k — коэффициент веса k-ой целевой функции.

При этом перед составляющими целевой функции, которые максимизируются, ставится знак плюс, перед минимизируемыми — минус. Из (7.2.1) следует, что для формирования обобщенной целевой функции необходимо знать a_k и F_k^норм. Значения F_k^норм принимаются при максимизации k-ой составляющей целевой функции:

F_k^норм = F_k^max,

при ее минимизации

F_k^норм = F_k^min.

Решение по обобщенной целевой функции рассмотрим для нашей задачи, приведенной на рис. 7.2.1.

Алгоритм 7.2.1. Оптимизация по обобщенной
целевой функции

Вызвать таблицу с условиями задачи (рис. 7.2.1).

Определить, какие составляющие целевые функции будут входить в обобщенные. Принимаем:

ЦФ1 — максимизация прибыли,

ЦФ2 — минимизация используемых финансов.

Рис. 7.2.1

При минимизации хотя бы для одной составляющей необходимо ввести нижние границы значений переменных. Вводим 1 в ячейки В4, С4, D4, E4.

Ввести условия задачи.

Решить задачу при максимизации прибыли.

На экране: результат решения задачи F6 = maxЦФ1 = 1290.

Ввести в ячейку F4 значения ЦФ2, которые равны левой части в ограничении по финансам (F11).

Решить задачу при минимизации используемых финансов.

На экране: результат решения задачи F4 = minЦФ2 = 33.

Провести экспертизу и определить коэффициенты веса. Принимаем a₁ = 0,75; a₂ = 0,25.

Ввести эти данные, как показано на рис. 7.2.1, в ячейки J2:J3.

Сформулировать обобщенную целевую функцию

J6 = ЦФ_об= J2*F6/1290 - J3*F4/33.

Решить задачу по обобщенной целевой функции.

Результаты решения по трем целевым функциям приведены в таблице (рис. 7.2.2).

Из этой таблицы видно следующее:

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

Такое положение не распространяется на значения переменных.

Рис. 7.2.2

2.2.2. Оптимизация по ресурсам

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

, (7.2.2)

где y_i — количество неиспользованного i-го ресурса,

b_i — количество располагаемого i-го ресурса,

b_i — коэффициент веса i-го ресурса,

m — количество ресурсов.

Нетрудно видеть, что смысл оптимизации по данной целевой функции заключается в максимизации использования ресурсов. При этом очередность их использования определяется назначенным коэффициентом веса. Решение по такой целевой функции рассмотрим на примере нашей базовой задачи (рис. 3.3.4).

Алгоритм 7.2.2. Оптимизация по ресурсам

Вызвать таблицу с условиями задачи (рис. 7.2.3).

Ввести значения у₁, у₂, у₃ в F2:H11.

Изменить знаки неравенства в ограничениях на равенства в J9:J11.

Ввести значения коэффициентов веса в J2:J4.

Рис. 7.2.3

Сформулировать целевую функцию

К2=(J2*F3/K9 +J3*G3/K10 + J4*H3/K11).

Ввести условия задачи по алгоритмам главы 3.

Решить задачу по алгоритмам главы 3.

На экране: результат решения задачи.

Для определения влияния коэффициентов веса на результат решения задачи можно решать ее при различных значениях этих коэффициентов. Результаты решения задачи при различных коэффициентах веса приведены на рис. 7.2.4, из которого видно, что увеличение коэффициента веса ресурса обеспечивает его равномерное использование. Например, для финансов: при b₃ = 0,5 неиспользуемые финансы y₃ = 0, т. е. финансы используются полностью, а при b₃ = 0,2 неиспользуемые финансы y₃ = 36.

Рис. 7.2.4

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

7.2.3. Метод последовательных уступок

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

Алгоритм 7.2.3. оптимизация методом
последовательных уступок

Вызвать таблицу с условиями задачи (рис. 7.2.5).

Рис. 7.2.5

Принять параметры, по которым будем решать задачу.

Принимаемв качестве целевой функции прибыль, значения которой находятся в ячейке I6, ав качестве задаваемогопараметра ¾ величину неиспользуемых финансов у₃, значение которой вводится в ячейку ввода исходных данных H4.

В качестве первого значения вводим y₃ = 50.

Вызвать диалоговое окно Поиск решения.

Изменить граничные условия Н3 >= Н4 на Н3 = Н4.

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

Результат параметрирования показан на рис. 7.2.6.

Рис. 7.2.6

Отредактировать отчет.

На экране: результат редактирования (рис. 7.2.7).

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

Рис. 7.2.7

Алгоритм 7.2.4. Графическое представление
последовательных уступок

Выделить А8:L9 (рис. 7.2.7).

Мастер диаграмм:

шаг 2 ¾ График

шаг 3 ¾ Вид2

шаг 4 ¾ 1 стр. метки; 1 столб.

шаг 5 ¾ Убрать легенду, ввести названия графика и осей.

На экране: график последовательных уступок.

Выполнить форматирование диаграммы.

На экране: рис. 7.2.8.

рис. 7.2.8

Из таблицы (рис. 7.2.7) видно, что если мы хотим иметь прибыль, скажем, 1020, то при этом величина неиспользуемых финансов будет равна 30. Если же мы хотим иметь неиспользованных финансов 60, то прибыль при этом будет равна 600.

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

7.3. Задачи сравнения вариантов

7.3.1. Оценка вариантов
по обобщенному критерию

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

, (7.3.1)

где К_S — значение обобщенного критерия для s-го варианта,

a_i — коэффициент веса i-го параметра,

x_i^S — значение i-го параметра для s-го варианта,

x_i^H — нормирующее значение для i-го параметра,

m — количество параметров.

Определение коэффициентов веса производится теми же методами, которые были рассмотрены в разделе 7.1. В качестве нормирующего значения x_i^H принимается либо заданное значение x_i^зад, либо некоторое значение, принимаемое за x_i^H.

Структура обобщенного критерия (7.3.1) аналогична структуре обобщенной целевой функции (7.1.1.), однако не следует забывать, что с помощью обобщенного критерия производится оценка и сравнение имеющихся вариантов, в то время как с помощью целевой функции производится определение таких значений параметров, которые обеспечивают максимизацию или минимизацию ее значения. Сравниваемые варианты характеризуются, как правило, тремя основными параметрами:

производительностью;

качеством;

стоимостью.

Оценка и сравнение вариантов производятся по следующим алгоритмам.

Алгоритм 7.3.1. Оценка вариантов
по обобщенному критерию

Провести экспертную оценку важности параметров.

Результаты экспертизы приведены на рис. 7.3.1.

Рис. 7.3.1

Составить таблицу для расчета по зависимости (7.3.1).

Таблица с формулами представлена на рис. 7.3.2, таблица с данными — на рис. 7.3.3.

Рис. 7.3.2

Ввести полученные значения экспертных оценок (рис. 7.3.1) в ячейки С8:Е8 (рис. 7.3.3).

Принять нормирующее значение для параметров и ввести их в ячейки С9:Е9 (рис. 7.3.3).

Рис. 7.3.3

Ввести исходные данные: принимаемые значения параметров сравниваемых вариантов в ячейки С3:Е7 (рис. 7.3.3). В рассматриваемом примере качество оценивается надежностью, измеряемой в часах наработки на отказ.

На экране: рис 7.3.3 (в ячейках I3:I7 значение критерия для каждого варианта).

Алгоритм 7.3.2. Сравнение вариантов

Ячейки В2:В7 (рис 7.3.3) скопировать в блок С13:С18.

Для ячеек I2:I7, содержащих значения критерия, выполнить следующее:

Выделить I2:I7.