Министерство образования и науки Российской Федерации
Ярославский государственный университет им. П.Г. Демидова
Кафедра компьютерных сетей
Метод Парето решения
многокритериальных задач
Методические указания
Ярославль 2004
1
Стр.1
ББК В 181я73
М 54
УДК 002:372.8
Метод Парето решения многокритериальных задач: Метод.
указания / Сост. С.Е. Ануфриенко; Яросл. гос. ун-т. Ярославль, 2004.
24 с.
Методические указания содержат примеры задач, в которых оптимальность
решения проверяется по нескольким критериям.
Предназначены для студентов второго курса, изучающих дисциплину
«Теория систем и системный анализ» (блок ЕН), специальности
351400 Прикладная информатика (в экономике) факультета информатики
и вычислительной техники ЯрГУ очной формы обучения.
Они могут быть полезны для всех, кто интересуется многокритериальной
оптимизацией.
Рецензент: кафедра компьютерных сетей Ярославского государственного
университета им. П.Г. Демидова.
© Ярославский государственный университет, 2004
© С.Е. Ануфриенко, 2004
2
Стр.2
Введение
Линейное программирование является одним из наиболее развитых
инструментальных средств в экономике. Успешность работы любого
предприятия в значительной степени определяется качеством
комплексного и системно организованного планирования выполняемых
операций. Линейное программирование позволяет существенно
повысить эффективность аналитических возможностей управленческого
аппарата. Открытие и практическое применение линейного
программирования было оценено мировой общественностью как одно
из величайших достижений в области моделирования управленческих
решений. За это достижение мирового значения американскому ученому
Т. Кумпансу и советскому математику-экономисту Л.В. Канторовичу
в 1975 г. была присуждена Нобелевская премия по экономике.
Однако при всех безусловных и качественно новых, ранее недоступных
возможностей исследований экономики с помощью линейного
программирования оно обладает и рядом недостатков. Один из
наиболее важных, часто оказывающий существенное влияние на системный
анализ экономических процессов недостаток заключается в
том, что оценка качества управления осуществляется по численному
значению одной целевой функции. На практике же эту оценку часто
приходится осуществлять одновременно по нескольким показателям.
Поясним некоторыми примерами.
В процессе функционирования предприятия ставятся цели: добиться
максимально возможной прибыли и выпуска продукции в натуральном
или стоимостном выражении, одновременно с этим выдержать
диктуемый рынком или заказчиком ассортимент, снизить себестоимость,
добиться определенного уровня качества и рентабельности
производства, и т.д. Некоторые из этих показателей при их
реализации могут быть противоречивыми. Например, стремление к
максимальному выпуску продукции одновременно ведет и к суммарному
росту себестоимости, так как изготовление каждого нового изделия
сопряжено с дополнительными затратами. Минимизировать
себестоимость производства имеет смысл только тогда, когда точно
установлен необходимый объем производства. Подобные противоречия
могут иметь место и в отношении других частных критериальных
показателей. В целом можно представить себе одну из двух альтернатив:
либо при некотором плане производства все принимаемые в рас3
Стр.3
чет частные критериальные показатели ведут себя в процессе динамики
выпуска продукции качественно сходным образом, достигая
одновременно своих максимальных или минимальных значений, либо
такого плана не существует.
Первой альтернативе отвечает по существу однокритериальная
ситуация, когда в модели используется в явном виде основной на содержательном
уровне критерий, а остальные игнорируются.
Вторая альтернатива заключается в выборе разумного, с практической
точки зрения, компромисса, когда для приемлемого варианта
производства не достигаются потенциально возможные наилучшие
значения отдельных целевых показателей, но каждый из них для этого
варианта принимает в той или иной мере близкое к оптимальному
значение.
Метод Парето
На содержательном уровне многокритериальная задача может
оказаться противоречивой, т.е. не содержать решения, но поскольку
подобные задачи встречаются на практике, необходимо разработать
разумные подходы для их решения.
Простейший способ – записать задачу по аналогии с однокритериальной:
f1
x →
∑ ≤ i
j=1
n
x ≥ 0
j
Здесь
a x b i =1,
j =1,
i j
j
, ( )
,m;
n
x = ( ,1x x ,, xn )
( ) max,
2
(2)
1( ), 2 ( ), – желательные критерии оптимальности.
Если в реальном критерии имеет место стремление к минимуму:
( ) min,→
( ) = − →
то взятие обратного знака дает:
( ) max .
4
f x →( )
2
m , ( ) max
ax, f x →
l
(1)
f
x
f
x
f
l
x
qx
s
qx
s
fx
s
Стр.4
Условия (2) задают допустимую область задачи, х – вектор искомых
переменных.
Посмотрим на простых примерах, к чему может привести постановка
(1) – (2). Возьмем одномерный случай и изобразим возможные
сочетания для трех критериев, полагая, что все критерии устремлены
к максимуму.
f1( )x
f2 ( )x
A x
a x =max)
A
f3( )x
b) max =x
A x
0
c x) max =∀ ∈[0, A]
A x
x
Рис. 1. Положение точки максимума в зависимости от угла наклона
графика целевой функции
Как видно из рисунка 1, при одном и том же множестве ограничений
0 ≤ x A≤ оптимальное значение по каждому из трех критериев
f x f x f x будет разным, и это зависит от угла наклона со1(
),
2 ( ),
3( )
ответствующих прямых f x f x f x . В случае, когда целевая
функция f1( )x возрастает (рис. 1a), максимум будет достигаться на
1( ),
правой границе x =max
2 ( ),
3( )
A. При убывающей целевой функции f2 ( )x
Наконец, если целевая функция f x const , то любое допустимое
5
(рис. 1b) максимальное значение достигается левой точке xmax 0= .
3( ) =
Стр.5
значение 0 ≤ x A≤ будет обеспечивать максимум (и одновременно
минимум) функционала f3( )x (рис. 1c).
Следовательно, многокритериальную задачу нужно решать, не
(
добиваясь максимума или минимума каждого функционала в отдельности,
так как эти решения будут давать, скорее всего, противоречивые
результаты, а предстоит построить «комплексную» целевую
функцию
( ) =
( ( ),
1
( ) , включающую все частные функционалы
( ) искать оптимальное
2 ( ),, ( )) ), и для функции
значение хmax. В итоге мы все равно сводим задачу к однокритериальной,
хотя на содержательном уровне она будет отражать многокритериальные
тенденции.
Многочисленными авторами изучались различные способы вы(
) . Мы рассмотрим способ, предложенный Парето.
бора функции
Его преимущества, во-первых, в том, что он не «портит» структуру
задачи линейного программирования (функционал
( ) остается линейным);
во-вторых, на формальном уровне хорошо отвечает многим
содержательно ясным предпосылкам. Объем вычислений при этом
может существенно возрастать, но качественно решаемые дополнительные
задачи являются однотипными. Таким образом, можно сказать,
что повышается только механическая трудоемкость решения задачи
при неизменном ее качественном уровне.
Рассмотрим задачу, имеющую l критериев оптимальности и допустимую
область, задаваемую условиями (2). Поставим задачу линейного
программирования с k-й целевой функцией в виде:
f =∑
j=1
n
k
∑
n
j=1
x ≥ 0;
j
j =1,
i j
a x b i
c x
k
j
j ≤ i ;
j →max
=1,
,m;
,n.
значения функционалов
∗
1 , 2 .
∗
,
,
∗
6
После решения всех l задач вида (3) будем иметь оптимальные
1( ), 2 ( ), , которые обозначим
, ( )
(3)
ux
ux
ux
ux
fx
l
Ffx
u
x
fx
l
fx
f
x
f
x
fl
f
f
Стр.6