Геометрическое программирование

Геометрическое программирование — раздел математического программирования, изучающий подход к решению нелинейных задач оптимизации специальной структуры. Термин впервые ввели в 1967 году Р. Даффин, Э. Питерсон и К. Зенер. Название дисциплины связано с тем, что одним из основных в излагаемой теории является неравенство между средним геометрическим и средним арифметическим и его обобщения. Предпосылкой к развитию ГП послужили некоторые геометрические задачи и методы их решения. Базовым понятием ГП является позином.

Формулировка задачи геометрического программированияПравить

Найти минимальное значение функции $g_0(t)$$g_{{0}}(t)$  при ограничениях:

$t_1>0,t_2>0,...,t_m>0$$t_{{1}}>0,t_{{2}}>0,...,t_{{m}}>0$ 

и

$g_1(t)⩽<!--\; ⩽\; -->1,g_2(t)⩽<!--\; ⩽\; -->1,...,g_p(t)⩽<!--\; ⩽\; -->1,$$g_{{1}}(t)\leqslant 1,g_{{2}}(t)\leqslant 1,...,g_{{p}}(t)\leqslant 1,$ .

Здесь

$g_k(t)=\underset{i\in <!--\; \in \; -->J[k]}{\sum <!--\; \sum \; -->}{c}_i{t}_1^{a_{i1}}{t}_2^{a_{i2}}...t_m^{a_{im}},k=0,1,...,p$$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$$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$$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)$$g_{{k}}(t)$  - позиномы.

Пример задач из геометрического программированияПравить

Пример 1Править

Найти длины сторон прямоугольника заданного периметра, имеющего наибольшую площадь. То же для треугольника.

Пример 2Править

$\underset{i=1}{\overset{n}{\prod <!--\; \prod \; -->}}{x}_i^{{\mathrm{\beta <!--\; \beta \; -->}}_i}\to <!--\; \to \; -->max$$\prod \limits _{{i=1}}^{{n}}x_{{i}}^{{\beta _{{i}}}}\rightarrow \max$ 

при ограничениях

$\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{\mathrm{\alpha <!--\; \alpha \; -->}}_i{x}_i=S,x_i>0,x_i\in <!--\; \in \; -->\mathbb{R},$$\sum \limits _{{i=1}}^{{n}}\alpha _{{i}}x_{{i}}=S,\ x_{i}>0,\ x_{i}\in {\mathbb {R}},$ 

где ${\mathrm{\beta <!--\; \beta \; -->}}_i>0,{\mathrm{\alpha <!--\; \alpha \; -->}}_i>0,{\mathrm{\beta <!--\; \beta \; -->}}_i\in <!--\; \in \; -->\mathbb{R},{\mathrm{\alpha <!--\; \alpha \; -->}}_i\in <!--\; \in \; -->\mathbb{R},i=\stackrel{¯<!--\; ¯\; -->}{1,n},$$\beta _{i}>0,\ \alpha _{i}>0,\beta _{i}\in {\mathbb {R}},\alpha _{i}\in {\mathbb {R}},\ i=\overline {1,n},$ 

Решением задачи является вектор $x_{}^{\ast <!--\; \ast \; -->}$$x_{{}}^{{*}}$  с компонентами $x_i^{\ast <!--\; \ast \; -->}=\frac{{\mathrm{\beta <!--\; \beta \; -->}}_{i}S}{{\mathrm{\alpha <!--\; \alpha \; -->}}_i\mathrm{\beta <!--\; \beta \; -->}},$$x_{{i}}^{{*}}={\frac {\beta _{i}S}{\alpha _{i}\beta }},$  где $\mathrm{\beta <!--\; \beta \; -->}=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{\mathrm{\beta <!--\; \beta \; -->}}_i.$$\ \beta =\sum \limits _{{i=1}}^{{n}}\beta _{i}.$ 

Связанные результатыПравить

• Моном
• Позином

ЛитератураПравить

• Р. Даффин, Э. Питерсон, К. Зенер. "Geometric Programming - Theory and Application". — 1967.
• Р. Даффин, Э. Питерсон, К. Зенер. Геометрическое программирование. — М.: Мир, 1972. — 311 с.