Матричная коррекция данных для несовместных систем линейных уравнений и ее применение в задачах оптимизации и классификации тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Муравьева, Ольга Викторовна

• Муравьева, Ольга Викторовна
• кандидат физико-математических наук
• 2002

Оглавление диссертации кандидат физико-математических наук Муравьева, Ольга Викторовна

Введение.

Глава 1. Коррекция системы линейных уравнений.

1.1. Существование и единственность минимальной матрицы.

1.2. Радиусы совместности и несовместности системы линейных уравнений.

1.3. Матрицы коррекции специального вида.

Глава 2. Решение двукритериальной задачи коррекции несобственной задачи линейного программирования.

2.1. Коррекция несобственной задачи ЛП без условия неотрицательности плана.

2.2. Коррекция несобственной задачи ЛП в канонической форме.

2.3. Коррекция несобственной задачи ЛП в стандартной форме.

Глава 3. Использование коррекции системы линейных уравнений для решения некоторых задач аппроксимации

3.1. Задача аппроксимации линейной функцией с коррекцией всех данных.

3.2. Аппроксимация в задаче векторной оптимизации.

3.3. Методы коррекции в геометрических задачах.

Введение диссертации (часть автореферата) на тему «Матричная коррекция данных для несовместных систем линейных уравнений и ее применение в задачах оптимизации и классификации»

Актуальность темы. Проблема наилучшего выбора всегда была в центре внимания, однако только с середины XX века она становится предметом науки — теории принятия решений. Разработка математических моделей и методов теории принятия решений происходит параллельно развитию вычислительных мощностей компьютерной техники. Становится возможным численное решение задач, которые еще несколько десятилетий назад считались слишком трудоемкими. Одним из новых разделов теории принятия решений является исследование несобственных задач оптимизации или задач, которые по тем или иным причинам не имеют решение.

В теории принятия решений можно выделить четыре основных направления [11].

1. Описание цели и способов действий, которые могут привести к достижению поставленной цели; среди них будет производиться выбор наилучших способов.

2. Создание модели задачи принятия решений, дающей математическое описание цели, процесса и результатов.

3. Оценка и сравнение эффективности конкурирующих способов действий на основании созданной модели.

4. Разработка понимания оптимального выбора действий и математических методов их поиска.

Первое направление является областью конкретных исследований, учитывающих специфику данной задачи и опирающихся на соответствующие разделы науки. Моделирование должно быть пограничной областью, где особенно важно достижение взаимопонимания и взаимодействия специалистов рассматриваемой конкретной задачи наилучшего выбора и математиков. Построение моделей в нетрадиционнных для естествознания и техники областях (экономика, военное дело, экология и др.) до сих пор остается скорее искусством, чем точной наукой [36]. Сопри- з касаясь с самыми различными по предмету и методу исследования науками, специалисты по математической теории принятия решений вынуждены пересматривать, модифицировать свои модели, расширять класс моделей, считающихся допустимыми.

Первоначальное описание объекта, имеющее вид системы уравнений, неравенств и других соотношений, связывающих параметры или характеристики объекта, может быть неадекватным, т. е. не соответствовать реальному течению процесса, в частности, противоречивым — соответствующая система соотношений может не иметь решений, быть несовместной. Модель, которая получается на последнем этапе исследования, должна быть непротиворечивой. Таким образом, моделирование сложных процессов и явлений — итеративный процесс [31], [43], [44].

Источники противоречивости модели и, как следствие, постановки несобственной задачи оптимизации, разнообразны. Эмпирические данные, как результаты измерения, могут быть недостаточно точными; не всегда известно заранее, разрешима ли данная задача при определенных значениях параметров, некоторые из которых, возможно, допускают изменения при необходимости. Разработка модели почти всегда связана с борьбой двух гю существу противоречивых желаний: как можно точнее отобразить в модели реальные процессы и получить модель достаточно простую, чтобы можно было надеяться решить задачу до конца и получить обозримые результаты [11], [43], [44]. Но по мере усложнения моделей возрастает вероятность прийти к противоречию при первоначальном отборе факторов, включаемых в модель, и способах их параметризации. Существует также возможность противоречивости информации как адекватного отражения глубоких внутренних свойств рассматриваемого объекта [29], [41].

Проблема построения непротиворечивых моделей, связанная с выбором их структуры и информационного наполнения, является одной из центральных в теоретической информатике. Отдельные примеры задач, которые сейчас называют несобственными, рассматривались и раньше. Наиболее известными являются метод наименьших квадратов для несовместных уравнений и систем и задача аппроксимации функции. Систематическое изучение началось недавно с работ И. И. Еремина ([24]-[31]), в которых рассматриваются несобственные задачи линейного и выпуклого программирования, проводится классификация, строится теория двойственности, предлагаются различные постановки и методы решения задач коррекции и их экономическая интерпретация.

Так же, как в классической оптимизации, одним из наиболее важных разделов теории несобственных задач является линейное программирование (ЛП). Это связано как с относительной простотой решения задач такого типа, так и с их практической значимостью. Как известно, очень многие прикладные задачи из области экономики и планирования производства можно моделировать линейными соотношениями.

Несобственные задачи оптимизации, как задачи, не имеющие решения, можно разбить на два класса: задачи с пустым допустимым множеством и задачи, в которых допустимое множество не пусто, но оптимизируемая функция на нем не достигает экстремального значения. Для линейного программирования можно уточнить, что в несобственной задаче либо допустимое множество пусто, либо целевая функция не ограничена на допустимом множестве. Используя теорию двойственности, можно выделить три типа задач, не имеющих решение [31]. Несобственной задачей ЛП первого рода называется задача, допустимое множество которой пусто, а допустимое множество двойственной задачи не пусто. В несобственной задаче второго рода целевая функция не ограничена на непустом допустимом множестве, и, следовательно, допустимое множество двойственной задачи пусто. Если системы ограничений и прямой, и двойственной задачи несовместна, получим несобственную задачу третьего рода. Задача первого рода может быть скорректирована изменением только вектора ограничений, в задаче второго рода этого, очевидно, недостаточно. Необходимо изменять также или коэффициенты целевой функции, или матрицу ограничений. Аналогично, в задаче третьего рода надо или изменять вектора ограничений и прямой, и двойственной задачи, или изменять матрицу ограничений. Заметим также, что двойственная к несобственной задаче первого рода является несобственная задача второго рода, и наоборот. Таким образом, по существу можно выделить два случая проблемы коррекции задачи ЛП — только одна из двух взаимно двойственных задач имеет несовместную систему ограничений или обе задачи не имеют допустимых планов. И в том, и в другом случае для устранения противоречивости может использоваться коррекция коэффициентов матрицы ограничений.

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

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

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

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

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

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

Цели работы. Перечисленные проблемы определили цели настоящей диссертации, которые можно сформулировать следующим образом:

• исследование свойств задачи аппроксимации несовместной системы линейных уравнений с коррекцией всех данных;

• анализ задачи коррекции несобственной задачи ЛП как двухкрите-риальной проблемы максимизации исходного критерия и минимизации коррекции, формализованной как задача минимизации нормы корректирующей матрицы при ограничении на значение исходного критерия;

9 сведение поставленной задаче к проблеме нахождения собственных чисел и векторов некоторых специальных матриц;

• применение полученных результатов для анализа геометрических задач минимальной коррекции кривых первого и второго порядка;

• постановка и решение задачи линейной аппроксимации табличных данных по критерию минимизации суммы квадратов расстояний от заданных точек до аппроксимирующей кривой;

• исследование проблемы построения единого критерия на классе линейных сверток в задаче векторного программирования с использованием дополнительной информации о значениях на конечной выборке стратегий.

Объектом исследования является теория несобственных задач линейного программирования.

Предметом исследования — несобственная задача линейного программирования с пустым множеством допустимых планов.

Проблема заключается в построении непротиворечивой модели оптимизации на основе количественных методов математической теории принятия решения и теоретическом обосновании процедур аппроксимации.

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

Для реализации поставленной цели и проверки сформулированной гипотезы потребовалось решить следующие задачи:

• исследовать задачу матричной коррекции несовместной системы линейных уравнений, теоретически обосновать сведение поставленной

- 9задачи к определению собственных чисел и векторов специальных матриц, включая проблему существования и единственности решения задачи коррекции;

• исследовать задачу матричной коррекции с фиксированными строками, обосновать сведение этой задачи к вспомогательной задаче на собственные числа и собственные вектора;

• исследовать постановку задачи матричной коррекции несобственной задачи ЛП как проблему минимальной коррекции допустимого множества с фиксированным пороговым значением целевой функции; для соответствующей задачи коррекции несовместной системы линейных уравнений с дополнительным ограничением-неравенством получить аналитическое выражение решения через собственные числа и собственные вектора некоторых матриц;

• сформулировать и обосновать вероятностно задачу линейной аппроксимации функции с коррекцией всех координат заданных узлов по критерию минимизации суммы квадратов расстояний от заданных точек до аппроксимирующей гиперплоскости;

• интерпретировать поставленную задачу как задачу коррекции несовместной системы линейных уравнений и найти решение в двумерном случае и аналитическое выражение решения через собственные значения вспомогательной матрицы в общем случае;

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

• сформулировать задачи коррекции прямых и плоскостей с целью получения заданных свойств (параллельность, пересечение и т. п.) и получить аналитическое выражение решения с использованием процедур коррекции несовместных систем линейных уравнений;

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

Методологическую основу работы составляют современные методы математической теории принятия решений, теории вероятностей, линейной алгебры, матричного анализа, аналитической геометрии, математического анализа.

Научная новизна. Есть несколько подходов к рассмотрению задачи ЛП в условиях неполной, неточной или недостоверной информации. Для поиска решения, устойчивого к изменению исходных данных, разработаны методы регуляризации в теории некорректных задач [59]. Такой подход используется давно, является наиболее хорошо изученным, результаты стали классическими и включаются в основное содержание теории линейного программирования в учебной литературе [1],[3], [23].

Другой подход — задать область изменения параметров и рассматривать неточную задачу оптимизации. Таким образом, параметры задачи являются неопределенным неконтролируемыми факторами с известной областью значений. Для этой задачи можно использовать принцип ми-нимакса (искать решение при наихудшем значении параметров) или абсолютной гарантированное™ (искать решение при всех возможных значениях параметрах) [9], [13], [53], [57].

В настоящей работе предполагается, что лицо, принимающее решение, может контролировать изменение параметров, или, по крайней мере, максимально возможную меру этого изменения. Корректируемые параметры можно интерпретировать как активные средства, возможность изменения которых может при необходимости быть включена в модель. Решение осуществляется на основе метода параметрического программирования [37]. Такие задачи до недавнего времени оставались малоисследованными. В большинстве работ, посвященных коррекции несобствен- и ной задачи ЛП, рассматривается коррекция по вектору ограничений Ъ и коэффициентам целевой функции с [5], [8], [22], [24], [28], [30], [45]-[47], [51], [52], [54], [55]. Вопросы матричной коррекции рассматривали немногие авторы. Это работы И. И. Еремина, А. А. Ватолина, В. А. Горелика, В. А. Кондратьевой и других [4], [6], [7], [14]-[16], [18], [25]-[27], [29], [31], [38]. Основные результаты достигнуты в построении общей теории анализа противоречивых моделей, в частности, теории двойственности для несобственных задач, набор процедур коррекции для конкретных постановок несобственных задач и опыт различных приложении не очень велик.

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

В настоящей работе

• исследуются вопросы существования и единственности решения в задаче матричной коррекции несовместной системы уравнений по критериям евклидовой и спектральной норм матрицы;

• рассмотрены некоторые не изученные ранее обобщения задачи коррекции несовместной системы линейных уравнений, в частности, фиксированные ограничения одновременно с некорректируемым вектором правой части системы, линейные ограничения на матрицу коррекции;

• получены аналитические выражения для решения несобственной задачи ЛП первого рода, формализованной заданием порогового значения целевой функции и введением ее в качестве директивного ограничения при коррекции, рассмотрены случаи с произвольным допустимым планом и с условием неотрицательности;

• для всех рассмотренных задач коррекции построены вспомогательные задачи определения собственных чисел и векторов специальных матриц, сведение к которым теоретически обосновано;

• формулируется и решается задача линейной аппроксимации дискретно заданной функции по критерию, отличному от используемого в методе наименьших квадратов;

• приводятся процедуры построения единого критерия в задаче векторной оптимизации, основанные на различных методах аппроксимации несовместных систем линейных уравнений с дополнительными ограничениями;

• теория коррекции несовместных систем линейных уравнений применяется для классификации свойств в задачах аналитической геометрии.

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

Основные положения, выносимые на защиту:

• коррекцию несобственной задачи ЛП можно осуществлять возмущением всех параметров задачи на основе аппроксимации несовместной системы ограничений с гарантированным пороговым значением целевой функции; формализованная таким образом задача является задачей квадратичного программирования, решаемой стандартными алгоритмами;

• целесообразно, наряду с классическими подходами, рассматривать в качестве критерия аппроксимации функции, заданной набором точек, сумму квадратов расстояний от эмпирических точек до аппрок

- 13 симирующей кривой; для линейной функции решение задачи аппроксимации можно получить с помощью вспомогательной задачи определения собственных векторов и значений специальной матрицы;

• на основе различных подходов к аппроксимации несовместных линейных систем могут быть построены методы сведения к единому критерию частных критериев количественного типа в задаче векторной оптимизации;

• на основе методов коррекции несобственной задачи линейной оптимизации могут быть сформулированы и решены задачи минимальной коррекции неточно заданных элементарных кривых.

Апробация работы. Результаты исследования были представлены на 1-й Московской конференции "Декомпозиционные методы в математическом моделировании", на научно-методических семинарах кафедры информатики и дискретной математики МПГУ.

Основное содержание работы. Работа состоит из введения, трех глав, заключения и списка литературы.

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

В первой и второй главах рассматривается несобственная задача ЛП с несовместной системой ограничений: тах{(с,х): Ах = 6, ж > 0}, где А е Rmxn, b G RTO, c,.t e Rn.

В качестве совместной задачи, аппроксимирующей данную, строится задача, полученная минимальным (по норме корректирующей матрицы)

- 14изменением параметров: inf{||[—Л, Н}\\2задача max{(c,rr): {А-\гН)х — Ь+h, X ^ 0} имеет решение}

H,h или inf{||#||2: задача max{(c, х): (А + Н)х = Ь1 X > 0} имеет решение}. н m,n

Норма матрицы ||Я|| евклидова ||Я||е = W £ Щ или спектральная

Я||2 = max ||Яе||, где II • II — евклидова норма вектора.

1И=1

Целевая функция исходной задачи, в соответствии с подходом, предложенным в [14], может быть учтена введением в задачу коррекции дополнительного ограничения снизу на ее значение вида (с, х) ^ с0. Тогда путем изменения значения Со можно добиться результатов, удовлетворяющих лицо, принимающее решение. Кроме того, на задачу коррекции могут накладываться другие дополнительные ограничения, связанные с содержательной интерпретацией задачи.

Для построения собственной задачи ЛП, аппроксимирующей данную, в первой главе формулируются и исследуются следующие вспомогательные задачи:

I. Задача минимальной матричной коррекции несовместной системы линейных уравнений: inf {\\[-h, Н]||2: {A + H)x = b + h} x,H,h или inf{||#||2: {А + Н)х = Ъ}. х,Н

2. Задача коррекции несовместной системы линейных уравнений с фиксированными ограничениями типа равенства: inf{||#||2: (Ai + Н)х = Ь\А0х = Ь0}. х,Н

3. Задача коррекции несовместной системы линейных ограничений с линейными ограничениями на матрицу коррекции: inf{||#||2: (А + Н)х = 6,стН = dT}. х ,Н

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

В § 1.2 с использованием теории коррекции несовместной системы линейных уравнений находятся радиусы совместности и несовместности системы линейных уравнений: inf{||[-/i,#]||2: Зж, (А + Н)х = b + h}, inf{||#||2: Зх,(А + Н)х = 6}, inf{|| [-Л, Я] ||2: {х: (А + Н)х = Ъ + К] = 0}, inf{||#||2: {х: {А + Н)х = Ь} = 0}.

Для произвольной квадратной матрицы определяется радиус невырожденности как величина минимального возмущения коэффициентов матрицы, приводящего к ее вырожденности:

R — inf{||if||2: detf^ + Я) =0}. н

Критерием степени возмущения является норма (евклидова или спектральная) корректирующей матрицы. Отдельно рассматривается случай, когда часть столбцов матрицы фиксируется и не изменяется, и определяется радиус невырожденности матрицы при этом условии.

Для положительно определенной симметрической матрицы ставится задача определения минимальной по норме симметрической корректирующей матрицы, сумма которой с исходной матрицей пе обладает свойством положительной определенности. Значение этой задачи — радиус положительной определенности — оказывается равным радиусу невырожденности:

Rq = illf {\\Н||2 : {А + Н) не является положительно определенной} = R, яе5(п) где S(n) — множество симметрических матриц порядка п.

Для всех перечисленных характеристик найдено выражение через собственные числа матрицы.

§ 1.3 посвящен матрицам коррекции специального вида. Пусть ограничения в задаче линейного программирования подразделяются на директивные и факультативные. Директивные ограничения заданы точно и не подлежат изменению. Коэффициенты факультативных ограничений могут корректироваться. Ставится задача минимальной коррекции части строк матрицы ограничений, приводящей к совместности всей системы: inf{||#||2: (А1 + Н)х = Ь\Аъх = Ъ°}.

Здесь в полной матрице коррекции определенные строки должны быть нулевыми.

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

Во второй главе результаты, полученные в первой главе, применяются

- 17 для построения собственной аппроксимирующей задачи ЛП. В §2.1 рассматривается задача ЛП, допустимое множество которой представляет собой множество решений системы линейных уравнений: тах{(с, х): Ах = Ь}.

Для аппроксимации несобственной задачи такого вида предлагается корректировать допустимое множество при дополнительном условии достижимости на нем порогового значения целевой функции. Основной задачей этого параграфа является коррекция несобственной задачи линейного программирования с ограничением снизу на значение целевой функции без условия неотрицательности плана: inf{||#||2: (А + Н)х = Ь,(с,х) > с0}.

В §2.2 рассматривается аппроксимация задачи ЛП в канонической форме. В качестве вспомогательной рассматривается задача коррекции несобственной задачи ЛП в канонической форме с дополнительным ограничением равенством: inf{||#||2: (А + Н)х = Ъ, (с, х) = с0, х > 0}.

Для построения аппроксимирующей собственной задачи ставится задача коррекция несобственной задачи ЛП в канонической форме с ограничением снизу на значение целевой функции: inf{||#||2 : (А + Н)х = 0, (с, х) > с0}

В §2.3 рассматривается коррекция задачи ЛП в стандартной форме. Для ее решения выполняется матричная коррекция системы линейных неравенств, в том числе с условием неотрицательности: inf{||[—Д, Н]\\2: (А + Н)х ^b + h}, inf {|| [-h, Я] ||2: (А + Н)х > Ъ + h, х > 0}.

Отдельно рассматривается случай фиксированной правой части системы ограничений: inf{||#||2: {А + Н)х>Ъ}, iiif{||i7||2: (А + Н)х > М > 0}.

Все сформулированные в этой главе задачи сводятся к задачам квадратичного программирования минимизации квадратичной формы на пересечении единичной сферы и неотрицательного ортанта.

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

В §3.1 рассматривается задача аппроксимации функции, заданной набором значений, линейной функцией. Пусть для неизвестной функциональной зависимости у — ср(х) получен набор точек (х\у%) и аппроксимирующая функция строится на классе линейных функций у — (а, х) -\-Ь. В качестве критерия " близости" берется сумма квадратов расстояний от заданных точек до аппроксимирующей прямой (гиперплоскости) ж: у = (о, х) 4- т. е. исследуется задача

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

В § 3.2 рассматривается проблема построения единого (общего) критерия в задаче векторной оптимизации. Известны частные критерии W\(x), W2(x), . , Wn(x), х G Шр. Для некоторой выборки из множества стратегий х1, ж2, . , хт известны количественные оценки значений общего критерия Ь\, -. • , Ът. На основании этой информации лицом, принимающим решение, строится единый критерий на классе линейных сверп п ток W(x) — A,W2(;r), Аг ^ О, ^г = Если ввести в рассмотрение г—1 г = 1 матрицу значений частных критериев при фиксированном наборе стратегий W = (wij) = (Wj{x1)), i — 1,., m, j — 1,. , тг, то веса Хг должны удовлетворять системе условий вида:

WX = b, А > 0, ^Аг = 1. г=1

Данная система линейных уравнений относительно А может не иметь решения. В этом случае в соответствии с подходом многошагового построения модели исходные данные корректируются для устранения противоречивости. Формулируются и исследуются следующие задачи: inf {IIA6II2: WX = b + Ab, А > О, V Аг = 1},

Л,Д6 ^ i=1 п inf {\\AW\\2: (W + AW)X = b, A > 0, ^ Аг = 1},

XjAW i=l n inf {\\[-Ab,AW}\\2: (W + AW)X = b + Ab, A >0, Va,- = 1}.

A,AW,A6 ' г=1

Последние две задачи являются частными случаями задач, рассмотренных в первой главе, и для них получены выражения через собственные числа и вектора некоторых матриц.

В § 3.3 рассматриваются некоторые задачи аналитической геометрии в условиях неточных данных. Для кривых первого и второго порядка формулируются задачи минимальной коррекции параметров для получения требуемых геометрических свойств. Обозначим 7Ti, тг2 6 Р — прямые или

ПЛОСКОСТИ, (p(7Ti), (f( 7Г2) -Образы 7Ti, 7Г2 При коррекции, Ф((/?(7Г1), (р(к2)) —

-20 характеристика величины коррекции — норма вектора, составленного из величин изменений всех параметров, задающих элемент из множества Р, р — некоторое бинарное отношение на множестве Р (параллельность, перпендикулярность, инцидентность). Для задач вида inf{<£(^(7Ti),^(7r2)): <р(т) pip{ir2)} получены аналитические выражения решения через собственные числа и вектора.

В соответствии с классификацией невырожденных кривых второго порядка (эллипс, гипербола, парабола) получены выражения для величины возмущения коэффициентов общего уравнения, достаточного для изменения класса кривой: inf{<£(/(7)): /(7) — эллипс}, inf{#(/(7)): /(7) — гипербола}, inf{$(/(7)): /(7) — парабола}, для всех действительных невырожденных кривых второго порядка 7 (гипербола или эллипс или парабола), где /(7) — кривая, полученная изменением коэффициентов уравнения, задающего кривую 7, <£(/(7)) — норма вектора изменений всех параметров уравнения кривой. Полученные результаты позволяют уточнить классификацию кривых второго порядка в пространстве параметров.

Заключение содержит основные результаты и выводы, полученные в ходе исследования.

Основное содержание диссертации отражено в работах: [17], [19], [20], [21], [61].

Заключение диссертации по теме «Теоретические основы информатики», Муравьева, Ольга Викторовна

Заключение

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

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

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

Решения рассмотренных задач можно интерпретировать как радиусы несовместности системы линейных уравнений. Получено также аналитическое выражения для радиуса совместности системы линейных уравнений (через собственное число некоторой матрицы).

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

Исследованы некоторые частные постановки задач коррекции системы линейных уравнений. Получено аналитическое выражение через собственное число некоторой матрицы для задачи коррекции системы ли- % нейных уравнений с фиксированным (некорректируемым) подмножеством ограничений. Аналогичный результат получен в случае, если матрица коррекции также должна дополнительно удовлетворять некоторой линейной системе ограничений.

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

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

Для задачи векторной оптимизации формулируется задача линейной свертки критериев с коррекцией различных подмножеств исходных данных. Поставленные задачи сводится к задачам коррекции несовместной системы линейных уравнений. Показано, что все задачи имеют решение и выполнено преобразование к стандартным задачам определения собственных чисел и векторов.

Список литературы диссертационного исследования кандидат физико-математических наук Муравьева, Ольга Викторовна, 2002 год

1. Ашманов С.А. Линейное программирование. М.: Паука, 1982. 134 с.

2. Баврин И.И., Матросов В.Л. Общий курс высшей математики. М.: Просвещение, 1995. 464 с.

3. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Изд-во "Факториал", 1998. 176 с.

4. Ватолин А.А. Аппроксимация несобственных задач линейного программирования по критерию евклидовой нормы. // ЖВМиМФ, 1984. Т. 24. №12. С. 1907-1908.

5. Ватолин А.А. Метод аппроксимации несобственной задачи выпуклого программирования. В кн.: Несобственные задачи оптимизации. УНЦ АН СССР. Свердловск, 1982. С. 67-74.

6. Ватолин А.А. Множества разрешимости и коррекция еедловых функций и систем неравенств. Препринт. Свердловск: УрО АН СССР, 1989. 89 с.

7. Ватолин А.А. Об аппроксимации несовместных систем уравнений и неравенств. В кн.: Методы аппроксимации несобственной задачи линейного программирования. УНЦ АН СССР. Свердловск, 1984. С. 39-54.

8. Ватолин А.А. Об одной общей реализации схемы двойственнности для несобственной задачи линейного программирования. В кн.: Противоречивые модели оптимизации. Свердловск, 1987. С. 21-27.

9. Ватолин А.А. О задачах линейного программирования е интервальными коэффициентами // ЖВМиМФ, 1984. Т.24. №1. С. 1629-1637.

10. Вептцель Е.С. Теория вероятностей. М.: Наука, 1964. 576 с.

11. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971. 384 с.

12. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999. 548 с.

13. Годунов С.К., Антонов А.Г. и др. Гарантированнная точность решения систем линейных уравнений в евклидовых пространствах. Новосибирск: ВО "Наука", 1992. 360 с.

14. Горелик В.А. Матричная коррекция задачи линейного программирования с несовместной системой ограничений. // ЖВМиМФ, 2001. Т. 41, № 11. С. 1697-1705.

15. Горелик В.А., Ерохин В.И. О верхней оценке минимума квадратичной формы на пересечении единичной сферы с областью неотрицательных координат. // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2001. С. 30-50.

16. Горелик В.А., Ерохин В.И. Интервальная коррекция непродуктивной матрицы прямых затрат в линейной модели межотраслевого баланса. // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2001. С. 51-56.

17. Горелик В.А., Кондратьева В.А. Параметрическое программирование и несобственные задачи линейной оптимизации. // Моделирова- 100ние, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 1999. С. 57-82.

18. Горелик В.А., Муравьева О.В. Задача аппроксимации с коррекцией всех данных. // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2000. С. 21-32.

19. Горелик В.А., Муравьева О.В. Коррекция несовместной системы линейных уравнений с дополнительными ограничениями. // Тезисы докладов 1-й Московской конференции Декомпозиционные методы в математическом моделировании. М.: ВЦ РАН, 2001. С. 36.

20. Давыдов Э.Г. О системах несовместных линейных уравнений. // Вестник МГУ, 1989. сер. 15. №2. С. 76-79.

21. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976. 192 с.

22. Еремин И.И. Вопросы двойственности для несобственной задачи многокритериальной линейной оптимизации. В кн.: Исследования по несобственным задачам оптимизации. УНЦ АН СССР. Свердловск, 1988. С. 27-33.

23. Еремин И.И. Двойственность в линейной оптимизации. Екатеринбург: УрО РАН, 2001. 179 с.

24. Еремин И. И. Двойственность для несобственной задачи линейного программирования. В кн.: Несобственные задачи оптимизации. УНЦ АН СССР. Свердловск, 1982. С. 3-10.

25. Еремин И.И., Ватолин А. А. Двойственность для несобственных бесконечномерных задач линейного и выпуклого программирования. В кн.: Методы аппроксимации несобственной задачи линейного программирования. УНЦ АН СССР. Свердловск, 1984. С. 3-20.

26. Еремин И. И. Несобственная задача квадратичного программирования и вопросы регуляризации. В кн.: Параметрическая оптимизация и методы аппроксимации несобственных задач математического программирования. УНЦ АН СССР. Свердловск, 1985. С. 47-50.

27. Еремин И. И. Противоречивые модели оптимального планирования. М.: Наука, 1988.160 с.

28. Еремин И. И. Противоречивые модели планирования и управления. В кн.: Противоречивые модели оптимизации. Свердловск, 1987. С. 28-37.

29. Еремин И.И., Мазуров В.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука. Физматлит., 1983. 336 с.

30. Жуковский В.И., Молостов B.C. Многокритериальная оптимизация систем в условиях неполной информации. М: МНИИПУ, 1990. 112 с.

31. Ильин В.А., Познлк Э.Г. Аналитическая геометрия. М.: Наука. Физматлит, 1999. 224 с.

32. Карманов В.Г., Федоров В.В. Моделирование в исследовании операций. М.: Твема, 1996.

33. Кондратьева В.А. Несобственные задачи линейной оптимизации и параметрическое программирование. Дисс. на соиск. учен. степ. канд. физ.-мат. наук: 05.13.17 / МПГУ, 2000.

34. Краснощекое П.С., Петров А.А. Принципы построения моделей. М.: Фазис: ВЦ РАН, 2000. 412 с.

35. Левитин Е. С. Теория возмущений в математическом программировании и ее приложения. М.: Наука, 1992. 360 с.

36. Лисьих И. Г. Изучение структуры множеств разрешимости параметризованных задач линейного программирования. В кн.: Нерегулярная двойственность в математическом программировании. Свердловск. 1990.

37. Лоусон Е., Хенсон Р. Численное решение задач метода наименьших квадратов. М.: Наука, 1986. 232 с.

38. Мазуров В.Д. Метод допустимых коррекций. В кн.: Несобственные задачи оптимизации. УНЦ АН СССР. Свердловск. 1982. С. 11-22.

39. Мазуров В.Д., Смирнов А.И. Неоднозначная интерпретация противоречивых данных. В кн.: Системы принятия решений в задачах классификации и планирования. Свердловск, 1992. С. 3-18.

40. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. М.: Высш.шк., 1986. 287 с.

41. Павловский Ю.Н. Имитационные модели и системы. М.: Фазис, 1998. 266 с.

42. Павловский Ю.Н., Смирнова Т. Г. Проблема декомпозиции в математическом моделировании. М.: Фазис, 2000. 265 с.

43. Попов Л.Д. Несобственные задачи оптимизации, методы их оптимальной коррекции и приложения. Дисс. на соиск. учен. степ. докт. физ.-мат. наук: 01.01.09 / Новосибирск, 1997.

44. Попов Л.Д. Об одном методе декомпозиции в несобственном линейном программировании. В кн.: Нерегулярная двойственность в математическом программировании. Свердловск, 1990. С. 42-45.

45. Прасолов В.В. Задачи и теоремы линейной алгебры. М.: Наука. Физ-матлит, 1996. 304 с.

46. Себер Дж. Линейный регрессионный анализ. М.: Мир, 1980. 456 с.

47. Румшиский Л.З. Математическая обработка результатов экспериментов. М.: Наука, 1971. 192 с.

48. Скарин В.Д. К анализу несобственной задачи выпуклого программирования с позиции последовательной оптимизации. В кн.: Несобственные задачи оптимизации. УНЦ АН СССР. Свердловск, 1982. С. 30-36.

49. Скарин В.Д. Об одном алгоритме численного анализа несобственной задачи линейного программирования. В кн.: Параметрическая оптимизация и методы аппроксимации несобственных задач математического программирования. УНЦ АН СССР. Свердловск,1985. С. 63-69.

50. Скарин В.Д. Об одном подходе к анализу несобственных задач линейного программирования. // Журн. Вычисл. матем. и матем. физики, 1980. 1986. Т.26. №3. С. 439-448.

51. Скарин В Д. Об одном регуляризующем алгоритме коррекции противоречивых задач выпуклого программирования с линейными ограничениями. В кн.: Исследования по несобственным задачам оптимизации. УНЦ АН СССР. Свердловск, 1988. С. 48-56.

52. Скарин В Д. О применении метода регуляризации для коррекции несобственной задачи линейного программирования первого рода. В кн.: Методы аппроксимации несобственной задачи линейного программирования. УНЦ АН СССР. Свердловск, 1984. С. 39-54.

53. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986. 328 с.

54. Тимохин С.Г., Шапкин А.В. О задачах линейного программирования в условиях неточных данных j j Экономика и матем. методы, 1981. Т.17. №5. С. 955-963.

55. Тихонов А.Н. О приближенных системах линейных алгебраических уравнений. // ЖВМиМФ, 1980. Т20. №6. С. 1373-1383.

56. Тихонов А.Н., Арсении В.Я. Методы решения некорректных задач. М.: Наука, 1986. 288 с.

57. Хори Р, Джонсон У. Матричный анализ. М.: Мир, 1989. 655 с.

58. Gorelik V.A. Muravyova O.V. Problem of approximating with variation of all data. // Тезисы докладов 3-й международной конференции по исследованию операций. М.: ВЦ РАН, 2001. С. 43.