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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



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

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

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

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

1. Разработка концепции оптимальности.

2. Доказательство существования решения, оптимального в соответствующем смысле.

3. Разработка методов нахождения оптимального решения.

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

, при (1.5)

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

Например, выбирая работу, человек, как правило, руководствуется несколькими критериями. Допустим, кому-то хочется, чтобы одновременно выполнялись такие условия:

- заработная плата была как можно выше;

- условия работы были как можно комфортнее;

- место работы было как можно ближе к дому.

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

Еще один пример – выбор инвестиционного решения, когда хочется получить максимальный доход (или доходность) при наименьшем риске [51].

Примеры многокритериальности в экономике

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

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

1. Планирование производства:
– mах – суммарный чистый доход, минимальный чистый доход за любой период;
– min – число невыполненных заказов, сверхурочное время, запасы готовой продукции.

2. Выбор портфеля ценных бумаг:
– mах – доход, дивиденды;
– min – риск, отклонения от желаемого уровня разнообразия бумаг.

3. Составление сметы капиталовложений:
– mах – наличие средств, инвестиции в проекты, связанные с охраной окружающей среды, инвестиция в проекты в заданном регионе, инвестиции в проекты по заданной товарной специализации;

– min – спрос на капитальные вложения, ежегодные эксплуатационные расходы.

4. Управление лесным хозяйством:
– max – устойчивый урожай древесины, человеко-дни отдыха в лесу, человеко-дни охоты в лесу, ареал распространения диких животных, число месяцев выпаса домашних животных;
– min – превышения бюджета.

5. Управление попусками водохранилищ:
– max – выгоды от рекреации на водохранилище № 1, выгоды от зарегулирования стока ниже водохранилища № 1, количество энергии, вырабатываемой в бассейне реки, выгоды от рекреации на водохранилище № 2, прибыль от орошения земель ниже водохранилища № 2;

– min – недопоставки воды на коммунальные нужды в бассейне реки.

6. Формирование ревизионной службы в фирме:
– max – доход, время, отведенное на профессиональный рост
– min – рост численности персонала службы, уменьшение численности персонала службы, избыточные сверхурочные, недоиспользование квалификации кадров;

7. Транспортировка:
– max – производство по заданной технологии;

– min – стоимость, среднее время доставки грузов приоритетным клиентам, расход топлива.

Конечно, решения, которое одновременно удовлетворяло бы всем противоречивым требованиям, как правило, не существует. Но математика может помочь и при решении таких задач. Помощь эта состоит не в нахождении несуществующего решения, одновременно обращающего все критерии в максимум, а в отбрасывании заведомо плохих решений [28,37,51].

Оптимизация по Парето

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

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

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

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

Проиллюстрируем это на примере, где нужно выбрать стратегию развития предприятия, критерии - ожидаемая прибыль в год (в смысле мат. ожидания из теории вероятностей), надёжность стратегии (вероятность того, что будет приемлемая для нас прибыль, хоть сколько-нибудь солидный доход) [37]. Допустим, у нас есть 5 стратегий:

Рис. 1.2. График оптимального плана развития предприятий

Стратегия 2 в среднем даёт больше прибыли, чем стратегия 1, при той же надёжности. Стало быть, стратегия 1 не может быть лучшей. Стратегия 3 по ожидаемой прибыли равноценна стратегии 2, но надёжнее. Стало быть, стратегия 2 тоже невыгодна. Стратегия 3 прибыльнее стратегии 4 при той же надёжность, то есть стратегия 4 тоже неоправданно. Остаются только стратегии 3 и 5. По одному критерию превосходит одна, по другому - другая.

Операции, оптимальные по Парето, не обязательно являются «самыми лучшими» - эти операции не являются худшими. Чтобы выбрать конкретное решение из Парето-оптимального множества, нужны дополнительные данные [21]. Выделение множества Парето ещё не даёт ответа на вопрос, какое решение оптимальное, но оно значительно упрощает применение алгоритмов, работающих с дополнительной информацией, поскольку сужает множество возможных вариантов [37,51].

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

 

 



Поделиться:


Последнее изменение этой страницы: 2017-02-21; просмотров: 256; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.224.52.210 (0.012 с.)