Постановка задачи целочисленного
программирования.
|
|
|
|
|
n |
max(min) F cj xj |
|||||
n |
|
|
|
|
j 1 |
|
|
|
|
|
|
aij x j bi |
, (i |
|
) ; |
||
1,m |
|||||
j 1 |
|
|
|
|
|
x j 0 , ( |
j |
|
), xj – целые числа. |
||
1,n |
|||||
Метод ветвей и границ
На основании полученного решения составляются дополнительные к исходной задаче ограничения
xj x*j |
и x j x*j 1 |
где [xj] - целая часть нецелочисленного значения переменной в оптимальном решении.
Пример. Найти максимум F=7x1 + 3x2 max
5x1 |
+ 2x2 20 |
|
8x1 |
+ 4x2 38; |
xj 0, |
целочисленные
Дерево решений
|
|
|
|
|
|
|
|
Зад.1 |
|
|
|
|
|
|||
|
|
|
|
|
|
|
x1=1 ; x2=7,5 |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
F=29,5 |
|
|
|
|
|
|||
|
|
|
|
x2 |
|
|
|
|
|
|
x2 |
|
|
|||
|
|
7 |
|
|
|
8 |
|
|
|
|
||||||
|
|
|
|
Зад.2 |
|
|
|
|
|
|
Зад.3 |
|
|
|||
|
|
|
x1=1,2 ; x2=7 |
|
|
|
|
|
x1=0,75 ; x2=8 |
|
|
|||||
|
|
|
|
F=29,4 |
|
|
|
|
|
|
F=29,25 |
|
|
|||
x |
|
|
|
x |
|
|
|
x2=0 |
|
x |
||||||
2 |
|
2 |
|
|
|
|
|
|
|
|
|
2 |
||||
1 |
|
2 |
|
|
|
|
|
|
|
|
|
1 |
||||
Зад.4 |
|
|
Зад.5 |
|
|
|
|
|
Зад.6 |
|
|
|
Зад.7 |
|||
x1=1 ; x2=7 |
|
|
x1=2 ; x2=5 |
|
|
x1=0 ; x2=9,5 |
|
|
Несовместность |
|||||||
|
|
|
|
|
|
|
ограничений. |
|||||||||
F=28 |
|
|
F=29 |
|
|
|
|
|
F=28,5 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
||||||
Лекция 19. Нелинейное программирование.
Методы одномерного поиска оптимального решения
|
|
|
Метод дихотомии. |
|
|
|
k-я итерация. |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Если bk - ak l , то |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x*=(ak+ bk)/2. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
l -длина интервала |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
a1 |
|
|
|
|
|
1 |
b1 |
|
|
||||||||
|
|
|
1 |
|
|
||||||||||||
|
|
|
|
|
неопределенности. |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
В противном случае |
|
|
ak bk |
|
|||||||||||||
k |
a |
k |
b |
k |
|
|
|
k |
|
||||||||
|
2 |
|
|
|
2 |
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Если |
|
F( k)<F( k), |
положить ak+1= ak; bk+1= k . |
||||||||||||||
В противном случае ak+1= k |
и bk+1=bk. |
||||||||||||||||
Метод золотого сечения.
Предварительный этап. Выбрать допустимую конечную длину интервала неопределенности l>0.
Пусть [a1,b1] - начальный интервал неопределенности. Положить
1=a1+(1- )( b1 - a1) и 1=a1+ ( b1 - a1), где =0,618. Вычислить F( 1) и F( 1), положить k=1, и перейти к основному этапу.
Основной этап. Шаг 1. Если bk - ak l , то вычисления заканчиваются x*=(ak+ bk)/2. В противном случае, если
F( k)>F( k), то перейти к шагу 2, |
если F( k) F( k), перейти |
к шагу 3. |
|
Шаг 2. Положить ak+1= k, bk+1=bk, |
k+1= k, |
k+1= ak+1+ ( bk+1 – ak+1). Вычислить F( k+1), перейти к шагу 4.
Шаг 3. Положить ak+1= ak, bk+1= k , k+1= k ,
k+1= ak+1+(1- )( bk+1 – ak+1). Вычислить F( k+1). Шаг 4. Присвоить k=k+1, перейти к шагу 1.
Пример. Найти min F(x)=(x2+2x) при условии -3 x 5. Зададим l=0,2.
k |
ak |
bk |
k |
k |
F( k) |
F( k) |
1 |
-3 |
5 |
0,056 |
1,944 |
0,115 |
7,667 |
2 |
-3 |
1,944 |
-1,112 |
0,056 |
-0,987 |
0,115 |
3 |
-3 |
0,056 |
-1,832 |
-1,112 |
-0,308 |
-0,987 |
4 |
-1,832 |
0,056 |
-1.112 |
-0,664 |
-0,987 |
-0,887 |
5 |
-1,832 |
-0,664 |
-1,384 |
-1,112 |
-0,853 |
-0,987 |
6 |
-1,384 |
-0,664 |
-1,112 |
-0,936 |
-0,987 |
-0,996 |
7 |
-1,384 |
-0,936 |
-1,208 |
-1,112 |
-0,957 |
-0,987 |
8 |
-1,208 |
-0,936 |
-1,112 |
-1,032 |
-0,987 |
-0,999 |
9 |
-1,112 |
-0,936 |
|
|
|
|
Метод Гаусса-Зайделя (покоординатного спуска)
(xi)k+1= (xi)k i
где (xi)k+1 - новая координата по i-ой переменной; (xi)k – текущая координата по i-ой переменной;
i - длина шага изменения координаты по i-ой переменной. Критерий остановки поиска |F(Xk+1)-F(Xk)|< .
Градиент многомерной функции
gradF(X ) |
F |
x |
|
F |
x |
|
...... |
F |
x |
|
||
x |
x |
|
|
x |
|
|
||||||
|
1 |
|
2 |
|
2 |
|
n |
|
n |
|||
|
1 |
|
|
|
|
|
|
|
|
|
||
Координаты точки при поиске минимума вычисляются по выражению:
(xi )k 1 |
|
F |
|
|
|
||
(xi )k k |
x |
|
|
|
|
i |
k |
где k - длина (параметр) шага на k-ой итерации вдоль антиградиента
Варианты остановки процесса поиска оптимума: 1. По разности значений целевой функции
F(X k ) F(X k 1) 1
2. |
По величине нормы |
|
|
|
|
|
|||||
gradF(X k ) |
|
2 |
|
gradF(X k ) |
|
|
n |
|
F |
2 |
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|||||
|
|
|
|
xi |
|
||||||
3. |
По величине изменения шага |
i 1 |
|
k |
|||||||
|
|
|
|
||||||||
(xi )k (xi )k 1 3