Методы первого порядка. Задачи и методы условной оптимизации нелинейного программирования, страница 14

З а м е ч а н и е 4.38. Квадратичная функция будет выпуклой (вогнутой), если матрица D будет  симметричной полуопределенной (отрицательно определенной).   

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

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

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

Таким образом, специальные методы решения задачи квадратичного программирования (в частности, метод Баранкина и Дорфмана) позволяют свести решение задачи НП к решению задачи ЛП.

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

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

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

Геометрическое программирование (ГП) представляет собой достаточно широкий и интересный с практической точки зрения класс задач НП. В [ …. ] приведены многочисленные примеры использования метода ГП при оптимальном проектировании технических и технологических систем.

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

 ,                                            (4.55)                   где x_j >0, j=1, 2,…, m;  С_i > 0;  i=1,2,…, n ;  a_ij – произвольные вещественные числа. (На переменные задачи наложены условия неотрицательности).

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

Основная особенность геометрического программирования состоит в том, что исходная задача с нелинейной ЦФ и ограничениями сводится к двойственной  задаче с нелинейной  ЦФ, но линейными  ограничениями, решить которую легче, чем исходную задачу. Кроме того, в рамках рассматриваемой задачи можно оценить сравнительную значимость слагаемых ЦФ и отдельных переменных оптимизации. (Последнее обстоятельство чрезвычайно важно при решении задачи проектирования).

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

З а м е ч а н и е 4.39. В частном случае решение задачи ГП (при так называемой “нулевой степени трудности” ) сводится к решению системы алгебраических уравнений.

В общем случае задача ГП является невыпуклой. В связи с этим использование общих методов решения задач НП для задач ГП может быть затруднено. В этом случае для эффективного использования методов НП рекомендуется осуществить преобразование переменных оптимизации x_i в переменные z_i по формуле x_j=exp(z_j), после чего задача ГП приводится к эквивалентной задаче выпуклого программирования.

Для решения задач ГП разработаны специальные машинные программы [….. ].