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

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

В общем виде задача П. п. заключается в максимизации целевой функции по всем х=(x₁,...,х _п), удовлетворяющим ограничениям

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

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

Если при любом фиксированном задача П. п. представляет собой задачу линейного программирования( выпуклого программирования и т. п.), то говорят о задаче линейного (соответственно выпуклого и т. <п.) параметрического программирования. В общем виде проблематику П. п. можно охарактеризовать следующим образом. 1) Нахождение и выяснение свойств множеств разрешимости 2) Нахождение областей устойчивости решений, характеризация их строения; анализ поведения неустойчивых задач. 3) Характеризация зависимости оптимального значения целевой функции от вектора параметров.

В полном своем объеме (т. е. для произвольных целевых функций, ограничений и областей изменения параметров ) эти задачи весьма трудны. Достаточно продвинуты в теоретическом и вычислительном отношении лишь нек-рые частные их классы. В основном это касается задач линейного П. п., в к-рых: либо а) целевая функция линейно зависит от одного скалярного параметра, либо б) правые части ограничений линейно зависят от одного параметра, либо в) целевая функция и правые части ограничений линейно зависят от двух независимых скалярных параметров или от одного и того же параметра, г) целевая функция линейно зависит от векторного параметра, д) правые части ограничений линейно зависят от векторного параметра. Случай зависимости от параметров матрицы ограничений задачи линейного программирования весьма сложен и пока (1983) исследован недостаточно. Для случая а), напр., решение указанных проблем 1) - 3) характеризуется следующим образом. Пусть требуется максимизировать

при условиях

где . Тогда существует такое разбиение на конечное число открытых слева интервалов: = (где интервал неограничен слева, неограничен справа, причем возможен случай совпадения одного из них с ), что при всех соответствующая задача линейного П. п. разрешима, причем на каждом интервале , она имеет один и тот же базис. Исключение могут составлять лишь интервалы и , на к-рых целевая функция (2) может быть неограниченна. Таким образом, в данной задаче множество разрешимости представляет собой объединение всех за возможным исключением и (или) . Далее, оптимальное значение целевой функции на каждом , является выпуклой кусочно линейной функцией параметра . Численные методы решения однопараметрических задач линейного П. п. представляют собой модификации симплексного метода;в случае многомерного пространства параметров приходится привлекать более сложные соображения.

Лит.:[1] Г о л ь ш т е й н Е. Г., Ю д и н Д. Б., Новые направления в линейном программировании, М., 1966; [2] Theorie der Hnearen parametrischen Optimierung, В., 1974.

А. А. Корбут.