Математичне програмування. Основні поняття та визначення

1. Навчально-науковий інститут комп’ютерних інформаційних технологій Кафедра комп’ютеризованих систем управління

Навчальна дисципліна
«МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ»
для спеціальності
6.05010202 «Системне програмування»
Курс 3
Лекцій
Лабораторних занять
Самостійна робота
Всього
Домашнє завдання
Екзамен
Семестр 5
34 години
34 години
67 година
135 годин
1 (5 семестр)
5 семестр

2. ГЛОБАЛЬНА ПРОБЛЕМА

3. ВИРОБЛЕННЯ РІШЕНЬ НА ОСНОВІ МАТЕМАТИЧНОЇ МОДЕЛІ

4. ВИРОБЛЕННЯ РІШЕНЬ НА ОСНОВІ ІМІТАЦІЙНОЇ МОДЕЛІ

5. ВИРОБЛЕННЯ РІШЕНЬ НА ОСНОВІ ЕКСПЕРТНОЇ МОДЕЛІ

6.

Математичне програмування –
науковий напрямок, присвячений
розробці та дослідженню чисельних
методів розв’язання екстремальних
(оптимізаційних) задач.

7.

«В мире не происходит ничего,
в чем не был бы виден смысл
какого-либо максимума или
минимума»
Леонард Эйлер (1707-1783).
Гражданин Швейцарии,
автор 800 научных работ.
Академик Петербургской АН (1731-1741).
Академик Берлинской АН (1741-1766).

8.

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

9.

Студент повинен знати:
● теоретичні основи математичного програмування;
● принципи побудови математичних моделей задач прийняття
проектних та управлінських рішень;
● основні методи і алгоритми лінійного, нелінійного,
цілочисельного, дискретного, динамічного програмування;
Студент повинен вміти:
● будувати математичні моделі задач прийняття проектних та
управлінських рішень;
● визначати, до якого класу задач математичного програмування
належить формалізована функціональна задача;
● вибирати для її розв’язання відповідний метод і алгоритм
оптимізації;
● розробляти схеми алгоритмів розв’язання задач оптимізації;
● застосовувати існуючі уніфіковані програмні засоби розв’язання
оптимізаційних задач;
● аналізувати та інтерпретувати результати розв’язання
функціональних задач.

10.

ЛІТЕРАТУРА
1. Кутковецький В.Я. Дослідження операцій // Навчальний посібник для студентів
ВНЗ. – Київ: Професіонал, 2004. – 349 с.
2. Ларіонов Ю.І., Марченко Л.С., Хажмурадов М.А. Дослідження операцій //
Навчальний посібник. – Харків: Інжек, 2005. – 288 с.
3. Охріменко М.Г., Дзюбан І.Ю. Дослідження операцій // Навчальний посібник. –
Київ: Центр навчальної літератури, 2006. – 183 с.
4. Ржавський С.В., Александрова В.М. Дослідження операцій // Підручник. – Київ:
Академвидав, 2006. – 560 с.
5. Зайченко Ю.П. Дослідження операцій. – Київ: ВІПОЛ. – 2000. – 688 с.
6. Васильев Ф. П. Численные методы решения экстремальных задач. – М.: Наука. –
1980. – 520 с.
7. Исследование операций: В 2-х томах./Под ред. Дж. Моудера, С.Элмаграба. – М.:
Мир. – 1981. т.1- 712 с., т.2. – 677 с.
8. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. – М: Мир. – 1985. –
512 с.
9. Таха Х. Введение в исследование операций: - в 2-х томах.М.: Мир. –1985. – Т.1 –
479 с. - Т.2- 496 с.
10. Химмельблау Д. Прикладное нелинейное программирование. – М.: Мир. – 1975.
– 536с.
11. Вентцель Е.С. Исследование операций. – М.: Наука. – 1980. – 208 с.

11. Тема 1. ОСНОВНІ ПОНЯТТЯ ТА ВИЗНАЧЕННЯ

1.1 Області застосування методів оптимізації
1.2 Загальна постановка ЗМП
Критеріальна (цільова) функція:
f ( x) opt (min, max)
(1)
Система обмежень:
h j ( x) 0, j 1, m
g j ( x) 0, j m 1, p
Умови:
x E n , x ( xi ; i 1, n)
(2)
(3)

12. Приклад побудови математичної моделі ЗПР (1)

Вхідні дані:
m – кількість підприємств (i 1, m) ;
n
– кількість видів виробів ( j 1, n) ;
r
– кількість типів ресурсів ( k 1, r ) ;
pj
– план виробництва виробів j -го виду;
a jk
– норматив витрат ресурсів k -го типу на одиницю
виробів j -го виду;
bik – об’єм ресурсів k -го типу на i -му підприємстві;
cij – витрати на випуск одиниці виробів j -го виду на i му підприємстві.

13. Приклад побудови математичної моделі ЗПР (2)

Необхідно: так розподілити планове завдання між
підприємствами, щоб сумарні витрати на випуск
виробів були мінімальні.
Шукані змінні:
xij
– план випуску виробів j -го виду на
i -му підприємстві; i 1, m ; j 1, n .
Модель:
m
n
f ( x) cij xij min ;
i 1 j 1
m
xij
i 1
n
pj ;
a jk xij bik ;
j 1
j 1, n ;
i 1, m ; k 1, r ;
xij 0 ; i 1, m ; j 1, n .

14.

1.3 Класифікація ЗМП
Математичне
програмування
Лінійне
програмування
Цілочисельне програмування
Дискретне
програмування
Комбінаторне
програмування
Нелінійне
програмування
Динамічне
програмування
Стохастичне
програмування
Потокове
програмування
Геометричне
програмування

15.

1.4 Терміни та визначення
1.4.1 Допустимість
1.4.2 Область допустимих розв’язків (ОДР)
1.4.3 Оптимальність
1.4.4 Унімодальні та мультимодальні функції

16. Рис. 1.2

f(x)
ρ
ρ
a
x1
x2
x3
Рис. 1.2
x4
x5
x6
b
x

17.

*
1.4.5 Глобальний мінімум x :
f ( x* ) f min min{ f ( x); x R};
x* arg min f ( x) .
x R
*
1.4.6 Локальний мінімум x :
min{ f ( x); x R0 } ;
f ( x* ) f min
x * arg min f ( x) ,
x R0
R0 {x R : x * x } .
1.4.7 Стаціонарні точки
1.4.8 Наближений оптимальний розв’язок
f ( x * ) f min .
x* :

18.

1.4.9 Опуклість та увігнутість
(x)
(x )
x
x1
x
x2
Опукла функція
Функція
x
x1
x
x2
Увігнута функція
(x) опукла в області R , якщо:
[ x1 (1 ) x2 ] ( x1 ) (1 ) ( x2 ) ;
x1 R ; x2 R ; 0 1 .
Функція
(x) увігнута в області R , якщо:
[ x1 (1 ) x2 ] ( x1 ) (1 ) ( x2 ) ;
x1 R ; x2 R ; 0 1.
Строго опуклі та строго увігнуті функції.

19.

Приклад
Визначити, опукла чи увігнута функція
( x) 2 x 2 5 x 7
при x1 0 ; x2 3 ; 0,3 :
(0,7 3) (2,1) 5,31
0,3 (0) 0,7 (3) 2,1 0,7 10 9,1
(0,7 3) 0,3 (0) 0,7 (3)
2
Висновок: функція ( x) 2 x 5 x 7 опукла.

20.

Множина Q , Q E n , опукла, якщо для будь-якої пари
x(1) Q та x( 2) Q
x ( x
(1)
, x ( 2 ) ) ( x Q) ;
x x (1) (1 ) x ( 2) ; 0 1.

21. Рис. 1.4

x2
x(2)2
x(2)
x`
x(1)2
x(1)
Q
x(1)1
x(2)1
Рис. 1.4

22.

Область допустимих рішень ЗМП з обмеженнями-нерівностями опукла,
якщо:
( j 1, m) g j ( x) 0 & g j ( x) опукла g j ( x) 0 & g j ( x) увігнута

23.

1.4.10 Градієнт функції
f (x)
(k )
(k )
(k )
(k )
n
в точці x ( x1 , x2 , ..., xn ) E :
(k )
f ( x )
f ( x (k ) )
x1
(k )
f (x )
x2
.
.
f ( x (k ) )
xn

24.

Приклад
f ( x) 2 x12 3x32 4 x 2 x3 5 x1 6 x 2 ; x ( k ) (2, 0, 1) .
f ( x)
f ( x)
4 x1 5 f ( x) 4 x 2 6
6 x3 4 x 2
.
;
;
x1
x3
x2
3
f ( x (k ) ) 6
.
6

25.

Рис.1.5

26.

(k )
(k )
(k )
(k )
n
1.4.11 Апроксимація функції f (x) в точці x ( x1 , x2 , ..., xn ) E :
● лінійна:
f ( x) f ( x ( k ) ) T f ( x ( k ) ) ( x x ( k ) ) ;
● квадратична:
1
f ( x) f ( x ( k ) ) T f ( x ( k ) ) ( x x ( k ) ) ( x x ( k ) ) T H ( x ( k ) ) ( x x ( k ) ) .
2

27.

Матриця Гессе для функції
f (x) в точці
x ( k ) ( x1( k ) , x2( k ) , ..., xn( k ) ) E n :
2 f ( x (k ) )
2 f ( x (k ) )
...
x2
x1 xn
1
H ( x (k ) ) 2 f ( x (k ) )
...
...
...
2
(k )
2
(k )
f ( x ) ... f ( x )
2
x x
x
n
1
n

28.

Приклад
f ( x) 2 x12 x 2 3x 22 x3 4 x1 x 2 x3 5 x1 x 22 6 x1 7 x3 ; x ( k ) (2, 0, 1) .
f ( x)
4 x1 x 2 4 x 2 x3 5 x 22 6 ;
x1
f ( x)
2 x12 6 x 2 x3 4 x1 x3 10 x1 x 2 ;
x2
f ( x)
3 x 22 4 x1 x 2 7 .
x3
2 f ( x)
2 f ( x)
2 f ( x)
4 x 2 ;
4 x1 4 x3 10 x 2 ;
4 x 2 ;
2
x1 x2
x1
x1 x3
2 f ( x)
2 f ( x)
2 f ( x)
4 x1 4 x3 10 x 2 ;
6 x3 10 x1 ;
6 x 2 4 x1 ;
x2 x1
x 2 x3
x22
2 f ( x)
4 x 2 ;
x3 x1
2 f ( x)
6 x2 4 x1 ;
x3 x 2
2 f ( x)
0.
2
x3

29.

1.5 Необхідні та достатні умови оптимальності
розв’язку ЗМП
f ( x) min ; x E n .
x
*
– оптимальний розв’язок задачі, якщо:
*
f
(x
)
x
1)
диференціюєма в ;
*
f
(
x
) 0;
2)
2
*
f
(
x
) 0.
3)

30.

Рис.1.6

31. Тема 2. ЛІНІЙНЕ ПРОГРАМУВАННЯ

2.1 Канонічна форма ЗЛП
n
f ( x) c j x j min
j 1
n
g i ( x) aij x j bi ; i 1, m ;
j 1
xj 0;
j 1, n .

32.

2.2 Основні поняття та визначення
Допустимі розв’язки ЗЛП.
Оптимальні розв’язки ЗЛП.
Варіанти:
m=n
m<n
m>n
Сумісність системи обмежень.
Ранг матриці коефіцієнтів rA .
Ранг розширеної матриці rB .
Ранг системи обмежень rC .

33.

Приклад
2 x1
x2
x1
x1
x2
x3 x4 1
2 x3
2 x1 x2 x3 4
4 x1 2 x2 2 x3 1
2
3
rA rB rC 3.
rA 1;
rB 2 ; rA rB .

34.

Лінійно незалежні обмеження
Приклад
x1
x2
x3 x4 2
x1
3x1
x2
x2
x3 x4 1
3 x3 x 4 0
rA rB rC 2

35.

Базисні та вільні змінні:
x1 g1 ( xm 1 , ..., xn )
……………………
xm g m ( xm 1 , ..., xn )
n m ; rA rB rC m .
Приклад
2 x1
x1
x1
x2
n 4;
x2 x3 x4 1
x2 2 x3 x4 2
3 x3
5 3x3 x4
rA rB rC 2 .

36.

2.3 Геометрична інтерпретація ЗЛП
Приклад
f ( x) x1 x2 2 x3 x4 3x5 x6 2 x7 min
x1 x2 x3 4
2 x1 x2 x3 x4 5
x1 x2 x5 4
x 2 x6 5
2 x1 2 x2 x6 2 x7 7
x j 0 ; j 1, 7 .
rA rB rC m 5 ;
n m 2.

37.

Вільні змінні: x1 та x 2 .
Базисні змінні: x3 , ..., x7 .
x3 x1 x2 4
x4 3x1 2 x2 1
x5 x1 x2 4
x6 x 2 5
1
x7 x1 x2 6
2

38.

Область допустимих рішень:
Рис. 1.7

39.

ЗНАХОДЖЕННЯ ТОЧКИ ОПТИМАЛЬНОГО РІШЕННЯ
f ( x) 5 x1 2 x2 12
f ( x) 5 x1 2 x2
Рівняння основної прямої:
f ( x) 5 x1 2 x2 0 .
Переміщення основної прямої:
f ( x) 5 x1 2 x2 C 0 .

40.

Рис. 1.8

41.

Оптимальне рішення:
*
*
x1* 8,5 ; x2 5 ; x3 0,5 ; x4 16,5 ;
x5* 17,5 ; x6* x7* 0 ;
*
f * 64,5 .

42.

Висновки:
1. Область допустимих рішень ЗЛП – опуклий
багатогранник.
(Опорні точки. Опорні рішення.)
2. У кожній опорній точці k n m змінних дорівнює
нулю.
3. Оптимальне рішення ЗЛП знаходиться на границі
ОДР: у вершині або на грані багатогранника,
найбільш віддаленої від початку координат у
напрямку спадання значень функції f (x) .

43.

Рис. 1.9

44.

2.4 Ідея симплекс-методу
f ( x) 0 ( 1 x1 2 x2 ... k xk ) min
xk 1 k 1 ( k 1,1x1 k 1, 2 x2 ... k 1,k xk )
xk 2 k 2 ( k 2,1x1 k 2, 2 x2 ... k 2,k xk )
……………………………………
xn n ( n,1x1 n, 2 x2 ... n,k xk ) .
x ( x1 , x2 , ..., xk , xk 1, ..., xn ) :
x1 x2 ... xk 0 ;
xk 1 k 1 ;
xk 2 k 2 ;…; xn n .
( i k 1, n)( i 0) x – опорне рішення.
( i : k 1 i n)( i 0)
x
– недопустиме рішення.

45.

Нехай i 0 ; k 1 i n .
Припустимо, ( j * :1 j * k )( i , j 0) .
*
Тоді ( x j ) ( xi ) .
*
I (j* ) i : (k 1 i n) & ( i , j* 0) & ( i 0) ( i , j* 0) & ( i 0)

46.

Границя збільшення x j :
*
0 i i , j* x max
(i ) ,
j*
звідки
x
max
j*
i
(i )
i I (j ) .
;
i , j*
*
Вибір xi * :
i*
( )
i
min ; i I j* .
i* j *
ij*
Заміна базисних змінних: xi x j .
*
*

47.

( i k 1, n)( i 0) & ( j 1, k )( j 0) x
оптимальне рішення.
f opt 0 .
*
*
(
j
:
1
j
k )( j* 0) .
Нехай
Тоді
( x j * ) [ f ( x ) ] .
I (j* ) i : (k 1 i n) & ( i , j* 0) .
i : k 1 i n (
i , j*
0) [ f ( x) ]
–

48.

Границя збільшення
x j* :
0 i i , j* x max
(i ) ,
j*
звідки
x
Вибір
max
j*
i
( )
(i )
i
I
;
j* .
i , j*
xi * :
i*
(
)
min i ; i I j* .
i* j *
ij*
Заміна базисних змінних: xi x j .
*
*

49.

2.5 Табличний алгоритм заміни базисних змінних
f ( x) 0 ( 1 x1 ... j x j ... k xk ) min
xk 1 k 1 ( k 1,1 x1 ... k 1, j x j ... k 1,k xk )
………………………………………..
xi i ( i ,1 x1 ... i , j x j ... i ,k xk )
……………………………………
xn n ( n,1x1 n, 2 x2 ... n,k xk ) ;
i k 1, n ;
j 1, k .
Заміна базисних змінних: xi x j ;
*
k 1 i* n ;
Дозволяючий рядок
Дозволяючий стовпчик
Дозволяючий елемент
*
1 j* k .

50.

0 , i
x1
f (x)
0
1
xk 1
k 1
k 1,1
…
k 1, j
…
…
…
…
…
xi *
i
i
…
…
…
…
…
xn
n
n ,1
…
*
*
,1
…
…
x j*
i
xk
k
*
…
k 1, k
…
…
…
i
…
…
…
n, j
…
n, k
i
*
, j*
*
*
*
,k

51.

Приклад
f ( x) 0 ( 1 x1 2 x2 3 x3 ) min
x4 4 ( 41x1 42 x2 43 x3 )
x5 5 ( 51x1 52 x2 53 x3 )
x6 6 ( 61x1 62 x2 63 x3 )
x j 0 ; j 1, 6

52.

x2 x5
x2
5 51
1
x1
x5 53 x3
52 52
52
52
x4 4 42 5 41 42 51 x1 42 x5 43 42 53 x3
52
52
52
52
62
62 5
62 51
62 53
61
x1
x5 63
x3
x6 6
52
52
52
52
f ( x) 0 2 5 1 2 51 x1 2 x5 3 2 53 x3
52
52
52
52

53.

Правила перетворення:
1
H
C ;
1)
i ,j
i , j
*
*
*
2)
3)
iH* , j
H
i , j*
*
C
H
i*
*
j {1, ..., k} \ { j } ; i*
iC* , j*
iC* , j
iC* , j*
;
H
C
4) i , j i , j
C
i , j*
C
i* , j *
; i {k 1, ..., n} \ {i } ;
*
iC , j iC, j
*
iC , j
*
H
i
H
0
C
0
C
j*
iC , j
*
*
C
i
C
i*
;
*
Hj*
; i {k 1, ..., n} \ {i } ;
*
;
Cj*
iC* , j*
;
j {1, ..., k} \ { j *} ;
*
iC iC, j
*
H
j
*
C
j
i {k 1, ..., n} \ {i*} ;
;
C
i* , j*
Cj iC , j
*
*
C
i* , j*
;
j {1, ..., k} \ { j *} .

54.

0 , i
f (x)
xk 1
0
k 1
…
*
*
,j
1
*
*
k 1, j i
*
i
*
*
k 1,1
…
n
i ,1 j
*
i
*
i
…
…
n, j i
*
,j
*
*
n ,1
…
…
…
i ,1 n , j
*
i
*
*
,j
*
*
…
…
…
j*
…
i* , j *
…
1
i
*
xk
k
i* , j *
k 1, j*
, j*
…
i* ,1
i* , j *
*
*
x j*
*
*
i*
i* , j *
i
,j
*
i ,1 k 1, j
, j*
…
xi *
xn
i j
i
…
x1
k 1, k
…
…
i* , j *
*
i
i
*
j*
,k
*
,k
, j*
k 1, j *
i
*
, j*
…
i* ,k
i* , j *
, j*
…
n , j*
i
…
…
…
n, k
i
*
,k
n, j *
i
*
, j*

55.

2.6 Знаходження опорного рішення
f ( x) 0 ( 1 x1 ... j x j ... k xk ) min
xk 1 k 1 ( k 1,1 x1 ... k 1, j x j ... k 1,k xk )
………………………..……………………..
xi i ( i ,1 x1 ... i , j x j ... i ,k xk )
………………………….……………
xn n ( n,1x1 n, 2 x2 ... n,k xk ) ;
i k 1, n ; j 1, k .
Рішення x ( x1, x2 , ..., xk , xk 1, ..., xn ) :
x1 x2 ... xk 0 ; xk 1 k 1 ; xk 2 k 2 ;…;
Припустимо, ( i : k 1 i n)( i 0) .
xn n .

56.

ПРАВИЛА ВИБОРУ ДОЗВОЛЯЮЧОГО ЕЛЕМЕНТА
i : i 0 ; k 1 i n .
вибирається коефіцієнт i , j 0 ;
1) Вибирається рядок
2)
В
рядку
i
*
1 j* k
(дозволяючий стовпчик).
( j 1, k )( i j 0) рішень немає.
*
3) В дозволяючому стовпчику j виділяються елементи, які мають
однакові знаки зі своїми вільними членами:
I (j* ) i : (k 1 i n) & ( i , j* 0) & ( i 0) ( i , j* 0) & ( i 0) .
4) Обчислюються відношення
i
ij*
( )
; i I j* .
5) В якості дозволяючого елемента обирається коефіцієнт
i*
( )
i
min ; i I j* .
i* j *
ij*
i
* *
j
:

57.

Приклад
x4 1 x1 2 x2 x3
x5 5 2 x1 x2 x3
x6 2 x1 x2
x7 1 x2 x3
x4 1 ( x1 2 x2 x3 )
x5 5 ( 2 x1 x2 x3 )
x6 2 ( x1 x2 )
x7 1 ( x2 x3 )

58.

Приклад
р/ст.
x4
x5
р/стр.
x6
x7
i
x1
x2
x3
i / ij
1
-5
2
1
-1
-2
1
0
-2
1
1
-1
1
-1
0
1
5/2=2,5
2/1=2
Заміна базиса: x1 x6 .
р/ст.
р/стр.
x4
x5
x1
x7
i
x6
x2
x3
i / ij
3
-1
2
1
1
2
1
0
-3
3
1
-1
1
-1
0
1
3/1=3
-1/-1=1
1/1=1
Заміна базиса: x3 x5 .
x4
x3
x1
x7
i
x6
x2
x5
2
1
2
0
3
-2
1
2
2
-3
1
2
1
-1
0
1
Опорне рішення: x1 2 ; x2 0 ; x3 1 ;
x4 2 ;
x5 0 ;
x6 0 ;
x7 0 .

59.

2.7 Пошук оптимального рішення
f ( x) 0 ( 1 x1 ... j x j ... k xk ) min
xk 1 k 1 ( k 1,1 x1 ... k 1, j x j ... k 1,k xk )
………………………………………..
xi i ( i ,1 x1 ... i , j x j ... i ,k xk )
……………………………………
xn n ( n,1x1 n, 2 x2 ... n,k xk ) ;
j 1, k .
i k 1, n ;
Рішення x ( x1 , x2 , ..., xk , xk 1 , ..., xn ) ;
x1 x2 ... xk 0 ; xk 1 k 1 ; xk 2 k 2 ;…; xn n ;
( i k 1, n)( i 0) .
( j : 1 j k )( j 0) x – оптимальне рішення.
Припустимо, ( j : 1 j k )( j 0) .

60.

ПРАВИЛА ВИБОРУ ДОЗВОЛЯЮЧОГО ЕЛЕМЕНТА
*
1) Вибирається дозволяючий стовпчик j : j* 0 .
2) В дозволяючому стовпчику
j
*
виділяються від’ємні елементи:
I (j* ) {i : (k 1 i n) & ( ij* 0)} .
[ i : (k 1 i n)]( ij* 0) f (x)
необмежена знизу
3) Обчислюються відношення
i
ij*
;
i I (j* ) .
4) В якості дозволяючого елементу вибирається коефіцієнт
i*
( )
i
min ; i I j* .
i* j *
ij*
i
* *
j
:

61.

Приклад
f ( x) x1 2 x2 x3 min
x4 2 x1 x2 2 x3
x5 1 x1 x2 x3
x6 2 x2 x3
xi 0 ; i 1, 6 .
Стандартна форма:
f ( x) 0 ( x1 2 x2 x3 ) min
x4 2 ( x1 x2 2 x3 )
x5 1 ( x1 x2 x3 )
x6 2 ( x2 x3 )
xi 0 ; i 1, 6 .
f ( x)
р/стр.
x4
x5
x6
р/ст.
0 , i
x1
x2
x3
i / ij
0
2
1
5
-1
1
1
0
2
1
-1
1
1
-2
1
1
1/1=1
5/1=5

62.

1) Заміна базиса: x5 x3 .
f ( x)
x4
x3
р/стр.
x6
0 , i
-1
4
1
4
x1
р/ст.
x2
x5
i / ij
-2
3
1
-1
3
-1
-1
2
-1
2
1
-1
4/2=2
i / ij
2) Заміна базиса: x6 x2 .
f ( x)
р/стр.
x4
x3
x2
0 , i
x1
x6
р/ст.
x5
-7
6
3
2
-1/2
5/2
1/2
-1/2
-3/2
1/2
1/2
1/2
1/2
3/2
1/2
-1/2
6/(3/2)=4
3/(1/2)=6
3) Заміна базиса: x4 x5 .
f ( x)
x5
x3
x2
0 , i
x1
x6
-9
4
1
4
-4/3
5/3
-1/3
1/3
-5/3
1/3
1/3
2/3
Оптимальний розв’язок:
x1 0 ; x2 4 ; x3 1 ;
x4 0 ;
x5 4 ;
x4
-1/3
2/3
-1/3
1/3
x6 0 ;
f opt 9 .

63.

Тема 3. Цілочисельне
програмування
n
f ( x) c j x j min ;
j 1
n
aij x j bi ;
j 1
xj 0; xj
i 1, m ;
– цiле;
j 1, n .

64.

3.1 Метод відсікання (відсікаючих площин) Р.Гоморі
Таблична форма:
xi i
j J C
ij
xj ; i I B .
Нехай xi i цiле ; i I B .
[ ij ] , [ i ] – найбільші цілі:
[ ij ] ij ; [ i ] i .

65.

Формування відсікаючого обмеження
xi
j J
[
j J C
xi
i j
x j i .
(3.1)
C
i j
]xj
[
i j
xj ;
j J C
i j
] x j i
j J C
xi
[
j J
C
i j
] x j [ i ] .
(3.2)

66.

Після віднімання (3.2) від (3.1):
i j
xj
j J C
(
j J C
[
j J C
i j
i j
] x j i [ i ] ;
[ i j ] ) x j i [ i ] .
ij ij [ ij ] ;
j JC;
i i [ i ] ;
0 i 1.
Відсікаюче обмеження:
i j x j i .
j J C
0 ij 1 ;

67.

Перетворення в рівняння:
i j
j J C
x j xn 1 i ; xn 1 0 ;
xn 1 i
i j
j J
xj .
(3.3)
C
Лемма. Якщо відсікання (3.3) додається до
симплексної таблиці задачі лінійного програмування,
то ніякі цілочисельні допустимі точки не виключаються.
Нова таблиця є допустимою, якщо i – ціле число, та
недопустимою в противному випадку.

68.

Приклад
f ( x) 7 x1 9x2 min
x1 3x2 x3 6
7 x1 x2 x4 35
x j 0 ; x j – ціле; j 1, 4 .
Перетворена система обмежень:
x3 6 x1 3x2
x4 35 7 x1 x2

69.

Вихідна симплексна таблиця №1 послабленої задачі:
f (x)
x3
x4
0 , i
x1
x2
0
6
35
7
-1
7
9
3
1
Кінцева симплексна таблиця №2 послабленої задачі:
f (x)
x2
x1
0 , i
x4
x3
-63
7/2
9/2
15/11
1/22
3/22
28/11
7/22
-1/22

70.

Розв’язок послабленої задачі:
x1 4.5 ; x2 3.5 ; x3 x4 0 ; fmin 63 .

71.

72.

7 1
7
x4 x3
2 22
22
1
1
2 3 ; [ 2 ] 3 ; 2
2
2
1
1
24 ; [ 24 ] 0 ; 24
22
22
7
7
23 ; [ 23 ] 0 ; 23
22
22
x2
Рівняння відсікання для x2 :
1 7
1
x5 x3 x4 .
2 22
22
1 1
7
x5
x4 x3
2 22
22

73.

Початкова симплексна таблиця №3, доповнена відсіканням для x2 :
0 , i
x4
x3
-63
15/11
28/11
f (x)
7/2
1/22
7/22
x2
x1
9/2
3/22
-1/22
x5
-1/2
-1/22
-7/22
Кінцева симплексна таблиця №4, доповнена відсіканням для x2 :
x5
x4
0 , i
-59
1
8
f (x)
x2
3
0
1
x1
32/7
1/7
-1/7
x3
11/7
1/7
-22/7

74.

Розв’язок задачі, доповненої відсіканням для x2 :
x1 32 / 7 ; x2 3 ; x2 11/ 7 ; x4 0 ; fmin 59 .

75.

32 1
1
x4 x5
7 7
7
4
4
1 4 ; [ 1 ] 4 ; 1
7
7
1
1
14 ; [ 14 ] 0 ; 14
7
7
1
1
6
15 ; [ 15 ] 1 ; 15 ( 1)
7
7
7
x1
Рівняння відсікання для x1 :
4 1
6
x6 x4 x5 .
7 7
7
4 1
6
x6 x4 x5
7 7
7

76.

Початкова симплексна таблиця №5, доповнена відсіканням для x1 :
f (x)
x2
x1
x3
x6
0 , i
x4
x5
-59
3
32/7
11/7
-4/7
1
0
1/7
1/7
-1/7
8
1
-1/7
-22/7
-6/7
Кінцева симплексна таблиця №6, доповнена відсіканням для x1 :
f (x)
x2
x1
x3
x4
0 , i
x6
x5
-55
3
4
1
4
7
0
1
1
-7
2
1
-1
-4
6

77.

Розв’язок вихідної (цілочисельної) задачі:
x1 4 ; x2 3 ;
x3 1 ; x4 4 ; fmin 55 .

78.

3.2 Метод гілок та границь
n
f ( x) c j x j min ;
j 1
n
aij x j bi ;
j 1
(3.4)
i 1, m ;
(3.5)
0 x j d j ; x j – ціле; j 1, n .
(3.6)
Кількість планів (варіантів розв’язку задачі)
n
G (d j 1) .
j 1
x ( x j j 1, n ) :

79.

Приклад
0 x1 3 ; 0 x2 1 ; 0 x3 2 .
G 4 2 3 24 :
0 0 0
0 0 1
0 0 2
..........
....
1 1 2
G 2 0 0
2 0 1
..............
3 1 0
3 1 1
3
1
2

80.

( xi i цiле) розбивання G :
xi [ i ] ;
G2 G : xi [ i ] 1 ; G1 G2 .
G1 G :
Додаткові обмеження:
для G1 :
для G2 :
xn 1 [ i ] xi ; xn 1 0 ;
xn 1 [ i ] 1 xi ; xn 1 0 .

81.

На k -му кроці:
G (k ) ; 1, k .
x ( k ) arg min( k ) f ( x) ;
x G
(G ( k ) ) f ( x ( k ) ) ; 1, k ;
x* ( x*j j 1, n) ;
( j 1, n)( x j цiле ) .

82.

Алгоритм
1. Перевірка на оптимальність:
f ( x* ) min{ (G ( k ) 1, k } .
2. Перевірка умови завершення обчислень.
(k )
G
3. Вибір * :
(G ( k*) ) min { (G ( k ) ) 1, k } .
4. Розбиття
G ( k*)
на
G ( k*,)1
та
G ( k*,)2 :
G ( k*,)1 : xn 1 [ i* ] xi* ;
xn 1 0 ;
G ( k*,)2 : xn 1 [ i* ] 1 xi* ;
xn 1 0 .
5. Розв’язок послаблених задач ЛП над
G ( k*,)1
та
G ( k*,)2

83.

Приклад
f ( x) 3x1 3x2 13x3 min
x4 8 3x1 6 x2 7 x3
x5 8 6 x1 3x2 7 x3
0 xj 5;
x j цiлe ;
j 1, 3 ;
x4 0 ;
x5 0 .

84.

85.

3.3 Комбінаторна оптимізація
f ( x) ci xi max ;
(3.7)
i I 0
a
i I j
x bj ;
ji i
j 1, n
;
(3.8)
x ( xi i 1, m ) ; xi 0, 1 ; i 1, m .
G X 1 X 2 ... X m ;
X i 0, 1 ; i 1, m ;
G 2m .

86.

Підмножини варіантів: Gk ; k 1, .
Частковий план підмножини Gk :
x C (k ) ( xi i I k0 I k1 )
,
( i I k0 )( xi 0) & ( i I k1 )( xi 1) .
Доповнюючий план підмножини Gk :
x D (k ) ( xi i I k ) ,
( i I k ) ( xi {0, 1}) .
Активні обмеження: J k {1,..., n} .

87.

Модель, приведена у відповідність k -тій підмножині варіантів:
f k ( x)
a
i I jk
1
c
x
c
i i k max ;
i I 0 k
x b jk ; j J k ;
ji i
x ( xi i I k ) ; xi 0, 1 ; i I k .
(3.9)
(3.10)

88.

I 00k I 0 I k0 ; I 01k I 0 I k1 ; I 0 k I 0 I k ;
I 0jk I j I k0 ;
I 1jk I j I k1 ; I jk I j I k ; j 1, n ;
с1k
c
i
;
i I 01 k
b jk b j
a
ij
i I 1jk
, j Jk .

89.

Підмножини та величини, необхідні для дослідження моделі (3.9)-(3.10):
I 03k i I 0 k : ci 0 ;
I 2jk i I jk : a ji 0 ; I 3jk i I jk : a ji 0 ;
I 2jk (i ) i i I 2jk : a ji a ji ;
I 3jk (i ) i i I 3jk : a ji a ji
s (jkp )
a
ji
;
;
p 2, 3 ; j J k ;
p
i I jk
(Gk ) c1k
c
i
i I 03k
;
k 1, .

90.

Аналіз підмножин варіантів
Твердження 1. Підмножина G не містить допустимих
планів, якщо для деякого обмеження j J виконується
умова:
( I 2jk ) & (bjk 0) ( I 2jk ) & (s(jk2) bjk ) .
k
k
Приклади.
a) x1 2 x2 3x3 1 ;
b) 3x1 2 x2 5x3 7 x4 4 x5 9 .

91.

Твердження 2. Обмеження j J не є активним по
відношенню до планів підмножини G , якщо для нього
виконується умова:
( I 3jk ) & (b jk 0) ( I 3jk ) & (s(jk3) b jk ) .
k
k
Приклади.
a) x1 2 x2 3x3 1 ;
b) 3x1 2 x2 5x3 7 x4 4 x5 9 .

92.

Твердження 3. Якщо
виконується умова
I 2jk ( j J k )
та для деякого
i I 2jk
s(jk2) bjk s(jk2) a ji ,
то з доповнюючих планів підмножини G допустимими
можуть бути тільки ті, в яких i I (i ) x 1 .
k
2
jk
i
Приклад.
x1 3x2 2 x3 5x4 4 x5 7 x6 11 .
i 4 ;
a ji 5 ;
x4 x6 1 .

93.

Твердження 4. Якщо
виконується умова:
I 3jk ( j J k )
та для деякого
i I 3jk
( I 2jk ) & (0 bjk a ji ) ( I 2jk ) & (s(jk2) b jk s(jk2) a ji ) ,
то з доповнюючих планів підмножини
можуть бути лише ті, в яких i I (i ) x
3
jk
i
допустимими
0 .
Gk
Приклади.
a) x1 3x2 5 x3 11x4 13 x5 9 ;
i 4 ; a 7 ; x x 0 ;
ji
4
5
b) x1 3x2 5x3 7 x4 9 x5 13x6 9 .
i 4 ; a 7 ; x x 0 .
ji
4
6

94. Схема алгоритму аналізу підмножини варіантів

Початок
WDA
P1
Так
U1=1
Ні
P2
U2=1
Так
Ні
DJ
Ні
P3
Так
U3=1
Ні
F1
P4
Так
I 5jk ( r )
Так
U4=1
Ні
Ні
WRA
F0
Кінець
J k*
Так

95. ФУНКЦІЇ БЛОКІВ

WDA – ввід вхідних даних;
WRA – вивід результатів аналізу підмножини Gk ;
P1, P2 , P3 , P4 – перевірка виконання умов тверджень
1, 2, 3 та 4 відповідно;
U 1, U 2 , U 3 , U 4 – фіксація факту виконання (UN 1 )
або невиконання (UN 0 ) N -го твердження; N 1, 4 ;
F1, F 0 – привласнення безальтернативним змінним
значення 1 та 0 відповідно, перетворення аналізованої
системи обмежень;
DJ – видалення номерів обмежень, що втратили
властивість активності.

96.

Алгоритм
1. Вибір підмножини варіантів
розбиттю:
Gk * ; 1 k * ,
яка підлягає
(Gk ) max (Gk ) ; k 1, .
*
2. Вибір незалежної змінної
фіксації:
xi * ; i* I k * ,
значення якої підлягає
ci * max { ci ; i I ok * } .
3. Розбиття підмножини варіантів
(G
k
(G
4. Аналіз підмножин
Gk0*
xi * 0) Gk0* ;
*
k
Gk* :
*
xi * 1) Gk1* .
та
Gk1* .
5. Перевірка допустимих планів на оптимальність:
max f ( x) ; x X * max (Gk ) ; k 1, * ;
x* arg max f ( x); x X * .

97.

Начало
WD
2
1
A(GA)
V(Gk*)
D(GA)=1
Да
Да
Да
5
Нет
mk*=0
GA=G
Z(GA)
Нет
Нет
GA Gk1
S(GA)
V(xi)
5
Нет
4
Да
Нет
xi*=0
3
GA Gk0
Да
4
* 0
Да
5
M(Gk*)
xi*=1
WR
2
3
Конец
Нет
1

98. ФУНКЦІЇ БЛОКІВ (1)

WD – ввід вхідних даних;
WR – вивід результатів обчислень;
MDP – фіксація часткових планів та оцінок цільової
функції підмножин варіантів;
А(GA ) – аналіз множини варіантів G A ( G , Gk0* або Gk1* );
D(GA ) – фіксація показника наявності ( D(GA ) 1) або
відсутності ( D(GA ) 0 ) припустимих планів в
підмножині G A ;
Z (GA ) – обчислення оцінки цільової функції на G A ;

99. ФУНКЦІЇ БЛОКІВ (2)

S (GA ) – занесення оцінки цільової функції та
часткового плану даної підмножини варіантів G A у
масив MDP ;
M (Gk * ) – перетворення математичної модель, що
відповідає підмножині Gk * , до виду, адекватному
підмножині Gk1* ;
V (Gk* ) – вибір підмножини варіантів для подальшого
розбиття;
для
V ( xi* ) – вибір незалежної змінної xi* , i * I k *
привласнення конкретних значень.

100.

Приклад.
f ( x) 2 x1 5x2 7 x3 3x4 4 x5 x6 6 x7 max
2 x1 6 x2 5x3 0
3x1 7 x4 5x5 7
7 x2 8x5 4 x6 3
4 x1 2 x2 x7 2
2 x2 9 x5 7 x7 5
xi {0, 1} ; i 1, 7
(1)
(2)
(3)
(4)
(5)

101.

Крок 1.
Розбиття G :
G1 G : x2 0 ; (G1 ) 4 ;
G2 G : x2 1 ; (G2 ) 9 .

102.

Аналіз G2 :
f 2 ( x) 5 2 x1 7 x3 3x4 4 x5 x6 6 x7 max
2 x1 5x3 6
3x1 7 x4 5x5 7
8 x5 4 x6 4
4 x1 x7 4
9 x5 7 x7 7
xi {0, 1} ; i {1, 3, 4, 5, 6, 7}
(G2 ) 9 .
З обмеження (1): x1 x3 1 .
(1)
(2)
(3)
(4)
(5)

103.

Після підстановки x1 x3 1 :
f 2 ( x) 4 3x4 4 x5 x6 6 x7 max
7 x4 5x5 10
8 x5 4 x6 4
x7 0
9 x5 7 x7 7
xi {0, 1} ; i {4, 5, 6, 7}
(G2 ) 0 .
З обмеження (4): x7 0 .
(2)
(3)
(4)
(5)

104.

Після підстановки x7 0 :
f 2 ( x) 4 3x4 4 x5 x6 max
7 x4 5x5 10
8 x5 4 x6 4
9 x5 7
xi {0, 1} ; i {4, 5, 6}
(G2 ) 0 .
З обмеження (5): x5 1 .
(2)
(3)
(5)

105.

Після підстановки x5 1 :
f 2 ( x) 8 3x4 x6 max
7 x4 5
4 x6 4
xi {0, 1} ; i {4, 6}
(G2 ) 4 .
З обмеження (2): x4 0 .
(2)
(3)

106.

Після підстановки x4 0 :
f 2 ( x) 8 x6 max
4 x6 4
xi {0, 1} ; i {6}
(G2 ) 7 .
З обмеження (3): x6 1 .
Після підстановки x6 1 :
x (1, 1, 1, 0, 1, 1, 0) ; (G2 ) f ( x) 7 .
(3)

107.

Аналіз G1 :
f1 ( x) 2 x1 7 x3 3x4 4 x5 x6 6 x7 max
2 x1 5x3 0
3x1 7 x4 5x5 7
8 x5 4 x6 3
4 x1 x7 2
9 x5 7 x7 5
xi {0, 1} ; i {1, 3, 4, 5, 6, 7}
(G2 ) 4 .
Обмеження (1) – не активне.
З обмеження (3): x6 1 .
(1)
(2)
(3)
(4)
(5)

108.

Після підстановки x6 1 :
f1 ( x) 1 2 x1 7 x3 3x4 4 x5 6 x7 max
3x1 7 x4 5x5 7
8 x5 1
4 x1 x7 2
9 x5 7 x7 5
xi {0, 1} ; i {1, 3, 4, 5, 7}
(G2 ) 4 .
З обмеження (3): x5 0 .
(2)
(3)
(4)
(5)

109.

Після підстановки x5 0 :
f1 ( x) 1 2 x1 7 x3 3x4 6 x7 max
3x1 7 x4 7
4 x1 x7 2
7 x7 5
xi {0, 1} ; i {1, 3, 4, 7}
(G2 ) 4 .
З обмеження (5): x7 1 .
(2)
(4)
(5)

110.

Після підстановки x7 1 :
f1 ( x) 5 2 x1 7 x3 3x4 max
3x1 7 x4 7
4 x1 1
xi {0, 1} ; i {1, 3, 4}
(G2 ) 2 .
З обмеження (4): x1 0 .
(2)
(4)

111.

Після підстановки x1 0 :
f1 ( x) 5 7 x3 3x4 max
7 x4 7
xi {0, 1} ; i {3, 4}
(G2 ) 2 .
(2)

112.

Крок 2.
Розбиття G1 :
G3 G1 :
x4 0 ; (G3 ) 5 ;
G4 G1 :
x4 1 ; (G4 ) 2 .

113.

Аналіз G4 :
f 4 ( x) 2 7 x3 max
xi {0, 1} ; i {3}
(G2 ) 2 .

114.

Крок 3.
Розбиття G4 :
G5 G4 : x3 0 ; (G5 ) 2 ;
G6 G4 : x3 1 ; (G6 ) 9 .

115.

Аналіз G5 :
I5 .
Оптимальний розв’язок:
x (0, 0, 0, 1, 0, 1, 1) ; (G5 ) f5 ( x) 2 .

116.

117.

Тема 4. Методи одномірної
оптимізації
f ( x) min ; x E 1 ; a x b .

118.

4.1 Метод дихотомії

119.

Вихідні дані:
f (x)
;
( a, b)
;
0.01.
a (1) a
На k -му кроці:
Якщо
Якщо
f1( k ) f 2( k ) ,
f1( k ) f 2( k )
b(1) b
1 (k )
a b( k )
2
f x(k ) ;
f 2( k )
2
x(k )
f1( k )
;
то a
, то a
( k 1)
x(k )
( k 1)
a(k )
;
;
.
;
f x(k ) .
2
b( k 1) b( k )
b( k 1) x ( k )
.
.
Критерій закінчення пошуку:
x*
b
( k 1)
.
a( k 1)
1 ( k 1)
a
b( k 1)
2
;
f min f ( x* ) .

120.

4.2 Метод золотого перетину
1
3 5
0,38 ;
2
2
5 1
0,62 .
2
1 2 1 ; 1 ( 2 )2 .

121.

122.

Вихідні дані:
f (x) ;
( a, b) ;
0.01.
a (1) a ;
b(1) b .
На k -му кроці:
x1( k ) a( k ) [ b( k ) a( k ) ] 1 ;
x2( k ) a( k ) [ b( k ) a( k ) ] 2 .
Якщо
то:
a ( k 1) a ( k ) ; b( k 1) x2( k ) ;
Якщо
f ( x1( k ) ) f ( x2( k ) ) ,
то:
a ( k 1) x1( k ) ; b( k 1) b( k ) ;
x1( k 1) a( k 1) [ b( k 1) a( k 1) ] 1 ;
x2( k 1) x1( k ) .
f ( x1( k ) ) f ( x2( k ) ) ,
Критерій закінчення пошуку:
x*
x2( k 1) a ( k 1) [ b( k 1) a ( k 1) ] 2 .
x1( k 1) x2( k ) ;
b
( k 1)
a( k 1) .
1 ( k 1)
a
b( k 1)
2
;
f min f ( x* ) .

123.

4.3 Метод однократної інтерполяції (метод ДСК)

124.

Вихідні дані:
f (x) ;
( a, b) ;
x1( k )
x(0) (a, b) ;
(0) ;
x ( 0 ) при k 1
( k 1)
;
x
при
k
1
min
( 0)
f ( xmin
) f ( x ( 0) ) ;
(k )
0.001 .
( 0)
при k 1
1
( k 1)
.
при
k
1
2

125.

На k -му кроці ( k 1 ):
1.
x2( k ) x1( k ) ( k ) ;
Якщо f ( x ) f ( x ) , то пункт 2.
У противному випадку прийняти : і повторити
пункт 1.
Якщо при повторному виконанні пункту 1 f ( x ) f ( x ) ,
то прийняти 1 і повторити пункт 1.
(k )
2
(k )
1
(k )
(k )
(k )
2
( k 1)
(k )
2
2.
x3( k ) x2( k ) 2 ( k ) .
Якщо f ( x ) f ( x ) , то прийняти : 2
У противному випадку пункт 3.
(k )
3
3.
(k )
2
(k )
x4( k ) x3( k ) ( k ) .
Якщо f ( x1( k ) ) f ( x3( k ) ) , то
У противному випадку
пункт 4.
пункт 5.
(k )
і
пункт 1.
(k )
1

126.

4. xa x1( k ) ; xb x2( k ) ; xc x4( k ) і пункт 6.
5. xa x2( k ) ; xb x4( k ) ; xc x3( k ) .
(k )
min
6. x
S1( k )
xb ( k ) ;
S2
S1( k ) ( k ) [ f ( xa ) f ( xc )] ;
S2( k ) 2[ f ( xa ) 2 f ( xb ) f ( xc )] .

127.

(k )
7. Якщо xmin
a , то xopt a і кінець обчислень.
(k )
Якщо xmin
b , то xopt b і кінець обчислень.
8. Якщо
(k )
( k 1)
f ( xmin
) f ( xmin
) ,
то:
(k )
;
xopt xmin
f opt f ( xopt ) і кінець обчислень.
У противному випадку ( k 1 )-й крок.

128.

129.

4.4 Метод багаторазової інтерполяції (метод Пауелла)

130.

Вихідні дані: f (x) ; (a, b) ; x(0) (a, b) ; ; 0.001 .
Попередній етап:
x1(1) x ( 0) ;
x2(1) x1(1) ;
(1)
3
x
x1(1) 2 , якщо f ( x2(1) ) f ( x1(1) )
.
(1)
x1 в противному випадку

131.

На k -му кроці ( k 1 ):
(k )
min
1. x
S1( k )
;
2 S2( k )
S1( k ) [( x1( k ) ) 2 ( x2( k ) ) 2 ] f ( x3( k ) )
[( x2( k ) ) 2 ( x3( k ) ) 2 ] f ( x1( k ) )
[( x3( k ) ) 2 ( x1( k ) ) 2 ] f ( x2( k ) ) ;
S 2( k ) [ x1( k ) x2( k ) ] f ( x3( k ) )
[ x2( k ) x3( k ) ] f ( x1( k ) )
[ x3( k ) x1( k ) ] f ( x2( k ) ) .

132.

(k )
2. Якщо xmin
a , то xopt a і кінець обчислень.
(k )
Якщо xmin
b , то xopt b і кінець обчислень.
3. Якщо
(k )
( k 1)
f ( xmin
) f ( xmin
) ,
то:
(k )
;
xopt xmin
f opt f ( xopt ) і кінець обчислень.

133.

(k )
4. Якщо f ( x1( k ) ) f ( x3( k ) ) і xmin
x2( k ) , то прийняти:
(k )
; x3( k 1) x2( k ) .
x1( k 1) x1( k ) ; x2( k 1) xmin
(k )
Якщо f ( x1( k ) ) f ( x3( k ) ) , але xmin
x2( k ) , то прийняти:
(k )
x1( k 1) x1( k ) ; x2( k 1) x2( k ) ; x3( k 1) xmin
.
(k )
Якщо f ( x1( k ) ) f ( x3( k ) ) і xmin
x2( k ) , то прийняти:
(k )
x1( k 1) xmin
; x2( k 1) x2( k ) ; x3( k 1) x3( k ) .
(k )
x2( k ) , то прийняти:
Якщо f ( x1( k ) ) f ( x3( k ) ) , але xmin
(k )
x1( k 1) x2( k ) ; x2( k 1) xmin
; x3( k 1) x3( k ) .
( k 1 )-й крок.

134.

135.

Тема 5. МЕТОДИ БАГАТОМІРНОЇ
БЕЗУМОВНОЇ ОПТИМІЗАЦІЇ
f ( x) min ;
x En

136.

5.1 Г радієнтний метод (най швидшог о сп уску)
x ( k ) x ( k 1)
На k -му кроці:
x ( k 1) x ( k ) x ( k ) ;
x ( k ) ( k ) e( k ) ;
e( k )
f ( x ( k ) )
f ( x ( k ) ) ;
f ( x ( k ) )
2
f ( x ( k 1) )
.
x
i 1
i
n

137.

138.

Вибір довжини кроку:
( ) f ( x( k ) e( k ) ) min .
Завершення процесу:
f ( x (k 1) ) .

139.

Приклад
f ( x) 2 x12 3x22 4 x1 5x2 min
x( k ) (1, 2)
f (1, 2) 2 3 4 4 5 2 2 12 4 10 0
x ( k 1) x ( k ) ( k ) e( k )
e
(k )
f ( x ( k ) )
f ( x ( k ) )
f ( x )
(k )
f ( x ( k 1) )
xi
i 1
n
2
4 x 4 4 4 0
f ( x( k ) ) 1
12 5 7
6
x
5
2
f ( x ( k ) ) 02 72 49 7

140.

e1( k )
0
0
7
x1( k ) 1 0 1
e2( k )
7
1
7
x2( k ) 2 ( 1) 2
( ) 2 3(2 )2 4 5(2 ) 3 2 7 min
x1( k 1) 1 0 1
7
6
x2( k 1) 2 ( 1) 2
7 5
6 6
5
147
1
25
5
f (1, ) 2 3 4 5
4
6
36
12
36
6

141.

5.2 Метод пошуку по багатограннику,
що деформується
Симплекс в E n .
Вершини симплексу:
{ xi i 1, n 1} ;
xi ( xij ; j 1, n ) .

142.

143.

Визначення координат вершин симплексу:
x1 ( 0, 0, ..., 0 )
0
d
1
d 2
D
d 2
...
d 2
0
d2
d1
0
d2
d2
...
...
...
d2
...
d2
d1
...
d2
...
...
d2
d1
t
n 2
d2
0
d 2
d2
d2
...
d1
( n 1) n
( n 1 n 1) ;
t
n 2
( n 1 1) .
d1 , якщо j i 1
xij x1 j
; i 2, n 1 ;
d
в
противному
випадку
2
j 1, n .

144.

Позначення
Вершини багатогранника:
xi( k ) ( xij( k ) j 1, n ) ; i 1, n 1 ; k 1, 2, ...
Значення цільової функцїї в вершинах:
f ( xi(k ) ) ; i 1, n 1 .
k)
xi(min
arg min { f ( xi( k ) ) ; i 1, n 1} ;
k)
xi(max
arg max { f ( xi( k ) ) ; i 1, n 1} .
(k )
xn( k )2 – центр тяжіння вершин багатогранника, за виключенням ximax .
Координаты центра тяжіння:
1 n 1 ( k ) ( k )
(k )
xn 2, j xij ximax , j ;
n i 1
j 1, n .

145.

146.

Алгоритм
Операції на k -му кроці:
1. Визначення xi( k ) та xi( k ) .
2. Обчислення координат центра тяжіння xn( k )2 .
3. Якщо
max
min
1/ 2
1 n 1
(k )
(k )
2
[
f
(
x
)
f
(
x
)]
i
n 2
n
1
i 1
3. Відображення:
, то кінець обчислень.
k)
xn( k )3 xn( k )2 ( xn( k )2 xi(max
) ; 1.
(k )
(k )
Якщо f ( xn 3 ) f ( ximin ) , то пункт 4.
В противному випадку пункт 7.
4. Розтягнення:
xn( k )4 xn( k )2 ( xn( k )3 xn( k )2 ) ;
(k )
(k )
Якщо f ( xn 4 ) f ( ximin ) , то пункт 5.
В противному випадку пункт 6.
5. Заміна вершини xi( k ) на xn( k )4 та k : k 1
6. Заміна вершини xi( k ) на xn( k )3 та k : k 1
max
max
2 3.

147.

148.

7. Якщо
k)
f ( xn( k )3 ) f ( xi(max
),
то пункт 8.
В противному випадку пункт 10.
8. Стиснення:
xn( k )5 xn( k )2 ( xi( k ) xn( k )2 ) ; 0,4 0,6 .
max
(k )
(k )
x
x
9. Заміна вершини imax на n 5 та k : k 1 .
10. Редукція:
(k )
i
x
x
(k )
i min
1 (k )
k)
( xi xi(min
) ; i {1, ..., n 1} \ {imin } .
2
Далі k : k 1 .

149.

Начало
f(x), x1, t, α, β, γ,
ε
xij;
Определение координат
вершин исходного симплекса
i 2, n 1 , j 1, n
xi min, xi max
Определение координат
центра тяжести
x n+2
{…}1\2
ε
нет
да
Отражение: хn+3
xmin, f(xmin), k
нет
нет
Редукция
f(xn+3)
f(xi max)
f(xn+3)
f(xi min)
да
да
Сжатие: хn+5
f(xn+4) < f(xi min)
да
Замена всех
xi, i = imin
Конец
Растяжение: хn+4
Замена: xi max →xn+5
Замена:xi max → xn+4
нет
Замена: xi max →xn+3

150.

Тема 6. МЕТОДИ ОПТИМІЗАЦІЇ ПРИ
НАЯВНОСТІ ОБМЕЖЕНЬ
f ( x) min
hi ( x) 0; i 1, m ;
gi ( x) 0; i m 1, p ;
x E n ; x ( x j ; j 1, n) .

151.

6.1 Мет од лінійної ап рокси мації
~ (k )
f ( x ) f ( x ( k ) ) T f ( x ( k ) ) ( x x ( k ) ) min
~
hi ( x( k ) ) hi ( x( k ) ) T hi ( x( k ) ) ( x x( k ) ) 0 ;
g~i ( x ( k ) ) g i ( x ( k ) ) T g i ( x ( k ) ) ( x x ( k ) ) 0 ;
x(k ) E n ;
x En .
i 1, m ;
i m 1, p ;

152.

x(1) x( 2) ... x( k ) x( k 1) ... xopt
Умови збіжності:
1) R ;
2) всі функції f (x) ; hi (x) ,
диференціюємі;
3) функція f (x) опукла;
i 1, m ;
g i (x) ,
i m 1, p
m
4) сума hi2 ( x) опукла;
i 1
5) всі функції gi (x) ; i m 1, p увігнуті;
6) множина R замкнена та опукла;
7) всі функції hi (x) , i 1, m ; gi (x) , i m 1, p обмежені:
hi (x) ; gi (x) , де 0 .
неперервні та

153.

Перетворення обмежень-нерівностей в рівняння:
g~i ( x ( k ) ) ui( k ) 0 ; ui( k ) 0 ; i m 1, p .
Наближення точки
x (k )
до ОДР:
p
(v( k ) ) vi( k ) min
i 1
~ (k )
hi ( x ) vi( k ) 0 ;
g~i ( x ( k ) ) ui( k ) vi( k ) 0 ;
vi( k ) 0 ;
i 1, m ;
i m 1, p ;
i 1, p .
Ознака завершення обчислень:
x ( k 1) x ( k ) .

154.

155.

156.

6.2 Метод штрафних функцій
Вихідна модель:
f ( x) min
hi ( x) 0; i 1, m ;
gi ( x) 0; i m 1, p ;
x E n ; x ( x j ; j 1, n) .
Перетворена модель:
m
F ( x) f ( x) wi H [hi ( x)]
i 1
p
w G[ g ( x)] min
i m 1
i
wi 0 ; i 1, p .
i

157.

Вимоги до функціоналів H :
якщо hi ( x) 0 , то H [hi ( x)] 0 .
Вимоги до функціоналів G :
якщо
якщо
якщо
якщо
gi ( x) 0 , то G[ gi ( x)] 0 ;
gi ( x) 0 , то G[ gi ( x)] 0 ;
g i ( x) 0( ) , то G[ gi ( x)] ;
g i ( x) 0( ) , то G[ gi ( x)] 0 .
Приклади
H [hi ( x)] hi2 ( x) ;
G[ g i ( x)]
1
1
1
G
[
g
(
x
)]
G
[
g
(
x
)]
ln
;
;
.
i
i
gi ( x)
gi2 ( x)
gi ( x)

158.

159.

6.3 Метод ковзного допуску
Вихідна модель:
f ( x) min
hl ( x) 0; l 1, m ;
gl ( x) 0; l m 1, p ;
x E n ; x ( x j ; j 1, n) .
Перетворена модель:
f ( x) min
( k ) T ( x) 0 ;
x En ;
x ( x j ; j 1, n) .

160.

( 0) 2(m 1)t ;
( k ) min{ ( k 1) ; ( k ) } ;
k 1, 2, 3, ... ;
1/ 2
m 1 r 1 n ( k )
(k )
(k )
2
[ xij xr 2, j ] ; r n m ;
r 1 i 1 j 1
xi( k ) и xr( k )2 – вершина та центр тяжіння багатогранника в E n з
(r 1) вершинами;
2
2
T ( x) hl ( x) ul g l ( x)
l m 1
l 1
0 при g l ( x) 0
ul
.
1
при
g
(
x
)
0
l
m
p
1/ 2
;

161.

( 0) (1) ... ( k ) 0 ;
Якщо x R , то T ( x) 0 .
Якщо x R , то T ( x) 0 .
Вектор xi( k ) називається:
– допустимим, якщо T ( x( k ) ) 0 ;
– квазидопустимим, якщо 0 T ( x( k ) ) ( k ) ;
– недопустимим, якщо T ( x( k ) ) ( k ) .

162.

СТРАТЕГІЯ МЕТОДУ
x(0) x(1) x( 2) ... x( k ) x( k 1) ... xopt
Із стартової точки x (k ) розв’язується основна задача:
f ( x) min
та визначається точка x ( k 1) .
Якщо T ( x( k 1) ) ( k ) , то здійснюється переміщення з x (k ) в x ( k 1) .
Якщо T ( x( k 1) ) ( k ) , то замість x ( k 1) відшукується інша точка x ( k 1) :
допустима або квазидопустима.
Для цього зі стартової точки x ( k 1) розв’язується допоміжна
задача:
T ( x) min .
Умова завершення допоміжної процедури:
T ( x ( k 1) ) ( k ) .
Після цього: x( k ) x ( k 1) .

163.

Нульовий крок пошуку:
1°. В E n будується симплекс ( f -симплекс) з (r 1) вершинами, призначений для
мінімізації f (x) .
Початкова вершина x1(0) ( x (j0) j 1, n) задається.
Координати інших вершин обчислюються, виходячи з рекомендованої відстані між
ними:
0,2 n
t min
(b j a j ) ; (b j a j ), j 1, n ,
n j 1
де a j x j b j ;
j 1, n .
2°. Визначається вершина
0)
xi(min
arg min{ f ( xi( 0) ) ; j 1, n} .
3°. Якщо
0)
(0) T ( xi(min
) 0 , то пункт 4°.
В противному випадку пункт 6°.
4°. Виконується один цикл безумовної мінімізації f (x)
деформуємому багатограннику.
5°. Виконується заміна:
– або точки xi(0) на одну з точок: xr( 0 )3 , xr(0 )4 чи xr(0 )4 ;
– або всіх точок, крім xi(0) (після операції редукції).
На цьому нульовий крок завершується.
max
min
методом пошуку по

164.

6°. Якщо
0)
(0) T ( xi(min
) 0,
то в E n будується другий симплекс ( T -симплекс) з (n 1) вершинами,
призначений для мінімізації T (x ) в околі xi(0) .
min
Початкова вершина xˆ x .
Координати інших вершин обчислюються, виходячи з
рекомендуємої відстані між ними:
t 0,05 ( 0) .
7°. Реалізується процедура безумовної мінімізації T (x ) в околі
xi( 0) методом пошуку по деформуємому багатограннику.
( 0)
1
( 0)
imin
min
Процедура завершується знаходженням точки
задовольняє умові допустимості/квазидопустимості:
(0) T ( xˆi( s ) ) 0 ,
де s – кількість реалізованих кроків алгоритму.
xˆi(mins ) ,
яка
min
8°. Проводиться заміна: точка xˆi( s ) вводиться у склад вершин f багатогранника замість вершини xi(0) .
min
max
На цьому нульовий крок завершується.

165.

166.

k-й крок пошуку
1. Проводиться один цикл безумовної мінімізації f (x) з
використанням f -багатогранника, побудованого на нульовому
кроці.
2. Визначається вершина
k)
xi(min
arg min{ f ( xi( k ) ) ; j 1, n} .
3. Якщо
k)
( k ) T ( xi(min
) 0 , то пункт 4.
В противному випадку пункт 6.
4. Перевіряється умова закінчення пошуку:
(k ) .
Якщо
вона
виконується,
то
завершується.
В противному випадку пункт 5.
обчислювальний
5. Проводиться заміна:
– або точки xi( k ) на одну з точок: xr( k )3 , xr( k )4 чи xr( k )4 ;
– або всіх точок, крім xi( k ) (після операції редукції).
max
min
Далі k : k 1 .
процес

167.

6. Якщо
k)
( k ) T ( xi(min
) 0,
то в E n будується новий симплекс ( T -симплекс) з
призначений для мінімізації T (x ) в околі xi( k ) .
(n 1)
вершинами,
min
Початкова вершина xˆ1(0) xi( k ) .
Координати інших вершин обчислюються, виходячи з рекомендованої
відстані між ними:
t 0,05 ( k ) .
min
7. Реалізується процедура безумовної мінімізації T (x ) в околі xi( k ) .
min
Процедура завершується знаходженням точки xˆi( s ) , яка задовольняє
умові допустимості/квазидопустимості:
( k ) T ( xˆi( s ) ) 0 .
min
min
8. Проводиться заміна: точка xˆi( s )
багатогранника замість вершини xi( k ) .
min
max
Далі k : k 1 .
вводиться в склад вершин
f -

168.

Рекомендовані параметри:
1;
0,5 ;
2;
10 5 .