Составители:
Рубрика:
7
Доказательство. Пусть нашлось в D решение X', для которо-
го
AkX
ss
< (
)
при k
t
(X) = A
t
,
ks
≠
. Тогда, по определению, X' безус-
ловно лучше, чем X. Значит, решение X, по определению эффективнос-
ти, не эффективно, что противоречит условию теоремы. Следователь-
но,
()
() ,
min ,
kX Ats
tt
ss
XD
AkX
=≠
∈
=
что и требовалось доказать.
4. Динамическое программирование
Постановка задачи такова: найти минимум (максимум) f(x
1
, x
2
, ..., x
n
)=
= f
1
(x
1
)+f
2
(x
2
)+...+f
n
(x
n
) при условии, что x
1
+x
2
+...+x
n
= A
n
, где
AA
n
≤
.
Подобного рода задачи часто встречаются в экономике, технологии, орга-
низации производства.
Обозначим
()
12
11 2 2
, , ...,
( ) min ( ) ( ) ... ( )
n
nn nn
xx x
FA fx fx fx
=+++
, тогда
()
()
12
, ,...,
12
1
11 2 2
, , ...,
11 2 2
min ( ) ( ) ... ( )
min min ( ) ( ) ... ( ) .
n
n
n
nn
xx x
nn
xxxx
fx fx fx
fx fx fx
−
+++ =
=+++
Так как при поиске внутреннего минимума последнее слагаемое
fx
nn
(
)
не меняется, то последнее выражение можно переписать как
()
, , ...,
12
1
11 2 2 1 1
min ( ) min ( ) ( ) ... ( )
n
n
nn n n
xxxx
fx fx fx f x
−
−−
++++
.
Второе слагаемое внутри скобок можно обозначить как
11
()
nn
FA
−−
.
Тогда можно записать, что
()
11
()min () ( )
n
nn nn n n
FA fx F A
x
−−
=+
, где
x
1
+x
2
+...+x
n–1
= A
n–1
.
Для n = 2
()
2
22 22 11
()min () (
)
x
FA fx fx
=+
, где x
1
+x
2
= A
2
.
Страницы
- « первая
- ‹ предыдущая
- …
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »
