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

1. Постановка задачи. Множество Парето.

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

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

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

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

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

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

3. Метод свертывания ─ ЛПР сводит многокритериальную задачу к задаче с одним критерием посредством суммирования произведений имеющихся критериев на «весовые» коэффициенты (коэффициенты важности критериев).

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

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

Определение. Множество граничных точек области M, перемещение которых по границе области уменьшает одну из координат при одновременном увеличении другой координаты, и правее и выше нет внутренних точек области M, называется множеством (границей) Парето (В. Парето − итальянский экономист, 1848 − 1923 гг.).

На рис. 4.1 указаны границы Парето жирными линиями для двух простейших областей:

Границу Парето для множества M из пространства можно определить как множество точек , обладающих свойством: если выполняются одновременно неравенства и , то

. При n=2 это определение равносильно предыдущему определению.

Границу Парето можно определить и для произвольного ограниченного точечного множества M на плоскости как множество точек множества M, для которых нет точек правее и выше во множестве M.

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

Выделение границы Парето отбросит неинтересные варианты и облегчит окончательный выбор.