Москвин Б.В. Теория принятия решений
Подождите немного. Документ загружается.
151
x
8
= x
7
= (4, 6) - итерация неудачна.
3). k = k + 1 = 8; вычисляется c' = 4 > c, то c = c' = 4.
Цикл неудачный, т.к. не было удачных итераций.
Производится переход на шаг 5.
5). Производится дробление шага h = α h, где 0 < α < 1.
Т.к. h = 1 > δ = 0.1, то производится переход на шаг 1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Аналогично проводятся итерации 9-16. Все циклы с 4-го по
7-ой аналогичны 3-му циклу (итерации 7, 8) и все они неудачны.
На
каждом цикле происходит дробление шага пока не выполнится
условие h < δ. Оптимальное решение: x
*
= (4, 6)
т
; f(x
*
) =68.0.
7.3.3. Метод условного градиента
(см.п.4.4.1)
Рассмотрим особенности применения метода условного
градиента на примере решения следующей задачи квадратичного
программирования.
Пример 7.14.
Найти максимум нелинейной функции
f(x) = 16x
1
- 2x
2
1
+ 12x
2
- x
2
2
→ max
при ограничениях
2x
1
- 3x
2
≤ 4
4x
1
+ 3x
2
≤ 26
-2x
1
+ 1x
2
≤ 2
x
1
,x
2
≥ 0.
0). Исходное состояние; x
o
= (0, 0), ε = 0.1; k = 0.
Итерация 1. x
o
= (0, 0); k = 0.
1).Рассчитывается ∇
т
F(x
o
) = (16 - 4x
1
, 12 - 2x
2
) = (16, 12);
2).Решается задача линейного программирования вида
x
o
∗
= arg max ∇
т
F(x
o
) x, x∈Δ
x
o
∗
= (2 6)
т
x
o
∗
задает направление максимального приращения целе-
вой функции из точки x
o
.
3).Вычисляется величина шага в направлении, задаваемом
x
o
∗
, для чего решается задача одномерной оптимизации
h
о
= arg max f(x
о
+h(x
о
∗
-x
о
)) arg max f(2h,6h) = 1.18, тогда h
о
=1.
0≤h≤1 0≤h≤1
4).Вычисляется значение x
1
= x
о
+ h
о
(x
о
∗
- x
о
) = (2 6)
т
.
5).Т.к. ║x
1
-x
о
║>ε, то k=k+1=1; производится переход на шаг 1.
Итерация 2. x
1
= (2 6); k = 1.
152
1). ∇
т
F(x
1
) = (8, 0);
2). x
1
∗
= arg max (8, 0) x, x∈Δ; x
1
∗
= (5, 2)
т
3). h
1
= arg max f(2 + 3h, 6 - 4h), 0 ≤ h ≤ 1; h
1
= 0.35
4). x
2
= x
1
+ h
1
(x
1
∗
- x
1
) = (3.06, 4.59)
т
.
5). Т.к. ║x
2
-x
1
║ > ε, то k=k+1=2; производится переход на шаг 1.
Итерация 3. x
2
= (3.06, 4.59); k = 2.
1). ∇
т
F(x
2
) = (3.76, 2.82);
2). x
2
∗
= arg max (5.36, 1.76) x, x∈Δ; x
2
∗
= (2, 6)
т
3). h
2
= arg max f(3.06 + 1.06h, 4.59 - 1.41h), 0≤h≤1; h
2
= 0.
4). x
3
= x
2
= (3.06, 4.59)
т
.
5). Т.к. ║x
3
- x
2
║ < ε, то решение x
2
= (3.06, 4.59)
т
оптимально.
Итак, оптимальное решение x
*
= (3.06, 4.59)
т
; f(x
*
) = 64.24.
Необходимость учета ограничений в задаче оптимизации
привела к тому, что оптимальное решение и значение целевой
функции достаточно сильно отличаются от тех, которые были по-
лучены при поиске безусловного экстремума (см. предыдущие
примеры 7.11, 7.12, 7.13).
7.3.4. Метод возможных направлений
(см.п.4.4.2)
Метод возможных направлений предназначен для решения
общей задачи выпуклого программирования. Алгоритм носит ите-
рационный характер. Каждая итерация заключается в выполне-
нии следующих шагов.
0). Задание начального приближения x
o
∈ Δ, e > 0; k = 0.
1). Выбор возможного направления γ
k
.
2). Вычисление максимально возможной величины шага h
м
k
в
направлении γ
k
.
3). Выбор шага h
k
, 0 ≤ h ≤ h
м
k
.
4). Вычисление нового приближения x
k+1
.
5). Если ║x
k+1
-x
k
║ ≤ ε или ║∇F(x
k
)║ ≤ ε - решение оптимально.
Пример 7.15.
Рассмотрим особенности алгоритма возможных направле-
ний на примере решения следующей задачи нелинейного про-
граммирования. Найти максимум функции
f(x) = 16x
1
- 2x
2
1
+ 12x
2
- x
2
2
→ max
при ограничениях
2x
1
- 3x
2
≤ 4
2x
1
+ 1x
2
≤ 12
-3x
1
+ 1x
2
≤ 2
153
x
1
,x
2
≥ 0.
0). Исходное состояние: x
o
= (0, 0)
т
; ε = 0.1; k = 0.
Итерация 1. x
o
= (0, 0)
т
; k = 0.
1). Выбор возможного направления осуществляется на основе
решения задачи линейного программирования следующего
вида
z → max,
-∇
т
f(x
о
) γ + z ≤ 0,
∇
т
ϕ
i
(x
о
) γ + z ≤ 0, i ∈ I
о
= {r | ϕ
r
(x
о
) = b
r
},
0 ≤ γ
j
≤ 1, j = 1,..., n.
т.к. x
o
= (0, 0)
т
, то как равенства выполняются ограничения
x
1,
≤ 0, x
2
≤ 0. Тогда задача выбора направления имеет вид
z → max, или z → max,
-(16-4x
1
,12-2x
2
) γ + z ≤ 0 -16γ
1
- 12γ
2
+ z ≤ 0
-γ
1
+ z ≤ 0 -γ
1
+ z ≤ 0
-γ
2
+ z ≤ 0 -γ
2
+ z ≤ 0
-1 ≤ γ
j
≤ 1, j = 1,2 -1 ≤ γ
j
≤ 1, j = 1,2.
Решая данную задачу симплекс-методом, получаем реше-
ние γ = (1, 1); z = 1.
2). Вычисляем h
м
в направлении γ.
h
м
= arg max { h | ϕ
i
(h, h) = b
i
, i = 1,2,3},
h
м
= max { -4, 4, -1 } = 4.
3). Выбор шага h
k
, 0≤h
k
≤h
м
.
h
k
= arg max f(h, h) = 4.67 > h
м
, следовательно, h
k
= 4.
4). x
1
= x
о
+ h
k
γ = (4, 4).
5). ║x
1
-x
о
║ > ε - переход на шаг 1.
Итерация 2. x
1
= (4, 4)
т
; k = 1.
1). z → max,
- 4γ
2
+ z ≤ 0
2γ
1
+ 1γ
2
+ z ≤ 0
-γ
1
+ z ≤ 0
-γ
2
+ z ≤ 0
-1 ≤ γ
j
≤ 1, j = 1,2.
Решение γ = (-1, 0.4); z = 1.6.
2). h
м
= arg max { h | ϕ
i
(4-h, 4+0.4h) = b
i
, i = 1,2,3}
h
м
= max { -2.5, 0, 2.94 } = 2.94.
3). h
k
= arg max f(4-h, 4+0.4h) = 0.43, h
k
= 0.43.
4). x
2
= x
1
+ h
k
γ = (3.57, 4.17).
5). ║x
2
-x
1
║ > ε - переход на шаг 1.
Итерация 3. x
2
= (3.57 4.17)
т
; k = 2.
154
1). Так как x
2
- внутренняя точка, то направление совпадает с
градиентом в этой точке.
γ = (1.72, 3.66).
2). h
м
= arg max{h| ϕ
i
(3.57+1.72h, 4.17+3.66h)=b
i
, i=1,2,3},
h
м
= max { -1.34, 0.10, -5.7 } = 0.1.
3). h
k
= arg max f(3.57+1.72h, 4.17+3.66h) = 0.42 > h
м
,
следовательно, h
k
= 0.1.
4). x
3
= (3.73 4.54).
5). ║x
3
-x
2
║ > ε - переход на шаг 1.
Итерация 4. x
3
= (3.73 4.54)
т
; k = 3.
1). z → max,
-1.08γ
1
- 2.92γ
2
+ z ≤ 0
2γ
1
+ 1γ
2
+ z ≤ 0
-γ
1
+ z ≤ 0
-γ
2
+ z ≤ 0
-1 ≤ γ
j
≤ 1, j = 1,2.
Решение γ = (-1, 0.79); z = 1.21.
2). h
м
= arg max{ h | ϕ
i
(3.73-h, 4.54+0.79h) = b
i
, i = 1,2,3},
h
м
= max { -2.32, 0, 2.28 } = 2.28.
3). h
k
= arg max f(3.73-h, 4.54+0.79h) = 0.23,
h
k
= 0.23.
4). x
4
= (3.5 4.72).
5). ║x
k+1
-x
k
║ > ε - переход на шаг 1.
Итерация 5. x
4
= (3.5 4.72)
т
; k = 4.
1). Так как x
4
- внутренняя точка, то направление совпадает с
градиентом в этой точке.
γ = (2 2.56).
2). h
м
= arg max{h| ϕ
i
(3.5+2h, 4.72+2.56h)=b
i
, i=1,2,3},
h
м
= max { -3.03, 0.04, -2.26 } = 0.04.
3). h
k
= arg max f(3.5+2h, 4.72+2.56h) =0.33 > h
м
,
следовательно, h
k
= 0.04.
4). x
5
= (3.58 4.84).
5). ║x
k+1
-x
k
║ > ε - переход на шаг 1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
И т.д. повторяются итерации вида 4, 5. На 9 итерации полу-
чаем решение (3.35 5.30), при котором выполняется критерий
окончания процесса 5. Тогда оптимальное решение x
*
= (3.35
5.30)
т
; f(x
*
) = 66.67.
7.4. Дискретное программирование
155
Задачи дискретного (целочисленного) программирования
характерны тем, что решение описывается вектором с целочис-
ленными компонентами. Тогда задача имеет вид
x
*
= arg max f(x),
x∈Δ
где Δ ⊆ Z
n
- n-мерное пространство векторов, компоненты кото-
рых являются целыми числами.
7.4.1. Метод отсечений Р.Гомори
(см.п.5.3)
Метод предназначен для решения линейных задач цело-
численного и частично целочисленного программирования. Алго-
ритм основан на последовательном решении задачи линейного
программирования без ограничений на целочисленность и вводе
ограничений (отсечений), отсекающих нецелочисленную точку и
оставляющих все целочисленные точки. Рассмотрим особенности
алгоритма на примере решения следующей задачи.
Пример 7.16.
4x
1
+ 6x
2
+ 2x
3
→ max
2x
1
+ 1x
2
+ 1x
3
≤ 6
1x
1
+ 2x
2
- 3x
3
≤ 4
x
1
,x
2
,x
3 .
≥ 0, целые.
Приведем задачу к канонической форме
4x
1
+ 6x
2
+ 2x
3
→ max
2x
1
+ 1x
2
+ 1x
3
+ x
4
= 6
1x
1
+ 2x
2
- 3x
3
+ x
5
= 4
x
1
,...,x
5 .
≥ 0, целые.
Итерация 1.
1). Решаем задачу симплекс-методом. Получаем решение
2 29.6 4.40 0.80
3 1.6 0.40 -0.20
2 4.4 0.60 0.20
Решение нецелочисленно. Переход на шаг 2.
2). Строим отсечение Р.Гомори по 1-ой компоненте (см. ф.
(5.12).
156
∑
∈
q
jj
{α
ij
} x
qj
. - x
n+1
= {β
i
} .
здесь α
11
=
0.6; α
14
= 0.4; α
15
= -0.2; β
1
= 0.6.
Тогда отсечение имеет вид
0.6x
1
+ 0.4x
4
+ 0.8x
5
- x
6
= 0.6 или 3x
1
+ 2x
4
+ 4x
5
- x
6
= 3.
3). Формируем задачу линейного программирования
4x
1
+ 6x
2
+ 2x
3
→ max
2x
1
+ 1x
2
+ 1x
3
+ x
4
= 6
1x
1
+ 2x
2
- 3x
3
+ x
5
= 4
3x
1
+ 2x
4
+ 4x
5
- x
6
= 3.
x
1
,...,x
6 .
≥ 0.
Итерация 2.
1). В результате решения получаем
2 29.0 4.40 0.80 -0.20
3 1.75 0.40 -0.20 0.05
2 4.25 0.60 0.20 -0.05
5 0.75 0.00 0.00 0.25
Значение целевой функции уменьшилось, но решение не
целочисленно. Переход на шаг 2.
2). Строим отсечение Р.Гомори по 2-ой компоненте.
α
21
= 0.25; α
24
= 0.5; α
26
= 0.05; β
2
= 0.25.
Тогда отсечение имеет вид
0.25x
1
+ 0.5x
4
+ 0.05x
6
- x
7
= 0.25.
3). Формируем задачу линейного программирования
4x
1
+ 6x
2
+ 2x
3
→ max
2x
1
+ 1x
2
+ 1x
3
+ x
4
= 6
1x
1
+ 2x
2
- 3x
3
+ x
5
= 4
3x
1
+ 4x
4
+ 2x
5
- x
6
= 3.
0.25x
1
+ 0.5x
4
+ 0.05x
6
- x
7
= 0.25.
x
1
,...,x
7 .
≥ 0.
Итерация 3.
1). В результате решения получаем
3 28.0 4.40 0.80 -0.20 -4.00
3 2.0 0.40 -0.20 0.05 1.00
2 4.0 0.60 0.20 -0.05 -1.00
5 2.0 0.00 0.00 0.25 5.00
6 5.0 0.00 0.00 0.00 20.00
Решение целочисленно. Работа алгоритма заканчивается.
Оптимальное решение исходной задачи x
*
= (0 4 2)
т
; L
*
=28.
157
7.4.2. Метод "ветвей и границ"
(см.п.5.4)
Метод "ветвей и границ" объединяет группу методов, ха-
рактеризующихся общей схемой решения задач дискретной оп-
тимизации. На основе этого метода могут решаться как линей-
ные, так и нелинейные задачи, особенность заключается в алго-
ритме вычисления оценок. Рассмотрим особенности применения
метода на примере решения общей задачи линейного целочис-
ленного
программирования.
4x
1
+ 6x
2
+ 2x
3
→ max
2x
1
+ 1x
2
+ 1x
3
≤ 6
1x
1
+ 2x
2
- 3x
3
≤ 4
x
1
,x
2
,x
3 .
≥ 0, целые.
Для построения возможных ветвлений вначале целесообразно
определить границы изменения переменных. Для данной задачи
это x
1
≤ 3, x
2
≤ 4, x
3 ,
≤ 6.
Пример 7.17.
Решим данную задачу с использованием метода ветвей и
границ.
0). Исходное состояние: список кандидатов Q ={Δ}, где Δ-
множество допустимых решений задачи; рекорд L
*
= -∞;
решение x
*
= (-1, -1, -1)
т
.
Итерация 1. Q = {Δ}; L
*
= -∞; x
*
= (-1, -1, -1)
т
; q = 0.
1). В списке Q всего один кандидат (Δ).
2). g(Δ) = 29.6; x - нецелочисленно.
3). Δ = Δ
1
∪Δ
2
;
Δ
1
= { Δ | x
1
< 2}
Δ
2
= { Δ | x
1
≥
.
2}
4). Q ≠ ∅, производится переход на шаг 1.
Итерация 2. Q = { Δ
1
, Δ
2
}; L
*
= -∞; x
*
= (-1,-1,-1)
т
; q = 2.
1). Выбираем Δ
1
.
2). g(Δ
1
) = 29.6; x - нецелочисленно.
3). Δ
1
= Δ
3
∪ Δ
4
;
Δ
3
= { Δ | x
1
< 2, x
2
< 2}
Δ
4
= { Δ | x
1
< 2, x
2 .
≥ 2 }
4). Q ≠ ∅ - шаг 1.
Итерация 3. Q = { Δ
2
,Δ
3
,Δ
4
}; L
*
= -∞; x
*
= (-1,-1,-1)
т
; q = 4.
1). Выбираем Δ
4
.
2). g(Δ
4
) = 29.6; x - нецелочисленно.
3). Δ
4
= Δ
5
∪ Δ
6
;
Δ
5
= { Δ | x
1
< 2, x
2 .
≥2, x
3
< 4}
Δ
6
= { Δ | x
1
< 2, x
2 .
≥ 2, x
3 .
≥ 4 }
158
4). Q ≠ ∅ - шаг 1.
Итерация 4. Q = { Δ
2
,Δ
3
,Δ
5
,Δ
6
}; L
*
= -∞; x
*
=(-1,-1,-1)
т
; q=6.
1). Выбираем Δ
6
.
2). g(Δ
6
) = 20 = L
*
; x
*
= (0,2,4)
т
. Δ
6
исключается из Q.
4). Q ≠ ∅ - шаг 1.
Итерация 5. Q = { Δ
2
,Δ
3
,Δ
5
}; L
*
= 20; x
*
=(0,2,4)
т
; q=6.
1). Выбираем Δ
2
.
2). g(Δ
2
) = 18.4 < L
*
; Δ
2
исключается из Q.
4). Q ≠ ∅ - шаг 1.
Итерация 6. Q = { Δ
3
,Δ
5
}; L
*
= 20; x
*
=(0,2,4)
т
; q=6.
1). Выбираем Δ
3
.
2). g(Δ
3
) = 20 = L
*
; Δ
3
исключается из Q.
4). Q ≠ ∅ - шаг 1.
Итерация 7. Q = {Δ
5
}; L
*
= 20; x
*
=(0,2,4)
т
; q=6.
1). Выбираем Δ
5
.
2). g(Δ
5
) = 29.6; x - нецелочисленно.
3). Δ
5
= Δ
7
∪ Δ
8
;
Δ
7
= { Δ| x
1
= 0, x
2
≥
.
2, x
3
< 4 }
Δ
8
= { Δ| x
1
= 1, x
2
.≥ 2, x
3
< 4 }
4). Q ≠ ∅ - шаг 1.
Итерация 8. Q = {Δ
7
,Δ
8
}; L
*
= 20; x
*
=(0,2,4)
т
; q=8.
1). Выбираем Δ
7
.
2). g(Δ
7
) = 29.6; x - нецелочисленно.
3). Δ
7
= Δ
9
∪Δ
10
;
Δ
9
= { Δ | x
1
= 0, 2≤x
2
≤3, x
3
< 4 }
Δ
10
= { Δ | x
1
= 0, x
2
= 4, x
3
< 4 }
4). Q ≠ ∅ - шаг 1.
Итерация 9. Q = {Δ
8
,Δ
9
,Δ
10
}; L
*
= 20; x
*
=(0,2,4)
т
; q=10.
1). Выбираем Δ
8
.
2). g(Δ
8
) = 24 = L
*
; x
*
= (1,3,1)
т
. Δ
8
исключается из Q.
4). Q ≠ ∅ - шаг 1.
Итерация 10. Q = {Δ
9
,Δ
10
}; L
*
= 24; x
*
=(1,3,1)
т
; q=10.
1). Выбираем Δ
9
.
2). g(Δ
9
) = 24 = L
*
; Δ
9
исключается из Q.
4). Q ≠ ∅ - шаг 1.
Итерация 11. Q = {Δ
10
}; L
*
= 24; x
*
=(1,3,1)
т
; q=10.
1). Выбираем Δ
10
.
2). g(Δ
10
) = 28 = L
*
; x
*
=(0,4,2)
т
; Δ
10
исключается из Q.
4). Q = ∅ полученное решение x
*
=(0,4,2)
т
оптимально.
Итак, оптимальное решение x
*
=(0,4,2)
т
; L
*
= 28.
159
РАЗДЕЛ 2. ПРИНЯТИЕ РЕШЕНИЙ НА ОСНОВЕ ДИНАМИЧЕ-
СКИХ МОДЕЛЕЙ ВОЕННО-ТЕХНИЧЕСКИХ СИСТЕМ
8. ПОСТАНОВКА И КАЧЕСТВЕННЫЙ АНАЛИЗ ПРОБЛЕМЫ
УПРАВЛЕНИЯ ДИНАМИЧЕСКИМИ СИСТЕМАМИ
8.1.Содержание проблемы управления динамическими
системами
Проектирование, внедрение и эксплуатация военно-
технических систем связаны с необходимостью решения ряда
проблем, центральными из которых являются проблемы повыше-
ния оперативности и качества принятия решений в указанных
системах на различных этапах их жизненного цикла. Основным
средством повышения качества решений в современных услови-
ях является автоматизация данного процесса на базе разработки
комплексов математических моделей, с помощью которых осуще-
ствляется исследование процессов функционирования основных
элементов военно-технических систем. Выбор того или иного ва-
рианта математической модели - суть неформальная процедура,
требующая разностороннего и глубокого системного анализа си-
туации принятия решения. При этом исследователь должен вы-
брать исходную структуру (модель) принятия решения и в рамках
этой структуры произвести формализованное описание решения,
условий, ограничивающих выбор, и предпочтений, которым долж-
но удовлетворять решение.
В качестве таких моделей в настоящее время принято рас-
сматривать два существенно различных класса моделей: стати-
ческие и динамические. И, если в статических моделях искомое
решение не является функцией времени, т.е. время фиксировано,
то в динамических моделях решение описывается некоторой
функцией времени.
Функция принятия (выбора) решения представляет собой
основу управления (u), которое направлено на достижение целей
функционирования (выхода y) системы в различных условиях
воздействия среды (ω).
160
Под у п р а в л е н и е м будем понимать процесс целена-
правленного изменения выхода системы, осуществляемый путем
воздействия на нее.
Среда
ω
Вход u y Выход
Далее будем полагать, что среда полностью известна (де-
терминированная), тогда процесс функционирования системы
под воздействием управления можно описать отношением вида
Г
⊆ T × U × Y ,
где
T - множество моментов времени;
U - множество управляющих воздействий;
Y - множество выходов системы.
Недостатком данного отношения является то, что оно не
отражает процессы, происходящие в самой системе. Вследствие
этого для пары (t,u) ∈ T × U выход однозначно не определен, т.е.
конкретному управляющему воздействию u в некоторый момент
времени t могут соответствовать подмножества
выходов из Y.
Введем понятие с о с т о я н и е системы, под которым
будем понимать совокупность параметров (характеристик), отра-
жающих наиболее существенные свойства системы и опреде-
ляющих ее поведение (функционирование). Множество состояний
системы обозначим через X, тогда функционирование системы
можно описать отношением
G ⊆ T × X × U × Y .
Изучение систем
, описываемых данным отношением, осно-
вывается на выполнении п р и н ц и п а п р и ч и н н о с т и:
1) выход системы не зависит от входных воздействий, которые
могут иметь место в будущем (упорядоченность причинно-
следственных связей);
2) выход системы однозначно определяется ее прошлыми
со-
стояниями и входными воздействиями (однозначность причинно-
следственных связей);
Системы, удовлетворяющие принципу причинности, назы-
ваются д и н а м и ч е с к и м и системами. Для таких систем от-
ношение, описывающее ее, является отображением (терминаль-
ным) вида
g: T × X × U → Y .
Система