Системна оптимізація

1.

Системна
Оптимізація
Нормативний курс

2.

Постановка задачі
Схема і – підсистеми, складної системи:
Mi
ui
xi
i 1, N
yi
і – та підсистема
zi

3.

Постановка задачі
Вектор
розмірність
ui mui
xi mxi
M i mM i
yi m y i
z i m zi
f i M i , xi
i 1, N
Вхідні сигнали, як на систему, так і на і-ту
підсистему, на які неможливо впливати;
Проміжні вхідні сигнали з інших підсистем;
Управління і-ю підсистемою;
Вихідні сигнали і-ої підсистеми, що входять в
загальний набір вихідних сигналів системи;
Проміжні вихідні сигнали і-ої підсистеми, які
надходять на входи інших підсистем;

4.

Постановка задачі
і-підсистеми, i 1, N ,
визначається при заданому векторі вхідних
сигналів u векторними рівняннями:
Поведінка
zi Ti M i , xi , i 1, N
yi S i M i , xi , i 1, N
(1)
(2)
Ti - вектор-функція розмірності mz
S i - вектор-функція розмірності m y
i
(2) Можна не враховувати, якщо
на
yi
i
не накладені обмеження.

5.

Постановка задачі
Взаємодія між N підсистемами
визначається лінійними взаємозв’язками:
N
xi cij z j , i 1, N
(3)
j 1
cij - елементи матриці розмірності mz mx
i
i

6.

Постановка задачі
Нехай цільова функція F складної системи
задана в аддитивно-сепарабельному виді:
N
F f i M i , xi max
(4)
i 1
Потрібно визначити вектори M i , xi , i 1, N,
що максимізують (4) при обмеженнях (1), (3)

7.

Зведемо задачу умовної оптимізації (1), (3), (4)
до задачі безумовної оптимізації:
N
T
L f i M i , xi i Ti zi pi xi cij z j
i 1
i 1
i 1
j 1
N
N
N
(5)
L – Функція Лагранжа задачі (1), (3), (4)

8.

i
pi
L, f i , Ti , i 1, N
Lxi , LM i , Lzi , L i , Lpi
Вектор множників Лагранжа розмірності
mzi , i 1, N
Вектор множників Лагранжа розмірності
mxi , i 1, N
Неперервні функції, що мають неперервні
перші похідні.
Частинні похідні від функції Лагранжа

9.

Оптимальний розв’язок
задовольняє умовам:
T
Lxi
Ti
f i
L
i pi 0, i 1, N
xi
xi
xi
LM i
Ti
f i
L
M i
M i
M
i
(6)
T
i 0, i 1, N
N
L
Lzi
i cijT p j 0, i 1, N
zi
j 1
L
L i
Ti zi 0, i 1, N
i
N
L
L pi
xi cij z j 0, i 1, N
pi
j 1
(7)
(8)
(9)
(10)

10.

Оптимальний розв’язок
задовольняє умовам:
Ti1
x1
i
Ti
...m z
xi
Ti i
1
x
i
Ti1
M 1
i
Ti
...m z
M i
Ti i
1
M
i
...
...
...
...
...
...
Ti1
m
xi xi
...
m
Ti zi
m xi
xi
Ti1
mM i
M i
...
m
Ti zi
m
M i M i

11.

Приклад 1
“Система водосховищ”

12.

Приклад 1. Система водосховищ
(підземних та наземних)
u1
u2
M1
z13
1
z14
M2
z 24
M4
x41
x34
4
2
z23
1,2,3 – наземні водосховища;
4 – підземне водосховище;
ui , i 1,4 - опади, річки, ґрунтові води;
xi , i 3,4 - водоскиди з інших водосховищ;
zi , i 1,4 - водоскиди в інші водосховища;
M i , i 1,4 - рівень наповнення водосховища.
3
z43
x42
u4
M3
x31
x32
u3
Y

13.

Приклад 2
“Туристична агенція”

14.

Приклад 2. Туристична агенція
Нехай туристичне агенство має три відділи:
1. Відділ реклами
2.
Виробничий відділ
(підготовка до поїздок: візи, білети, угоди і т.п.)
3.
Відділ обслуговування на маршрутах
(під час поїздок: гіди, водії, транспортні засоби, готелі,
екскурсії, ресторани і т.п.)

15.

Приклад 2. Туристична агенція
u
M 11
z2
x21
z1
1
M3
M2
M12
x22
2
x3
3
M 13
M 11 - бюджет реклами
M12 - кількість маршрутів, що пропонує фірма
M 13 - репутація (ціна, якість маршрутів)
M 2 - бюджет виробничого відділу
M 3 - бюджет відділу обслуговування
z3
y1
y2

16.

Приклад 2. Туристична агенція
u
M 11
z2
x21
z1
1
M3
M2
M12
x22
2
x3
3
z3
y1
y2
M 13
u - час, законодавчі зміни країн, міжнародні події, форс-м
x21 - кількість клієнтів, що прийшли оформляти тури після
реклами
x22 - кількість клієнтів, що звернулися після турпоїздок
знову
x3 - кількість клієнтів, що поїхали в турпоїздку

17.

Приклад 2. Туристична агенція
u
M 11
z2
x21
z1
1
M3
M2
M12
x22
2
x3
3
z3
M 13
z1 - кількість клієнтів, що звернулися після реклами
z2 - кількість клієнтів, які оформлені в поїздку
z3 - кількість клієнтів, що повернулися та поїдуть знову
y1 - кількість клієнтів, які не повернулися
y2 - кількість незадоволених клієнтів, які подали
прокламації
y1
y2

18.

Приклад 2. Туристична агенція
3
F1 f1i M i , xi min
i 1
мінімізація витрат агенції
3
F2 f 2i M i , xi max
i 1
максимізація долі ринку за
всіма маршрутами агенції

19.

Приклад 2. Туристична агенція
z1 l11u1 l12u2 l13u3 l14 M11 l15M12 l16 M13
z2 l2 x21 x22 2 M 2
l2
- статистичний коефіцієнт врахування
відсіву клієнтів
2 - коефіцієнт залежності кількості
оформлених клієнтів від бюджету

20.

Приклад 2. Туристична агенція
z3 l3 x3 3 M1 M 2 M 3
l3 - статистичний коефіцієнт фірми
3 - коефіцієнт залежності повторних
клієнтів від бюджету
y1 11x3 12u2 13u3
y2 21x3 22 M 3 23u4

21.

Ітераційні алгоритми
координації (ІАК)

22.

Принцип ієрархічної оптимізації
в ІАК:
Розподіл процедур розв’язання рівнянь (6)-(10) між
двома рівнями – центром (координатором) та
нижнім рівнем підсистем ( під задач). Лагранжіан
розглядають в адитивно – сепарабельній формі
N
-
L Li i ,
i 1
вектор змінних параметрів координації;
i , i 1, N - вектор змінних і – під задачі
(підсистеми) нижнього рівня.

23.

Структура дворівневого алгоритму
визначається
Координатор
підзадача
i
i
j
…
визначається
підзадача
j

24.

Розподіл процедур розв’язання рівнянь (6)-(10)
між верхнім (ВР) та нижнім (НР) рівнями в
ітераційних алгоритмах координації (МЦК, МКМ,
ЗМ) та порівняння алгоритмів:
МЦК
МКМ
ЗМ
Умова
Lx 0
LM 0
Lz 0
L 0
Lp 0
ВР
НР
НР
ВР
НР
*
*
*
*
*
*
*
*
*
МЦК – метод цільової координації;
МКМ – метод координації моделей;
ЗМ – змішаний метод.
ВР
*
*
*
*
*
*

25.

Метод цільової координації
(МЦК)

26.

Метод цільової координації (МЦК)
T pT ,
x , M , z , , i 1, N
T
i
T
i
T
i
T
i
T
i
I. Зміст i–підзадачі нижнього рівня:
Знайти для заданих pi , i 1, N
iT xiT , M iT , ziT , iT
N
N
N
N
i 1
j 1
i 1 j 1
T
T
p
c
z
p
i ij j j c ji zi

27.

Метод цільової координації (МЦК)
Локальна оптимізація
N
T
T
f i pi xi p j c ji zi
j 1
max f i M i , xi f i (12)
xi p , zi p
zi Ti M i , xi

28.

Метод цільової координації (МЦК)
Аналітично j знаходять з системи (6)-(9):
T
з (8) знаходять
i для фіксованих pi , i 1, N
з (6), (7) знаходять x , M для відомих pi , i
i
i
з (9) знаходять zi для відомих xi , M i

29.

Метод цільової координації (МЦК)
II. Зміст задачі координації:
знайти
T pTз (10):
Lpi 0, i 1, N
Алгоритм градієнтного типу в дискретній формі:
pi t 1 pi t k L pi t
N
pi t k xi cij z j , i 1, N
j 1
k 0
t
- ітераційний індекс координатора
N
f 0 - в оптимальних розв’язках
i 1
i
модифікація критерія дорівнює 0.
(13)

30.

Метод цільової координації (МЦК)
III. Інформаційний обмін між рівнями:
N
pi t 1 pi t k xi cij z j , i 1, N
j 1
k 0
pi , i 1, N
координатор
zi p
xi p
N T
T
max f i M i , xi pi xi p j c ji zi
j
1
zi Ti M i , xi
підсистема
i
i 1, N

31.

Метод цільової координації (МЦК)
Критерій закінчення МЦК:
L Lp
T
p
- вибирають з міркувань прийнятного часу
та точності рішення задачі

32.

Метод координації моделей
(МКМ)

33.

Метод координації моделей (МКМ)
T zT ,
x , M , p , , i 1, N
T
i
T
i
T
i
T
i
T
i
I. Зміст i–підзадачі нижнього рівня:
Знайти для заданих zi , i 1, N
x , M , p ,
T
i
T
i
T
i
T
i
T
i

34.

Метод координації моделей (МКМ)
Локальна оптимізація
max f i M i , xi
zi Ti M i , xi
N
xi cij z j
j 1
(14)

35.

Метод координації моделей (МКМ)
Аналітично T знаходять з системи (6), (7),
j
(9), (10):
mM i mzi : з (10) знаходять xi для заданих zi , i 1, N
з (9), (7) знаходять M i , i для відомих zi , xi
з (6) знаходять
pi
для відомих
M i , i
mM i mzi : (9) не має розв’язку, МКМ не працює
mM i mzi : (9) може не мати розв’язку, мати один або
багато розв’язків

36.

Метод координації моделей (МКМ)
II. Зміст задачі координації:
знайти
z
T
Tз
(8):
Lzi 0, i 1, N
Алгоритм градієнтного типу в дискретній формі:
zi t 1 zi t k Lzi t
N
T
zi t k i cij p j , i 1, N
j 1
k 0
(15)

37.

Метод координації моделей (МКМ)
III. Інформаційний обмін між рівнями:
N
T
zi t 1 zi t k i cij p j , i 1, N
j 1
k 0
координатор
i z
pi z
zi , i 1, N
max f i M i , xi
zi Ti M i , xi
N
xi cij z j
j 1
підсистема
i
i 1, N

38.

Метод координації моделей (МКМ)
Умова використання МКМ:
mM i mzi , i 1, N
Критерій закінчення МКМ:
L Lz
T
z
- вибирають з міркувань прийнятного часу
та точності рішення задачі

39.

Змішаний метод (ЗМ)

40.

Змішаний метод (ЗМ)
T pT , z T
x , M , , i 1, N
T
i
T
i
T
i
T
i
I. Зміст i–підзадачі нижнього рівня:
Знайти для заданих pi , zi , i 1, N
x , M ,
T
i
T
i
T
i
T
i

41.

Змішаний метод (ЗМ)
Локальна оптимізація
N
T
T
max f i M i , xi pi xi pi cij z j
j 1
(16)
zi Ti M i , xi

42.

Змішаний метод (ЗМ)
Аналітично T знаходять з системи (6), (7),
j
(9):
mxi mM i mzi :
з (6), (7), (9) знаходять
для відомих
zi , pi
xi , M i , i

43.

Змішаний метод (ЗМ)
II. Зміст задачі координації:
знайти
T pT , z T
з (8), (10): Lzi 0, L pi 0, i 1, N
Алгоритм градієнтного типу в дискретній формі:
N
pi t 1 pi t k L pi t pi t k xi z j t (17)
j 1
N
T
zi t 1 zi t k Lzi t zi t k i cij p j t
j 1
i 1, N , k 0

44.

Змішаний метод (ЗМ)
III. Інформаційний обмін між рівнями:
N
pi t 1 pi t k xi z j t
j 1
N
zi t 1 zi t k i cijT p j t
j 1
i 1, N , k 0
pi , zi
i 1, N
координатор
i p, z
xi p, z
N
T
T
max f i M i , xi pi xi pi cij z j
j 1
zi Ti M i , xi
підсистема
i
i 1, N

45.

Змішаний метод (ЗМ)
Умова використання ЗМ:
mxi mM i mzi , i 1, N
Критерій закінчення ЗМ:
L Lp
T
p
L Lz
T
z
- вибирають з міркувань прийнятного часу
та точності рішення задачі

46.

Приклади розв’язання задач
координації ітераційними
методами

47.

Приклад 1

48.

Розв’язок
M1
U
x1
M2
z12 x2
1
z13
2
M3
z2 x32
x31
Y
3
1. Модель взаємодії між підсистемами визначається
співвідношеннями:
x1 z3
x2 z12
x31 z13
x32 z2
z3

49.

Розв’язок
2. Проведемо аналіз застосування кожного з методів для даної
задачі.
Випишемо розмірності векторів:
mM1 1
mz1 2
mx1 1
mM 2 1
mz 2 1
m x2 1
mM 3 1
m z3 1
mx3 2
a) Метод цільової координації можна застосовувати без
обмежень;

50.

Розв’язок
b) Метод координації можна застосовувати, якщо mM mz , i 1,3
i
підсистема 1:
підсистема 2:
підсистема 3:
i
mM1 1 , mz1 2
mM 2 1 , mz2 1
mM 3 1 , mz3 1
Метод координації моделей для розв’язку задачі
використовувати не можна, оскільки для першої підсистеми
умова не виконується;

51.

Розв’язок
c) Змішаний метод можна використовувати за умови
mxi mM i mzi , i 1,3
підсистема 1:
підсистема 2:
підсистема 3:
mx1 mM1 2
mx2 mM 2 2
mx3 mM 3 3
,
,
,
mz1 2
mz 2 1
m z3 1
Отже, змішаний метод можна використовувати для
розв’язку даної задачі.

52.

Приклад 2

53.

Структурна схема багатозв’язної
системи
u1
x1
x2
M1
x3
z11
Підсистема 1
Підсистема 2
M2
z12
z2
M3
y3
Підсистема 3

54.

Постановка задачі
u x M x M x M min
2
1
2
1
2
1
2
2
2
2
2
3
2
z
x
11
1 M 1 u1 ;
3
2
z
x
M
12 1
1 u1 ;
z x2 M ;
2
2
2
при
_
умовах
x1 z 2 ;
x2 z12 ;
x3 z11.
Зрозуміло, що даній задачі умова
2
3
mM i mzi не виконується
mM1 1, mz1 2 . Отже, можна застосовувати лише метод
цільової координації або змішаний метод.

55.

Задача координації
Лагранжіан може бути записаний у вигляді:
L u12 x12 M 12 11 x12 M 1 u1 z11 12 x13 M 12 u1 z12
x22 M 22 2 x22 M 2 z2 x32 M 32 p1 x1 z2 p2 x2 z12
p3 x3 z11 ,
де 11, 12 , 2 , pi i 1,2,3 - множники Лагранжа.

56.

Цільова координація
Для заданого p лагранжіан переписується наступним
чином:
L Li u x M p1 x1 p2 z12 p3 z11
i 1
L1
11 x12 M 1 u1 z11 12 x13 M 12 u1 z12
x22 M 22 p2 x2 p1 z2 2 x22 M 2 z 2 L2
3
2
1
2
1
2
1
x M p3 x3 L3
2
3
2
3
Досліджуючи кожний доданок Li , можна визначити
окремі підзадачі:

57.

Цільова координація
Підзадача 1. Для заданих p1 , p2 , p3 потрібно знайти
u
2
1
x M p1 x1 p2 z12 p3 z11 min
2
1
2
1
при умовах
z11 x12 M 1 u1 ;
3
2
z
x
M
12
1
1 u1

58.

Цільова координація
Підзадача 2. Для заданих p1 , p2 потрібно знайти
x
2
2
M p2 x2 p1 z2 min
2
2
при умові
z2 x M 2
2
2

59.

Цільова координація
Підзадача 3. Для заданого p3 потрібно знайти
x
2
3
M p3 x3 min
2
3

60.

Цільова координація
Розв’язавши ці підзадачі, отримаємо значення x* , M * , z * ,
які задовольняють всім умовам стаціонарності для L (за
виключенням умови L p 0 , що розглядається на другому
рівні).
При використанні градієнтного алгоритму координації (t
– ітераційний індекс координатора) можна записати
p1 t 1 p1 t kLp1 p1 t k x1* z2* ;
*
*
p2 t 1 p2 t k x2 z12 ;
k 0
*
p3 t 1 p3 t k x3* z11
;
Глобальний розв’язок досягається, якщо LTp Lp , -
деяке завчасно вибране мале число.

61.

Змішана координація
У випадку змішаної координації,
координуючими змінними є вектори p та z .
Для яких лагранжіан стає роздільним, що
веде до появи наступних підзадач:

62.

Змішана координація
Підзадача 1. Для заданих p1, z11, z12 , z2 потрібно знайти
u
2
1
x M p1 x1 z2 min
2
1
2
1
при умовах
z11 x12 M 1 u1 ;
3
2
z
x
M
12 1
1 u1

63.

Змішана координація
Підзадача 2. Для заданих p2 , z12 , z2 потрібно знайти
x
2
2
M p2 x2 z12 min
2
2
при умові
z2 x M 2
2
2

64.

Змішана координація
Підзадача 3. Для заданого p3 , z11
x
2
3
потрібно знайти
M p3 x3 z11 min
2
3

65.

Змішана координація
Координація оптимальних рішень:
Градієнтний метод:
p t 1 p t k x z
p t 1 p t k x z
p1 t 1 p1 t k x1* z 2
2
3
2
*
2
3
*
3
12
11
z t 1 z t k p
z t 1 z t k p
*
z11 t 1 z11 t k p3 11
12
2
12
2
2
1
Метод прямих ітерацій:
p1 t 1 2* t
z11 t 1 x3* t
p3 t 1 11* t
z 2 t 1 x1* t
p2 t 1 12* t
*
12
z12 t 1 x2* t
*
2

66.

Безітераційні алгоритми
координації (БАК)

67.

Верхній
рівень
Центр
підсистема
N
підсистема 1
Нижній
рівень
…
…
підсистема i
H 0 Ф0 F0 max,
N
F0 X 0 F , m0 mi
m0
Фi xi max,
xi X i E ni ,
Fi xi , i 1,..., N
i 1
Fi xi E mi , Фi xi E ki

68.

i підсистема нижнього рівня
i 1,..., N
стан і-ої підсистеми:
показники роботи і-ої
підсистеми:
локальні інтереси і-ої
підсистеми:
1
2
F f x ,..., f x
Ф x x ,..., x max 3
xi xi1 ,..., xini X i E
i
i
i1
i
i
imi
i1
i
ni
i
iki
i
ni - кількість змінних і-ої підсистеми;
mi - кількість показників роботи і-ої підсистеми;
ki - кількість критеріїв і-ої підсистеми.
mi ni
ki ni

69.

Центр
F0 F1 ,..., FN X 0 E m0
стан центра:
4
N
Fi Fi xi , m0 mi
інтереси центра:
узагальнений критерій:
k0
Ф0 F0 01 F0 ,..., 0k0 F0 max
i 1
H 0 Ф0 F0 max
5
6
- кількість критеріїв центра;
Фi xi Fi xi , i 1, N
X 0 F0 : H F0 b, b b1 ,..., bM
7
8

70.

Схема безітераційного алгоритму
координації (БАК)
H 0 F1 ,..., FN max
H j F1 ,..., FN b j , j 1,..., M
Fi QiF Fi : xi QiX або xi X i , i 1,..., N
Q1F
F1 x1 max
x1 X 1
2
1
F1 x1 F1*
x1 X 1
FN*
QNF
F1*
12
1
…
FN xN max
xN X N
6
8
9
2
1
FN xN FN*
xN X N
12
1

71.

Способи визначення множини
Q , i 1, N
F
i
1.
2.
Q Fit , t 1,..., Ti
F
i
10
Q Fi : Fi it Fit , it Ti 11
t 1
Ti
Ti it : it 1, it 0
t 1
F
i
Ti

72.

Задача координації в БАК для
лінійних систем
H a , F , j 0,..., M
13
N
j
N
i 1
i 1 t 1
i max
14
jit
i b j , j 1,..., M
15
Ti
z
i 1 t 1
i
0 it
Ti
z
N
ji
t
t
mi
де z jit a ji , f it a jil f itl ,
l 1
Ti
t 1
it
1, i 1,..., N
i 0,1
t
i 0
t
16
17
18

73.

Позначення
j
-
номер загального критерію та обмежень центра,
j 0, M
i
t
-
номер підсистеми, i 1, N
-
номер ефективної точки,
l
-
номер локального критерію підсистеми, l 1, mi
t 1, Ti

74.

Приклад розв’язання задачі
координації для лінійних
систем за допомогою
безітераційного алгоритму
координації

75.

Схема системи
центр
підсистема 1
підсистема 2

76.

Математична модель першої
підсистеми нижнього рівня
Ф1 F 1 f11, f12 - векторний критерій
f11 x1 2 x2 max
f12 2 x1 x2 max
Множина допустимих розв’язків першої підсистеми:
x : x1 x2 4
x x 2
1
2
X1
x1 2 x2 1
x1 , x2 0
(19)

77.

Математична модель другої
підсистеми нижнього рівня
Ф2 F2 f 21, f 22 - векторний критерій
f 21 y1 y2 max
f 22 y1 5 y2 max
Множина допустимих розв’язків другої підсистеми:
y : y1 2 y2 4
y 2y 8
1
2
X2
2 y1 y2 10
y1 , y2 0
(20)

78.

Математична модель верхнього
рівня (центра)
Глобальна цільова функція:
H 0 x1 2 x2 y1 y2 max
Глобальне обмеження:
H1 2 x1 x2 y1 5 y2 23

79.

Позначення
j
-
номер глобального критерію та обмежень, j 0, M
i
t
-
номер підсистеми, i 1, N
-
номер крайньої ефективної точки, t 1, Ti
l
-
номер локального критерію, l 1, mi

80.

I етап
Позначимо:
1
- оптимальний розв’язок задачі (19) за критерієм
f11
x2
- оптимальний розв’язок задачі (19) за критерієм
f12
1
- оптимальний розв’язок задачі (20) за критерієм
f 21
- оптимальний розв’язок задачі (20) за критерієм
Знаходимо ефективні крайні точки задач (19) та (20) за
допомогою симплекс-методу.
f 22
x
y
y2

81.

I етап
Отримаємо:
x1 1,3
x 3,1
2
2
Врахуємо обмеження
it
i 1
y1 4,2
y 2 2,3
1 , перепозначимо
i i , i 1 i , i 1,2
1
2
F
Q
Множини ефективних значень критеріїв i , i 1,2
використовують на II етапі алгоритму формування задачі
центра.

82.

I етап
Визначимо, відповідно (11), множину ефективних значень
F
Q
критеріїв підсистеми 1 :
2
F1 : F1 f11 , f12 1t F1t
t 1
F
1
2
Q1 1 F1 x 1 1 F1 x
1
2
1 f11 x 1 1 f11 x f11 x
1
2
f
x
1
f
x
f
x
1 12
12
1 12

83.

I етап
Визначимо, відповідно (11), множину ефективних значень
F
Q
критеріїв підсистеми 2 :
2
F2 : F2 f 21, f 22 2t F2t
t 1
F
1
2
Q2 2 F2 y 1 2 F2 y
1
2
2 f 21 y 1 2 f 21 y f 21 y
f y1 1 f y 2 f y
2
22
22
2 22

84.

II етап
Визначимо вектори a ji , j 0,1, i 1,2 в позначеннях
a ji , Fi , введених в задачі координації безітераційного
алгоритму координації для лінійних систем.
1
1
a0i : a01 ; a02
0
0
0
0
a1i : a11 ; a12
1
1

85.

II етап
Відповідно (13), задача центра набуває вигляд (14), (15):
H 0 a01, F1 a02 , F2
1 f11 x 0 f12 x 1 f 21 y 0 f 22 y
x x 2 x x x x 2 x x 1
y y y y y y y y 1
f11 x1 1 f11 x 2 1 1 f 21 y1 2 f 21 y 2 1 2
1
1
1
2
1
1
2
1
1
1
2
2
2
2
2
1
1
2
2
2
1 6 1 3 2 1 1 4 2 2 2 3 1 2
7 1 5 5 1 6 2 5 5 2 2 1 2 10 max

86.

II етап
При глобальному обмеженні:
H1 a11 , F1 a12 , F2
0 f11 x 1 f12 x 0 f 21 y 1 f 22 y
2 x x x x 2 x x x x 1
y y 5 y y y y 5 y y 1
f12 x 1 f12 x 1 1 f 22 y 2 f 22 y 1 2
1
2
1
1
1
2
1
1
1
2
1
1
1
2
2
2
1
2
2
1
2
2
2
2
2 3 1 6 1 1 1 4 10 2 2 15 1 2
2 1 7 3 2 17 2 1 3 2 24 23
2 1 3 2 1

87.

II етап
Маємо задачу лінійного програмування:
2 1 2 10 max
2 1 3 2 1
1 , 2 0
Розв’язок:
1
1/ 2
1 1 / 2
2 0
1/ 3
1
2

88.

II етап
*
*
Підрахуємо оптимальні значення критеріїв підсистем F1 , F2 :
1
1
*
1
1
2
2
f
x
x
2
x
x
x
x
2
x
x
11
1
2
1
2
1
/
2
2
2
F1* 1
1
1
1
1
2
2
f*
2
x
x
x
x
2
x
x
x
x
2
1
2
12 1 1/ 2 2 1
2
1
7 5
1
1
6
3
2
6
2
2
2
1 2 3 1 6 1 5 7 6
2
2
2

89.

II етап
*
*
Підрахуємо оптимальні значення критеріїв підсистем F1 , F2 :
f 21*
y1 y 2 y2 x 2 2 3 5
2 0
*
F2 *
2
2
f
y
x
5
y
x
2 15 17
22 0
1
2
2

90.

II етап
Вектори F1* та F2* передаємо у відповідні підсистеми нижнього
рівня:
*
f11
6
*
F1 *
f12 1 1/ 2 6
f
F
f
*
2
*
21
*
22 2 0
5
17

91.

III етап
Знаходимо локальні розв’язки xi* , i 1,2 в підсистемах.
Для першої підсистеми:
*
*
x
f
x
2
x
6
f
11 1
1 2
*
2
11
F1
*
*
f12 2 x1 x2 6 f12 x2 2
Для другої підсистеми:
*
*
y
f
y
y
5
f
21 1 2
1 2
*
11
F2
*
*
f 22 y1 5 y2 17 f12 y2 3

92.

Постановка задачі прийняття
рішень (ЗПР) в термінах
багатокритеріальної оптимізації

93.

fi x , i I
I 1,..., M
M
I1 1,..., m
- множина критеріїв
- множина індексів критеріїв
- кількість критеріїв
- множина індексів критеріїв, що
максимізуються
I 2 m 1,..., M - множина індексів критеріїв, що
I I1 I 2
D0
мінімізуються
- множина допустимих альтернатив
opt f i x , i I
x D0
1

94.

Визначення
Альтернатива x0 називається ефективною, якщо на
множині допустимих альтернатив D0 не існує іншої
альтернативи x , для якої виконуються нерівності:
f i x f i x0 , i I1
f i x f i x0 , i I 2
та хоча б одна нерівність була строгою.

95.

Додаткова інформація в ЗПУР.
Перший евристичний аспект в
задачах БО
(2)
f i 0 f i x
, i I1
f0 f
i min
i
wi f i x
0
f i x f i , i I
2
f i max f i 0

96.

Додаткова інформація в ЗПУР.
Перший евристичний аспект в
задачах БО
0 wi f i x 1, i I , x D0 ,
wi x wi fi x , i I - монотонні перетворення значень
критеріїв f i x , що призводять критерії до безрозмірного
вигляду та одного напрямку оптимізації;
f i min , f i max
fi
W
0
- відповідно, найменші та найбільші значення
критеріїв, що оптимізуються, на множині
допустимих альтернатив D0 ;
- оптимальне значення критерію i на множині
допустимих розв’язків D0 ;
- простір перетворених значень критеріїв f x , i I
i

97.

Другий евристичний аспект в
задачах БО
i , i I i : i 1, i 0, i I 3
i I
Переваги ОПР на множині функцій цілі
fi x , i I

98.

Процедури виявлення переваг ОПР на
множині критеріїв
1.
2.
3.
4.
5.
Ранжування критеріїв
Попарне порівняння
Безпосередня оцінка
, i I
*
i
*
x D0
f *, i I
i w j f j x* / w j f j x* , i I
j I
j i
q I j I
j q
4

99.

Три способи визначення множини
ефективних альтернатив
1.
min
x D0
i I
i
wi x
5
i Г i : i 0, i I , i 1 ,
i I
D
відносно параметрів
де wi x , i I - увігнуті неперервні функції,
замкнена множина.
2.
min max i wi x
x D0
i I
0
є опукла
6
відносно параметрів i Г i : i 0, i I , i 1 ,
i I
де wi x , i I - монотонні перетворення (2) критеріїв f i x , i I

100.

Три способи визначення множини
ефективних альтернатив
3.
f i x zi , i I1 , i l
f i x zi , i I 2
x D0
max f l x
відносно параметрів z Z M 1
f
i I1
i l
7
0
0
,
f
f
i , fi max
i min
i
i I 2

101.

Визначення
Рішення задачі БО називають компромісним
рішенням. Нехай додаткова інформація від ОПР
задана у вигляді (2), (3), то компромісним рішенням
*
задачі БО буде
ефективний розв’язок
x D0
для заданого в просторі W вектора переваг критеріїв
i , i I

102.

Метод обмежень
(метод знаходження компромісного рішення )
Визначення
Під компромісним рішенням задачі БО в методі обмежень
розуміють ефективну альтернативу x* D0, що знаходиться
на заданому вектором i , i I напрямку в просторі W , та
забезпечує однакові мінімальні зважені відносні відхилення
від оптимальних значень по всім критеріям одночасно:
1 w1 x* ... M wM x*
компромісне рішення для заданих i , i I можна знайти при
розв’язуванні задачі параметричного програмування відносно
параметра k0 :

103.

Метод обмежень
(метод знаходження компромісного рішення)
min k0
i wi x k0 , i I
8
x D0
k0 0
xn 1 k0
min xn 1
w x x
i i
n 1
x D0
xn 1 0
9

104.

Ітераційний процес в методі
обмежень
k0 0,1 M
k0 0 i wi x 0, i I f i x f i , i I
0
l - ітераційний індекс
, 0 - заданий параметр закінчення ітераційного процесу
l
- номер ітерації, на якій система нерівностей в (8)
сумісна
l 1- номер ітерації, на якій система нерівностей в (8)
несумісна
k0 l k0 l 1
процесу
- критерій закінчення ітераційного

105.

Геометрична інтерпретація метода
обмежень
w2
1
k0 1
j
w2 j
k0 j
w2 l l
k0 l
l
1
WD0
w2 l 1
k0 l 1
w1 l 1 w1 l w1 j w1 1
w2 1
w1

106.

Геометрична інтерпретація метода
обмежень
WD0- множина перетворених значень критеріїв на множині
допустимих розв’язків D0
j i wi x k0 j , i I
j - номер ітерації
WD0 j 0, j 1, l
WD0 l 1 0, j l 1

107.

Метод обмежень
багатокритеріальної задачі
лінійного програмування
n
f f i x cij x j , i I
j 1
n
D0 x : aij x j bi , i 1, p, x j 0, j 1, n
j 1
n
n
0
cij x j cij x j
j 1
n j 1
, i I1
n
0
x
c
j cij x j min
ij
j 1
j 1
wi x n
n
cij x j cij x 0j
j 1
j 1
,i I2
n
n
cij x j max cij x 0j
j 1
j 1
arg max f i x , i I1 ,
x D0
0
xj
arg min f i x , i I 2 , j 1, n
x D0
x j min arg min f i x , i I1 , j 1, n
x D0
x j max arg max f i x , i I 2 , j 1, n
x D0

108.

min k0
n
k0 n
0
cij x j cij x cij x j cij x j min , i I1
i j 1
j 1
j 1
j 1
n
n
n
n
k
0
0
0
cij x j cij x j cij x j max cij x j , i I 2
i j 1
j 1
j 1
j 1
n
n
0
j
n
a
j 1
ij
x j bi , i 1, p
x j 0, j 1, n
k0 0
i , i I - заданий ОПР вектор переваг на множині
критеріїв

109.

Прийняття рішень при
коаліційному об’єднанні критеріїв

110.

F , D0
топ-менеджер
f , D0
X Fl , wq x k
X Fl X l
менеджери
q 1,..., Q
f
1
, D0
Xl
f Ufq
q X
p, q , p q :
…
X 1l 1 , w1 x1
f p fq 0
f
q
, D0
…
X ql q , wq xq
f
Q
, D0
X Q Q , wQ xQ

111.

Постановка задачі багаторівневої
багатокритеріальної оптимізації
при коаліційному об’єднанні
критеріїв

112.

f f i x , i I
I 1,..., M
M
D0
- множина критеріїв
- множина індексів критеріїв
- кількість критеріїв
- множина допустимих альтернатив
f , D0 opt fi x , i I - задача багатокритеріальної оптимізації
x D0
l
X
1,..., Q
- множина ефективних рішень задачі
f , D0
- множина індексів коаліцій критеріїв
f q , q , на які декомпозована множина f
Q
- кількість коаліцій критеріїв, на які
розділена множина критеріїв f
f U f q , p, q , p q : f p f q 0
q X

113.

- множина критеріїв в коаліції q, q
1,..., i ,..., M - множина індексів критеріїв в коаліції q
f f , iq I q
iq
q
Iq
q
Mq
iq
q
- кількість критеріїв в коаліції q
q
- поточний індекс критерія в коаліції
iq
f , D0 opt f , iq I q - задача багатокритеріальної оптимізації
x D0
q
q
для коаліції
X
l
q
q
- множина ефективних рішень задачі f , D0
Знайти розв’язок задачі багаторівневої
багатокритеріальної оптимізації f , D0 при
коаліційному об’єднанні критеріїв

114.

Пошук внутрішньокоаліційних
компромісних розв’язків задач
f
q
, D0 , q

115.

iq : iq 0, iq I q , iq 1 , q
iq I q
q
- заданий вектор переваг критеріїв в коаліції
wq wiq x , iq I q
q
- задані монотонні перетворення значень критеріїв f q
коаліції q , що призводять до їх мінімізації та
безрозмірного виду з інтервалом зміни значень (0,1).

116.

xq , xq X
l
q
- внутрішньокоаліційний компромісний розв’язок
задачі f q , D0 при заданих q, w q , який можна
знайти методом обмежень:
xq arg min max iq wiq x , q
x D0 iq I q
- з узагальненим критерієм для коаліції q:
1

117.

Fq , x max iq wiq x , q
q
iq I q
k Fq , xq max iq wiq xq , q
*q
0
q
- значення
iq I q
2
3
Fq q , x в компромісному розв’язку xq

118.

Пошук міжкоаліційного
компромісного розв’язку задачі
F , D0

119.

F Fq , x , q
q
- множина всіх узагальнених критеріїв коаліцій
F , D0
min F , x , q
q
x D0
q
- нова міжкоаліційна задача багатокритеріальної
оптимізації
X
l
F
- множина ефективних рішень задачі
F , D0

120.

q : q 0, q , q 1
q
- заданий вектор переваг коаліцій
wq Fq , x
q
max iq wiq x k
iq I q
1
k0*q
Mq
*q
0
, q
4
- побудовані монотонні перетворення значень
критеріїв Fq q , x , q , де
1 *q
та оптимальні значення
, k0 - відповідно найбільші
q
Mq
F
, x , q на множині допустимих
критеріїв q
альтернатив D0

121.

x ,x X
k
k
l
F
-компромісний розв’язок міжкоаліційної задачі
F , D0
який можна знайти методом обмежень:
x arg min max q wq Fq , x
k
x D0
q
q
5

122.

Загальна схема розв’язання задачі
міжкоаліційного прийняття
управлінських рішень

123.

I етап
Знайти внутрішньокоаліційні компромісні
розв’язки xq , q задачі багатокритеріальної
оптимізації f q , D0 для кожної коаліції q, q
q
q
w
, q , наприклад, методом
при заданих
та
обмежень:
min Fq , x max iq wiq x , q 6
x D0
q

124.

II етап
Знайти міжкоаліційний компромісний розв’язок
задачі багатокритеріальної оптимізації F , D0 з
числом критеріїв (2), рівним кількості коаліцій
при заданих та wq , наприклад, методом
обмежень:
min max q wq Fq , x
x D0
x X
k
q
w
F
,x
- з монотонності
q
q
l
F
X X
l
F
q
q
l
- при фіксованих векторах переваг
критеріїв
q , кожної коаліції q
xk
7

125.

Матрична структура підприємства

126.

Власник
1. Власники
Голова ради директорів
Генеральний директор
Управління
виробництвом
Функціональні
підрозділи
Управління
бізнесом
БО1
Дільниці
2. Вища ланка
управління (топменеджери)
БО2
…
БОS
3. Бізнесодиниці
БП11
БП12
БП13
БП 21
БП 22
4. Бізнеспроцеси

127.

Бізнеси (бізнес-процеси - БП) – організовані
за продуктовим ланцюгом платежі –
постачання сировини – реалізація – повернення
грошей.
Бізнес-одиниці – підрозділи, що
управляють бізнесами.
Виробничі та функціональні підрозділи
виконують замовлення бізнес одиниць.

128.

Схема інформаційної та
математичної підтримки
управління розвитком

129.

Інформаційні технології
(Стратегічне планування)
Технологія аналізу “дерево-цілей”
цілі
(критерії, … задачі/про
місія …
блеми
цільові
установки)
Потенціал
поле проектів
(види
…
діяльності
механізми
управління і т.п.
модель
критеріїв
SWOT –
аналіз
потенціал
D0 , D0 X
f fi , i I
бажаний стан
( G ) “як має
бути”
D0 , D1
G, G X
модель цільових
установок
поточний
стан “як є”
f , D0

130.

Метод аналізу “витрати-ефект”

131.

сумарний ефект
Математичні методології
(функціонування ♦ D0 G 0 ♦
класична оптимізація)
x
*
потенціал
цільова установка
f , D0
f , D0 , G, D0 G 0, G x*
G
сумарні витрати
x*
G
D0

132.

сумарний ефект
Математичні методології
(розвиток ♦ D0 G 0 ♦ системна
оптимізація)
x
*
цільова установка
потенціал
G
f , D0
f
f
, D , G, D G 0, G x
0
1
, D0 , G, D0 G 0
1
1
1
x*
сумарні витрати
x*
G
D0
G
G
D0 D1
D1
*

133.

Постановка задачі системної
оптимізації для оргсистем, що
формалізуються в класі
багатокритеріальних задач
лінійного програмування

134.

Модель оргсистеми
f , D0
n 0
0
D0 x : alj x j bl , l Q 1,..., m , j J 1,..., n
j 1
n
f f i x cij x j opt , i I 1,..., M I1 I 2
j 1

135.

Модель цільових установок
G
Задача системної оптимізації виникає, якщо:
1. G D0 0;
2. alj0 , bl0 , cij , l Q, j J , i I
alj , bl , cij , l Q, j J , i I
a alj , l Q0 , Q0 Q, j J
b bl , l Q0 , Q0 Q
c ci , i I 0 , I 0 I
P0 a, b, c - задає ОПР на основі реальних
можливостей задачі в процесі її рішення

136.

Потрібно побудувати нову модель
оргсистеми
f , D1
при якій D1 G 0 на основі зміни початкової моделі
оргсистеми f , D0 у відповідності з
в межах P0
G
f x f x , i I
x k , x k D1 : f i x k f i x , i I1
k
i
i
x G
з урахуванням специфіки реальної задачі.
2

137.

Алгоритм системної оптимізації з
моделлю цільових установок у
просторі рішень

138.

Постановка задачі
G x , x D
f f x f
*
*
0
*
i
*
i min
i
, f i max ,
f i min min f i x
x D0
f i max max f i x , i I
x D0
I I1 , f i 0 f i max , i I
Потрібно побудувати D1 шляхом зміни D0 в межах P0 , в якій
x D1 , x D1 : f i x f i x , i I
*
k
k
*

139.

Алгоритм
1. Визначення узгодженості цілей оргсистеми з G
x0k - ефективний розв’язок f , D0 , знайдений методом *
обмежень при заданому векторі переваг критеріїв
f
wi x* f i 0 f i x
0
i
f i min , i I
*
*
*
i w j x wh x , i, j, h I , i j, h q
q I
x* f x* f 0 , f min w x* * x0k
i w j f j x* / w j f j x* , i I
*
Вважаємо
j I
j i
q I j I
j q
f i x* f i x0k , i I , x* D0
і хоча б одна з нерівностей строга.

140.

w1
*
WD0
w x*
wx
w x0k
*
w2

141.

n
2. Визначимо Q l : a x* b , l Q , Q Q
lj j
0
0
l
Теорема
j 1
Якщо f i x* f i x0k , i I , і хоча б одна нерівність
строга, то допустимі розв’язки D , які знаходяться на
0
гіперплощинах з номерами з множини Q , є
0
ефективними розв’язками по множині критеріїв f
3. Побудуємо область варіацій параметрів для Q0

142.

alj , bl , l Q0 , j J :
alj , bl , l Q0 , j J :
n
n
x* a b b 0 a 0 x , l Q
j
lj
l
l
lj
j
0
j 1
j 1
bl bl0 , bl0 0, l Q0
P
bl bl0 , bl 0, l Q0
alj alj0 , alj0 0, l Q0 , j J
alj alj0 , alj0 0, l Q0 , j J

143.

P P0 0 :
4. Задачі вибору варіацій параметрів
.
min
a , b P P0
alj , bl , l Q0 , j J :
C a, b
C a, b - функція витрат, пов’язаних зі змінами
параметрів D
0
. opt F
a , b P P0
F alj , blj , l Q0 , j J - множина критеріїв,
де величина зміни кожного параметра суттєвих обмежень Q0
виступає як окремий критерій, який в залежності від
фізичної суті може максимізуватися або мінімізуватися.

144.

alj0 , l Q / Q0
alj 0
alj alj , l Q0 , j J
bl0 , l Q / Q0
bl 0
bl bl , l Q0
n
D1 x : alj x j bl , l Q, j 1, n
j 1

145.

Твердження 1
Якщо серед обмежень D0 є:
Q l : alj0 0, bl0 0, j 1, n, l Q 0,
то область D1 побудована за рахунок зміни параметрів обмежень
Q0 згідно з P є обмеженою та замкнутою.
Якщо Q 0, D0 - замкнута та обмежена, то, щоб D1 була
обмеженою та замкнутою, додамо до D0
n
x j bm 1 0 - наслідок системи D0
j 1
n
bm 1 max x j
x D0
j 1
n
n
*
*
a
x
b
b
x
m 1
m 1
j
m 1 j j
j 1
j
P : am 1 j 1, j 1, n
bm 1 bm 1

146.

P P0 P 0 : alj , bl , l Q0 m 1 , j J
n
D1 x : alj x j bl , l Q, j J ,
j 1
n
am 1 j x j bm 1
j 1
am 1 j am 1 j 1,
bm 1 bm 1 bm 1
1
*
*
k
x* f x* , f 0 1 , f min
w
f
x
w
x
x
1
1 1

147.

Твердження 2
x k , x k D1 : f i x k f i x* , i I ,
x arg min max i 1 wi 1 x ,
k
x D1
де
i I
wi 1 x , i 1 wi 1 x побудовані для f , D1

148.

Загальна постановка задачі
системної оптимізації

149.

Модель оргсистеми
f , D0
D0 x : gl x 0, l Q 1,..., m , x x j , j J 1,..., n
f f i x max, i I1 , f i x min, i I 2 , I1 I 2 I 1,..., M

150.

Модель цільових установок
G
f , f , i I : G x : f f x f , i I , x
x x , j J : G x : x x , j J
x , x , j J : G x x x , j J
f * f i * , i I : G x : f i * f i x , i I1 , f i * f i x , i I 2 , x j 0, j J
i Н
*
i В
i Н
*
j
j Н
X:
opt L x :
x X
*
j
j
j В
j Н
j
G X
G arg opt L x
x X
i В
i
j В
j
0, j J

151.

Задача системної оптимізації
виникає, якщо
G D0 0 або G 0
Q0 l : l Q, D0 G 0 , Q0 Q
- множина індексів обмежень D0 , через які G D0 0 :
I 0 i : i I , G 0 , I 0 I
- множина індексів критеріїв f , через які G 0 :
2. pl , l Q0
- вектори варіацій параметрів обмежень
з індексами з множини Q0
pi , i I 0 - вектори варіацій параметрів критеріїв
з індексами з множини I 0
P0 pl , l Q0 , pi , i I 0
Обмежену область обмежень на варіації параметрів задає ОПР
на основі реальних можливостей задачі в процесі її
рішення.
1.

152.

P pl , l Q0 , pi , i I 0
-
область обмежень на варіації параметрів з індексами з
множин Q0, I 0 , яка математично забезпечує побудову D1
так, що D1 G 0
, або переформування множини
критеріїв f при G 0 на f1 таким чином, що G 0 , без
врахування реальних можливостей P0 по зміні параметрів
системи.
Задача системної оптимізації полягає в побудові f1 , D1
шляхом зміни параметрів f , D0 в межах P0 , що D1 G 0
,
(при D0 G 0), або G 0 (при f1 ) з урахуванням
специфіки задачі.

153.

1.
2.
3.
4.
Специфічні особливості задачі
системної оптимізації
Модель оргсистеми представлена f , D0 ,
або D0 .
Необхідний ступінь узгодженості цілей
оргсистеми з моделлю цільових установок G.
Необхідний ступінь узгодженості D1 та G :
G D1 , або G D1 0.
В практичних задачах ОПР має різні
можливості по формуванню P0 .

154.

Кінець