Задача ГП без ограничений: двойственность

Двойственная задача

Теория двойственности для задач линейного программирования обязательно изучается в курсах, посвященных решению экстремальных задач. Однако и для любой задачи нелинейного программирования, частным случаем которой является задача ГП, можно указать некоторую другую задачу, которая называется двойственной по отношению к исходной (прямой) задаче. Основная идея двойственности состоит в том, что при некоторых предположениях о свойствах прямой задачи равны оптимальные значения целевых функций прямой и двойственной задач. Это дает возможность получить решение прямой задачи, решив двойственную задачу.

Рассмотрим определенную в лекции 2 задачу ГП без ограничений:

$$g(x)=\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}.$$

Двойственной задачей для задачи (32) называется следующая задача:

$$v(w) = \prod\limits_{i=1}^{n}\Bigl(\frac{c_i}{w_i}\Bigr)^{w_i}\rightarrow\max$$

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

$$\sum\limits_{i=1}^{n}w_{i}a_{ij} = 0,\ j = \overline{1,m},$$ $$\sum\limits_{i=1}^{n} w_{i}=1,$$ $$w_i>0,\ i=\overline{1,n}.$$

Функция $$v(w)$$ называется двойственной функцией для функции $$g(x)$$, переменные $$w_i,\ i=\overline{1,n}$$ называются двойственными переменными. Ограничения (34) называются условиями ортогональности, ограничение (35) называется условием нормальности.

Систему ограничений (34)--(35) можно записать в матричном виде. Здесь и далее будем использовать матричную форму записи, принятую в теории двойственности: вектор двойственных переменных - левый элемент умножения, матрица ограничений - правый. Тогда получим формулу

$$w\overline{A}=b,$$

где $$\overline{A}=||A|\mathbf{1}||$$,\ $$b_j=0,\ j=\overline{1,m}$$,\ $$b_{m+1}=1$$.

Прямая и двойственная задачи связаны следующей теоремой, доказательство которой имеется, например, в [5]:

Теорема 7 (теорема двойственности) Если задача (32) разрешима и достигает своего минимума в точке $$x^{*}$$, то двойственная задача (33) также разрешима и достигает своего максимума в некоторой точке $$w^{*}$$. При этом выполняются следующие равенства:

$$g(x^*) = v(w^*),$$ $$c_i\prod\limits_{j=1}^{m}({x^{*}_j})^{a_{ij}} = v(w^*) w_{i}^{*}, \ i=\overline{1,n}.$$

Из теоремы двойственности следует, что для нахождения оптимального решения прямой задачи ГП можно попытаться сначала найти оптимальное решение двойственной задачи. Если решение двойственной задачи существует, то оптимальное решение прямой задачи удовлетворяет уравнениям (39). В противном случае прямая задача не имеет оптимального решения.

Такой подход особенно просто реализовать, когда двойственная задача имеет единственное допустимое решение, которое, естественно, будет и оптимальным. Приведем примеры.

Пример 27 Докажем, используя теорему двойственности, что следующая задача ГП не имеет оптимального решения:$$g(x) = x_1^{2} + 2x_1x_2+ x_2^{-2} \rightarrow \min,$$ $$x_j>0,\ j=1, 2.$$

Определим сначала двойственную функцию для позинома $$g(x)$$, используя формулу (33). Позином состоит из трех мономов, следовательно, двойственная функция имеет три переменные: $$w_1, w_2, w_3$$. Вектор коэффициентов позинома $$c = (1, 2, 1)$$. Следовательно, двойственная функция для позинома $$g(x)$$ имеет вид:

$$v(w) = \left(\frac{1}{w_1}\right)^{w_1}\left(\frac{2}{w_2}\right)^{w_2}\left(\frac{1}{w_3}\right)^{w_3}.$$

Запишем теперь условия ортогональности для позинома (формулы (34)). Поскольку в позином $$g(x)$$ входят две переменные $$x_1,\ x_2$$, то условия ортогональности состоят из двух равенств. Матрица экспонент позинома $$g(x)$$

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

где $$j$$ -й столбец образован показателями степеней при $$j$$ -й переменной $$(j=1, 2)$$. По формуле (34) условия ортогональности для позинома $$g(x)$$ имеют вид:

$$\begin{array}{rcrcrcr} 2w_1+w_2=0, \\ w_2-2w_3=0. \end{array}$$

Запишем условие нормальности (формулы (35)):

$$w_1 + w_2 + w_3 = 1.$$

Таким образом, двойственная задача имеет вид:

$$v(w) = \left(\frac{1}{w_1}\right)^{w_1}\left(\frac{2}{w_2}\right)^{w_2}\left(\frac{1}{w_3}\right)^{w_3}\rightarrow\max$$

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

$$\begin{array}{rcrcrcr} 2w_1+w_2= 0, \\ w_2-2w_3= 0, \\ w_1+w_2+w_3= 1, \end{array}$$ $$w_i>0,\ i=1, 2, 3.$$

Cистема линейных уравнений (41) имеет единственное решение: $$w_{1}^{*} = -0.5$$, $$w_{2}^{*} = 1$$, $$w_3^{*} = 0.5$$, которое не удовлетворяет условию (36): $$w_i>0\ (i = 1, 2, 3)$$. Это означает, что не существует допустимого решения двойственной задачи, следовательно, не существует и оптимального решения этой задачи. Из теоремы двойственности следует, что в этом случае прямая задача ГП не имеет оптимального решения.

Пример 28 Решим следующую задачу ГП, используя теорему двойственности:$$g(x) = x_{1}^{-5}x_{2}^{2} + 2x_{1}^{2}x_{2}^{-1} + 3x_{1}\rightarrow \min,$$ $$x_j>0,\ j=1, 2.$$

Определим сначала двойственную функцию для позинома $$g(x)$$. Позином состоит из трех мономов, следовательно, двойственная функция имеет три переменные: $$w_1, w_2, w_3$$. Вектор коэффициентов позинома $$c =(1, 2, 3)$$. Следовательно, двойственная функция для позинома $$g(x)$$ имеет вид:

$$v(w) = \left(\frac{1}{w_1}\right)^{w_1}\left(\frac{2}{w_2}\right)^{w_2}\left(\frac{3}{w_3}\right)^{w_3}.$$

Запишем теперь условия ортогональности для позинома. Поскольку в позином $$g(x)$$ входят две переменные $$x_1,\ x_2$$, то условия ортогональности состоят из двух равенств. Матрица экспонент позинома $$g(x)$$

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

где $$j$$ -й столбец образован показателями степеней при $$j$$ -й переменной $$(j=1, 2)$$. По формуле (34) условия ортогональности для позинома $$g(x)$$ имеют вид:

$$\begin{array}{rcrcrcr} -5w_1+2w_2+w_3=0, \\ 2w_1-w_2=0. \end{array}$$

Запишем условие нормальности (формула (35)):

$$w_1 + w_2 + w_3 = 1.$$

Таким образом, двойственная задача имеет вид:

$$v(w) = \left(\frac{1}{w_1}\right)^{w_1}\left(\frac{2}{w_2}\right)^{w_2}\left(\frac{3}{w_3}\right)^{w_3}\rightarrow\max$$

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

$$\begin{array}{rcrcrcr} -5w_1+2w_2+w_3= 0, \\ 2w_1-w_2= 0, \\ w_1+w_2+w_3= 1, \end{array}$$ $$w_i>0,\ i=1, 2, 3.$$

Так как система линейных уравнений (43) имеет единственное решение: $$w_{1}^{*} = 0.25$$, $$w_{2}^{*} = 0.5$$, $$w_3^{*} = 0.25$$ и оно удовлетворяет условию $$w_i>0\ (i=1, 2, 3)$$, то это оптимальное решение двойственной задачи. Теперь мы можем вычислить оптимальное значение двойственной функции. Ограничим точность вычисления значения $$v(w^*)$$ и наших дальнейших вычислений двумя знаками после запятой:

$$v(w^*) =\left(\frac{1}{0.25}\right)^{0.25}\left(\frac{2}{0.5}\right)^{0.5}\left(\frac{3}{0.25}\right)^{0.25}= 5.26 .$$

Согласно теореме двойственности$$g(x^*) = v(w^*) = 5.26.$$ Двойственная переменная $$w_i$$ показывают, каков вклад монома $$u_i$$ в минимальное значение целевой функции $$g(x^*)$$. Следовательно, вклад первого монома в целевую функцию составляет $$0.25$$, вклад второго - $$0.5$$, а вклад третьего - $$0.25$$.

Осталось определить оптимальное решение прямой задачи. Используем для этого формулы (39) из теоремы двойственности. Требуется решить нелинейную систему из трех уравнений с двумя неизвестными:

$$\begin{array}{rcr} x_{1}^{-5}x_{2}^{2}=5.26\times 0.25, \\ 2x_{1}^{2}x_{2}^{-1}=5.26\times 0.50, \\ 3x_{1}=5.26\times 0.25. \end{array}$$

Из третьего уравнения системы (44) находим, что $${x}_{1}^{*} = 0.44$$. Из второго уравнения получаем, что $${x}_{2}^{*} = 0.15$$. Не должен удивлять тот факт, что при нахождении решения системы (44) не использовалось первое уравнение системы. Это объясняется тем, что в этой системе одно из уравнений (любое) является избыточным.

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

Простейшая задача управления запасами

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

В классических моделях принято характеризовать запас неизбежными издержками на выполнение выбранной стратегии его пополнения. Мы рассмотрим задачу управления запасами в следующих предположениях: спрос на запасаемый продукт постоянен во времени; заказ выполняется мгновенно; дефицит не допускается.

Мы рассмотрим случай, когда общие затраты на управление запасами состоят из затрат на оформление заказов и затрат на их хранение. Введем следующие обозначения:

$$d$$ - спрос на запас (в единицу времени);

$$k$$ - затраты на оформление заказа (не зависят от его объема);

$$h$$ - затраты на хранение единицы складируемой продукции (в единицу времени).

В сделанных предположениях стратегия управления запасами будет определяться двумя величинами: объемом заказа $$q$$ и временем между двумя последовательными заказами $$t$$. Так как предполагается равномерный расход запаса, то

$$t=\frac{q}{d} .$$

Так как средний уровень запаса равен $$\frac{q}{2}$$, то затраты на хранение вычисляются по формуле:

$$h\frac{q}{2} t.$$

Используя введенные обозначения и формулу (45), напишем формулу для величины общих затрат $$S(q)$$ в единицу времени:

$$S(q)=\frac{k+h\frac{qt}{2}}{t}= \frac{kd}{q}+\frac{h}{2} q.$$

Естественно определить величину заказа $$q$$, при которой значение функции $$S(q)$$ минимально. Так как из формулы (46) следует, что функция $$S(q)$$ является позиномом, то мы используем для вычисления ее минимального значения теорему двойственности.

Определим сначала двойственную функцию для позинома $$S(q)$$. Позином состоит из двух мономов, следовательно, двойственная функция имеет две переменные. Вектор коэффициентов позинома $$c = (kd, \frac{h}{2})$$. Следовательно, двойственная функция для позинома $$S(q)$$ имеет вид:

$$v(w) = \left(\frac{kd}{w_1}\right)^{w_1}\left(\frac{h/2}{w_2}\right)^{w_2}.$$

Запишем теперь условия ортогональности для позинома. Поскольку в позином $$S(q)$$ входит одна переменная $$q$$, то условия ортогональности состоят из одного равенства. В равенстве два слагаемых, поскольку в позиноме два монома. Матрица экспонент позинома $$S(q)$$

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

По формуле (34) условие ортогональности для позинома $$S(q)$$ имеет вид:

$$-w_1 + w_2 = 0.$$

Запишем условие нормальности (формула (35)):

$$w_1 + w_2 = 1.$$

Таким образом, двойственная задача имеет вид:

$$v(w) = \left(\frac{kd}{w_1}\right)^{w_1}\left(\frac{0.5 h}{w_2}\right)^{w_2}$$

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

$$\begin{array}{c} -w_1 + w_2 = 0, \\ \hphantom{-}w_1 + w_2 = 1, \end{array}$$ $$w_i>0,\ i=1, 2.$$

Так как система линейных уравнений (47) имеет единственное решение: $$w_{1}^{*} = 0.5$$, $$w_{2}^{*} = 0.5$$ и оно удовлетворяет условию $$w_i>0$$ $$(i=1, 2)$$, то это оптимальное решение двойственной задачи. Теперь мы можем вычислить оптимальное значение двойственной функции:

$$v(w^*) =\left(\frac{kd}{0.5}\right)^{0.5}\left(\frac{0.5 h}{0.5}\right)^{0.5}=\sqrt{2kdh}.$$

Согласно теореме двойственности$$S(q^*) = v(w^*) = \sqrt{2kdh}.$$ Осталось определить оптимальное решение прямой задачи. Используем для этого формулы (39) из теоремы двойственности. Требуется решить нелинейную систему:

$$\begin{array}{rcr} k d {q}^{*^{-1}}=0.5 \sqrt{2kdh}, \\ 0.5 h q^{*}=0.5 \sqrt{2kdh}. \end{array}$$

Из любого уравнения находим, что $$q^* = {\sqrt{\frac{2 k d}{h}}}$$ \ (одно из уравнений является избыточным).

Степень трудности задачи ГП

Степень трудности задачи геометрического программирования (Degree of Difficulty или, сокращенно, DOD) определяется по формуле:

$$DOD = n -(m_{ind} + 1),$$

где $$n$$ - число мономов в позиноме, $$m_{ind}$$ - число независимых переменных (определяемое рангом матрицы $$\| a_{ij}\|$$ ).

Пример 13 (продолжение) Вычислим степень трудности для задачи ГП:

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

Матрица экспонент позинома $$g(L, W, H)$$

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

Здесь $$n = 4$$, $$m_{ind} = 3$$, поэтому $$DOD = 4-(3+1)= 0$$.

Пример 14 (продолжение). Вычислим степень трудности для задачи ГП:

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

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

$$A = \left\| \begin{array}{r} 2 \\ 1 \\ -1 \\ -2 \\ \end{array} \right\|.$$

Здесь $$n = 4$$, $$m_{ind} = 1$$, поэтому $$DOD = 4-(1+1)= 2$$.

Пример 29 Вычислим степень трудности для задачи ГП и запишем матрицу системы уравнений двойственной задачи из примера 28.

Вычислим степень трудности для задачи ГП:

$$g(x) = x_{1}^{-5}x_{2}^{2} + 2x_{1}^{2}x_{2}^{-1} + 3x_{1}\rightarrow \min,$$ $$x_j>0,\ j=1, 2.$$

Матрица экспонент позинома $$g(x)$$

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

Здесь $$n = 3$$, $$m_{ind} = 2$$, поэтому $$DOD = 3-(2+1)= 0$$. Система ограничений двойственной задачи имеет вид:

$$\begin{array}{rcrcrcr} -5w_1+2w_2+w_3= 0, \\ 2w_1-w_2= 0, \\ w_1+w_2+w_3= 1. \end{array}$$

Матрица системы ограничений двойственной задачи (формула (37)) имеет вид:

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

Заметим, что все столбцы этой матрицы линейно независимы. Таким образом, система (49) однозначно разрешима.

Для того, чтобы система уравнений {(34)}--{(35)} была однозначно разрешима, необходимо и достаточно, чтобы степень трудности задачи ГП была равна нулю. Если степень трудности больше нуля, то система {(34)}--{(35)} разрешима, но имеет не единственное решение. Двойственная задача в этом случае может быть переформулирована в терминах базисных переменных, число которых совпадает со степенью трудности задачи ГП.

Использование теоремы двойственности

Покажем на примерах, как в ряде случаев можно использовать теорему двойственности для решения задач ГП.

Решение задачи ГП при DOD=0

Вернемся к задаче о перевозке груза из лекции 2.

Пример 13 (продолжение) Решим задачу ГП:

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

Двойственная задача имеет вид:

$$v(w) =\left(\frac{c V}{w_1}\right)^{w_1}\left(\frac{2d}{w_2}\right)^{w_2}\left(\frac{2b}{w_3}\right)^{w_3}\left(\frac{b}{w_4}\right)^{w_4}\rightarrow\max$$

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

$$\begin{array}{rcrcrcrcr} -w_1+w_2+w_4=0, \\ -w_1+w_3+w_4=0, \\ -w_1+w_2+w_3=0, \\ w_1+w_2+w_3+w_4=1, \\ % w_i>0,i=1, 2, 3, 4. \end{array}$$ $$w_i>0,\ i=1, 2, 3, 4.$$

Степень трудности задачи ГП равна нулю (столбцы и строки матрицы системы уравнений линейно независимы), следовательно, система (50) разрешима и имеет единственное решение:

$$w_{1}^{*}= 2/5,\ w_{2}^{*} = 1/5,\ w_{3}^{*} = 1/5,\ w_{4}^{*} = 1/5.$$

Поскольку выполняется условие $$w_i>0\ (i=1, 2, 3, 4)$$, то это оптимальное решение двойственной задачи. Теперь мы можем вычислить оптимальное значение двойственной функции:

$$v(w^*) =\left(\frac{c V}{2/5}\right)^{2/5}\left(\frac{2d}{1/5}\right)^{1/5}\left(\frac{2b}{1/5}\right)^{1/5}\left(\frac{b}{1/5}\right)^{1/5}.$$

Рассмотрим численный пример. Пусть $$V = 400 \mbox{ м}^{3}$$, $$c = 10$$ руб., $$b = 1 000$$ руб., $$d = 2 000$$ руб. Вычислим значение двойственной функции при этих значениях параметров:

$$v(w^*) =\left(\frac{10\times 400}{2/5}\right)^{2/5}\left(\frac{2\times 2 000 }{1/5}\right)^{1/5}\left(\frac{2\times 1 000 }{1/5}\right)^{1/5}\left(\frac{1 000}{1/5}\right)^{1/5} = 10 000.$$

По теореме двойственности 7выполняется следующее равенство:

$$g(L^*,W^*,H^*)=v(w^*)=10 000\mbox{ (руб.)}$$

Вычислим теперь оптимальные значения переменных $$L$$, $$H$$, $$W$$, используя формулы (39):

$$\begin{array}{rcr} 4 000L{^{-1}}W{^{-1}}H{^{-1}}=10 000\ (2/5), \\ 4 000 LH=10 000\ (1/5), \\ 2 000 HW=10 000\ (1/5), \\ 1 000 LW=10 000\ (1/5). \end{array}$$

Упростив, получим систему уравнений:

$$\begin{array}{rcl} LWH=1, \\ LH=0.5, \\ HW=1, \\ LW=2. \end{array}$$

Решим систему, используя общий подход к решению такого рода нелинейных систем. Прологарифмируем каждое уравнение и выполним замену переменных $$\ln L = x_1$$, $$\ln W = x_2$$, $$\ln H = x_3$$.

Получим следующую систему линейных уравнений:

$$\begin{array}{rcrcrcl} x_1+x_2+x_3=\phantom{-}0, \\ x_1+x_3= -0.69, \ x_2+x_3=\phantom{-}0, \\ x_1+x_2=\phantom{-}0.69. \end{array}$$

Решая ее, находим $$x_1 = 0$$, $$x_2 = 0.69$$, $$x_3 = -0.69$$. Выполнив обратную замену $$L = \exp(x_1)$$, $$W = \exp(x_2)$$, $$H = \exp(x_3)$$, получаем оптимальные размеры контейнера: $$L^{*} = 1$$, $$W^{*} = 2$$, $$H^{*} = 0.5$$.