5.6. ГЕОМЕТРИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

Достаточно широкий и интересный с практической точки зрения класс задач НП составляют задачи геометрического программирования (ГП). Приведем пример такой задачи.

Пусть требуется переправить через речку 400 м3 гравия. Допустим, что гравий грузится в открытый ящик длиной , шириной  и высотой . Боковые стороны и дно ящика изготовлены из материала, 1 м2 которого стоит 10 условных денежных единиц (условн. денеж. ед.), а передняя и задняя стенки из материала, который стоит 20 таких единиц за 1 м2. Каждая перевозка ящика любых размеров с одного берега на другой и обратно стоит 0,1 условн. денеж. ед., причем после его использования ящик не будет иметь остаточной стоимости. Требуется найти такие размеры ящика , , , при которых суммарная стоимость перевозки 400 м3 гравия, включая стоимость самого ящика, будет минимальна.

При линейных размерах ящика , ,  число перевозок, которые требуется выполнить, чтобы перевезти 400 м3 гравия, составляет , а стоимость всех перевозок . Общая стоимость материала составляет . Следовательно, суммарная стоимость перевозок с учетом стоимости материала равняется

Заметим, що функция  состоит в рассматриваемом примере из слагаемых  вида , где .

Определение. Функции вида , где , носят название позиномов.

Для исследования задачи минимизаци позиномов воспользуемся неравенством о среднем арифметическом и геометрическом, которое называют геометрическим (отсюда и название соответствующего класса методов).

Для  переменных  оно выглядит так:

.                                   (5.6.1)

Причем равенство в (5.6.1) будет в том случае, когда . Более общим случаем является геометрическое неравенство для средневзвешенных арифметического и геометрического:

                                (5.6.2)

где все веса  и выполняется условие нормализации .

В частности, при  получим .

Доказательство неравенства (5.6.2) приведено в приложении 3.

Это геометрическое неравенство можно использовать для нахождения минимума позинома .

Пример 5.8. Пусть . Чтобы найти нижнюю оценку для , используем геометрическое неравенство при

 .

Тогда

 .

Таким образом, 8 является нижней оценкой для  при . Более того, 8 является точной нижней оценкой, поскольку

               

Двойственная функция. Рассмотрим общий случай геометрического неравенства (5.6.2):

где все , а веса  удовлетворяют условию нормализации .

Для удобства произведем замену переменных в (5.6.2), полагая . Тогда геометрическое неравенство (5.6.2) примет вид

                                     (5.6.3)

Левая часть (5.6.3) представляет собой функцию-позином . Назовем ее прямой функцией задачи геометрического программирования. Правая часть (5.6.3) называется преддвойственной функцией. Обозначим ее через . Тогда неравенство (5.6.3) можно записать так:

                                           (5.6.4)

Если исходная функция – позином, причем все , то подставляя выражение для  в правую часть (5.6.4), получим выражение для :

             (5.6.5)

где

                             (5.6.6)

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

                  (5.6.7)

Из неравенства (5.6.3) следует, что  имеет положительную точную нижнюю грань . Поэтому

                                  (5.6.8)

Из (5.6.8) следует, что  является оценкой сверху для двойственной функции для любого выбора весов , при котором все показатели становятся нулями.

Пример 5.9. Используем полученные выше результаты, чтобы решить задачу, рассмотренную выше:

Для функции  запишем двойственную функцию

                                   (5.6.9)

где веса  удовлетворяют условиям:

                                          (5.6.10)

Условия (5.6.10) называют условиями ортогональности. Кроме того, веса  должны удовлетворять условию нормализации:

                                             (5.6.11)

Решая систему уравнений (5.6.10), находим единственное решение

Подставляя эти значения в (5.6.9), получим

Итак, . Таким образом, минимальная суммарная стоимость перевозок равна 100 условн.денеж.ед.

Максимум двойственной функции и нахождения оптимального решения прямой задачи геометрического программирования

Докажем, что существуют положительные веса , удовлетворяющие условиям ортогональности, и максимум двойственной функции  равен минимуму прямой функции .

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

В минимизирующей точке  производные  по каждой переменной обращаются в нуль, следовательно, получим  уравнений вида

                 (5.6.12)

Разделив эти уравнения (5.6.12) на  и полагая

                                  (5.6.13)

получим

                              (5.6.14)

Таким образом, вектор , задаваемый (5.6.13), удовлетворяет условиям ортогональности, а кроме того, он удовлетворяет и условиям нормализации. поэтому

Но согласно (5.6.13),    и поэтому

                        (5.6.15)

Тогда из (5.6.15) следует, что

                                    (5.6.16)

Это соотношения вместе с (5.6.8) доказывает, що минимум прямой функции  равен максимуму двойственной функции .

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

                            (5.6.17)

Решая систему (5.6.17), найдем искомые значения для неизвестных

Пример 5.10. Продолжим рассмотрение предыдущего примера и покажем, как найти переменные .

Ранее было найдено:

Из (5.6.17) следует, что вектор  удовлетворяет системе

                                   (5.6.18)

Решая уравнения системы (5.6.18), находим искомые значения переменных

 .

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

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

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

В наиболее общей постановке прямая задача ГП формулируется таким образом [14; 18].

Прямая задача А. Найти минимальное значение функции

при ограничениях         (5.6.19)

                      (5.6.20)

где

                 (5.6.21)

                   (5.6.22)

             (5.6.23)

Все , а показатели степени – действительные числа. Следовательно, все функции – позиномы. Минимизируемая функция  называется прямой функцией, ограничения (5.6.19) – условиями неотрицательности, а ограничения (5.6.20)– вынужденными ограничениями. Матрица  – называется матрицей экспонент.

Двойственная задача В. Двойственная задача В, соответствующая прямой задаче А, формулируется следующим образом.

Найти максимальное значение функции-произведения

                             (5.6.24)

где

                             (5.6.25)

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

                   (5.6.26)

                                     (5.6.27)

                                  (5.6.28)

Функция  называется двойственной функцией, а переменные  – двойственными переменными. Условие (5.6.27) – условие нормализации, соотношения (5.6.28) – условия ортогональности.

Сопоставляя формы записи прямой (5.6.19) – (5.6.23) и двойственной (5.6.24) – (5.6.28) задач, можно установить следующие соотношения между ними [14; 18].

Каждому члену позиномов прямой задачи вида  соответствует одна двойственная переменная , и наоборот.

Каждый множитель  функции  определяется вынужденными ограничениями

Заметим, что целевая функция не влечет появления такого множителя, так как по условию нормализации .

Условие нормализации (5.6.27) – это единственное условие, по которому различаются целевая функция  и позиномы-ограничения .

Связь между оптимальными решениями прямой и двойственной задач геометрического программирования устанавливается в основной теореме ГП [14].

Теорема 5.15. Пусть прямая задача А совместна и существует решение  такое, что , а также оптимальное решение. Тогда справедливы следующие утверждения.

1. Соответствующая двойственная задача совместна и существует точка, удовлетворяющая ее ограничениям, в которой достигается условный максимум двойственной функции .

2. Максимальное значение целевой функции двойственной задачи равно минимальному значению целевой функции прямой задачи:

3. Если  – минимизирующая точка прямой задачи А, то существуют неотрицательные множители Лагранжа , такие, что пара векторов  является седловой точкой функции Лагранжа  прямої задачи, то есть

                         (5.6.29)

 для всех произвольных ,

где

                         (5.6.30)

Кроме того, существует максимизирующий вектор  двойственной задачи с компонентами,  определяемыми из условий:

              (5.6.31)

где

           

Далее

                                    (5.6.32)

4. Если  – максимизирующая точка двойственной задачи В, то минимизирующая точка  прямой задачи удовлетворяет системе уравнений

                       (5.6.33)

где  пробегает все положительные целочисленные значения, для которых .

Доказательство теоремы 5.15 приведено в приложении 3.

Пользуясь результатами этой теоремы, зная решение прямой задачи , можно на основании соотношений (5.6.31) определить максимизирующий вектор двойственной задачи . И наоборот, если известно решение двойственной задачи , то, используя соотношения (5.6.33), можно определить оптимальный решение прямой задачи .

Заметим, что система (5.6.33) после логарифмирования обеих частей каждого уравнения оказывается линейной относительно . Наконец, с (5.6.32) следует, что величины  с точностью до постоянного множителя совпадают с множителями Лагранжа для прямой задачи.

Одним из условий теоремы 5.15 является предположение о существовании точки, удовлетворяющей ограничениям прямой задачи и в которой достигается минимум функции .

Достаточные условия, при которых это предположение справедливо, определяет следующая теорема двойственности.

Теорема 5.16. Если прямая задача А совместна и существует точка  с положительными компонентами, удовлетворяющая ограничениям двойственной задачи В, то существует точка , удовлетворяющая ограничениям прямой задачи, в которой функция  достигает своего минимума.

Следует заметить, что все функции-позиномы  выпуклые, и поэтому прямая задача ГП является задачей выпуклого программирования.

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

Этот метод будет рассмотрен ниже.

Исследуем некоторые особенности задачи геометрического программирования. С этой целью рассмотрим позином

                            (5.6.34)

и выполним замену переменных, полагая

                              (5.6.35)

Преобразованная функция, имеющая вид

                               (5.6.36)

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

Итак, прямую задачу преобразовали к следующему виду.

Прямая задача А. Найти минимум положительной экспоненциальной функции  при ограничениях

                      (5.6.37)

где

                     (5.6.38)

Очевидно, все функции  – положительные экспоненциальные функции. Анализ преобразованной задачи А позволяет выявить многие важные свойства прямой задачи А. Например, из рассмотрения задачи А сразу следует, что любую прямую задачу можно сформулировать так, что ее матрица экспонент  будет иметь ранг .

Действительно, задачу  можно представить в безкоординатной форме:

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

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

           

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

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

Таким образом, не теряя общности, можно считать, что ранг матрицы А всегда равен . Если такая матрица квадратная (то есть ), то ее векторы-столбцы образуют базис для пространства . В таком случае всегда существует последовательность векторов , для которой

                  (5.6.39)

Тогда из соотношения (5.6.39) следует, что

                      (5.6.40)

Это означает, что задача  совместна и  имеет минимум, равный 0. Кроме того, ясно, что задачи этого типа вообще не имеют условного минимума.

Соответствующая двойственная задача всегда несовместна, поскольку единственным решением условий ортогональности является нулевой вектор, но он не удовлетворяет условию нормализации.

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

Целое число  называется степенью трудности такой задачи ГП.

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

Так, если , то это означает, что ограничения двойственной задачи имеют лишь единственное решение .

Если оно удовлетворяет условиям неотрицательности, то это и будет искомое оптимальное решение двойственной задачи.

Если же , то для нахождения оптимального решения  нужны дополнительные усилия. Однако, как мы покажем даже не определяя , из двойственной задачи можно получить много полезной информации.

Двойственная задача имеет линейные ограничения двух типов:

в форме уравнений                            

и в форме неравенств

Все решения условий ортогональности образовывают подпространство пространства , которое называется двойственным пространством и является ортогональным дополнением прямого пространства, представляющего собой пространство векторов-столбцов матрицы А.

Условие нормализации определяет гиперплоскость в , которая называется гиперплоскостью нормализации, а условия неотрицательности определяют первый ортант пространства ; пересечение двойственного пространства с гиперплоскостью нормализации и первым ортантом определяет допустимое множество решений двойственной задачи.

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

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

                             (5.6.41)

где  – произвольные числа, удовлетворяющие условиям неотрицательности вида

                      (5.6.42)

Вектор , удовлетворяющий условиям нормализации

                                    (5.6.43)

и условиям ортогональности

                          (5.6.44)

называется вектором нормализации.

Векторы  образуют базис пространства решений линейной однородной системы уравнений:

                        (5.6.45)

Их называют векторами базиса, а переменные , связанные с векторами – базисными (переменными).

Однако это условие (вогнутость) для функции  в общем случае не выполняется. Но в то же время функция  всегда вогнута, даже если  не обладает этим свойством (доказательство этого факта приведено в [14]).

Поскольку логарифмическая функция является монотонно возрастающей, то  и  имеют одно и то же множество максимизирующих точек.

Таким образом, решение преобразованной двойственной задачи Вr сводится к оптимизации вогнутой функции, полученной заменой  на  на выпуклом множестве допустимых решений.

Воспользуемся этими свойствами для нахождения условий оптимальности для искомого решения.

Допустим, что  – точка, в которой . Логарифмируя  и беря производную  в точке , получим

Значит, точка  является стационарной точкой функции  тогда и только тогда, когда

              (5.6.54)

что эквивалентно

                                (5.6.55)

Если  удовлетворяет этим уравнениям, то после несложных преобразований выражение для  можно привести к виду

                     (5.6.56)

Соотношение (5.6.55), (5.6.56), а также тот факт, что для вогнутой функции всякая стационарная точка является точкой максимума, доказывают следующую теорему [14].

Теорема 5.17. Если  удовлетворяет ограничениям двойственной задачи В і все компоненти  положительны, то является максимизирующей точкой двойственной задачи, тогда и только тогда, когда

                     (5.6.57)

где

                                (5.6.58)

При этом, если  удовлетворяет соотношениям (5.6.57), то

                         (5.6.59)

Уравнения (5.6.57) называются максимизирующими. Они образуют систему, состоящую из  нелинейных уравнений относительно  базисных переменных . Решив эту систему, можно определить максимизирующую точку двойственной задачи В. формула (5.6.59) задает максимальное значение двойственной целевой функции для такой максимизирующей точки. Заметим, что поскольку базисные постоянные  и двойственные переменные  входят в разные части максимизирующих уравнений, то такое разделение переменных и постоянных (констант) облегчает исследование зависимости оптимальных точек двойственной задачи В и прямой задачи А от коэффициентов .

Описание алгоритма

На основании вышеизложенных результатов приведем описание алгоритма геометрического программирования.

Пусть задана прямая задача ГП в виде (5.6.19) – (5.6.23).

1. Составим задачу, двойственную к начальной, (5.6.24) – (5.6.28).

2. Находим решения ограничений ортогональности и нормализации (5.6.27), (5.6.28) – . Если степень трудности задачи , то это решение единственно, и переходим к шагу 3, в противном случае (если ), к шагу 4.

3. Используя значения , составляем систему уравнений (5.6.33), которую решаем относительно неизвестных . При этом для оптимальных решений .

4. Если степень трудности , то находим общее решение системы уравнений (5.6.27), (5.6.28) в виде

где  – вектор произвольных параметров.

5. Используя условия оптимальности теоремы 5.17, составляем и решаем систему нелинейных уравнений (5.6.57) относительно неизвестных . Найдя ее решение и подставляя его в (5.6.53), определим оптимальные значения двойственных переменных , а подставляя  в (5.6.59), найдем оптимальное значение двойственной целевой функции .

6. Переходим к прямої задаче и, используя соотношения (5.6.33), решаем систему уравнений относительно оптимальных значений прямой задачи  на основе известного оптимального решения двойственной задачи .

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

                                                  (1)

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

                                             (2)

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

Двойственная задача к задаче (1), (2) записывается в виде

                    максимизировать                   (3)

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

                                              (4)

                                      (5)

Условия (4), (5) образуют систему из четырех уравнений с четырьмя неизвестными и имеют единственное решение.

Находим значения двойственной функции

Используем теорему 5.15 для нахождения оптимального решения прямой задачи .

Очевидно, что .

Используя четвертое утверждение теоремы 5.15 и соотношение (5.6.33), составляем такую систему уравнений:

                                             (7)

Чтобы решить систему (7), прологарифмируем обе части соотношений (7) и получим систему линейных уравнений относительно . Она имеет единственное решение , откуда искомое решение имеет вид . Можно непосредственно убедиться в том, что .

Пример 5.12. Пусть требуется

                              минимизировать                            (1)

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

                                               (2)

Соответствующая двойственная задача имеет такой вид:

 максимизировать                    (3)

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

                                           (4), (5)

                              (6)

Степень трудности этой задачи равна

Решаем систему (4) – (6) методом Гаусса: результаты последовательных итераций приведены в табл.5.6 – 5.11.

Отсюда получаем следующее базисное решение:

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

                                                           (7)

Таблица 5.6

 

Таблица 5.7

 

1

1

1

   

1

 

1

1

1

   

1

-1

1

1

-2

 

0

 

0

2

2

-2

 

1

-1/2

 

1

-2

1/2

0

 

0

1/2

3/2

-2

1/2

1/2

-1

1

1

 

-1

0

 

0

2

2

 

-1

1

Таблица 5.8

 

Таблица 5.9

 

1

0

0

1

 

1/2

 

1

 

0

1

 

1/2

0

1

1

-1

 

1/2

   

1

1

-1

 

1/2

0

0

1

-3/2

1/2

1/4

     

2

-3

1

1/2

0

0

0

2

-1

0

     

2

-1

0

1/2

Таблица 5.10

 

Таблица 5.11

 

1

 

0

1

 

1/2

 

1

 

0

1

 

1/2

 

1

0

-1/2

 

1/4

   

1

0

-1/2

 

1/4

   

0

-2

1

0

     

1

-1/2

 

1/4

   

1

-1/2

 

1/4

       

-2

1

0

Из этих уравнений, используя условия неотрицательности , получаем вывод, что переменная  должна удовлетворять неравенству

 .                                              (8)

Записывая полное решение системы (4) – (6) в виде , определяем, что

 .                                       (9)

Используя условия оптимальности (5.6.57) теоремы 5.17, находим искомое значение , при котором

 .

Вычисляем

В соответствии с (5.6.57), учитывая, что  получим

                                            (10)

где  определяется из (7), – из (9 ), а

Подставляя эти значения в (10), получим

 .                         (11)

Откуда

или

                                                        (12)

Из (12) определяем оптимальное значение .  Заметим, что это значение удовлетворяет неравенству (8). Подставляя  в (7), находим оптимальные значения двойственных переменных:

Тогда максимум двойственной функции будет равен

Итак,

                                                    (13)

Используя соотношения (5.6.33) из теоремы двойственности 5.15, составляем уравнения относительно неизвестных прямой задачи:

                                       (14)

                                             (15)

                                           (16)

                                                    (17)

Разделив уравнение (16) на (15), получим . Подставив  в (17), получим , откуда . Наконец, подставив  в (15), найдем .

Непосредственной проверкой убеждаемся, что