В 1997 году доктор математических наук Александр Немировский впервые обнаружил, что задачи линейного программирования могут обладать особенностями, крайне неприятными для пользователя. Разница (даже в доли процента) между данными, с которыми оперирует оптимальный алгоритм решения, и теми, которые будут иметь место в случае применения полученного решения, может привести к тому, что в большой доле задач полученное оптимальное решение окажется не только не оптимальным, но и вообще недопустимым, то есть будут нарушены заданные ограничения. Следовательно, доверять оптимальному решению можно лишь если заранее определить подверженность задачи «болезни неопределенности» – и найти «лекарство». Немировский предложил математически строгий способ, который обеспечивает надежность применения оптимального решения, назвав его «робастная оптимизация». Этот способ менял и традиционную постановку задач линейного программирования, и алгоритм ее решения. Задача решалась при дополнительном условии, что все коэффициенты могут принимать любые значения из некоторого множества – множества неопределенности. Какими бы ни оказались коэффициенты, если они принадлежат множеству неопределенности, решение обязательно будет допустимым (точнее, робастно допустимым). Робастная оптимизация находит оптимальное решение только среди всех робастно допустимых решений. Введение множества неопределенностей в стандартную задачу линейного программирования превращает ее в некоторое множество задач. А значит, стандартные методы решения задач линейного программирования непригодны. Но такая задача может быть решена как задача выпуклой оптимизации, а для этого класса Немировским ранее уже были получены оптимальные алгоритмы решения (метод эллипсоидов). Это открывало дорогу для широкого применения методов робастной оптимизации в прикладных задачах. Сразу после опубликования первых результатов идеи робастности были подхвачены всеми, кто на практике или в теории занимался теорией оптимизации.
По материалам Пресс-центра Министерства образования и науки Российской Федерации.