Математичне програмування

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

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

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.

Приклад
Вхідні дані:
n підприємств (r 1, n) ;
m видів виробів (i 1, m) ;
k типів ресурсів ( j 1, k ) .
bi – план виробництва виробів i -го виду;
bij – норматив витрат ресурсів j -го типу на одиницю виробів i -го виду;
a rj – об’єм ресурсів j -го типу на r -му підприємстві;
pri – витрати на випуск одиниці виробів i -го виду на r -му підприємстві.
Необхідно: так розподілити планове завдання між підприємствами, щоб сумарні витрати на
випуск виробів були мінімальні.
Шукані змінні: x ri – план випуску виробів i -го виду на r -му підприємстві; r 1, n ; i 1, m .
n
m
f ( x) pri xri min ;
Модель:
r 1 i 1
n
xri bi ;
r 1
m
b
i 1
ij
i 1, m ;
xri arj ; r 1, n ;
j 1, k ;
x ri 0 ; r 1, n ; i 1, m .

13.

1.3 Класифікація ЗМП
МП
ЛП
ЦП
ДП
НЛП
ДинП
КомбП
Рис. 1.1
СтП
ПотП
ГеомП

14.

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

15. Рис. 1.2

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

16.

*
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* :

17.

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 .
Строго опуклі та строго увігнуті функції.

18.

Приклад
2
Визначити, опукла чи увігнута функція ( x) 2 x 5x 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) .
Висновок: функція ( x) 2 x 2 5x 7 опукла.

19.

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

20. Рис. 1.4

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

21.

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

22.

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

23.

Приклад
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

24.

Рис.1.5

25.

(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

26.

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

27.

Приклад
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

28.

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

29.

Рис.1.6

30. Тема 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 .

31.

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

32.

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

33.

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

34.

Базисні та вільні змінні:
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 .

35.

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.

36.

Вільні змінні: 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

37.

Область допустимих розв’язків:
Рис. 1.7

38.

Знаходження точки оптимального розв’язку:
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 .

39.

Рис. 1.8

40.

Оптимальний розв’язок:
*
*
*
x1* 8,5 ; x2 5 ; x3 0,5 ; x4 16,5 ;
x5* 17,5 ; x6* x7* 0 ;
f * 64,5 .

41.

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

42.

Рис. 1.9

43.

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
– недопустимий розв’язок.

44.

Нехай 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)

45.

Границя збільшення 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 .
*
*

46.

( 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) ]
–

47.

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

48.

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 .
змінних:
1 j* k .
Дозволяючий рядок
Дозволяючий стовпчик
Дозволяючий елемент
xi * x j * ;
k 1 i* n ;

49.

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

50.

Приклад
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

51.

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

52.

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

53.

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*

54.

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 ;…; xn n .
Припустимо, ( i : k 1 i n)( i 0) .

55.

Правила вибору дозволяючого елемента:
i : i 0 ; k 1 i n .
вибирається коефіцієнт i , j 0 ; 1 j * k
1) Вибирається рядок
2) В рядку i
*
(дозволяючий
стовпчик).
( 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
:

56.

Приклад
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 )

57.

Приклад
р/ст.
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 .

58.

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 ) ;
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 ;…; xn n ;
( i k 1, n)( i 0) .
( j : 1 j k )( j 0) x – оптимальний розв’язок.
Припустимо, ( j : 1 j k )( j 0) .

59.

Правила вибору дозволяючого елементу:
*
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*
(
)
min i ; i I j* .
i* j *
ij*
i
* *
j
:

60.

Приклад
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 )
x 6 2 ( x 2 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

61.

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 .

62.

Тема 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 .

63.

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

64.

Формування відсікаючого обмеження
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)

65.

Після віднімання (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;
0 ij 1 ;
i i [ i ] ; 0 i 1 .
Відсікаюче обмеження:
i j
j J C
x j i .

66.

Перетворення в рівняння:
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 – ціле число, та
недопустимою в противному випадку.

67.

Приклад
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

68.

Вихідна симплексна таблиця №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

69.

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

70.

71.

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

72.

Початкова симплексна таблиця №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

73.

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

74.

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

75.

Початкова симплексна таблиця №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

76.

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

77.

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 ) :

78.

Приклад
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

79.

( 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 .

80.

На 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ле ) .

81.

Алгоритм
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

82.

Приклад
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 .

83.

84.

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 .

85.

Підмножини варіантів: 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} .

86.

Модель, приведена у відповідність 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)

87.

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 .

88.

Підмножини та величини, необхідні для дослідження моделі (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, .

89.

Аналіз підмножин варіантів
Твердження 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 .

90.

Твердження 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 .

91.

Твердження 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 .

92.

Твердження 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

93.

Алгоритм
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 * .

94.

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

95.

Приклад.
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)

96.

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

97.

Аналіз 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)

98.

Після підстановки 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)

99.

Після підстановки 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)

100.

Після підстановки 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)

101.

Після підстановки 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)

102.

Аналіз 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)

103.

Після підстановки 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)

104.

Після підстановки 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)

105.

Після підстановки 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)

106.

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

107.

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

108.

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

109.

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

110.

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

111.

112.

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

113.

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

114.

Вихідні дані:
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* ) .

115.

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

116.

117.

Вихідні дані:
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* ) .

118.

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

119.

Вихідні дані:
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

120.

На 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

121.

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 )] .

122.

(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 )-й крок.

123.

124.

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

125.

Вихідні дані: 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 в противному випадку

126.

На 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 ) ) .

127.

(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 ) і кінець обчислень.

128.

(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 )-й крок.

129.

130.

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

131.

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

132.

133.

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

134.

Приклад
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

135.

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

136.

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

137.

138.

Визначення координат вершин симплексу:
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 .

139.

Позначення
Вершини багатогранника:
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 .

140.

141.

Алгоритм
Операції на 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.

142.

143.

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 .

144.

Начало
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

145.

Тема 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) .

146.

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 ;

147.

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 .
неперервні та

148.

Перетворення обмежень-нерівностей в рівняння:
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 ) .

149.

150.

151.

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

152.

Вимоги до функціоналів 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[ gi ( x)] ln
.
i
2
gi ( x)
g i ( x)
gi ( x)

153.

154.

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) .

155.

( 0) 2(m 1)t ;
( k ) min{ ( k 1) ; ( k ) } ;
k 1, 2, 3, ... ;
1/ 2
xi( k ) и xr( k )2
m 1 r 1 n ( k )
(k )
(k )
2
[ xij xr 2, j ] ; r n m ;
r 1 i 1 j 1
– вершина та центр тяжіння багатогранника в E n з (r 1)
вершинами;
p
m 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
1/ 2
;

156.

( 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 ) .

157.

Стратегія методу
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) .

158.

Нульовий крок пошуку
1°. В E n будується симплекс ( f -симплекс) з (r 1) вершинами, призначений для мінімізації
f (x) .
Початкова вершина x1(0) ( x (j0) j 1, n) задається.
Координати інших вершин обчислюються, виходячи з рекомендованої відстані між ними:
0,2 n
t min
(
b
a
)
;
(
b
a
),
j
1
,
n
,
j
j
j
j
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

159.

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
Процедура завершується знаходженням точки xˆi( s ) , яка задовольняє
умові допустимості/квазидопустимості:
(0) T ( xˆi( s ) ) 0 ,
де s – кількість реалізованих кроків алгоритму.
min
min
8°. Проводиться заміна: точка xˆi( s ) вводиться у склад вершин f багатогранника замість вершини xi(0) .
min
max
На цьому нульовий крок завершується.

160.

161.

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 .

162.

6. Якщо
k)
( k ) T ( xi(min
) 0,
то в E n будується новий симплекс ( T -симплекс) з (n 1) вершинами, призначений для
мінімізації T (x ) в околі xi( k ) .
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 ) вводиться в склад вершин f -багатогранника
замість вершини xi( k ) .
min
max
Далі k : k 1 .

163.

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