Задача ГП без ограничений

Постановка задачи

Задача геометрического программирования без ограничений заключается в нахождении положительного вектора $$x = (x_1, \ldots, x_m)$$, при котором значение позинома $$g(x)$$ будет наименьшим:

$$g(x)=\sum\limits_{i=1}^{n}u_{i}=\sum\limits_{i=1}^{n}c_{i}\prod\limits_{j=1}^{m}{x_{j}}^{a_{ij}}\rightarrow\min,$$ $$x_j>0,\ c_i>0, \ a_{ij}\in \mathbb{R},\ i=\overline{1,n},\ j=\overline{1,m}.$$

Введем специальные обозначения для индексных множеств задачи ГП:

$$I=[1, 2, \ldots, n],\ J=[1, 2, \ldots, m].$$

Эти обозначения удобно использовать, когда не важен порядок перечисления индексов, поэтому в таких случаях записи $$i=\overline{1,n}$$ и $$i\in I$$, а также $$\ j=\overline{1,m}\mbox{ и } j\in J$$ будут эквивалентны.

Примеры задач оптимизации с позиномами

В этой лекции в качестве примеров мы приведем постановки задач оптимизации с позиномами без ограничений.

Пример 13 Требуется перевезти $$V$$ кубометров угля из шахты на завод. Для транспортировки угля необходимо изготовить открытый прямоугольный контейнер. Стоимость материала, идущего на изготовление боковых сторон и дна контейнера, составляет $$b$$ (руб. за квадратный метр), на фронтальные стороны - $$d$$ (руб. за квадратный метр). Стоимость доставки одного контейнера не зависит от его размера и составляет $$c$$ (руб.).

(рис 2.1)

Затраты на доставку угля складываются из транспортных расходов и стоимости материала, идущего на изготовление контейнера, в котором он будет перевозиться. Требуется выбрать размеры контейнера, при которых эти затраты будут минимальны.

Обозначим через $$L$$ - длину, $$W$$ - ширину и $$H$$ - высоту контейнера. Тогда контейнер будет использоваться $$\frac{V}{LWH}$$ раз. Тогда транспортные расходы равны $$\frac{c V}{LWH}$$ (руб.). Стоимость материала, потраченного на изготовление фронтальных сторон, составит $$2 d LH$$ (руб.), боковых сторон - $$2 b HW$$ (руб.), дна - $$b LW$$ (руб.).

Таким образом, задача свелась к минимизации позинома, выражающего суммарные затраты:

$$g(L, W, H) = \frac{c V}{LWH}+2 d LH+2 b HW+ b LW \rightarrow \min.$$

Пример 14 Корыто имеет форму полуцилиндра (рис. 2.2). При каких размерах его вес будет минимальным, если толщина стенок равна $$t$$, емкость равна $$v$$, а удельный вес материала равен - $$\gamma$$?

(рис 2.2)

Обозначим через $$r$$ - внутренний радиус корыта, $$l$$ - внутреннюю длину. Тогда вес торцовых стенок равен

$$G_{1} = \gamma\pi (r + t)^{2}t,$$

вес остальной части корыта равен

$$G_{2} =\frac{1}{2} \gamma l [ \pi (r + t)^{2} - \pi r^{2}] =\frac{\gamma \pi t}{2} l (2 r + t).$$

Так как $$v = \pi r^{2}l/2$$, то $$l/2 = v/(\pi r^{2})$$ и

$$G_{2} = \gamma\pi t \frac{v}{\pi r^2} (2 r + t).$$

Следовательно, вес корыта равен

$$G = G_1 + G_2 = c (r+t)^2 + \frac{cv}{\pi r^2} (2 r+t),$$

где $$c = \gamma\pi t$$, или

$$G = c \left[ r^2 + 2 rt + t^2 + \frac{2 v}{\pi r} + \frac{vt}{\pi r^2} \right],$$

или

$$G = c \left[ r^2 + 2 rt + t^2 +\frac{2 b}{r} + \frac{bt}{r^2}\right],$$

где $$b = v/\pi$$.

Таким образом, задача свелась к минимизации позинома:

$$g(r) =r^2 + 2 rt + \frac{2 b}{r} + \frac{bt}{r^2}\rightarrow \min.$$

Пример 15 Работа, затрачиваемая на сжатие 1 кг воздуха в поршневом компрессоре от давления $$\rho_0$$ до давления $$\rho$$ ( $$\rho > \rho_0);$$ отношение $$\rho / \rho_{0}$$ называется степенью сжатия), выражается формулой

$$A = RT_{0}\frac{\gamma}{\gamma - 1}\left[ \left(\frac{\rho}{\rho_0}\right)^{(\gamma - 1)/\gamma} - 1\right],$$

где $$R$$ - так называемая газовая постоянная, $$T_0$$ - абсолютная температура воздуха до сжатия, $$\gamma$$ $$(\gamma >1)$$ - некоторая постоянная, учитывающая конструктивные особенности компрессора. Для получения высоких давлений делают многоступенчатые компрессорные установки, состоящие из нескольких последовательно соединенных компрессоров (ступеней) с холодильными устройствами между ступенями. Пусть проектируется $$n$$ -ступенчатая компрессорная установка и предполагается воздух, поступающий в любую из ступеней, охлаждать до температуры $$T_{0}$$. Требуется при заданных $$n, \ \rho_0, \ \rho, \ T_0$$ определить такие промежуточные значения давлений $$\rho_1, \rho_2,\ldots,\rho_{n-1}$$, чтобы работа, затрачиваемая на весь процесс сжатия, была минимальна.

По формуле (20) работа, затрачиваемая на сжатие воздуха в $$i$$ -й ступени, равна

$$A_{i} = RT_{0}\frac{\gamma}{\gamma - 1}\left[\left(\frac{\rho_i}{\rho_{i-1}}\right)^{{(\gamma-1)}/ \gamma} - 1\right], \ i = \overline{1,n}, \ \rho_n= \rho.$$

Следовательно, при выбранных $$\rho_1, \rho_2,\ldots,\rho_{n-1}$$ работа, затрачиваемая на весь процесс сжатия, выразится формулой

$$A = \sum\limits_{i = 1}^{n}A_{i} = RT_{0}\frac{\gamma}{\gamma - 1} \left[ \sum\limits_{i=1}^{n}\left(\frac{\rho_i}{\rho_{i-1}}\right)^{{(\gamma-1)}/ \gamma} - n\right].$$

Таким образом, задача свелась к нахождению наименьшего значения позинома:

$$g(\rho_1, \rho_2,\ldots,\rho_{n-1}) =\sum\limits_{i=1}^{n}\left(\frac{\rho_i}{\rho_{i-1}}\right)^{{(\gamma-1)}/ \gamma}\rightarrow \min.$$

Теперь можно сказать, что задачи из примеров 13, 14, 15 - это задачи ГП.

В некоторых случаях оптимальное решение задачи ГП можно получить при помощи теоремы 2 из лекции 1. Приведем примеры.

Пример 16 Решим задачу геометрического программирования

$$g(x_1,\ldots,x_m) = \sum\limits_{i =1}^{m} \alpha_{i} x_{i}+ \frac{b}{\prod\limits_{i=1}^{m}x_{i}^{\alpha_i}}\rightarrow \min,$$ $$x_{i} > 0,\ i=\overline{1,m}.$$

Предполагается, что $$\ b > 0,\ \alpha_i > 0,\ i=\overline{1,m}$$. Обозначим через $$\alpha_{m+1} = b$$, $$x_{m+1} = \prod\limits_{i=1}^{m}x_{i}^{-\alpha_i}$$. Тогда $$x_{m+1}\prod\limits_{i=1}^{m}x_{i}^{\alpha_i} = 1$$. Во введенных обозначениях задача с позиномом $$g(x_1,\ldots,x_m)$$ принимает вид:

$$f(x_1,\ldots,x_{m+1}) =\sum\limits_{i =1}^{m+1} \alpha_{i} x_{i}\rightarrow \min,$$ $$x_{i} > 0,\ \ i=\overline{1,m+1}$$

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

$$x_{m+1}\prod\limits_{i=1}^{m}x_{i}^{\alpha_i} = 1.$$

Воспользуемся теоремой 2 при $$n = m + 1$$, $$\beta_i = \alpha_i$$, $$(i = \overline{1,n})$$, $$\beta_{m+1} = 1$$, $$\beta =\sum\limits_{i=1}^{n}\beta_i$$, $$P = 1$$:

$$\min f(x_1,\ldots,x_{m+1}) =\min g(x_1,\ldots,x_m) = \beta b^{1/\beta},$$

причем минимум достигается в единственной точке

$$(b^{1/\beta},\ldots, b^{1/\beta}).$$

{Пример 15 (продолжение). Найдем теперь решение получившейся задачи ГП:

$$g(\rho_1, \rho_2,\ldots,\rho_{n-1}) =\sum\limits_{i=1}^{n}\left(\frac{\rho_i}{\rho_{i-1}}\right)^{{(\gamma-1)}/ \gamma}\rightarrow\min.$$

Обозначим через

$$x_i = \left(\frac{\rho_i}{\rho_{i-1}}\right)^{{(\gamma-1)}/ \gamma}, \ i = \overline{1,n}.$$

Тогда сумма $$x_i$$ равна константе, так как выполнено следующее равенство:

$$\prod\limits_{i=1}^{n}x_i = \left[\prod\limits_{i=1}^{n}\left(\frac{\rho_i}{\rho_{i-1}}\right)\right]^{(\gamma-1)/\gamma} = \left(\frac{\rho}{\rho_0}\right)^{(\gamma-1)/\gamma}.$$

Воспользуемся теоремой 2 при $$P = \left(\frac{\rho}{\rho_0}\right)^{(\gamma-1)/\gamma}$$, $$\alpha_i=1$$, $$\beta_i =1$$, $$(i = \overline{1,n})$$:

$$\min\limits_{x_1\ldots x_n = c,\atop x_i >0}\sum\limits_{i=1}^{n}x_{i} = n P^{1/n} = n\left(\frac{\rho}{\rho_0}\right)^{(\gamma-1)/(n\gamma)},$$

и достигается он только при $$x_{1} = x_{2} = \ldots =x_{n} = \left(\frac{\rho}{\rho_0}\right)^{(\gamma-1)/(n\gamma)}$$.

Система уравнений

$$x_{i} = \left(\frac{\rho_i}{\rho_{i-1}}\right)^{(\gamma-1)/\gamma} = \left(\frac{\rho}{\rho_0}\right)^{(\gamma-1)/(n\gamma)}, \ i=\overline{1,n},$$

имеет положительное решение

$$\rho_{1} =\rho_{0}q,\ \rho_{2} =\rho_{1}q = \rho_{0}q^2,\ldots, \ \rho_{n-1} =\rho_{n-2}q = \rho_{0}q^{n-1}, \mbox{ где }q = (\rho/\rho_0)^{1/n}.$$

Таким образом, работа, затрачиваемая на $$n$$ -ступенчатый процесс сжатия газа, минимальна, когда на всех ступенях степени сжатия одинаковы и равны $$\rho_i/\rho_{i-1}$$, то есть числа $$\rho_0,\ \rho_1,\ldots,\ \rho_n = \rho$$ образуют геометрическую прогрессию со знаменателем $$q = (\rho/\rho_0)^{1/n}$$.

В следующих лекциях мы вернемся к задачам из примеров 14, 15 и решим их.

Понижение размерности задачи ГП

В общем случае сложность решения экстремальной задачи растет с ростом числа переменных, входящих в задачу. Принято это число называть размерность задачи. Для многих задач ГП размерность задачи может быть уменьшена с помощью простых преобразований.

Пусть требуется минимизировать позином

$$g(x)=\sum\limits_{i=1}^{n}c_{i}\prod\limits_{j=1}^{m}{x_{j}}^{a_{ij}},\quad x_j>0,\ c_i>0, \ a_{ij}\in \mathbb{R}.$$

Матрицей экспонент позинома называется $$n\times m$$ -матрица $$A = \|a_{ij}\|$$, каждый столбец которой образован показателями степеней соответствующей переменной $$x_j$$. Будем обозначать через $$A_j$$ столбец $$j$$ этой матрицы.

Напомним определение из курса линейной алгебры. Говорят, что столбец $$A_k$$ матрицы $$A$$ является линейной комбинацией остальных столбцов этой матрицы, если можно указать такие вещественные числа $$\lambda_j$$, что выполняются равенства

$$A_k = \sum_{j=\overline{1,m},\ j\neq k}\lambda_jA_j.$$

Пример 17 Покажем, что в матрице экспонент позинома

$$g(x_1, x_2, x_3) = 4 x_{1}^{-1}x_{2}x_{3} + 5 x_{2}^{2}x_{3}^{4} + x_{1}x_{2}^{-3}x_{3}^{-5}$$

имеет место линейная зависимость столбцов.

Матрица экспонент позинома $$g(x_1, x_2, x_3)$$ имеет вид:

$$A=\left\| \begin{array}{rrr} -1 1 1 \\ 0 2 4 \\ 1 -3 -5 \end{array} \right\|.$$

Третий столбец этой матрицы является линейной комбинацией первых двух столбцов с коэффициентами $$\lambda_1 = 1,\ \lambda_2 = 2$$:

$$A_3 = 1\times A_1 + 2\times A_2,$$$$\left\|\begin{array}{r} 1 \\ 4 \\ -5 \end{array}\right\|=\left\|\begin{array}{r} -1 \\ 0 \\ 1 \end{array}\right\|+ 2\times \left\|\begin{array}{r} 1 \\ 2 \\ -3 \end{array}\right\|.\qquad$$

Наличие линейной зависимости столбцов в матрице экспонент упрощает решение задачи ГП. Приведем теорему, которая показывает, в чем именно заключается это упрощение.

Теорема 3 Пусть столбец $$A_j$$ матрицы экспонент $$A$$ позинома $$g(x_1,\ldots, x_m)$$ является линейной комбинацией других столбцов. Обозначим через $$f$$ - позином от $$m - 1$$ переменной, получающийся при подстановке в позином $$g$$ переменной $$x_j = 1$$ :

$$f(x_1,\ldots, x_{j-1},x_{j+1},\ldots,x_{m}) = g(x_1,\ldots, x_{j-1}, 1, x_{j+1},\ldots,x_{m}).$$

Тогда в предположении, что обе функции достигают своих минимумов, верны следующие утверждения:

$$\min g = \min f$$ ;

если $$(x_{1}^{*},\ldots, x_{j-1}^{*},x_{j+1}^{*},\ldots,x_{m}^{*})$$ - точка минимума позинома $$f$$, то $$(x_{1}^{*},\ldots, x_{j-1}^{*}, 1, x_{j+1}^{*},\ldots,x_{m}^{*})$$ - точка минимума позинома $$g$$.

Процедуру понижения размерности задачи ГП можно повторять до тех пор, пока все столбцы не станут линейно независимыми. Таким образом, количество возможных шагов понижения размерности задачи ГП ограничено максимальным числом линейно независимых столбцов матрицы экспонент $$A$$. Далее будем обозначать это число через $$r$$ и называть рангом матрицы $$A$$.

Таким образом, если ранг $$r$$ меньше числа переменных задачи $$m$$, то задача минимизации исходного позинома от $$m$$ переменных может быть сведена к задаче минимизации позинома от $$r$$ переменных. Приведем пример.

Пример 17(продолжение). Понизим размерность задачи

$$g(x_1, x_2, x_3) = 4 x_{1}^{-1}x_{2}x_{3} + 5 x_{2}^{2}x_{3}^{4} + x_{1}x_{2}^{-3}x_{3}^{-5}\rightarrow\min,$$

применив теорему 3}.

Ранее было показано, что третий столбец матрицы экспонент этого позинома является линейной комбинацией остальных столбцов: $$A_3 = 1\times A_1 + 2\times A_2$$. Поэтому по теореме 3 минимальное значение позинома $$g$$ совпадает с минимальным значением позинома $$f$$:

$$f(x_1, x_2) = g(x_1, x_2, 1) = 4 x_{1}^{-1}x_{2} + 5 x_{2}^{2} + x_{1}x_{2}^{-3}.$$

Матрица экспонент $$A'$$ позинома $$f$$ (получается удалением из матрицы $$A$$ столбца $$A_3$$ ) имеет вид:

$$A' = \left\| \begin{array}{rr} -1 1 \\ 0 2 \\ 1 -3 \end{array} \right\|.$$

Очевидно, что столбцы матрицы $$A'$$ линейно независимы, следовательно, ее ранг (как и ранг матрицы $$A$$ ) равен 2.

В случае существования линейной зависимости столбцов матрицы экспонент можно поступить по-другому - понизить размерность задачи, выполнив замену переменных. Приведем примеры.

Пример 18 Понизим размерность задачи$$g(x_1, x_2, x_3) = 5 x_{1}x_{2}^{3}x_{3}^{-2} + 7 x_{1}x_{2}^{3}x_{3}\rightarrow \min,$$ выполнив замену переменных.

Переменные $$x_{1}$$ и $$x_{2}$$ входят во все мономы в виде комбинации $$x_{1}x_{2}^{3}$$. Выполним замену $$y = x_{1}x_{2}^{3}$$. Получим позином

$$f(y, x_3) = 5 yx_{3}^{-2} + 7 yx_{3}.$$

Его матрица экспонент

$$A' = \left\| \begin{array}{rr} 1 -2 \\ 1 1 \end{array} \right\|$$

имеет ранг, равный 2.

Пример 19 Понизим размерность задачи$$g(x_1, x_2, x_3) = 2 x_{1}x_{2}x_{3}^{2} + 3 x_{1}^{-4}x_{2}^{2}x_{3}^{4} + x_{2}^{-1}x_{3}^{1}\rightarrow \min,$$ выполнив замену переменных.

Заметим, что комбинация $$x_{2}x_{3}^{2}$$ входит во все мономы в различных степенях. Выполним замену $$y = x_{2}x_{3}^{2}$$, тогда получим позином

$$f(y, x_1) = 2 x_{1}y + 3 x_{1}^{-4}y^{2} + y^{-1}.$$

Его матрица экспонент

$$A' = \left\| \begin{array}{rr} 1 1 \\ -4 2 \\ 0 -1 \end{array} \right\|$$

имеет ранг, равный 2.

Число переменных задачи далее не может быть уменьшено.

Рассмотрим пример, в котором линейная зависимость некоторых столбцов видна сразу, но есть еще и неочевидная зависимость.

Пример 20 Понизим размерность задачи

$$g(x_1, x_2, x_3, x_4) = % 4 x_{1}^{2}x_{3}^{-1}x_{4} + x_{1}x_{2}^{0. 5}x_{3}x_{4}^{-1} + % 3 x_{1}^{-2}x_{2}x_{3}^{4}x_{4}^{-4}\rightarrow \min.$$

Заметим, что комбинация $$x_{3}x_{4}^{-1}$$ входит во все мономы в различных степенях. Выполнив замену $$y = x_{3}x_{4}^{-1}$$, получим позином

$$f(x_1, x_2, y) = 4 x_{1}^{2}y^{-1} + x_{1}x_{2}^{0. 5}y + 3 x_{1}^{-2}x_{2}y^{4},$$

его матрица экспонент

$$A' = \left\| \begin{array}{rlr} 2 0 -1 \\ 1 0. 5 1 \\ -2 1 4 \end{array} \right\|.$$

Третий столбец этой матрицы является линейной комбинацией первых двух столбцов с коэффициентами $$\lambda_1 = -0.5,\ \lambda_2 = 3$$:

$$A_3 = -0.5\times A_1 + 3\times A_2$$,

$$\left\|\begin{array}{r} -1 \\ 1 \\ 4 \end{array}\right\|=-0.5\times \left\|\begin{array}{r} 2 \\ 1 \\ -2 \end{array}\right\|+ 3\times \left\|\begin{array}{l} 0 \\ 0. 5 \\ 1 \end{array}\right\|.$$

По теореме 3 вместо минимизации позинома

$$f(x_1, x_2, y) = 4 x_{1}^{2}y^{-1} + x_{1}x_{2}^{0.5}y + 3 x_{1}^{-2}x_{2}y^{4},$$

можно минимизировать позином

$$h(x_1, x_2) = f(x_1, x_2, 1) = 4 x_{1}^{2} + x_{1}x_{2}^{0.5} + 3 x_{1}^{-2}x_{2}.$$

Матрица экспонент этого позинома получается удалением из матрицы позинома $$f$$ третьего столбца:

$$A'' = \left\| \begin{array}{rl} 2 0 \\ 1 0. 5 \\ -2 1 \end{array} \right\|.$$

Очевидно, что столбцы матрицы $$A"$$ линейно независимы, следовательно, ее ранг (как и ранг матрицы позинома $$g$$ ) равен 2. Число переменных больше не может быть уменьшено и необходимо решить задачу минимизации позинома $$h(x_1, x_2)$$.

Краткие итоги

Сформулирована задача геометрического программирования без ограничений. Описана процедура понижения размерности задачи в случае очевидной и неочевидной линейной зависимости.