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

Многокритериальные задачи принятия решений в условиях определенности

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

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

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

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

— критерий первого вида; (2.1)

— критерий второго вида; (2.2)

при ограничениях:

, (2.3)

(2.4)

где — количество производимых продуктов j- го типа (соответственно столов и шкафов), j = 1,2;

— нормативная матрица затрат i -го вида сырья на 1 единицу j -го типа продукта;

— ограничение на i -й вид сырья (пиломатериал, шурупы, краска), j = 1,2,3.

Вернемся к графическому способу решения задачи в отдельности по каждому из критериев (рис. 2.1).

Рис. 2.1 — Графическое решение задачи

Если решать задачу только с учетом критерия первого вида , то решение получим в точке = (517,156), а значение критерия рублей. Если решать задачу без учета критерия первого вида, а только с учетом критерия второго вида, то получим решение в точке , а значение критерия 700 столов.

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

Рис. 2.2 — Компромиссное множество решений

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

Сведение многокритериальной задачи к однокритериальной

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

.

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

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

,

где — отнормированное значение i -го критерия;

— коэффициент относительной важности i-го критерия (весовой коэффициент);

.

Весовой коэффициент определяется экспертными методами. Значение для каждого из критериев, как правило, есть безразмерная величина и находится в интервале Наиболее простым способом нормализации [7] является получение оценок по формуле , где — идеальное (возможно максимальное) значение i -го критерия.

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

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

Выделение главного критерия

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

;

— ограничение по критерию ;

.

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

Предположим, что частные критерии упорядочены в порядке убывания их важности . Решая задачу по критерию , найдем решение . Если ЛПР может сделать некоторую уступку по первому критерию в объеме (пусть = 5500), чтобы улучшить решение по следующему критерию (рис. 3.32), то это приводит к задаче поиска решения по второму критерию с уступкой по первому: при ограничениях:

;

— уступка по первому критерию;

.

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

Метод целевой точки

Метод целевой точки (опорной, идеальной) базируется на задании по каждому критерию так называемых уровней притязаний [3, 4,7] в виде желаемых значений критериев . Поскольку оценки задаются без точного знания структуры множества допустимых решений, то целевая точка может оказаться как внутри, так и вне области допустимых решений. Наиболее близкая точка решения к целевой будет определять наилучшее решение. В качестве меры близости между решением и целевой точкой, т.е. между векторами предлагается использовать различные расстояния [4], в том числе расстояние типа

,

где — коэффициент относительной важности критерия

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

,

при ограничениях (3.52) и (3.53).

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

Дата добавления: 2015-05-09