Документ взят из кэша поисковой машины. Адрес оригинального документа : http://mph.cs.msu.su/Home/Opus/a77.doc Дата изменения: Tue Apr 6 14:59:14 2010 Дата индексирования: Sat Apr 9 23:40:38 2016 Кодировка: koi8-r

Журнал вычислительной математики и математической физики .1966

А. Н. Тихонов

О некорректных задачах оптимального планирования


Рассмотрим задачу линейного программирования [1]: найти элемент [pic], n-
мерного пространства[pic], удовлетворяющий m условиям
[pic] (I()
с ограничениями
[pic] (I(()
и минимизирующий линейную форму
[pic]. (I((()
Эту задачу мы будем обозначать (I).
Практически при задании задачи линейного программирования задаются
приближенные входные данные, т. е. вместо [pic]даются [pic], причем
предполагается известным [pic] - порядок погрешности приближенных входных
данных.
Задача называется устойчивой (или корректно поставленной, см., например,
[2], стр. 229), если входным данным с малой погрешностью [pic]
соответствует решение, мало отличающееся от решения исходной задачи.
Задача некорректно поставлена (в смысле Адамара), если как угодно малым
погрешностям входных данных может соответствовать решение, сильно
отличающееся от решения исходной задачи. Естественно возникает вопрос о
возможности практического использования решений подобных задач.
Если условие [pic] имеет линейно зависимые строки, то. задача линейного
программирования, как правило, некорректна. Обычно делается предположение,
что строки задаваемых условий линейно независимы . Однако подобное
предположение при приближением задании входных данных практически
непроверяемо. В настоящей статье мы не будем делать предположения
относительно' линейной независимости задаваемых условий и будем иметь дело
с некорректно поставленными задачами.
В § 1 будут рассмотрены вопросы существования и единственности системы
(I). Будет доказано, что система всегда имеет решение, если только условия
(I() и (I(() совместны, что в дальнейшем мы всегда будем предполагать.
Однако система (I) может иметь много решений.
Будет введено понятие нормального решения задачи (I) при помощи
дополнительного условия, что ищется решение задачи (I), ближайшее к началу
координат (или любой заранее фиксированной точке [pic] ).
Понятие нормального решения вполне естественно в задачах оптимального
планирования. Если работа выполняется в соответствии с планом [pic] и его
надо изменить в связи с тем, что изменились входные данные, которым
соответствует несколько новых оптимальных планов, то естественно
.предпочесть тот, который наименее отклоняется от старого плана [pic].
Подобный выбор будет вызывать минимум затрат на организационные
перестройки, если они не были учтены в самой постановке задачи. Мера
уклонения нового и старого планов, [pic] и [pic], выбирается как взвешенное
квадратичное уклонение
[pic].
Будет доказано, что при совместности условий (I() и (I(() нормальное
решение существует и определено однозначно, т. е. что задача о нахождении
нормального решения математически вполне определена.
Однако эта задача об определении решения задачи (I) (или ее нормального
решения в случае неоднозначного решения) может быть некорректна в смысле
Адамара. Приводится пример такой задачи (I), что задание как угодно
высокоточной приближенной информации об этой системе может вызывать как
угодно большие изменения ее решения.
§2 и §3 посвящены методу регуляризации приближений для определения [pic]-
нормального решения задачи (I), т. е. построению таких приближений,
которые мало уклоняются от [pic], если входные данные задаются с
достаточной точностью [pic] .
Подобного результата можно достигнуть, если отказаться от обычного
выбора приближенного решения как «точного» решения исходной задачи с
приближенными входными данными. Для настроения приближенного решения
предлагается алгоритм, зависящий от вспомогательных параметров: [pic],
причем такой, что для заданного [pic], если только параметры [pic] и [pic]
согласованы с заданным [pic] и [pic] - точностью входных данных - и [pic]
достаточно мало.
Элемент [pic] определяется как элемент z реализующий минимум
квадратичной функции
[pic]
на множестве точек [pic], где [pic]- точка [pic] , по отношению к которой
строится нормальное решение.

Мы не будем останавливаться на том, каким методом пользоваться для
нахождения минимизирующей последовательности для [pic], так как основной
результат исследования от этого не зависит.
В § 2 будет дано обоснование для описанного алгоритма, если входные
данные задаются «точно» и введена задача ( I[pic]), нужная для дальнейшего.
В § 3 дается обоснование алгоритма при задании приближенных входных
данных, которому посвящена теорема 6.

§1

Обратимся к изучению систем типа (1).
Теорема 1. Если условия (I() и (I(() совместны, то задача (I) имеет по
крайней мере одно решение.
Пусть [pic] для [pic] и [pic] для [pic]. Рассмотрим множество [pic]где
[pic] ; по предположению оно не пусто. Пусть [pic]- нижняя грань значений
[pic] на М и [pic]- последовательность точек М , минимизирующих [pic], т.
е. [pic].
Будем предполагать, что [pic]. Очевидно, что координаты [pic]ограничены,
так как
[pic].
Последовательность точек [pic] пространства[pic], компактна. Будем
предполагать, что она сходится к точке [pic] этого пространства. Так как
[pic] зависит только от [pic]первых координат точки z, то очевидно, что
[pic].
Рассмотрим систему уравнений
[pic],
относительно [pic] ([pic], [pic], [pic]) относительно [pic] ([pic]) . Эта
система совместна. Это следует из того, что система
[pic]
совместна и вектор [pic] удовлетворяет всем линейным соотношениям, которым
удовлетворяют строки матрицы А". Следовательно, вектор [pic] также
удовлетворяет всем этим соотношениям.
Убедимся, что система [pic] имеет положительные решения [pic]. Если это
неверно, то линейное многообразие, определяемое таким уравнением, отстоит
от [pic] на конечное расстояние. В этом случае многообразие, определяемое
уравнением[pic] при достаточно больших k также отстоит от [pic] на конечное
расстояние, что противоречит тому, что [pic].
Беря любое положительное решение [pic], получим, что элемент [pic]
удовлетворяет условиям (I() и (I(() и [pic].
Нетрудно построить примеры, показывающие, что задача может иметь не
единственное' решение.
Пример 1. Если условия (I() и функционал (I((() имеют вид
[pic]
то на [pic] минимум функционала С(z) равен нулю:[pic], и он достигается на
полупрямой, определяемой уравнением
[pic].
Определение. Пусть дана некоторая точка [pic][pic] [pic]. Элемент [pic]
будем называть нормальным решением задачи (I) (по отношению к точке [pic])
, если
[pic],
где z - любое решение задачи (I).
Если решение задачи (I) определено однозначно, то понятия решения и
нормального решения совпадают. Если некоторая задача допускает несколько
решений, то существование нормального решения очевидно, так как множество (
, на котором достигается минимум С(z), замкнуто, поскольку оно является
пересечением трех замкнутых множеств: [pic].
Теорема 2. Нормальное решение задачи (I) определено однозначно.
Пусть [pic] и [pic] - два нормальных решения задачи (I).
Рассмотрим отрезок
[pic].
В силу линейности условия (I() элемент z ему удовлетворяет, так как
[pic].
Все точки отрезка удовлетворяют условию (I(() и
[pic]
достигает минимального значения во всех точках отрезка. Однако так как
[pic], то для [pic] [pic]имеем
[pic],
что противоречит тому, что [pic]- нормальное решение, если [pic][pic][pic].

Таким образом, при совместности условий (I() и (I(() нормальное решение
задачи (I) существует и определено однозначно.
Обратимся к рассмотрению устойчивости задачи (I). Пусть вместо
[pic]задаются их приближенные значения [pic] и [pic] - мера погрешности.
Будем предполагать (для простоты), что мера погрешности берется в виде
квадратических норм
[pic]
Нетрудно построить примеры неустойчивых задач типа (I), если допускать, что
среди условий [pic] могут быть линейно-зависимые.
Однако если задаются лишь приближенные значения [pic] мы не можем
судить, имеет система [pic]зависимые условия или нет.
Пример 2. Пусть условия [pic]имеют вид
[pic]
где [pic] - иррациональное число,

[pic] и [pic].
Очевидно, что[pic]. Однако каково бы ни было [pic], легко указать
приближенную систему [pic], решение которой будет однозначно определено и
[pic] где B - наперед заданное положительное число. В самом деле,
[pic]
где [pic]-приближенное значение числа [pic] и [pic] - погрешность, равная
[pic]. Если при этом
[pic]

и все погрешности меньше [pic], то все требования выполнены и [pic].
Таким образом, оказывается, что задачи типа (I) могут быть
неустойчивыми, даже если их решения определены однозначно и нет
необходимости обращаться к нормальным решениям.

§ 2

Обратимся к построению устойчивого метода определения нормального
решения задачи (I). Рассмотрим параметрический функционал
[pic]
где [pic]фиксированная точка, по отношению к которой строится нормальное
решение, и [pic] - параметры.
Алгоритм приближенного нахождения нормального решения задачи (1)
заключается в том, что в качестве приближенного решения берется элемент
[pic], на котором [pic] имеет минимальное значение на [pic]. Существование
и единственность такого элемента [pic] очевидны в силу квадратичности
[pic]и того, что [pic][pic] при [pic][pic].
В настоящем параграфе приведенный алгоритм изучается применительно к
заданию точной информации о системе (I).
Теорема 5 представляет собой обоснование этого алгоритма в
предположении, что мы обладаем методом построения минимизирующих
последовательностей для квадратических функций на множестве [pic]
пространства [pic].
Рассмотрим задачу (I[pic])
[pic] (I[pic]()
[pic] (I[pic](()
[pic] (I[pic]((()
Будем обозначать через [pic], решение этой задачи, существование и
единственность которого очевидны. Пусть [pic]- нормальное решение задачи
(I).
Прежде всего, докажем, что приведенный выше (параметрический по [pic] и
[pic]) алгоритм определен. Имеет место
Теорема 3. Для всякого [pic] существует такое [pic] , что если [pic],
то
[pic],
где [pic] - решение задачи (I[pic]) и [pic] - нормальное решение задачи
(I).
Если это неверно, то существует такое [pic] и[pic], что [pic] для всех k
. В этом случае
[pic],
или
[pic],
так как [pic] в силу того, что [pic] для всех [pic].
Отсюда следует, что последовательность [pic]компактна. Будем полагать,
не меняя обозначений, что она сходится к элементу [pic]. Очевидно, что
[pic],
а также что
[pic] и [pic].
Эти условия определяют единственное нормальное решение задачи (1),
Отсюда и следует, что [pic], что противоречит условию [pic] для всех k.
Итак, [pic] для [pic].
Теорема 4. Каково бы ни было [pic] и [pic], существует такое [pic],
что[pic]для [pic][pic]
Если это не так, то существует [pic] и такие последовательности [pic]
и[pic], что [pic][pic]. Однако
[pic]
откуда получаем, что
[pic] [pic] при [pic]
и что
[pic].
Отсюда следует, что [pic] - компактная последовательность. Не меняя
обозначений, 'будем считать, что [pic][pic]при [pic]. Очевидно, что
[pic][pic][pic]
и что
[pic][pic][pic]
или
[pic].
Отсюда следует, что [pic]; это и доказывает теорему.
Как следствие этих двух теорем имеет место *
Теорема 5. Для любого [pic] существует такое [pic] и [pic], что
[pic], если [pic] [pic], [pic][pic], где [pic]- нормальное решение
задачи (1), а [pic] - элемент, реализующий минимум [pic].

§ 3

Обратимся к обоснованию того, что элемент [pic]обращающий на [pic]в
минимум [pic], дает приближенное значение для [pic]- нормального решения
системы (1) также и в том случае, если [pic]представляют собой приближенную
информацию о системе (1), [pic] достаточно мало и значение параметра [pic]
согласовано с [pic] - точностью задания [pic].
Система уравнений [pic] совместна только в том случае, если [pic].
Если [pic], то обозначим через [pic]ортогональную проекцию [pic] на
[pic]. Очевидно, что для любого z
[pic].
Отсюда следует, что
[pic][pic][pic]
и так как второе слагаемое правой части от [pic]не зависит, то элементы
[pic]минимизирующие
[pic] и [pic]
тождественны между собой. Существование такого элемента очевидно.
Обратимся теперь к обоснованию приведенного алгоритма, если система (I)
задается при помощи приближенной информации об A, и и С с известной
точностью [pic]:
[pic].
При этом в качестве норм [pic]могут браться любые нормы, согласованные с
нормой [pic]. Например, в качестве этих норм могут быть выбраны
квадратичные нормы.
Пусть, кроме того заданы [pic] и [pic] - непрерывные убывающие функции
[pic], равные 0 при [pic]= 0 и удовлетворяющие условию
[pic][pic][pic] или [pic][pic] ([pic])
Имеет место
Теорема 6. Пусть для системы (1) задана приближенная [pic]-информация
[pic]
и вспомогательные убывающие функции [pic], [pic], равные 0 при [pic]= 0 и
удовлетворяющие условию [pic][pic][pic]. Пусть [pic] - элементу
минимизирующий [pic] на [pic].
Каково бы ни было[pic], существуют такие [pic] и [pic], зависящие также
от [pic][pic],[pic], что
[pic]
если [pic] удовлетворяет условию
[pic][pic][pic] ([pic])
[pic]и [pic]достаточно малы:[pic].
Для доказательства теоремы достаточно показать, что при выполнении ее
условий для любого фиксированного [pic] существует такое [pic], что
[pic]
если [pic] удовлетворяет условию ([pic]), [pic][pic], где [pic]- элемент,
минимизирующий
[pic] на [pic].
В самом деле, выберем [pic]. Из приведенной выше оценки будет следовать,
что
[pic]
Как было доказано (теорема 3), для элемента [pic] ([pic]) имеет место
оценка
[pic],
так что
[pic].
Оценим [pic]. Нетрудно видеть, что
[pic]
где B=const . В самом деле, для этого достаточно установить, что
[pic] .
Эта последняя оценка следует из того, что
[pic].
так как в силу свойств ортогональной проекции
[pic]
для любого элемента z. Продолжая оценку, будем иметь
[pic],
где [pic].
Итак, при любом фиксированном [pic]и [pic], удовлетворяющем условию
([pic])
[pic][pic],
так как [pic] - убывающая функция [pic].
Оценим теперь [pic]. Имеем
[pic]
[pic]и[pic] (для любого z),
так как
[pic][pic]
Продолжая оценку, получаем
[pic]
Докажем теперь, что существует такое [pic], что [pic], если [pic]
удовлетворяет условию ([pic]) при [pic][pic].
Если это неверно, то существует такое [pic] и последовательность [pic]
таких, что при [pic], удовлетворяющих условию ([pic]), будем иметь [pic].
Однако [pic] и образуют компактное множество. Пусть [pic] -
последовательность, сходящаяся к [pic]. Нетрудно видеть, что [pic]и
[pic].
В самом деле, [pic], откуда и следует последнее равенство.
Кроме того, для [pic], имеем
[pic]
Оценим
[pic]
Так как [pic]
[pic]
[pic]то
[pic].
Отсюда следует, что
[pic] , т.е. [pic].
Но в этом случае
[pic] для [pic],
что противоречит предположению. Таким образом, теорема доказана.
Замечание. Ранее мы полагали [pic]и фактически использовали только то,
что множество точек, для которого[pic], компактно. Все результаты
сохраняются, если в качестве [pic] выбрать произвольную положительно
определенную квадратическую форму
[pic],
видоизменив соответствующим образом понятие нормального решения.

Литература

1. Линейные неравенства. М., Физматгиз, 1962.
2. Р. Курант. Уравнения с частными производными. М., Изд-во ин. лит., 1964.