2.8. многокритериальные ЗАДАЧИ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Во многих практических задачах исследования операций, описываемых моделями ЛП (например, из сферы экономики) выбор решения по одному показателю качества может быть неадекватным сути решаемой задачи, так как требуется учитывать одновременно несколько таких показателей - критериев [6; 9; 21].
Это приводит к необходимости решения многокритериальных задач ЛП.
Пусть задано некоторое множество целевых функций 
, где
(2.8.1)
причем m первых целевых функций надо максимизировать, а другие (M-m) - минимизировать. На вектор управляющих воздействий
наложены линейные ограничения вида
(2.8.2)
. (2.8.3)
Для решения этой задачи применим метод ограничений, описанный в гл. I. Преобразования, приводящие критерии к безразмерному виду, в данном случае примут следующий вид:
а) для максимизируемых целевых функций,
(2.8.4)
б) для минимизируемых целевых функций
(2.8.5)
где 
- решение, удовлетворяющее условиям (2.8.2), (2.8.3) и оптимизирующее 
-ю целевую функцию;
-решение, которое минимизирует (максимизирует) соответствующую Ц.Ф. на допустимом множестве решений.
Компромиссным решением рассматриваемой многокритериальной задачи будет такое эффективное решение Х, для которого взвешенные относительные 'затраты' одинаковые и минимальные, т.е
Согласно методу ограничений, искомое компромиссное решение может быть найдено из решения системы линейных неравенств:
(2.8.6)
для минимального значения параметра 
, при котором эта система совместна.
Решение системы (2.8.6) эквивалентно решению следующей задачи ЛП [ЗЗ]:
минимизировать 
= хn+1 (2.8.7)
при ограничениях
|
(2.8.9)
, (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)
|
(6)
После элементарных преобразований приводим эту задачу к виду
минимизировать 
при условиях
(8)
. (9)
Данная задача имеет n = 3 переменных и m = 7 ограничений. С целью упрощения поиска оптимального решения, поскольку m > n, воспользуемся переходом к двойственной задаче, сопряженной к (7) - (9). Она имеет такой вид:
максимизировать (
) (10)
при условиях
Будем решать ее симплекс-методом. Для этого введем свободные сменные и заполним начальную симплекс-таблицу (табл. 2.32.).
Результаты последовательных итераций приведены в табл. 2.32 - 2.35.
Таблица 2.32.
|
¯ |
|||||||||||||
|
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 |
Таблица 2.33.
|
¯ |
|||||||||||||
|
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 |
Таблица 2.34.
|
¯ |
|||||||||||||
|
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 |
Таблица 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 |
|
|
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.). Ему соответствуют минимальные относительные потери и отклонение от оптимального значения на обоих критериях:
,
.
