Eng | Rus | Ukr | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Исследование операций
|
24.12.2008
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2.8. многокритериальные ЗАДАЧИ
|
|
, (2.8.10)
, (2.8.11)
где (2.8.12)
(2.8.12)
(2.8.13)
Рассмотрим пример.
Пример 2.11.
максимизировать f1(x) = x1 + 4x2 (1)
минимизировать f2(x) = 3x1 - x2 (2)
при ограничениях
Допустимое множество решений задачи R(x) представлено на рис 2.5. в виде многоугольника ABCDE.
Нетрудно получить графически оптимальное решение этой задачи по критерию f1(x). Оно находится в точке С( x1 = 6; x2 = 7 ).
Ему соответствует f1 = f( x1 = 6; x2 = 7 ) = 34.
Минимальное значение будет в точке E(x1 = 3; x2 = 0,5), f1min = 5.
По второму критерию f2(x) оптимальное решение будет в точке B(1,4) ему соответствует , а наихудшее значение критерия f2(x) - в точке D(5,2): . Отрезок BC представляет собой эффективный план.
Рассмотрим случай, когда критерии равноценны, то есть , и будем искать компромиссное решение, обеспечивающее минимальные одинаковые относительные потери. Функции относительных потерь равны
, (3)
.
Запишем эквивалентную задачу ЛП согласно (2.8.7) - (2.8.10):
минимизировать
при условиях
; (4)
; (5)
|
После элементарных преобразований приводим эту задачу к виду
минимизировать
при условиях
(8)
. (9)
Данная задача имеет n = 3 переменных и m = 7 ограничений. С целью упрощения поиска оптимального решения, поскольку m > n, воспользуемся переходом к двойственной задаче, сопряженной к (7) - (9). Она имеет такой вид:
максимизировать ( ) (10)
при условиях
Будем решать ее симплекс-методом. Для этого введем свободные сменные и заполним начальную симплекс-таблицу (табл. 2.32.).
Результаты последовательных итераций приведены в табл. 2.32 - 2.35.
¯ |
|||||||||||||
Ci |
34 |
1 |
4 |
7 |
-17 |
-23 |
-7 |
0 |
0 |
0 |
|||
Bx |
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
A9 |
A10 |
||
? |
0 |
Y8 |
0 |
1 |
-1 |
3 |
3 |
3 |
-5 |
-3 |
1 |
||
0 |
Y9 |
0 |
4 |
1 |
2 |
1 |
-5 |
1 |
4 |
1 |
|||
0 |
Y10 |
1 |
58 |
28 |
0 |
0 |
0 |
0 |
0 |
1 |
|||
|
0 |
-34 |
-1 |
-4 |
-7 |
17 |
23 |
7 |
0 |
0 |
0 |
¯ |
|||||||||||||
Ci |
34 |
1 |
4 |
7 |
-17 |
-23 |
-7 |
0 |
0 |
0 |
|||
Bx |
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
A9 |
A10 |
||
34 |
Y1 |
0 |
1 |
-1 |
3 |
3 |
3 |
-5 |
-3 |
1 |
|||
? |
0 |
Y9 |
0 |
0 |
5 |
-10 |
-11 |
-17 |
21 |
16 |
-4 |
1 |
|
0 |
Y10 |
1 |
0 |
86 |
-174 |
-174 |
-174 |
290 |
174 |
-58 |
1 |
||
|
0 |
0 |
-33 |
98 |
95 |
119 |
-147 |
-95 |
34 |
0 |
0 |
¯ |
|||||||||||||
Ci |
34 |
1 |
4 |
7 |
-17 |
23 |
-7 |
0 |
0 |
0 |
|||
Bx |
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
A9 |
A10 |
||
34 |
Y1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
0 |
|
1 |
Y2 |
0 |
0 |
1 |
-2 |
|
|
|
|
|
|
0 |
|
? |
0 |
Y10 |
1 |
0 |
0 |
-2 |
|
|
|
-101,2 |
10,8 |
-17,2 |
1 |
|
0 |
0 |
0 |
22 |
18 |
-13 |
7 |
28 |
5 |
9 |
0 |
Ci |
34 |
1 |
4 |
7 |
-17 |
-23 |
-7 |
0 |
0 |
0 |
||
Bx |
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
A9 |
A10 |
|
34 |
Y1 |
0,068 |
1 |
0 |
0,932 |
0,851 |
0 |
-1,04 |
-1,144 |
0,236 |
0,141 |
0,068 |
1 |
Y2 |
0,058 |
0 |
1 |
-2,06 |
-2,63 |
0 |
2,15 |
0,284 |
-0,49 |
-0,295 |
0,058 |
17 |
Y5 |
0,0168 |
0 |
0 |
0,017 |
0,128 |
1 |
-0,6 |
-0,855 |
0,091 |
-0,145 |
0,016 |
|
0,175 |
0 |
0 |
26,27 |
15,02 |
0 |
0,8 |
16,9 |
3,03 |
5,22 |
0,175 |
Так как в табл. 2.35. все оценки то найдено оптимальное решение двойственной задачи. Воспользовавшись соотношением , найдем оптимальное решение многокритериальной прямой задачи.
Имеем
Этому решению соответствует точка F на отрезке ВС (рис. 2.5.). Ему соответствуют минимальные относительные потери и отклонение от оптимального значения на обоих критериях:
,
.