ОПТИМАЛЬНОСТИ НЕОБХОДИМЫЕ УСЛОВИЯ

— характеристические свойства, которыми обладает оптимальная точка (вектор) в задаче программирования математического. Форма О. н. у. определяется формой, в которой задается допустимое множество. Впервые общие О. н. у. для экстремальных задач при наличии ограничений в виде равенств сформулировал Лагранж (см. Лагранжа правило множителей). В 1951 амер. математики Г. Кун и А. Таккер сформулировали необходимые и достаточные условия оптимальности точки х в задаче программирования выпуклого, т. е. в задаче отыскания

где ф-ция вогнута, а все ф-ции — выпуклы. Для того, чтобы вектор х являлся решением задачи (1), когда допустимое мн-во содержит внутр. точки, т. е. , необходимо и достаточно, чтобы нашелся неотрицательный вектор и, который вместе с вектором х является седловой точкой ф-ции Лагранжа для всех Если к тому же ф-ции дифференцируемы, то для оптимальности вектора х необходимо и достаточно, чтобы нашелся неотрицательный вектор и, который вместе с вектором х удовлетворяет следующей системе ур-ний и неравенств

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

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

принципа максимума необходимые условия экстремума для задач оптим. управления (см. Ионтрягина принцип максимума). В начале 60-х годов сов. ученые А. Я. Дубовицкий и А. А. Милютин построили общую теорию необходимых условий и развили технику построения таких условий для широкого класса задач матем. программирования. В частности, им удалось осуществить вложение оптимального управления теории в общую теорию

Сущность общей теории О. н. у. заключается в следующем. Пусть требуется отыскать

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

для достаточно малых t и для которых Далее будем считать, что существует касательное к L подпростр. , т. е. для всякого найдется такой вектор что для достаточно, малых t, причем при Кроме того, пусть существует выпуклый конус Ко, для любого элемента которого выполняется условие (4) для Тогда выполняется следующее утверждение (теорема Дубовицкого — Милютина): для того, чтобы точка х являлась решением задачи (3), необходимо, чтобы

Пусть

где В — простр., сопряженное банаховому простр. пустое мн-во. Чтобы конусы не пересекались, необходимо и достаточно существование функционалов , среди которых по крайней мере один отличен от 0 и таких, что теорема Дубовицкого—Милютина). На основе этой теоремы удается единообразно получать различные результаты, начиная от классических теорем двойственности в программировании линейном и кончая принципом максимума Понтрягина.

Помимо самостоятельного значения, О. н. у. играют важную роль при создании вычислительных алгоритмов для эффективного отыскания оптим. точки х. На основе теории О. н. у. удалось с новой точки зрения осмыслить некоторые классические результаты теории чебышевских приближений, проблемы моментов И др. Р. А. Поляк, М. Е. Примак.