Green-sell.info

Новые технологии
1 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Многокритериальная оптимизация примеры

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

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

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

Похожие темы научных работ по математике , автор научной работы — Маркина М. В.

MULTICRITERIA OPTIMIZATION PROBLEMS IN ECONOMICS

The article demonstrates a numerical technique to solve two-criteria multiextremal problems with constraints which approximates a Pareto set with a given accuracy. The technique is based on the information-statistical approach to global optimization. Some cases are discussed when a mathematical model of an economic problem is the problem of multicriteria optimization.

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

Математическое моделирование. Оптимальное управление Вестник Нижегородского университета им. Н.И. Лобачевского, 2014, № 4 (1), с. 416-421

МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ ОПТИМИЗАЦИИ В ЭКОНОМИКЕ © 2014 г. М.В. Маркина

Нижегородский госуниверситет им. Н.И. Лобачевского

Поступбла в редаоцбю 03.04.2014

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

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

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

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

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

• Оценить эффективность экономической системы по нескольким показателям. При необходимости принятия решения по инвестиционному проекту его следует оценивать по всем показателям (NPV, IRR, рентабельности и др.).

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

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

• Оценить доходность инвестиционного портфеля и его риск. В этом случае математическая модель управления инвестиционным портфелем с учетом риска будет бикритериальной задачей оптимизации [2].

• Выбрать наилучший вариант организации поставок сырья, например, из нескольких доступных анализируемых вариантов. При этом в качестве частных критериев могут выступать следующие: минимизация ожидаемых годовых издержек, обусловливаемых соответствующими расстояниями и затратами на перевозки; минимизация ожидаемых годовых издержек, обусловливаемых форс-мажорными ситуациями у поставщика (учет влияния факторов надежности); минимизация оценки годовых издержек, обусловливаемых возможными срывами поставок из-за погодных условий и т.д. Данная задача является примером задачи логистики. В работе [3] рассматриваются различные постановки задач в логистике, решение которых сводится к решению многокритериальных задач оптимизации.

Математическая модель бикритериальной задачи оптимизации

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

1) точки x . x предшествующих итераций

перенумеровываются нижними индексами в порядке возрастания координаты, т.е.

a = x0 p>, 1 p>, 1 m, сопоставляется вектор q’ = (q1, q2), где

qj = E[(Zji — Zjmin ) / hj ]hj + Zjmin, j = 1, (11) q’ = 1 — параметр метода), причём если max

v(xt)> 0), прекращающим итерации при выполнении неравенства

МЕТОДЫ РЕШЕНИЯ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

Многокритериальные задачи в экономике

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

Будем полагать, что известны варьируемые экономические переменные х„ на значения которых наложены ограничения

где X — множество допустимых значений (альтернатив, вариантов, решений).

Предполагается, что множество Xзамкнуто.

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

В общем случае многокритериальную задачу можно записать в виде отображения

где U с R M — множество значений критериев.

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

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

Читать еще:  Оптимизация проекта по времени

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

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

Качественные критерии не всегда правильно используются на практике. Пусть при сравнении успеваемости студентов Л и В по двум равнозначным дисциплинам были использованы следующие данные: студент А получил 70 баллов по линейной алгебре и 70 баллов по математическому анализу (по 100-балльной шкале), что соответствует оценкам 4 по пятибалльной шкале. Студент В был соответственно оценен в 48 и 100 баллов по 100- балльной шкале, что соответствует двум и пяти баллам по пятибалльной шкале. В результате получаем, что по 100-балльной шкале лучше второй студент: 70 + 70 2 + 5.

В дальнейшем будем рассматривать только количественные критерии.

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

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

9 Многокритериальные задачи

Постановка задачи линейного программирования. Математическая модель задачи. Примеры задач линейного программирования. Графический метод решения задачи. Симплекс– метод решения задачи линейного программирования. Анализ решения задачи линейного программирования.

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

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

n показатели-критерии являются одноименными для всех альтернатив и их количество у всех альтернатив одинаковое;

n другие показатели альтернатив либо одинаковы, либо несущественны в данной задаче.

Если альтернативы оцениваются по m критериям, где m > 1, то такая задача принятия решений называется многокритериальной.

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

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

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

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

Предположим, что при оценке альтернатив использовались два критерия: стоимость (К1) и надежность (К2). Значения критериев для трех альтернатив представлены в таблице.

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

Альтернатива ai является доминирующей по отношению к альтернативе ak, если по всем критериям оценки альтернативы ai не хуже, чем альтернативы ak, а хотя бы по одному критерию оценка ai лучше. При этом альтернатива ak называется доминируемой. Из определения следует, что альтернатива 3 из приведенного выше примера является доминирующей по отношению к альтернативе 1 и альтернативе 2. Это можно увидеть из рис. 1, где альтернатива 3 занимает самое правое и верхнее положение по отношению к другим альтернативам.

Читать еще:  Примеры задач многокритериальной оптимизации

Рассмотрим теперь альтернативы 1 и 2. Из рис. 1 также следует, что альтернативы 1 и 2 не находятся в отношении доминирования. Действительно, по стоимости предпочтительнее альтернатива 1, а по надежности — альтернатива 2. Эти альтернативы являются несравнимыми по отношению предпочтения между векторными оценками, так как их невозможно сравнить непосредственно на основе критериальных оценок. Множество несравнимых альтернатив образуют область эффективных решений и называется множеством Парето, а альтернативы, образующие это множество Парето-оптимальными. Если вернуться к примеру, то оставшиеся альтернативы 1 и 2 принадлежат множеству Парето.

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

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

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

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

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

1. Указание нижних границ критериев. Набор оценок нижних границ по каждому критерию представляет собой дополнительную информацию. При указании нижних границ критериев оптимальной может считаться только такая Парето-оптимальная альтернатива, для которой оценка по каждому из критериев не ниже назначенной оценки. Это приводит к сужению Парето-оптимального множества.

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

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

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

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

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

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

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

n При практическом применении данного метода возникают трудности в установлении полной упорядоченности критериев по их относительной важности.

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

Проиллюстрируем рассмотренные в этом пункте методы нахождения оптимального решения в многокритериальных ЗПР на следующем примере.

Пример. Выбор места работы. Предположим, что Вам предстоит выбрать место работы из девяти вариантов, представленных в табл. 5.1. В качестве основных критериев взяты: зарплата 3, длительность отпуска Д, время поездки на работу В. Так как критерий В имеет характер потерь, оценки по этому критерию берутся со знаком «минус». Какой вариант является оптимальным?

Читать еще:  Как записать linux mint на диск

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Классификация методов оптимизации

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

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

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

Если необходимо установить экстремум целевой функции при некоторых условиях, которые накладываются на ряд других величин (например, определение максимальной производительности при заданной себестоимости, определение оптимальной температуры при ограничениях по термостойкости катализатора и др.), то такая оптимизация называется условной [2].

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

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

В зависимости от управляющих параметров различают следующие задачи:

— оптимизация при одной управляющей переменной — одномерная оптимизация;

— оптимизация при нескольких управляющих переменных — многомерная оптимизация;

— оптимизация при неопределённости данных;

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

В зависимости от критерия оптимизации различают:

— с одним критерием оптимизации — критерий оптимальности единственный;

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

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

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

Общая постановка задачи одномерной оптимизации сводится к следующему: имеется некоторая функция f(x) от одной переменной x, необходимо найти такое значение x*, при котором функция f(x) принимает экстремальное значение. Под этим значением понимают минимальное или максимальное значения.

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

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

Для решения задачи минимизации функции f(x) на отрезке [a, b], в большинстве случаев, используют приближенные методы. С их помощь можно найти решения этой задачи с необходимой точностью в результате нахождения конечного числа значений функции f(x) и ее производных в некоторых точках отрезка [a, b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации. Достоинством прямых методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность определения значений f(x) в заданных точках [4]. Среди задач математического программирования самыми распространёнными и наиболее хорошо исследованными являются так называемые задачи линейного программирования (линейной оптимизации). Рассмотрим этот тип задач. Для них характерно то, что целевая функция линейно зависит от , а также, что ограничения, накладываемые на независимые переменные, имеют вид линейных равенств или неравенств относительно этих переменных.

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

Общая задача линейной оптимизации заключается в нахождении максимума (минимума) линейной целевой функции. Вид целевой функции и ограничений описываются формулами (1.11.4).

где целевая функция, критерий оптимальности или линейная форма;

x вектор неизвестных;

коэффициенты целевой функции;

величины правых частей ограничений.

Вектор значений неизвестных x = (x1, x2, …, xn), удовлетворяющих условию задачи (1.1) — (1.4) , называется допустимым решением или допустимым планом задачи линейной оптимизации. Совокупность всех допустимых планов называется множеством допустимых планов. Допустимое решение x * = (x1 * , x2 * , …, xn * ) называется оптимальным, если оно обеспечивает максимальное (или, в зависимости от условий задачи, минимальное) значение целевой функции.

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

При решении ряда оптимизационных задач требуется, чтобы значения неизвестных x = (x1, x2, …, xn) выражались в целых числах. К задачам подобного типа относятся те, в которых требуется определить необходимые для принятия решений значения физически цельных объектов (машин, агрегатов различного типа, людей, транспортных единиц и т.д. и т.п.).

Такие задачи относятся к задачам целочисленной оптимизации. Математическая модель задачи линейной целочисленной оптимизации также определяется формулами (1.1) — (1.4), но в данном случае налагается дополнительное требование целочисленности всех (или части) неизвестных. Если требование целочисленности распространяется лишь на часть неизвестных величин задачи, то такая задача называется частично целочисленной [5].

Ссылка на основную публикацию
ВсеИнструменты
Adblock
detector
×
×