Геометрическое программирование — раздел математического программирования, изучающий подход к решению нелинейных задач оптимизации специальной структуры. Термин впервые ввели в 1967 году Р. Даффин, Э. Питерсон и К. Зенер. Название дисциплины связано с тем, что одним из основных в излагаемой теории является неравенство между средним геометрическим и средним арифметическим и его обобщения. Предпосылкой к развитию ГП послужили некоторые геометрические задачи и методы их решения. Базовым понятием ГП является позином .
Формулировка задачи геометрического программирования
править
Найти минимальное значение функции
g
0
(
t
)
{\displaystyle g_{0}(t)}
при ограничениях:
t
1
>
0
,
t
2
>
0
,
.
.
.
,
t
m
>
0
{\displaystyle t_{1}>0,t_{2}>0,...,t_{m}>0}
и
g
1
(
t
)
⩽
1
,
g
2
(
t
)
⩽
1
,
.
.
.
,
g
p
(
t
)
⩽
1
,
{\displaystyle g_{1}(t)\leqslant 1,g_{2}(t)\leqslant 1,...,g_{p}(t)\leqslant 1,}
.
Здесь
g
k
(
t
)
=
∑
i
∈
J
[
k
]
c
i
t
1
a
i
1
t
2
a
i
2
.
.
.
t
m
a
i
m
,
k
=
0
,
1
,
.
.
.
,
p
{\displaystyle g_{k}(t)=\sum _{i\in J[k]}c_{i}t_{1}^{a_{i1}}t_{2}^{a_{i2}}...t_{m}^{a_{im}},k=0,1,...,p}
,
где
J
[
k
]
=
(
m
k
,
m
k
+
1
,
m
k
+
2
,
.
.
.
,
n
k
)
k
=
0
,
1
,
.
.
.
,
p
{\displaystyle J[k]=(m_{k},m_{k}+1,m_{k}+2,...,n_{k})k=0,1,...,p}
и
m
0
=
1
,
m
1
=
n
0
+
1
,
m
2
=
n
1
+
1
,
.
.
.
,
m
p
=
n
p
−
1
+
1
,
n
p
=
p
{\displaystyle m_{0}=1,m_{1}=n_{0}+1,m_{2}=n_{1}+1,...,m_{p}=n_{p-1}+1,n_{p}=p}
.
Функции
g
k
(
t
)
{\displaystyle g_{k}(t)}
- позиномы .
Пример задач из геометрического программирования
править
Найти длины сторон прямоугольника заданного периметра, имеющего наибольшую площадь.
То же для треугольника.
∏
i
=
1
n
x
i
β
i
→
max
{\displaystyle \prod \limits _{i=1}^{n}x_{i}^{\beta _{i}}\rightarrow \max }
при ограничениях
∑
i
=
1
n
α
i
x
i
=
S
,
x
i
>
0
,
x
i
∈
R
,
{\displaystyle \sum \limits _{i=1}^{n}\alpha _{i}x_{i}=S,\ x_{i}>0,\ x_{i}\in \mathbb {R} ,}
где
β
i
>
0
,
α
i
>
0
,
β
i
∈
R
,
α
i
∈
R
,
i
=
1
,
n
¯
,
{\displaystyle \beta _{i}>0,\ \alpha _{i}>0,\beta _{i}\in \mathbb {R} ,\alpha _{i}\in \mathbb {R} ,\ i={\overline {1,n}},}
Решением задачи является вектор
x
∗
{\displaystyle x_{}^{*}}
с компонентами
x
i
∗
=
β
i
S
α
i
β
,
{\displaystyle x_{i}^{*}={\frac {\beta _{i}S}{\alpha _{i}\beta }},}
где
β
=
∑
i
=
1
n
β
i
.
{\displaystyle \ \beta =\sum \limits _{i=1}^{n}\beta _{i}.}
Связанные результаты
править
Р. Даффин, Э. Питерсон, К. Зенер. "Geometric Programming - Theory and Application". — 1967.
Р. Даффин, Э. Питерсон, К. Зенер. Геометрическое программирование. — М. : Мир, 1972. — 311 с.