Геометричне програмування

Геометричне програмування — розділ математичного програмування, що вивчає підхід до розв'язування нелінійних задач оптимізації спеціальної структури. Термін вперше ввели 1967 року Шаблон:Нп, Е. Пітерсон і К. Зенер. Назва дисципліни пов'язана з тим, що однією з основних у викладаній теорії є нерівність між середнім геометричним і середнім арифметичним і її узагальнення. Передумовою до розвитку геометричного програмування стали деякі геометричні задачі і методи їх розв'язування. Базовим поняттям геометричного програмування є позіном.

Формулювання задачі геометричного програмування

Знайти найменше значення функції $g_0(t)$ за обмежень:

$t_1>0,t_2>0,...,t_m>0$

і

$g_1(t)⩽1,g_2(t)⩽1,...,g_p(t)⩽1,$.

Тут

$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$

і

$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)$ — позіноми.

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

Приклад 1

Знайти довжини сторін прямокутника заданого периметра, що має найбільшу площу. Те саме для трикутника.

Приклад 2

$\prod _{i=1}^n{x}_i^{{\beta }_i}\to \max$

за обмежень

$\sum _{i=1}^n{\alpha }_i{x}_i=S,x_i>0,x_i\in ℝ,$

де ${\beta }_i>0,{\alpha }_i>0,{\beta }_i\in ℝ,{\alpha }_i\in ℝ,i=\overline{1,n},$

Розв'язком задачі є вектор $x_{}^{*}$ з компонентами $x_i^{*}=\frac{{\beta }_{i}S}{{\alpha }_i\beta },$ де $\beta =\sum _{i=1}^n{\beta }_i.$

Програмні засоби

Існує декілька пакунків програм, які допомагають формулювати та розв'язувати задачі геометричного програмування.

• MOSEK Шаблон:Webarchive — це комерційний розв'язувач, здатний розв'язувати задачі геометричного програмування, а також інші задачі нелінійної оптимізації.
• CVXOPT Шаблон:Webarchive — це розв'язувач із відкритим кодом для опуклих задач оптимізації.
• GPkit Шаблон:Webarchive — це пакунок Python для чіткого визначення та маніпулювання моделями геометричними програмування. Містить низку прикладів моделей геометричного програмування, написаних разом із цим пакетом.
• GGPLAB Шаблон:Webarchive — це набір інструментів MATLAB для постановки та вирішення задач геометричного програмування (ГП) та узагальнених задач геометричного програмування (УГП).
• CVXPY Шаблон:Webarchive — це вбудована в Python мова моделювання для визначення та розв'язування опуклих задач оптимізації, включано з ГП, УГП та LLCP.

Див. також

• Моном
• Позіном

Література

• Шаблон:Книга
• Шаблон:Книга