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

Дисциплина МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ Кафедра математических методов в экономике

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

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

Задача выбора наилучшего проектного решения. Необходимо принять решение о строительстве нового предприятия. Для этого из нескольких конкурсных проектов необходимо выбрать один. Критериями эффективности могут служить стоимость реализации проекта и величина прибыли, которую обеспечит построенное предприятие. Если ограничить рассмотрение задачи лишь одним критерием эффективности, практическая значимость её решения окажется незначительной. Так как при использовании только первого критерия будет выбран самый дешёвый проект, но его реализация может привести к недопустимо малой прибыли. С другой стороны, на строительство самого прибыльного проекта, выбранного на основе второго критерия эффективности, может просто не хватить имеющихся средств. Поэтому в данной задаче необходимо учитывать оба указанных критерия одновременно. Если же дополнительно стараться минимизировать нежелательные экологические последствия строительства и функционирования предприятия, то к двум указанным следует добавить еще один – третий критерий и т. д. Рассмотренная многокритериальная задача носит название задачи выбора наилучшего проектного решения.

Математическая формулировка многокритериальной задачи

Эффективное решение Если цели находятся в противоречии друг с другом, то не существует оптимального решения, которое удовлетворяло бы всем критериям эффективности. В этом случае вводится понятие «эффективное решение». Оно означает, что невозможно улучшить значение любой из целевых функций без ухудшения значений одной или нескольких целевых функций. Уточним введенное понятие для задачи максимизации: решение X* называется эффективным, если не существует допустимого решения , такого, что по крайней мере, для одного индекса j. Множество всех эффективных решений в непрерывном случае известно как эффективная граница. Эффективное решение называют также недоминируемым решением, неулучшаемым решением или решением по Парето (Парето-оптимальным решением).

2.2. Множество Парето Внутренние и граничные точки

Возможные перемещения точек

Граница Парето

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

Геометрическая интерпретация

Неразрешимость задачи

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

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

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

Замечание 1 Задачу максимизации можно путем умножения Целевой функции на (–1) преобразовать в задачу минимизации, решаемую при тех же самых ограничениях. Это связано с наличием следующего свойства: функция (- f ) достигает наибольшего значения в тех точках, в которых функция f принимает наименьшее значение, и наоборот. Это означает, что условия [f → min] и [(-f) → max] равносильны. Следовательно, поменяв знак целевой функции на противоположный, любую двухкритериальную задачу можно свести к задаче максимизации с двумя целевыми функциями.

2.4.Применение метода идеальной точки

ОДР

Идеальная точка

Ответ

Замечание 2

Пример 2

Геометрическая интерпретация

Ответ

2.5. Пример решения экономической задачи с двумя критериями эффективности Задача 1. ОАО «Мукомольный завод» реализует хлебопекарную муку высшего сорта двумя способами: через сеть магазинов и через прямые поставки по договорам неторговым организациям. Известно, что ежемесячно магазины могут реализовать не более 50 тыс., а ежемесячные поставки неторговым организациям не должны превышать 35 тыс. т муки. Для продажи в каждом месяце выделяется не более 45 тыс. т муки. Предприятие выработало определенную политику в области ценообразования, которой собиралось следовать. Однако в связи с сильно изменившейся экономической ситуацией, затраты на реализацию увеличились, а мука вошла в перечень продуктов, которые должны продаваться по ранее установленной цене, регулируемой местной властью. При продаже 1 тыс. тонны муки через магазины расходы на реализацию стали составлять 7 тыс. руб., а цена осталась прежней — 10 тыс. руб.; при втором способе реализации расходы и цена составили 5 и 8 тыс. руб. соответственно. Необходимо определить, сколько муки следует продавать каждым способом, чтобы расходы были минимальными, а выручка от продажи — максимальной.

ОДР на плоскости

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

Формулировка задачи

Метод решения

Нахождение оптимального плана выпуска продукции Задача 2. АООТ «Прицеп» выпускает 4,5-тонные прицепы и кормораздатчики «Ванюша» по цене 40,3 и 74,3 тыс. руб. соответственно. По результатам маркетинговых испытаний спрос на изделия первого вида не менее 1 200 шт. в год. Для производства прицепов используются сталь и чугун, запасы которых на предприятии составляют 25 000 и 4 500 т соответственно. Для изготовления одной тысячи прицепов норма расхода стали составляет 1 615 т, а чугуна — 385 т. Для изготовления одной тысячи кормораздатчиков расходуется: стали — 2 022 т, чугуна — 478 т. Себестоимость прицепов — 34,66, а кормораздатчиков — 63,9 тыс. руб. Составить годовой план производства прицепов и кормораздатчиков, такой, чтобы количество выпускаемых изделий и выручка от их реализации были максимальными, а себестоимость — минимальной.

Список литературы Мастяева И.Н., Горемыкина Г.И., Семенихина О.Н., Методы оптимизации: линейные модели. М.: МЭСИ, 2015. Мастяева И.Н., Горемыкина Г.И., Семенихина О.Н., Исследование операций и методы оптимизации. М.: МЭСИ, 2015. Мастяева И.Н., Горемыкина Г.И., Семенихина О.Н., Методы оптимальных решений. М.: Курс, 2016.