Системы линейных неравенств. Зоркальцев В.И - 75 стр.

Глава 5. Теория двойственности для задач оптимизации с
линейными ограничениями

    Многие прикладные математические модели (в т.ч. экономических,
физических, биологических процессов и явлений) представляются в виде
задач оптимизации – поиска экстремума (максимума или минимума)
некоторой функции (называемой целевой функцией) при ограничениях на
переменные. Иногда ограничения отсутствуют – такая ситуация
называется задачей безусловной оптимизации.
    Изучение свойств задач оптимизации, разработкой и обоснованием
алгоритмов их решения занимается теория оптимизации. Особенно
активно теория и методы оптимизации стали развиваться после второй
мировой войны в связи с необходимостью решения проблем составления
наиболее рациональных планов (программ) в военных областях и
экономике. По сложившейся традиции задачами оптимизации называют
также задачи математического программирования. Соответственно,
синонимом к термину «теория оптимизации» является термин «теория
математического программирования».
    Важной составляющей теории оптимизации является теория
двойственности. Для широкого класса задач математического
программирования      применяются     специальные    конструкции    –
двойственные задачи оптимизации. Двойственная задача используется для
доказательства оптимальности полученного решения, для теоретического
обоснования алгоритмов, при анализе устойчивости оптимальных решений
к варьированию исходных данных, при экономической или физической
интерпретации решения. Двойственная задача может служить основой для
конструирования алгоритмов решения исходной задачи.
    Основу теории двойственности составляют множители Лагранжа
ограничений исходной задачи оптимизации. Ранее, в начале главы 3,
множители Лагранжа рассматривались нами для задачи минимизации
выпуклой функции на линейном многообразии, при ограничениях в виде
системы линейных уравнений. Свойства оптимальных решений такой
задачи использовались для доказательства теорем об альтернативных
системах линейных неравенств.
    В свою очередь теоремы об альтернативных системах линейных
неравенств могут служить для построения теории двойственности
линейного и нелинейного программирования. Здесь ограничимся
рассмотрением задач минимизации выпуклых функций при линейных
ограничениях в форме равенств и неравенств. Ограничения в форме
линейных неравенств являются новым моментом по отношению к
рассмотренной в начале главы 3 задачи минимизации выпуклой функции
при ограничениях в форме линейных уравнений.


                                 75