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

1. Задание 2: Использование метода ветвей и границ для Поиска глобально оптимальных Решений многокритериальных задач

ЗАДАНИЕ 2: ИСПОЛЬЗОВАНИЕ
МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ
ПОИСКА ГЛОБАЛЬНО
ОПТИМАЛЬНЫХ РЕШЕНИЙ
МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ
ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ

2.

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

3. Формальная постановка задачи

i n
k : F k ci ,k xi max(min) ;
i 1
i n
(1)
j : ai , j xi b j ;
i 1
i : xi {d1,i , d 2,i ,.....d m,i }.

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

неявного перебора
i, вычислить Fi,max и Fi,min .
Fi Fi min
zi
Fi max Fi min
i
Новый
критерий
2
,
zi = 1, если Fi
И
zi = 0, если Fi
max,
min.

5. Пояснения

Свертка критериев с помощью эталонов
позволяет получить новую целевую функцию
вида:
Fi Fi min
zi
Fi max Fi min
i
2
,
где Fi - i– я целевая функция, zi = 1, если Fi
и zi = 0, если Fi min.
max,

6. Новая формальная постановка задачи

2
zi Fi Fi min
Fi max Fi min
i
i n
(2)
j : ai , j xi b j ;
i 1
i : xi {d1,i , d 2,i ,.....d m ,i }.

7. ТЕОРЕМА

Оптимальный вектор
переменных задачи (2) является
Парето - оптимальным
вектором задачи (1).

8. ПРИМЕР 1

Пользуясь описанным выше методом
свертки, решить методом типа ветвей и
границ в сочетании с перебором,
многокритериальную задачу с булевыми
переменными вида:
F1 7 x1 2 x2 5 x3 3 x4 max;
F 3 x 4 x 2 x 5 x min;
1
2
3
4
2
(1)
4 x1 3 x2 2 x3 6 x4 8;
5 x 7 x 4 x 8 x 8;
2
3
4
1
i : xi 1,0.

9. Условия свертки

Для того, чтобы
преобразовать (1) в
однокритериальную задачу,
следует определить
максимальные и
минимальные значения F1 и
F2.

10. Поиск максимальной величины F1

F1 7 x1 2 x2 5 x3 3 x4 max;
4 x 3 x 2 x 6 x 8;
1
2
3
4
( 2)
5 x1 7 x2 4 x3 8 x4 8;
i : xi 1,0.

11. Решение задачи (2) методом типа ветвей и границ

S
17 1
1
1
17
0
0
0
-∞
15
F1 7 x1 2 x2 5 x3 3 x4 max;
4 x 3 x 2 x 6 x 8;
1
2
3
4
( 2)
5
x
7
x
4
x
8
x
8
;
1
2
3
4
i : xi 1,0.
1
12 15
-∞ 1
10
0
0
10
12
F1 max = 12

12. Поиск минимальной величины F1 сводится к решению задачи (3):

F1 7 x1 2 x2 5 x3 3 x4 min;
4 x 3 x 2 x 6 x 8;
1
2
3
4
(3)
5 x1 7 x2 4 x3 8 x4 8;
i : xi 1,0.

13. Решение задачи (3) методом типа ветвей и границ

S
7 1
0
F1 7 x1 2 x2 5 x3 3 x4 min;
4 x 3 x 2 x 6 x 8;
1
2
3
4
(3)
5 x1 7 x2 4 x3 8 x4 8;
i : xi 1,0.
1
1 7
F1 min = 3.
5
1
0
2
0 0
0 2
1
5
0 0
+∞ 0
3
1
+∞
0

14. Поиск максимальной величины F2

F2 3 x1 4 x2 2 x3 5 x4 max;
4 x 3 x 2 x 6 x 8;
1
2
3
4
( 4)
5 x1 7 x2 4 x3 8 x4 8;
i : xi 1,0.

15. Решение задачи (4) методом типа ветвей и границ

F2 3 x1 4 x2 2 x3 5 x4 max;
4 x 3 x 2 x 6 x 8;
1
2
3
4
( 4)
5 x1 7 x2 4 x3 8 x4 8;
i : xi 1,0.
s
14
1
1 -∞
1
-∞
0
7
0
1
14
10
0
12
1
-∞
1
11
0
11 1
10
0 8
0
5
F2 max = 7
1
-∞
7 0
1 11
0
-∞
0
1
-∞
9
0
6

16. Поиск минимальной величины F2

F2 3x1 4 x2 2 x3 5 x4 min;
4 x 3x 2 x 6 x 8;
1
2
3
4
(5)
5 x1 7 x2 4 x3 8 x4 8;
i : xi 1,0.

17. Решение задачи (5) методом типа ветвей и границ

S
3
1
0
7
3
1
6
0
+∞
1
0
2
0
+∞
1
0
4
1
+∞
0
1
3
1
F2 3x1 4 x2 2 x3 5 x4 min;
4 x 3x 2 x 6 x 8;
1
2
3
4
(5)
5
x
7
x
4
x
8
x
2
3
4 8;
1
i : xi 1,0.
4
0
5
0
+∞
0
0
1
7
1
0
+∞ 5
0
F2 min = 5
1
+∞
0

18. Использование эталонов для преобразования(1) в однокритериальную задачу

2
2
F2 5
F1 3
0
min;
1
7 5
12 3
F1 7 x1 2 x2 5 x3 3 x4 ;
(6)
F2 3 x1 4 x2 2 x3 5 x4 ;
4 x 3 x 2 x 6 x 8;
2
3
4
1
5 x1 7 x2 4 x3 8 x4 8;
i : xi 1,0.

19. Вид системы (6) после преобразований

2
2
12 F1 F2 5
min;
9 2
F1 7 x1 2 x2 5 x3 3x4 ;
(7 )
F2 3 x1 4 x2 2 x3 5 x4 ;
4 x 3 x 2 x 6 x 8;
2
3
4
1
5 x1 7 x2 4 x3 8 x4 8;
i : xi 1,0.

20. Вычисление оценки

2
2
F1 max min( F1 max ; F1 ) F2 min max( F2 min ; F2 )
,
F1 max F1 min
F2 max F2 min
где Δφ – нижняя оценка функции φ; ΔF1 = min{ ΔF1, F1max};
ΔF2 = max {ΔF2 ; F2min } .
Дерево ветвлений представлено на следующем слайде.

21. Решение системы (7)

S
0
0.0121
1
0
1
X1
0
1
X2
0
0 1
0.0121
+∞
0
X3
0
1
0
Xopt = {1,0.1.0}; φ = 0; F1 = 12; F2 = 5.
X4

22. Требования, предъявляемые к отчету

Отчет должен содержать:
1. Содержательную постановку задачи.
2. Использованные обозначения и формальную постановку
задачи.
3. Блок-схему алгоритма или его пошаговое описание.
4. Пример, иллюстрирующий работу алгоритма .
5. Экспериментальные графические и аналитические
зависимости среднего, максимального и минимального
времени счета от числа переменных и от числа целевых
функций с указанием параметров использованной ЭВМ и
ОС.
6. Инструкции и рекомендации по применению программы.
7. Листинг программы.