close

Вход

Забыли?

вход по аккаунту

?

41.Метод Парето решения многокритериальных задач Методические указания

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство образования и науки Российской Федерации
Ярославский государственный университет им. П.Г. Демидова
Кафедра компьютерных сетей
Метод Парето решения
многокритериальных задач
Методические указания
Ярославль 2004
1
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ББК В 181я73
М 54
УДК 002:372.8
Метод Парето решения многокритериальных задач: Метод.
указания / Сост. С.Е. Ануфриенко; Яросл. гос. ун-т. Ярославль, 2004.
24 с.
Методические указания содержат примеры задач, в которых оптимальность решения проверяется по нескольким критериям.
Предназначены для студентов второго курса, изучающих дисциплину «Теория систем и системный анализ» (блок ЕН), специальности 351400 Прикладная информатика (в экономике) факультета информатики и вычислительной техники ЯрГУ очной формы обучения.
Они могут быть полезны для всех, кто интересуется многокритериальной оптимизацией.
Рецензент: кафедра компьютерных сетей Ярославского государственного университета им. П.Г. Демидова.
 Ярославский государственный университет, 2004
 С.Е. Ануфриенко, 2004
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Введение
Линейное программирование является одним из наиболее развитых инструментальных средств в экономике. Успешность работы любого предприятия в значительной степени определяется качеством
комплексного и системно организованного планирования выполняемых операций. Линейное программирование позволяет существенно
повысить эффективность аналитических возможностей управленческого аппарата. Открытие и практическое применение линейного
программирования было оценено мировой общественностью как одно
из величайших достижений в области моделирования управленческих
решений. За это достижение мирового значения американскому ученому Т. Кумпансу и советскому математику-экономисту Л.В. Канторовичу в 1975 г. была присуждена Нобелевская премия по экономике.
Однако при всех безусловных и качественно новых, ранее недоступных возможностей исследований экономики с помощью линейного программирования оно обладает и рядом недостатков. Один из
наиболее важных, часто оказывающий существенное влияние на системный анализ экономических процессов недостаток заключается в
том, что оценка качества управления осуществляется по численному
значению одной целевой функции. На практике же эту оценку часто
приходится осуществлять одновременно по нескольким показателям.
Поясним некоторыми примерами.
В процессе функционирования предприятия ставятся цели: добиться максимально возможной прибыли и выпуска продукции в натуральном или стоимостном выражении, одновременно с этим выдержать диктуемый рынком или заказчиком ассортимент, снизить себестоимость, добиться определенного уровня качества и рентабельности производства, и т.д. Некоторые из этих показателей при их
реализации могут быть противоречивыми. Например, стремление к
максимальному выпуску продукции одновременно ведет и к суммарному росту себестоимости, так как изготовление каждого нового изделия сопряжено с дополнительными затратами. Минимизировать
себестоимость производства имеет смысл только тогда, когда точно
установлен необходимый объем производства. Подобные противоречия могут иметь место и в отношении других частных критериальных
показателей. В целом можно представить себе одну из двух альтернатив: либо при некотором плане производства все принимаемые в рас3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
чет частные критериальные показатели ведут себя в процессе динамики выпуска продукции качественно сходным образом, достигая
одновременно своих максимальных или минимальных значений, либо
такого плана не существует.
Первой альтернативе отвечает по существу однокритериальная
ситуация, когда в модели используется в явном виде основной на содержательном уровне критерий, а остальные игнорируются.
Вторая альтернатива заключается в выборе разумного, с практической точки зрения, компромисса, когда для приемлемого варианта
производства не достигаются потенциально возможные наилучшие
значения отдельных целевых показателей, но каждый из них для этого варианта принимает в той или иной мере близкое к оптимальному
значение.
Метод Парето
На содержательном уровне многокритериальная задача может
оказаться противоречивой, т.е. не содержать решения, но поскольку
подобные задачи встречаются на практике, необходимо разработать
разумные подходы для их решения.
Простейший способ – записать задачу по аналогии с однокритериальной:
f1 ( x) → max, f 2 ( x) → max,, f l ( x) → max
x = ( x1 , x2 ,, xn )
n
∑a
j =1
ij
x j ≤ bi
xj ≥ 0

i = 1, , m;

j = 1,  n 
(1)
(2)
Здесь f1 ( x), f2 ( x),, fl ( x) – желательные критерии оптимальности. Если в реальном критерии имеет место стремление к минимуму:
q s ( x) → min, то взятие обратного знака дает:
f s ( x) = −q s ( x) → max .
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Условия (2) задают допустимую область задачи, х – вектор искомых переменных.
Посмотрим на простых примерах, к чему может привести постановка (1) – (2). Возьмем одномерный случай и изобразим возможные
сочетания для трех критериев, полагая, что все критерии устремлены
к максимуму.
f1 ( x)
f 2 ( x)
A
x
A
x
b) xmax = 0
a ) xmax = A
f 3 ( x)
A
x
c) xmax = ∀x ∈ [0, A]
Рис. 1. Положение точки максимума в зависимости от угла наклона
графика целевой функции
Как видно из рисунка 1, при одном и том же множестве ограничений 0 ≤ x ≤ A оптимальное значение по каждому из трех критериев f1 ( x), f 2 ( x), f 3 ( x) будет разным, и это зависит от угла наклона соответствующих прямых f1 ( x), f 2 ( x), f 3 ( x) . В случае, когда целевая
функция f1 ( x) возрастает (рис. 1a), максимум будет достигаться на
правой границе xmax = A . При убывающей целевой функции f 2 ( x)
(рис. 1b) максимальное значение достигается левой точке xmax = 0 .
Наконец, если целевая функция f 3 ( x) = const , то любое допустимое
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
значение 0 ≤ x ≤ A будет обеспечивать максимум (и одновременно
минимум) функционала f 3 ( x) (рис. 1c).
Следовательно, многокритериальную задачу нужно решать, не
добиваясь максимума или минимума каждого функционала в отдельности, так как эти решения будут давать, скорее всего, противоречивые результаты, а предстоит построить «комплексную» целевую
u ( x) ,
функцию
включающую все частные функционалы
( u ( x) = F ( f1 ( x), f2 ( x),, fl ( x)) ), и для функции u ( x) искать оптимальное
значение хmax. В итоге мы все равно сводим задачу к однокритериальной, хотя на содержательном уровне она будет отражать многокритериальные тенденции.
Многочисленными авторами изучались различные способы выбора функции u ( x) . Мы рассмотрим способ, предложенный Парето.
Его преимущества, во-первых, в том, что он не «портит» структуру
задачи линейного программирования (функционал u ( x) остается линейным); во-вторых, на формальном уровне хорошо отвечает многим
содержательно ясным предпосылкам. Объем вычислений при этом
может существенно возрастать, но качественно решаемые дополнительные задачи являются однотипными. Таким образом, можно сказать, что повышается только механическая трудоемкость решения задачи при неизменном ее качественном уровне.
Рассмотрим задачу, имеющую l критериев оптимальности и допустимую область, задаваемую условиями (2). Поставим задачу линейного программирования с k-й целевой функцией в виде:


j =1

n

ai j x j ≤ bi ; i = 1,, m;
∑
j =1

x j ≥ 0;
j = 1,, n. 


n
f k = ∑ c kj x j → max
(3)
После решения всех l задач вида (3) будем иметь оптимальные
значения функционалов f1 ( x), f2 ( x),, fl ( x) , которые обозначим
f1∗ , f2∗ ,, fl ∗ .
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Поставим следующую однокритериальную задачу максимизации
по Парето:
l
α k fk
αk n k

F = ∑ ∗ = ∑ ∗ ∑ c j x j → max 
k =1 f k
k =1 f k j =1

l
n
a i j x j ≤ bi ;
∑
j
i = 1,, m;
x j ≥ 0;
j = 1,, n.






=1
Числа α k ≥ 0 обладают свойством
(4)
l
α k = 1 и являются весовыми
∑
k
=1
коэффициентами для частных критериев fk . Эти числа, как правило,
задаются экспертами и выражают значимость каждого критерия.
Оптимальное решение задачи (4) при некотором фиксированном
наборе весов α k называется эффективной точкой по Парето. Множество всех эффективных точек при всевозможных допустимых значе-
ниях α k называется множеством Парето.
Рассмотрим несколько примеров.
Задача 1
Для производства двух видов изделий А и В используется токарное, фрезерное и шлифовальное оборудование. Нормы затрат времени для каждого из типов оборудования на одно изделие данного вида
приведены в таблице. В ней же указан общий фонд рабочего времени
каждого из типов оборудования, цена одного изделия и затраты на
его производство. Найти план выпуска изделий, обеспечивающий
максимальную прибыль и минимальные затраты при условии, что
предприятие не может выпускать менее 5 изделий.
Тип
оборудования
Фрезерное
Токарное
Шлифовальное
Цена
Затраты
Затраты времени на обра- Общий фонд полезного рабочеботку одного изделия
го времени оборудования
А
В
10
8
168
5
10
180
6
12
144
14
18
max
7
5
min
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2
Запишем условия задачи линейного программирования.
Пусть x1 и x2 – план выпуска изделий А и В. Допустимая область
описывается неравенствами:
10 x1 + 8 x2 ≤ 168,
5 x + 10 x ≤ 180,
2
 1
6 x1 + 12 x2 ≤ 144,
 x + x ≥ 5,
2
 1
 x1 ≥ 0, x2 ≥ 0.
Целевые функции имеют вид:
f1 = 14 x1 + 18 x2 → max,
q2 = 7 x1 + 5 x2 → min .
Так как второй функционал стремится к минимуму, то умножим
его на –1 и получим:
f2 = −q 2 = −7 x1 − 5 x2 → max .
Задача содержит две переменных, значит, будем искать оптимальное решение графическим способом.
х2
_
20
_
15 B
_
10
_A
5
C
E
|
5
D
|
10
|
15
|
20
|
25
Рис. 2
8
x1
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Найдем оптимальное значение первой целевой функции. Допустимая область для задач 1 и 2 изображена на рисунке 2 – это многоугольник ABCDE.
Уравнения прямых:
(BC) 6 x1 + 12 x2 = 144 ,
(CD) 10 x1 + 8 x2 = 168 ,
(AE) x1 + x2 = 5 .
Условие 5 x1 + 10 x2 ≤ 180 выполнено для всех точек многоугольника ABCDE.
Градиент целевой функции имеет координаты (14, 18).
Максимальное значение достигается в точке C. Вычислим ее координаты:
6 x1 + 12 x2 = 144,

10 x1 + 8 x2 = 168.
 x1 = 12,

 x2 = 6.
∗
Таким образом, f1 = 14 ⋅12 + 18 ⋅ 6 = 276 .
Найдем оптимальное значение второй целевой функции. Ее градиент имеет координаты (-7, -5). Максимальное значение достигается
в точке A (0, 5).
∗
Получаем: f 2 = −25 .
Теперь составим комплексную целевую функцию. Положим
α1 = α , α 2 = 1 − α ( 0 ≤ α ≤ 1 ). Получим:
1−α
⋅ (7 x1 + 5 x2 ) =
25
276
 18α 5 ⋅ (1 − α ) 
 14α 7 ⋅ (1 − α ) 
=
+
+
 ⋅ x2 .
 ⋅ x1 + 
F ( x1 , x2 ) =
 276
α
25
⋅ (14 x1 + 18 x2 ) +

 276

25
Для нахождения оптимального решения вычислим угловой коэффициент прямой F ( x1 , x2 ) = 0 и сравним его с угловыми коэффициентами прямых (BC) и (CD).
9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
a
b
Угловой коэффициент прямой ax1 + bx2 = 0 равен k = − . Значит,
14 ⋅ 25 ⋅ α + 7 ⋅ 276 ⋅ (1 − α )
1936 − 1582 ⋅ α
966 − 791 ⋅ α
276 ⋅ 25
k=−
=−
=−
18 ⋅ 25 ⋅ α + 5 ⋅ 276 ⋅ (1 − α )
1380 − 930 ⋅ α
690 − 465 ⋅ α .
276 ⋅ 25
Угловые коэффициенты прямых (BC) и (CD) равны соответственно
1
2
k1 = − , k2 = −
10
.
8
Если k < k1 , то оптимальное решение достигается в точке B, если k1 < k < k2 – в точке C, если k > k2 – в точке D. В случае, когда
k = k1 , оптимальной является любая точка отрезка [BC], если же
k = k2 , то любая точка отрезка [CD].
Проверим условие k < k1 : −
Получим: α >
966 − 791 ⋅ α 1
< .
690 − 465 ⋅ α 2
1242
. Учитывая, что
1117
α ≤ 1 , заключаем, что точка B
оптимальной быть не может.
Пусть k1 < k < k2 . В этом случае имеем: −
Или α >
414
.
839
Очевидно, что при 0 ≤ α <
в точке D.
Таким образом, получили:
при 0 ≤ α <
при
966 − 791 ⋅ α 10
< .
690 − 465 ⋅ α
8
414
839
414
оптимальное решение достигается
839
оптимальное решение: x1 = 16,8; x2 = 0; Fmax = 13524 − 11074α ;
2875
2622 − 2047α
414
< α ≤ 1 оптимальное решение: x1 = 12; x2 = 6; Fmax =
;
575
839
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
414
оптимальное решение достигается в любой точке отрезка
839
2352
≈ 2,8 .
[CD], Fmax =
839
при α =
1
оптимальное
2
9591
=
≈ 2,78 .
3450
В частности, при α1 = α 2 =
максимальное значение Fmax
решение: x1 = 12; x2 = 6; а
Из приведенных формул видно, что в случае, когда второй критерий считается более значимым, оптимальный план предусматривает
выпуск только продукции вида А, так как суммарные затраты на
производство при этом минимальны. Если же более значимым является первый критерий, то предприятие должно выпускать изделия
обоих видов.
Задача 2
Добавим к условиям задачи 1 еще одно требование: нужно выпускать как можно больше новых товаров. Сопоставим каждому товару коэффициент «новизны». Для изделий вида А этот коэффициент
равен 1 (устаревший товар), для изделий вида В – 3 (новый товар).
Введем целевую функцию f3 ( x1 , x2 ) = x1 + 3x2 → max .
Найдем оптимальное значение третьей целевой функции. Ее градиент имеет координаты (1, 3). Максимальное значение достигается в
∗
точке B (0, 12). Получаем: f3 = 36 .
Составим комплексную целевую функцию. Положим α 3 = 1 − α1 − α 2
( α1 ≥ 0, α 2 ≥ 0, α1 + α 2 ≤ 1 ). Получим:
1 − α1 − α 2
⋅ ( x1 + 3 x2 ) =
276
25
36
 14α1 7α 2 1 − α1 − α 2 
 18α1 5α 2 3 ⋅ (1 − α1 − α 2 ) 
=
+
+
+
+
 ⋅ x1 + 
 ⋅ x2 .
F ( x1 , x2 ) =
 276
α1
25
⋅ (14 x1 + 18 x2 ) +
36

α2
⋅ (7 x1 + 5 x2 ) +
 276
25
36

Вычислим угловой коэффициент прямой F ( x1 , x2 ) = 0 :
14 ⋅ 25 ⋅ 36 ⋅ α1 + 7 ⋅ 276 ⋅ 36 ⋅ α 2 + 276 ⋅ 25 ⋅ (1 − α1 − α 2 )
575 + 475 ⋅ α 1 + 5221 ⋅ α 2
276 ⋅ 25 ⋅ 36
=−
k=−
18 ⋅ 25 ⋅ 36 ⋅ α1 + 5 ⋅ 276 ⋅ 36 ⋅ α 2 + 276 ⋅ 25 ⋅ 3 ⋅ (1 − α 1 − α 2 )
1725 − 375 ⋅ α 1 + 2415 ⋅ α 2
276 ⋅ 25 ⋅ 36
11
.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сравним значение k с угловыми коэффициентами прямых (BC) и
(CD).
1
Пусть k < . Имеем:
2
575 + 475 ⋅ α 1 + 5221 ⋅ α 2
1
< .
1725 − 375 ⋅ α 1 + 2415 ⋅ α 2 2
Отсюда получаем: 1325 ⋅ α 1 + 8027 ⋅ α 2 < 575 . При этом условии
оптимальной является точка B.
1
5
k
<
<
Пусть теперь
. Достаточно рассмотреть неравенство
2
4
575 + 475 ⋅ α 1 + 5221 ⋅ α 2
5
< . Получим: 25 ⋅ α1 + 8809 ⋅ α 2 < 6325 .
1725 − 375 ⋅ α 1 + 2415 ⋅ α 2 4
Таким образом, оптимальное значение будет достигаться в точке
C при выполнении следующих условий:
1325 ⋅ α 1 + 8027 ⋅ α 2 > 575,

25 ⋅ α 1 + 8809 ⋅ α 2 < 6325,
α + α ≤ 1.
2
 1
5
4
В случае, когда k > , оптимальной является точка D, при этом
должны быть выполнены условия:
25 ⋅ α 1 + 8809 ⋅ α 2 > 6325,

α 1 + α 2 ≤ 1.
Результаты удобно изобразить на графике.
На рисунке 3 выделены области в плоскости параметров ( α1 ,α 2 ) и
указаны точки, в которых функция F ( x1 , x2 ) достигает максимального
значения.
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
α2
1 −K
D
N
L
C
M
B
O
R
|P
1
α1
Рис. 3
Уравнения прямых:
(MR) 1325 ⋅α1 + 8027 ⋅α 2 = 575 ,
(NL) 25 ⋅α1 + 8809 ⋅α 2 = 6325 ,
(KP) α1 + α 2 = 1 .
Если в плоскости параметров точка с координатами ( α1 ,α 2 ) лежит
внутри треугольника OMR, то оптимальное решение:
x1 = 0; x2 = 12 (точка B), Fmax =
1725 − 375α1 + 2415α 2
1725
.
Внутри пятиугольника MNLPR оптимальное решение:
2875 + 575α1 + 12857α 2
x1 = 12; x2 = 6 (точка C), Fmax =
.
3450
Внутри треугольника NKL оптимальное решение:
x1 = 16,8; x2 = 0 (точка D), Fmax =
4025 + 3325α 1 + 36547α 2
8625
.
Оптимальный план предусматривает выпуск только изделий вида
В в том случае, когда значимость третьего критерия близка к единице. Если очень высока значимость второго критерия ( α 2 > 0,72 ), то
следует выпускать только изделия вида А. Во всех остальных случаях
оптимальным является выпуск изделий обоих видов.
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Целевые функции в задачах 1 и 2 зависели от двух переменных,
поэтому их удобно решать графическим способом. На следующем
примере мы рассмотрим, как применять метод Парето к задачам
большей размерности.
Задача 3
Для изготовления различных изделий А, В и С предприятие использует три вида сырья. Нормы расхода сырья на производство одного изделия каждого вида, цена изделий, а также запасы сырья приведены в таблице. Сопоставим каждому изделию коэффициент «новизны». Требуется составить план производства изделий, при
котором стоимость всей произведенной продукции максимальна, но
при этом предприятие должно выпускать как можно больше новых
товаров.
Вид сырья
I
II
III
Цена одного изделия
Коэффициент
«новизны»
Нормы затрат сырья на одно изделие
А
В
С
18
15
12
6
4
8
5
3
3
9
10
16
4
2
1
Общее количество сырья
360
192
180
Max
Max
Составим математическую модель задачи.
Пусть x1 , x2 , x3 – искомый выпуск изделий вида А, В, С соответственно, тогда ограничения, задающие допустимую область задачи,
примут вид:
18 x1 + 15 x2 + 12 x3 ≤ 360,
6 x + 4 x + 8 x ≤ 192,
 1
2
3

5 x1 + 3 x2 + 3 x3 ≤ 180,
 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
Условия, записанные в последней строке, вытекают из экономического смысла: мы не можем выпускать отрицательное число изделий.
Допустимым множеством данной задачи является непустой ограниченный многогранник. Он содержит точку x1 = x2 = x3 = 0 , при этом
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
выполнены неравенства: 0 ≤ x1 ≤ 20 , 0 ≤ x2 ≤ 24 , 0 ≤ x3 ≤ 24 . Следовательно, любая линейная функция достигает на данном множестве
своего максимального и минимального значения.
Целевые функции задачи имеют вид:
f1 = 9 x1 + 10 x2 + 16 x3 → max ,
f2 = 4 x1 + 2 x2 + x3 → max .
Решать задачу будем симплекс-методом. Для этого запишем ее в
канонической форме. Введем неотрицательные переменные x4 , x5 , x6 и
перейдем от ограничений-неравенств к ограничениям-равенствам.
Дополнительные переменные по экономическому смыслу означают
не используемое при данном плане производства количество сырья
того или иного вида. Система ограничений примет вид:
18 x1 + 15 x2 + 12 x3 + x4 = 360,
6 x + 4 x + 8 x + x = 192,
 1
2
3
5

5 x1 + 3 x2 + 3 x3 + x6 = 180,
 x j ≥ 0, j = 1,,6.

Систему равенств запишем в векторной форме:
x1 A1 + x2 A2 + x3 A3 + x4 A4 + x5 A5 + x6 A6 = b,
12 
15 
 360 
 0
 0
1 
18 
 
 


 
 
 
 
A
8
,
=
A
4
,
=
0
,
A
1
,
A
0
,
b
=
192
A
=
=
=
6
,
A
=





.






3


2
4
5
6
где 1
3 
3 
180 
 0
1 
 0
5 
 
 


 
 
 
 
Найдем максимум первой целевой функции f1 = 9 x1 + 10 x2 + 16 x3 .
Единичные векторы A4 , A5 , A6 образуют базис в трехмерном пространстве, поэтому можно сразу записать опорный план:
x1 = x2 = x3 = 0, x4 = 360, x5 = 192, x6 = 180.
Составляем симплексную таблицу для первой итерации. Над векторами Aj ( j = 1,,6) запишем коэффициенты, с которыми переменные x j входят в целевую функцию. В столбцах, соответствующих
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
каждому вектору (включая вектор b), запишем их коэффициенты. В
столбец C баз запишем коэффициенты, с которыми входят в целевую
функцию x j , соответствующие векторам, образующим базис (в данном случае все они равны нулю). В последней строке будем записывать оценки ∆ j для каждого вектора Aj , а в столбце, соответствующем вектору b, – текущее значение целевой функции.
Базис
A4
A5
A6
∆j
Cбаз
0
0
0
b
360
192
180
0
9
10
16
0
0
0
A1
A2
A3
A4
A5
A6
18
6
5
-9
15
4
3
-10
12
8
3
-16
1
0
0
0
0
1
0
0
0
0
1
0
Оценка для каждого вектора – это сумма произведений координат вектора на соответствующий базисный коэффициент минус коэффициент, стоящий над вектором. Текущее значение функции –
сумма произведений координат вектора b на соответствующие базисные коэффициенты. Пользуясь этим правилом, найдем:
∆1 = 18 ⋅ 0 + 6 ⋅ 0 + 5 ⋅ 0 − 9 = −9 ,
∆ 2 = 15 ⋅ 0 + 4 ⋅ 0 + 3 ⋅ 0 − 10 = −10 ,
∆ 3 = 12 ⋅ 0 + 8 ⋅ 0 + 3 ⋅ 0 − 16 = −16 ,
∆ 4 = ∆ 5 = ∆ 6 = 0 (для базисных векторов ∆ j = 0 ),
f1 = 360 ⋅ 0 + 192 ⋅ 0 + 180 ⋅ 0 = 0 .
Среди оценок есть отрицательные, а в каждом столбце с отрицательной оценкой есть положительные элементы. Следовательно,
нужно переходить к новому плану. Найдем среди оценок минимальную – это ∆ 3 . Это значит, что вектор A3 будет включен в базис.
Найдем отношения компонент вектора b к соответствующим компонентам вектора A3 (если последние положительны) и выберем среди
этих отношений минимальное:
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 360 192 180  192
,
,
min
=
.
3
8
8
12


Это значит, что вектор A5 будет исключен из базиса. Перейдем к
новому базису A4 , A3 , A6 . Для этого вычислим коэффициенты всех
векторов в новом базисе. Введем обозначения. Пусть
a i j ( i = 1,2,3; j = 1,,6 ) – компоненты векторов Aj , a i 0 – компоненты
вектора b в старом базисе. В новом базисе компоненты этих векторов
обозначим a i/ j ( i = 1,2,3; j = 0,,6 ). Тогда справедливы формулы:
a 2/ j =
a2 j
a2 j
/
=
−
a i 3 ( i = 1,3; j = 0,,6 ).
a
a
j
=
0
,

,
6
), i j
ij
a 23 (
a 23
Составим таблицу для второй итерации:
Базис
Cбаз
0
16
0
A4
A3
A6
∆j
b
72
24
108
384
9
10
16
0
0
0
A1
A2
A3
A4
A5
A6
9
¾
11/4
3
9
½
3/2
-2
0
1
0
0
1
0
0
0
-3/2
1/8
-3/8
2
0
0
1
0
Минимальная оценка ∆ 2 < 0 . Координаты вектора A2 положи 72 24 108  72


тельны. Найдем min 9 , 1 , 3  = 9 . Значит, вектор A4 следует ис2 2

ключить из базиса и ввести в него вектор A2 .
Вычислим коэффициенты всех векторов в базисе A2 , A3 , A6 :
a1/ j =
a1 j
a1 j
/
( j = 0,,6 ), a i j = a i j − a i 2 ( i = 2,3; j = 0,,6 ).
a1 2
a1 2
Составим таблицу для третьей итерации:
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Базис
A2
A3
A6
Cбаз
10
16
0
∆j
b
8
20
96
400
9
10
16
0
0
0
A1
A2
A3
A4
A5
A6
1
¼
5/4
5
1
0
0
0
0
1
0
0
1/9
-1/18
-1/6
1/9
-1/6
5/24
-1/8
5/3
0
0
1
0
После третьей итерации все ∆ j ≥ 0 . Это значит, что мы нашли
∗
оптимальное решение: x1 = 0, x2 = 8, x3 = 20, f1 = 400 . Значение дополнительных переменных x4 , x5 , x6 несущественно.
Найдем максимальное значение второй целевой функции
f2 = 4 x1 + 2 x2 + x3 .
Опорное
решение
нам
известно:
x1 = x2 = x3 = 0, x4 = 360, x5 = 192, x6 = 180.
Составим таблицу для первой итерации:
Базис
A4
A5
A6
∆j
Cбаз
0
0
0
b
360
192
180
0
4
2
1
0
0
0
A1
A2
A3
A4
A5
A6
18
6
5
-4
15
4
3
-2
12
8
3
-1
1
0
0
0
0
1
0
0
0
0
1
0
Минимальная оценка ∆1 < 0 . Координаты вектора
A1 положи-

тельны. Найдем min
360 192 180  360
,
,
=
. Значит, надо исключить из
5  18
 18 6
базиса вектор A4 и ввести в него вектор A1 .
Вычислим коэффициенты всех векторов в базисе A1 , A5 , A6 :
a1/ j =
a1 j
a1 j
/
( j = 0,,6 ); a i j = a i j − a a i 1 ( i = 2,3; j = 0,,6 ).
a11
11
Составим таблицу для второй итерации:
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Базис
Cбаз
4
0
0
A1
A5
A6
∆j
b
20
72
80
80
4
2
1
0
0
0
A1
A2
A3
A4
A5
A6
1
0
0
0
5/6
-1
-7/6
2/3
2/3
4
-1/3
5/3
1/18
-1/3
-5/18
2/9
0
1
0
0
0
0
1
0
Все ∆ j ≥ 0 , поэтому оптимальное решение имеет вид:
x1 = 20, x2 = 0, x3 = 0, f2∗ = 80 .
Составим комплексную целевую функцию:
F=
α1
400
(9 x1 + 10 x2 + 16 x3 ) +
α2
80
(4 x1 + 2 x2 + x3 ) → max .
Положим α1 = α , α 2 = 1 − α ( 0 ≤ α ≤ 1 ). Имеем:
F=
=
α
400
(9 x1 + 10 x2 + 16 x3 ) +
1−α
(4 x1 + 2 x2 + x3 ) =
80
x 5 + 11α
20 − 11α
x1 + 2 +
x3 → max .
400
40
400
Опорное решение имеет вид: x1 = x2 = x3 = 0, x4 = 360, x5 = 192, x6 = 180.
Составим таблицу для первой итерации:
Базис
A4
A5
A6
∆j
Cбаз
0
0
0
b
360
192
180
0
20 − 11α
400
1
40
5 + 11α
400
0
0
0
A1
A2
A3
A4
A5
A6
18
6
5
15
4
3
12
8
3
1
0
0
0
0
1
0
0
0
0
1
0
11α − 20
400
-
1
40
19
-
5 + 11α
400
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
15
наименьшей является ∆1 < 0 . Коэффициенты вектора
22
При α ≤
A1 . Найдем
 360 192 180  360
,
,
min
=
. Значит, надо исключить из базиса
5  18
 18 6
вектор A4 и ввести в него вектор A1 .
Вычислим коэффициенты всех векторов в базисе A1 , A5 , A6 :
a1/ j =
a1 j
a1 j
/
a i 1 ( i = 2,3; j = 0,,6 ).
j = 0,,6 ); a i j = a i j −
(
a11
a11
Составим таблицу для второй итерации:
Базис
Cбаз
A1
20 − 11α
400
A5
A6
0
0
20 − 11α
400
1
40
5 + 11α
400
0
0
0
A1
A2
A3
A4
A5
A6
20
1
5/6
2/3
1/18
0
0
72
80
0
0
0
-1
-7/6
4
-1/3
-1/3
-5/18
8 − 11α
480
5 − 11α
240
20 − 11α
7200
1
0
0
0
1
0
b
20 − 11α
20
∆j
При 0 ≤ α ≤
вид:
5
все ∆ j ≥ 0 , поэтому оптимальное решение имеет
11
x1 = 20, x2 = 0, x3 = 0, Fmax =
При α >
нат вектора
20 − α
.
20
5
наименьшей оценкой является ∆ 3 < 0 . Среди коорди11
A3
есть положительные числа. Найдем
 20 72  72
min
,  =
.
2
4
4
 3

Значит, надо исключить из базиса вектор A5 и ввести в него вектор
A3 . Вычислим коэффициенты всех векторов в базисе A1 , A3 , A6 :
a
a
a 2/ j = 2 j ( j = 0,,6 ); a i/ j = a i j − 2 j a i 3 ( i = 1,3; j = 0,,6 ).
a 23
a 23
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Составим таблицу для третьей итерации:
Базис
Cбаз
A1
20 − 11α
400
20 − 11α
400
1
40
5 + 11α
400
0
0
0
A1
A2
A3
A4
A5
A6
8
1
1
0
1/9
-1/6
0
b
A3
5 + 11α
400
18
0
-1/4
1
-1/12
1 /4
0
A6
0
86
0
0
-5/4
0
0
-11/36
1/12
65 − 77α
14400
11α − 5
960
1
0
25 + 11α
40
∆j
При
вид:
5
7
≤α ≤
все
11
11
7 − 11α
320
∆ j ≥ 0 , поэтому оптимальное решение имеет
x1 = 8, x2 = 0, x3 = 18, Fmax =
25 + 11α
.
40
7
При α >
наименьшей оценкой является ∆ 2 < 0 . Одна коорди11
ната вектора A2 положительна, поэтому из базиса исключаем вектор
A1 и вводим в него вектор
ров в базисе A2 , A3 , A6 :
a1/ j =
A2 . Вычислим коэффициенты всех векто-
a1 j
a1 j
/
( j = 0,,6 ), a i j = a i j − a i 2 ( i = 2,3; j = 0,,6 ).
a1 2
a1 2
Составим таблицу для четвертой итерации:
Базис
A2
Cбаз
1
40
20 − 11α
400
1
40
5 + 11α
400
0
0
0
A1
A2
A3
A4
A5
A6
8
1
1
0
1/9
-1/6
0
b
A3
5 + 11α
400
20
1 /4
0
1
-1/18
5/24
0
A6
0
96
5/4
-1/8
11α − 7
320
0
0
-1/6
9 + 11α
20
0
0
15 − 11α
7200
11α − 3
1920
1
0
∆j
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
При
вид:
7
≤ α ≤ 1 все ∆ j ≥ 0 , поэтому оптимальное решение имеет
11
x1 = 0, x2 = 8, x3 = 20, Fmax =
9 + 11α
.
20
Подведем итоги.
При 0 ≤ α ≤
5
оптимальное решение имеет вид:
11
x1 = 20, x2 = 0, x3 = 0, Fmax =
20 − α
,
20
т.е. в случае, когда значимость второго критерия достаточно велика,
оптимальный план предусматривает выпуск только изделий вида А.
При
5
7
≤α ≤
оптимальное решение имеет вид:
11
11
x1 = 8, x2 = 0, x3 = 18, Fmax =
25 + 11α
40
.
Здесь значимость критериев примерно одинакова. В этом случае
предприятие должно выпускать продукцию видов А и С.
7
≤ α ≤ 1 оптимальное решение имеет вид:
При
11
x1 = 0, x2 = 8, x3 = 20, Fmax =
9 + 11α
.
20
В случае, когда велика значимость первого критерия, предприятие должно выпускать продукцию видов В и С.
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Заключение
В заключение отметим, что в случае, когда все коэффициенты
комплексной целевой функции положительны, множество Парето обладает свойством достижения компромиссов. Вот в каком смысле это
можно понимать. Пусть при некотором фиксированном наборе весовых коэффициентов α k эффективными точками являются
x0 = ( x10 ,, xn0 ) и x∗ = ( x1∗ ,, xn∗ ) , пусть существует номер i, такой что
xi0 > xi∗ , тогда существует номер j, для которого x0j < x∗j . Это свойство можно охарактеризовать фразой «если хочешь выиграть в одном –
будь готов уступить в другом». Тот, кто хочет выгадать во всем, ничем не поступаясь, в условиях равного партнерства ничего не добьется.
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Учебное издание
Метод Парето решения
многокритериальных задач
Составитель: Ануфриенко Сергей Евгеньевич
Редактор, корректор А.А. Антонова
Компьютерная верстка И.Н. Ивановой
Подписано в печать 17.06.2004 г. Формат 60×84/16. Бумага тип.
Усл. печ. л. 1,39. Уч.-изд. л. 1,0. Тираж 80 экз. Заказ
.
Оригинал-макет подготовлен
редакционно-издательским отделом ЯрГУ.
Отпечатано на ризографе.
Ярославский государственный университет.
150000 Ярославль, ул. Советская, 14.
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Метод Парето решения
многокритериальных задач
26
Документ
Категория
Без категории
Просмотров
98
Размер файла
320 Кб
Теги
решение, указания, метод, методические, парето, задачи, многокритериальной
1/--страниц
Пожаловаться на содержимое документа