Глава 9. Многокритериальные методы и экономико-математические модели в условиях определенности
В практической деятельности часто встречаются задачи, заключающиеся в поиске лучшего (оптимального) решения при наличии различных критериев оптимизации. Эти критерии обычно противоречивы в том смысле, что не существует решения, наилучшего одновременно по каждому из них. Такого рода задачи могут быть сформулированы как задачи выбора наилучшей альтернативы при заданном наборе критериев и ограничений. Многокритериальные задачи выбора альтернатив чрезвычайно многообразны: множество альтернатив может быть конечным, счетным или континуальным; критерии могут иметь как количественный, так и качественный характер; режим выбора может быть однократным (разовым) или повторяющимся, допускающим обучение на опыте; последствия выбора могут быть точно известны (выбор в условиях определенности), иметь вероятностный характер (выбор в условиях риска), или иметь неоднозначный исход, не допускающий введения вероятностей (выбор в условиях неопределенности); и т.д. Различные сочетания перечисленных вариантов и приводят к многообразным задачам выбора, которые изучены не в одинаковой степени. Целью раздела является изложение наиболее простых и часто используемых в условиях определенности методов и моделей линейной многокритериальной оптимизации и метода многокритериальной оценки для случая, когда каждую отдельно взятую альтернативу можно оценить конкретным числом (значением критерия), и сравнение альтернатив сводится к сравнению соответствующих им чисел. Более подробно с данными вопросами можно ознакомиться в литературе [1-10].
9.1. Многокритериальные методы: основные понятия Впервые задача многокритериальной (векторной) оптимизации возникла у итальянского экономиста В.Парето (V.Pareto, 1848-1923) при математическом исследовании процесса рыночного обмена товаров. Позже аналогичные задачи появились и в других областях. Основные определения. Важнейшим понятием многокритериальной теории является понятие оптимальности по Парето. Оно представляет собой обобщение понятия точки максимума числовой функции на случай нескольких функций: решение оптимально по Парето, если значение любого из критериев можно улучшить лишь за счет ухудшения значений хотя бы одного из остальных критериев. Основы теории многокритериальной оптимизации были заложены в работах К.Эрроу, Х.Куна, Т.Саати, А.Таккера, Т.Купманса, С.Карлина и др. в начале 50-х гг. 20 века. Пусть задано множество альтернатив на множестве Х, т.е. в максимизации каждой компоненты вектора f(x) на множестве Х. Такую задачу будем обозначать через (X, f). Если нужно минимизировать функцию fi(x), то такая задача сводится к задаче на максимум путем замены fi(x) на Отметим еще, что любой критерий fi можно заменить на kfi+l (где k>0), afi (a>1), b - fi (0<b<1) или на Задачи, в которых критерии упорядочены по важности (и перенумерованы) так, что каждый предыдущий несравненно важнее, чем все последующие, называются лексикографическими задачами оптимизации. В таких задачах следует добиваться сколь угодно малого приращения более важного критерия за счет сколь угодно больших потерь по всем остальным менее важным критериям. В зависимости от структуры множества Х и свойств функций Если Х выпукло, а все fi – вогнутые функции, то задача называется вогнутой. В частности, если Х – полиэдральное множество, т.е. «вырезано» из Rn конечной системой линейных неравенств и равенств, а все fi – линейны, то многокритериальная задача называется линейной. Сущность многокритериальной задачи (X, f) состоит в нахождении оптимального ее решения, т.е. такого Будем говорить, что альтернатива
причем среди этих неравенств имеется хотя бы одно строгое. Это означает, что выбор х1, а не х2 позволяет каждому критерию получить не меньшее значение, а хотя бы по одному – строго большее. Те альтернативы из множества Х, для которых не существует доминирующих альтернатив, называются эффективными или оптимальными по Парето. Иначе говоря, альтернатива
и хотя бы для одного i это неравенство строгое. Из данного определения вытекает, что улучшение по какому-либо критерию относительно альтернативы, оптимальной по Парето, может быть достигнуто только за счет ухудшения по какому-нибудь иному критерию. Множество всех оптимальных по Парето альтернатив для задачи (X, f) будем обозначать через Р(X, f) и называть множеством Парето. Важнейшая особенность задачи многокритериальной оптимизации состоит в том, что ее решением является, как правило, не единственная точка, а множество Парето, представленное неэквивалентными и содержательно существенно разными решениями. В однокритериальных задачах в качестве оптимального можно брать любое решение, максимизирующее критерий (поскольку все они эквивалентны). В многокритериальной задаче каждая альтернатива В случаях наличия лишь двух или трех критериев множество P(F) можно изобразить графически. Поэтому при анализе двух-, а иногда и трехкритериальных задач нередко удобнее всего выбирать оптимальное по Парето решение непосредственно на основе рассмотрения графика множества P(F). Для иллюстрации рассмотрим простейший пример с двумя критериями. Пусть множество векторных оценок
Рис. 9.1. Множество векторных оценок Легко видеть, что множество векторных оценок, доминирующих по Парето векторную оценку f(x), совпадает с неотрицательным ортантом (конусом[2]) C(x), вершина которого перенесена в точку f(x). В самом деле, для любой точки Базовые методы решения многокритериальных задач можно подразделить на следующие группы: методы, основанные на свертывании критериев; метод нахождения арбитражных решений; метод идеальной точки; метод последовательных уступок. Вместо исходной многокритериальной задачи в соответствии с выбранным методом, формируется замещающая задача. В состав замещающей задачи входит один критерий, а к исходной системе ограничений добавляется одно или несколько дополнительных ограничений. Решение замещающей задачи должно принадлежать области Парето, т.е. быть эффективным. Широко известным подходом к решению многокритериальной задачи (X, f) является метод многокритериальной оценки, в рамках которой происходит сведение многокритериальной задачи к обычной («однокритериальной») задаче математического программирования путем замены целевых функций Одним из самых ответственных и сложных этапов построения обобщенных критериев является определение коэффициентов важности. Обычно для их определения приходится использовать специальную информацию, запрашиваемую у лица, принимающего решение, или получаемую от эксперта. Вначале все исходные критерии 1) 2) где Далее все критерии Частный случай данного подхода заключается в выборе главного критерия, т.е. в том, чтобы все веса l i, за исключением некоторого Один из вариантов описанного подхода состоит в том, что исходная многокритериальная задача (x, f) сводится к задаче оптимизации по одному критерию
Дж.Нэшем (J.Nash) предложен метод нахождения так называемых арбитражных решений [4], существенно ограничивают число выбираемых решений среди оптимальных по Парето. Его идея состоит в установлении на основании содержательных соображений некоторых минимальных допустимых значений
В [3] для задачи (x, f) предлагается использовать метод идеальной точки, состоящий в нахождении такой точки множества Парето, векторная оценка которой находится ближе всего к идеальной точке
где Хотя метод идеальной точки представляется очень привлекательным, он не лишен довольно существенных недостатков. В самом деле, метрику в Rn можно вводить различными способами, а при разных метриках наилучшими могут оказываться разные оптимальные по Парето решения. Можно показать, что для любого оптимального по Парето решения найдется метрика, в которой векторная оценка этого решения будет ближайшей к идеальной точке. Итак, от задачи выбора оптимального по Парето решения приходим к задаче выбора метрики, которая отнюдь не проще. В [3] для решения многокритериальной задачи предлагается использовать метод последовательных уступок. Суть метода состоит в том, что критерии нумеруются в порядке убывания важности. Далее в соответствии с рейтингом решается однокритериальная задача на основе определяется оптимальное значение критерия Если в задаче более двух критериев, то процедура повторяется для других критериев. Далее приведем примеры решения задач многокритериальной оптимизации. Пример 9.1. Предприятие может производить продукцию двух видов П1 и П2, используя для этого два вида ограниченных ресурсов Р1 и Р2. Расход ресурсов на производство продукции, запасы ресурсов и прибыль приведены в таблице 9.1. Таблица 9.1
Определить план производства продукции, максимизирующий прибыль и суммарное количество продукции. Необходимо решить задачу: 1. Методом последовательных уступок, если более важным является критерий прибыли и уступка по нему составляет 175 ден.ед. 2. Методом идеальной точки, исходя из того, что целевое значение показателя прибыли составляет 3. Методом многокритериальной оценки при 4. Методом арбитражных решений, если минимальные допустимые значения для критериев Решение. Построим математическую модель задачи. Обозначим через х1 и х2 количество продукции вида П1 и П2 соответственно. Тогда модель задачи Для определения множества Парето сделаем графическую иллюстрацию (рис. (9.2)) Рис. 9.2. Область допустимых решений и оптимальные решения по двум критериям В точке А с координатами (0; 40) значение первой целевой функции максимально и составляет В точке В с координатами (32; 24) вторая целевая функция достигает максимума, ее значение равно
1. Решим задачу методом последовательных уступок. Уступка по критерию прибыли составляет 175 ден. ед. Дополнительное ограничение замещающей задачи формируется в соответствии с неравенством
тогда замещающая задача примет вид Решением задачи является х1 = 23,3; x2 = 28,3; f2= 23,3 + 28,3 = 51,6; f1 = 10 ∙ 23,3 + + 35 ∙ 28,8 = 1225. Полученное решение является эффективным, т.к. точка (23,3; 28,3) расположена на отрезке АВ. Таким образом, при выпуске 22,3 т продукции первого вида и 28,3 т продукции второго вида прибыль составит 1225 ден. ед., объем выпуска – 51,6 т. 2. Решим задачу методом идеальной точки. Запишем модель замещающей задачи Получим решение Поскольку отклонения от оптимальных величин критериев ненормированы, то решение приближено к максимальному значению первого критерия т.к. масштаб этого показателя больше. Пронормируем отклонения, разделив их на максимальные значения функций, чтобы привести отклонения критериев к сопоставимому и безразмерному виду Решение: 3. Решим задачу методом аддитивной свертки. Модель замещающей задачи Решение: Если изменить значения весовых коэффициентов и принять
Получим решение 4. Решим задачу методом арбитражных решений. Модель замещающей задачи Решение:
Популярное: Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... ![]() ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (599)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |