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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

t_{1}>0, t_{2}>0, ..., t_{m}>0

и

g_{1}(t) \leqslant 1, g_{2}(t) \leqslant 1, ..., g_{p}(t) \leqslant 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\limits_{i =1}^{n}x_{i}^{\beta_{i}} \rightarrow \max

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

\sum\limits_{i =1}^{n}\alpha_{i}x_{i} = S,  \ x_i> 0,\    x_i\in\mathbb{R},

где \beta_i>0,\ \alpha_i>0, \beta_i\in\mathbb{R}, \alpha_i\in\mathbb{R},\ i = \overline{1,n},

Решением задачи является вектор x_{}^{*} с компонентами  x_{i}^{*}=\frac{\beta_i S}{\alpha_i\beta}, где \ \beta=\sum\limits_{i=1}^{n}\beta_i.

Связанные результаты[править | править вики-текст]

Литература[править | править вики-текст]

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