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

Задача многокритериальной оптимизации — это задача с несколькими критериями, которые с разных сторон характеризу­ют различные решения. Чаще всего заранее выделено направле­ние улучшения каждого критерия, например его увеличение. Но одновременное увеличение всех критериев практически всегда не­возможно. Скажем, имея некоторую ограниченную сумму де­нег, нельзя купить побольше и сахара, и муки. Более конкрет­но можно сказать так: «Имея деньги в количестве S при ценах на сахар Рс и на муку Рм, можно купить такое количество сахара Хс и такое количество муки Хм, что Р_СХ_С + Р_МХ_M ≤ S, Х_с ≥ 0, Х_M ≥ 0

На рис. 5.3. показана область АВО, любая точка которой удов­летворяет этому нестрогому неравенству. Все границы включены в область допустимых значений. Нам хотелось иметь одновремен­но шах Х_C и max Х_M но это невозможно.

Поэтому в этой задаче, как и в других многокритериальных задачах, речь ведут не об оптимальных решениях, а об эффектив­ных.

Вспомним: вектор значений показателей X*(X = (Хс, Хм) в на­шем примере) называют эффективным (или оптимальным по Па­рето), если в множестве имеющихся показателей нет другого та­кого, который был бы не хуже X* по всем компонентам и превос­ходил X* хотя бы по одной компоненте. Эффективные решения — это такие решения, которые не мо­гут быть улучшены сразу по всем критериям. Возникает вопрос, как искать решение, как формализовать задачу (ведь, наверняка, потребуется использование ЭВМ), как согласовать противоречивые стремления? Перечислим некоторые возможные способы действий.

Рис. 5.3. Соотношение между объемами покупок

Можно взять сумму критериев, в которую каждый критерий войдет с каким-то сомножителем («весом критерия»). Можно ка­ким-либо другим образом объединить (говорят «свернуть») исход­ные критерии в один. Иногда критерии предварительно упорядо­чивают по важности, а затем последовательно решают несколько оптимизационных задач (число задач равно числу критериев) в порядке убывания важности критериев.

Если после упорядочивания критериев по важности оказыва­ется, что первый критерий К₁ существенно важнее всех осталь­ных, критерий К₂ намного важнее всех критериев, кроме К₁, кри­терий К₃ существенно важнее всех, кроме К₁ и К₂ и т.д., то есте­ственно считать, что i-ое решение (альтернативу) лучше j-гo решения (j-ой альтернативы), когда это i-ое решение лучше j-го по критерию К₁. Если i-ое и j- ое решения эквивалентны по К₁: то предпочтение отдается лучшему по критерию К₂, и т.д. Такое упо­рядочение называется лексикографическим, оно возможно лишь при значительной неравноценности критериев. В приводимой табл. 5.8 дается пример такого упорядочивания пяти альтернатив

A₁,..., A₅ по четырем критериям K₁,,..., К₄. В клетках — значения a_ij для i-ой альтернативы по j-му критерию.

Таблица 5.8 - Результаты многокритериального оценивания

По каждому критерию хотим иметь максимум, К₁ — самый важный, К₄ — самый неважный.

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

Для примера с мукой и сахаром можно было бы искать реше­ние, задавшись дополнительным ограничением снизу на объем закупки, например, сахара:

Тогда получилась бы просто однокритериальная задача:

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

Пример 5.10. Предприимчивая тетя покупает в одном месте муж­ские свитера (в количестве не более 60 штук), в другом — женские (не более 40 штук). С помощью мягкой щетки она делает начес и продает по 2 условные единица за мужские и по 4 единицы за жен­ские. За некоторый единичный интервал времени она может наче­сать не более 80 свитеров. Поскольку тетя хочет удержаться и на рынке мужских свитеров (пусть их индекс М), и на рынке женских свитеров (пусть их индекс Ж), постольку она интересуется не мак­симумом дохода или прибыли, а оценками сразу по нескольким критериям. Пусть закупочные цепы в условных единицах таковы: мужские свитера по 1 ед / шт., женские по 2 ед / шт. Оптимизацион­ная задача тети выглядит так (х_м, х_ж — объемы закупок):

На рис. 5.4 показана допустимая область OABCD, направле­ния благоприятных изменений критериев К₁, К₂, К₃. Отдельно по каждому из критериев решения находятся сразу (по К₁: х_м = 60, К₁ = 120; по K₂ х_ж = 40, К₂ = 160; по К₃ х_м - х_ж = 0, К₃ = 0). Зная значения критериев для однокритериальных задач, ситуацию на рынках и свои финансовые возможности, эта тетя выбирает та­кие пороги: П₁ = 100 (то есть она хочет иметь K₁ ≥П₁ = 100), П₂= 112 (хочет иметь К₂ ≥П₂ = 112) и П₃= 120 (K₃ ≤ П₃ = 120).

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