Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

Глава 7. Вопросы устойчивости в математическом программировании

7.1. Корректные и некорректные задачи

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

Рассмотрим задачу отыскания таких элементов y∈X, что

(7.1)

где


f(x)- векторная функция,


а φ(x) и fi(x) (i = 1,...,m)- заданные непрерывные скалярные функции.

На практике информация о φ(х) и f(x) носит приближенный характер, то есть вместо φ(х) и f(x) известны такие функции φε(x) и fε(х), определенные на множестве Г, что


При этом выбор функций ε и fε из множества Ре не заносит от нашего желания. Таким образом, о решении входной задачи судят по решению yε приближенной задачи:

(7.2)

где


случайно выбранной из класса приближенных задач. Пусть


и


Назовем задачу (7.1) слабо корректной, если

(7.3)

Задачу (7.1) будем называть корректной, если

(7.4)

где Z = Gε∪G.

Поясним эти определения. Предельное соотношение (7.3) означает, что семейство множеств Gε стягивается при ε→0 к множеству, принадлежащему G. На языке "ε, δ" это значит, что для любого δ > 0 найдется такое ε0 > 0, что для любого ε∈(0, ε0] и любого yε∈Gε найдется такой y∈G, что ||yε-y||≤δ. Отсюда следует, что для любого δ > 0 найдется такое ε0 > 0, что для любых ε∈(0, ε0] и φε∈Pε будет


Читателям предоставляется возможность самостоятельно удиться в справедливости этого утверждения.) Таким образом, слабая корректность по сути дела означает ректность по функционалу:


Условие (7.4) означает, что семейство множеств Gε стягивается при ε→0 к множеству G, состоящему из единственного элемента у. То есть для любого δ > 0 найдется такое ε0 > 0, что для любого ε ∈ (0, ε0] и любого yε ∈ Gε будет


Очевидно, что корректная задача всегда является слабо корректной, но не наоборот.

Будем говорить, что задача (7.1) некорректна, если нарушается условие (7.4).

В случае некорректности задачи (7.1), при заданном ε > 0 всегда найдутся такие пары φε, fε и φ̃ε, f̃ε, принадлежащие множеству Рε(φ, f), для которых решения yε и ỹε соответствующих задач вида (7.2) существенно различны и поэтому не несут в себе достаточной информации о решении исходной задачи.

Пример 1. Рассмотрим в Е2 пару задач:

(7.5)

и

(7.6)

Очевидно, что задача (7.5) является слабо корректной и в то же время некорректной. Пример 2.

(7.7)

Очевидно, что задача (7.7) при ε = 0 будет некорректной и, более того, она не будет слабо корректной.

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

симплексного метода решения задачи линейного программирования



можно интерпретировать следующим образом: на каждом итерационном шаге метода элементы матрицы А и компоненты векторов b и с преобразуются в А', b' и с' по формулам тождественных преобразований (по формулам полного исключения Жордана-Гаусса) и в результате итерационного шага, если все преобразования осуществлять точно, возникает новая задача



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

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"