автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Матричная коррекция несобственных задач линейного программирования со специальной структурой

На прзпах рукописи

Хвостов Михаил Николаевич

МАТРИЧНАЯ КОРРЕКЦИЯ НЕСОБСТВЕННЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СО СПЕЦИАЛЬНОЙ

СТРУКТУРОЙ

05.13.17 — Теоретические основы информатики

Автореферат 2 7 МАЙ 2015

диссертации на соискание учёной степени кандидата физико-математических наук

Научный руководитель: доктор физико-математических наук, профессор Ерохшт В.И.

Москпа — 2015

005569494

Работа пылол йена в Борисоглебском филиале Федерального государственного бюджетного образовательного утреждегсия высшего профессионального образования «Воронежский государственный университет».

Научный руководитель: Ерохин Владимир Иванович, доктор физико-математических наук, профессор.

Официальные оппоненты: Хачай Михаил Юрьевич, доктор физико-математических наук, с.и.е.. Федеральное государственное бюджетное учреждение uaj'KH Институт математики и механики им. H.H. Красовского УрО РАН, заведующей Отделом математического программирования.

Муравьева Ольга Викторовна, кандидат ф;гзико-математических наук, до пен т. Федеральное государственное бюджетное образовательное учреждепие высшего ттрофессиоиаль-ного образования «Московский педагогический государственный университет», доцент кафедры теоретической информатики и ;[искperпoft математики математического факультета.

Ведущая организация: Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования «Санкт-Петербургский государственный университет».

Защита состоится « 25 ш> икыя 2015г. в 16 : 00 па заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки Вычислительный центр им. A.A. Дородницына Российской академии наук, расположенном по адресу: 119333, г. Москва, ул. Вавилова, д. {0.

С диссертацией можно ознакох*иться в библиотеке Федерального государственного бюджетного учреждения науки Вычислительный центр им. A.A. Дородницына Российской академии наук л па сайте http://www.ccas.ru.

Автореферат разослан < 12 » мая 2015г.

Учёный секретарь

диссертационного совета Д 002.017.02, д.ф.-м.н., профессор

ВВРяза"ов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

информатики.

Несмотря на то, что изучение методов коррекции данных несобственных задач линейного программирования является относительно новым направлением развития теоретической информатики, предпосылки к исследованию проблем коррекции данных несобственных задач выпуклого программирования и противоречивых систем линейных алгебраических уравнений можно проследить еще в работах А.Н. Тихонова. Систематические же исследования в данной области были начаты в 80-х годах (XX века) И.И. Еремиными, его учениками и коллегами: H.H. Астафьевым. A.A. Ва~ толиным. Вл.Д. Мазуровым. Л.Д. Поповым. В.Д. Скариным. С.П. Трофимовым, В.Н. Фроловым и другими.

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

В конце 90-х годов (XX в.) исследования в области коррекции несобственных задач линейного программирования были продолжены (а также продолжаются в настоящее время) в ВЦ им. A.A. Дородницына РАН и Московском педагогическом государственном университете В.А. Гореликом, его учениками и коллегами: В.И. Ерохиным, В.А. Кондратьевой, О.В. Муравьевой. P.P. Ибатуллиным, Р.В. Печенкиным, И.А. Золтоепой и другими. Указанными авторами широко исследовалась коррекция несовместных систем линейных алгебраических уравнений при условии неотрицательности решения, а так же показана их тссная связь с задачами матричной корекции несобственных задач линейного программирования.

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

рованной линейной оптимизационной модели. Одними из первых трудов в области матричной коррекции двойственной пары задач линейного программирования были работы Еремина И.И.. Ватолинл A.A.. Трофимова С.П., Астафьева H.H., Ерохина В.И. В настоящее время работы в области матричной коррекции двойственной пары задач линейного программирования активно ведутся Ерохиным В.И.. Красншювым A.C.. Баркаловой O.G. не только но критерию евклидовой нормы, но и по минимуму полиэдральных норм.

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

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

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

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

В большинстве исследований численные методы решения задачи математического программирования к которой сводится исходная задача матричной коррекции данных не рассматриваются. Исключениями могут служить работы В.А. Горелика. В.И. Ерохина, Р.В. Печенкина. И.А. Золтос-вой. Н.З. Ле в которых намечаются подходы к разработке соответствующих численных методов и алгоритмов матричной коррекции данных на основе TLN (Total Least Norm - алгоритм обобщенной наименьшей нормы) и метода Ньютона. К данному ряду работ можно отнести работы В.И. Ерохина и A.C. Красникова, исследовавших численные методы коррекции данных с применением метода Марквардта.

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

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

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

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

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

В основу исследования положена следующая гипотеза. Пусть несобственная линейная оптимизационная модель является результатом неточно заданных или противоречивых исходных данных. Причем, данная оптимизационная модель представляет собой несобственную задачу ЛП 1-го рода. Оптимальная матричная коррекция, сводимая к задаче оптимизации, позволяет получить оптимальные по минимуму евклидовой нормы матрицы коррекции II{ или — /?,£], гарантирующие собственность и структурный вид скорректированной линейной модели

(Л Н[)х = Ъ. X > 0, стх -* max ИЛИ (Л + Щ)х = b + h*, х 0, стх ~> max

и соответствующие оптимальные векторы .г^ и uj. Результатами оптимальной совместной матричной коррекции, сводимой к задаче оптимизации, позволяющей получить оптимальные по минимуму евклидовой нормы матрицы коррекции являются или {Н2 — h^}. гарантирующие собственность и структурный вид скорректированных линейных модели

и соответствующие оптимальные векторы х\ и и*2. Тогда Щ и Щ, 1г\ и ¡1',, х\ и х%, и\ и и% попарно совпадают.

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

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

2. Опираясь на теоретические результаты, полученные при решении предыдущей задачи, получить и обосновать условия существования реше-

или

ния несобственных задач линейного п;юграммировання 1-го рода со специальной структурой в виде запрета на кор[)екцию отдельных элементов расширенной матрицы коэффициентов их ограничений.

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

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

Научная новизна диссертации заключается в том, что получены и теоретически обоснованы:

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

2) конструктивные формулы построения указанного решения.

3) соответствующие численные алгоритмы квазиньютоновского типа с аналитическим вычислением производных.

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

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

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

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

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

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

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

Внедрение и апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались и обсуждались па Х1У-Я Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2011), Международной конференции «Современные проблемы прикладной математики и механики: теория, эксперимент и практика» (Новосибирск, 2011), Научно-технической конференции молодых ученых Санкт-Петербургского технологического института (технического университета) «Неделя науки - 2013» (Санкт-Петербург, 2013), VII Московской международной конференции по исследованию операций 011М-2013 (Москва, 2013), семинаре по конструктивному негладкому анализу и недифференцируемой оптимизации (С'^ЧЯА & ХТЮ) Санкт-Петербургского технологического института (технического университета)(Санкт-Петербург, 2014). Кроме того, основные результаты, полученные в диссертации, докладывались и обсуждались на научно-методических семинарах кафедры прикладной математики информатики, фикики и методики их преподавания Борисоглебского филиала федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Воронежский государственный университет» и кафедры инноватики и информационных технологий Санкт-Петербургского государственного -технологического института (технического университета).

Получено свидетельство о регистрации алгоритма [10].

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Пусть

L(A, Ь, с) : Ах = Ь, х ^ 0, стх max (1)

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

L*{A, b, с) : ii~A ^ ст, bTu ->■ min (2)

- двойственная ей задача линейного программирования в стандартной форме, где А 6 К'"*", с,х <= b,u € Rm . Символом Х(А,Ь) ± {х\Ах = Ь, х > 0] обозначим допустимое множество задачи L(A, 6, с), а символом 1А(А, с) = {u\uTA^cJ} - допустимое множество задачи L*(A,b, с).

Задач» (1), (2) условимся рассматривать как несобственные, в силу чего хотя бы одно из множеств Х(А,Ь) или И(А.с) является пустым. Задачей ~h' матричной коррекции пары взаимно двойственных несобственных задач ЛП L(A.b,c) и L*(A,b,c) будем называть задачу построения матрицы {Н - Л] С; Rm*("+1>, обладающей минимальной евклидовой нормой и гарантирующей разрешимость скорректированных задач

Г L(A + H,b+ h,c) :(A + H)x = b+h, х ^ 0, стх шах, \ L*{A + H,b + h,c) : ur(A + Я) > cT, {b + h)ru min.

Задачей DH матричной коррекции только левых частей (h — 0) пары взаимно двойственных несобственных задач ЛП L(A,b,c) и L*(A,b,c) будем называть задачу построения матрицы Я 6 Rmxr", обладающей минимальной евклидовой нормой и гарантирующей совместность скорректированных задач

Г L(A + Я, Ь, с) : (Л + Н)х = Ь, х ^ 0, с7х -»■ max, \ L'(A + Я, Ь, с) : п7(А + Я) Js ст, bTu min.

Одновременно с задачами

d\h -л]

и Dn будем рассматривать коррекцию противоречивой системы ограничений задачи L(A.,b,c), формализованную с помощью задач

р[Н -ы . { IIIя -411 min, я _ Г IIЯ|| mill,

\х(А + Н,Ъ+!г)ф0, ' \ Х(А + Н,Ь) ф 0,

где ||-Ц - евклидова матричная (далее, в зависимости от контекста, матричная или векторная) норма. Допустимые множества всех рассматриваемых задач матричной коррекции будем обозначать как FS(-)- Например, VS(SD^rr "''•) - допустимое множество решений задачи SD!-H

Теорема 1. (О достаточных условиях существования решения задачи D11)

Если X(A,b) — 0,U(A,c) ф 0 (т.е. Ь(А.Ъ.с) - несобственная задача ЛП 1-го рода), b ф 0, задача Рп разрешима и матрица Н* является её. реше.нисм, то задача D11 также разрешима и матрица Я* является ее решением.

Теорема 2. (О достаточных условиях существования решения задачи D\n -П)у

Если Х(А,Ь) = 0, U(A.c) ф 0 (т.е. L(A,b,c) - несобственная задача ЛП 1-го рода), задача Р[И разрешима и матрица [Я* —h*] является её решением, то задача D',If также разрешима и матрица [Я* — /)*] также является её решением.

Пусть задачи L(A,b,c) и L*(A,b,c) таковы, что Х(А,Ь) = 0, 1А(А,с) ф 0. С несобственными задачами Ь(А,Ь,с) и L'(A,b,c) будем связывать задачи SDU, SD*n SPH, SP'H структурной матричной коррекции, и которых матрице Я или расширенной матрице [Я — h] предписано иметь структуру нулевых и ненулевых элементов, задаваемую множествами индексов нулевых элементов

К = {(» е {1,2,..., т}, 3 € {1,2,...,тг})|Я,^ =0} ик = {« 6 {1,2.....т}|

А,- = 0}.

Для реализации структурных требований к Н и [Н — /г] вводится ряд объектов:

И =

Ъ = (У

= 0 если {г, .?'} € К, "Ну = 1 в противном случае ,

Г); = 0 если г € к, [); = 1 в противном случае . Как видно из представленных выше формул, матрица "Н и вектор [) - логические шаблоны для структуры нулевых и ненулевых элементов матрицы Н и вектора 1г.

(Р, Я) = («О =

П(Н)

р2 если ф 0. 0 в противном случае,

8

вектор, составленный из элементов строк в соответствии с шаблонами строк аналогично Й.([Я — Л]) - вектор, составленный из элементов строк —в соответствии с шаблонами строк ,

ВД =

(х,П1)

матрица, г-я строка которой составлена из нулевых элементов и элементов вектора х в соответствии с шаблоном Л,,. Выражения //(й) и [Я (Л) — Л(Л)] = [Я —Л] (Гг), - это соответственно матрицы Я и [Я — Л], восстановленные по вектору К.

Теорема 3. (О достаточных условиях существования решения задачи

Если Х(А,Ь) = 0,и(А,с) ^ 0 (т.е. /-(Дб, с) - несобственная задача ЛП 1-го рода), Ь ф 0. задача БР" разрешима и матрица Я* является

её решением, то ладана SDH также разрешима и матрица Н" является её решением.

Теорема 4. (О достаточных условиях существования решения задачи.

SDW -Ч)

Если A'(A,b) — 0,U(A,c) ф 0 (т.е. L(A,b,c) - несобственная задача ЛП 1-го рода), задача 5Р1Я ~А1 (с параметром I) ф 0) разрешима и матрица [ií* — h*] является её решением, то задача SDIй также разрешима и .матрица [Н — /г] является её решением.

Как показывают вычислительные эксперименты, часто в задачах SDH, SPH, SD^!Í SP¡í" и других задачах матричной коррекции оказывается оправданным использование взвешенной евклидовой нормы. Это связано с тем, что величина коррекция больших и малых по модулю коэффициентов систем ограничений равнозначна. Таким образом, при относительно небольшой по евклидовой норме матрице коррекции может быть получена задача ЛП совсем не «похожая» на исходную.

Пусть задачи L(A.b.c) и L*(A,b,c) таковы, что Х(А,Ь) — 0, U(А, с) ф 0. С несобственными задачами L(A,b,c) и L*(A,b,c) будем связывать задачи SwDH, SwD'H ~h\ SwP11, SwPV структурной взвешенной матричной коррекции, в которых матрице Н или расширенной матрице [Н — /i] предписано иметь структуру нулевых и ненулевых элементов, задаваемую множествами индексов нулевых элементов К и к, а также, весовые коэффициенты задаваемые матрицами W и №. Вес каждого элемента H¡j и /¡, задается элементами Wy и го,- соответственно, где W - весовая матрица с размерами т х п и ГО - весовая матрица с размерами т х 1.

Критерий оптимальности матричной коррекции в данной форме при условии

W= (Wij > 0|i е l,...,m, j 6

го = (го,- > 0|г е 1,.. .,т)

обладает почти максимальной общностью при использовании евклидовой нормы и является существенным условием ряда теоретических выкладок. Так, если некоторая прикладная задача может потребовать применения нулевых весов для отдельных элементов матриц Н, [Н — /г], то нулевые коэффициенты VV и го мотут быть заменены некоторыми малыми (отно-

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

Решения задач в общем случае (при произвольных матрицах И* и Из) не могут быть записаны в терминах собственных векторов матриц, построенных использованием матрицы А и вектора Ь, так как произведением матриц по Адамару («о») в общем случае не сводится к классическому матричному умножению.

Тогда для решения указанной проблемы вводятся следующие объекты: и(У\?) = [Н7!. ... И*,,,»]7 - вектор, составленный из элементов строк УУ,. и ш([>У го]) = [[И^ь №1] ... [УУт, ГО,,,]]' - вектор, составленный из элементов строк [УУ,„ го,-].

Теорема 5. (О достаточных условиях существования решения задачи

Если Х(А,Ь) = 0,Ы(А,с) ф 0 (т.е. Ь(А,Ь.с) - несобственная задача ЛП 1-го рода), Ь ф- 0, задача БгиР11 разрешима и матрица Н* является её решением, то задача Яги О11 также разрешгша и матрица II" является её решением.

Теорема 6. (О достаточных условиях существования решения задачи

Если Х(А, Ь) — 0,Ь((А,с) ф 0 (т.е. Ь(А,Ь,с) - несобственная задача ЛП 1-го рода), задача БюР'-1' (с параметром !) ф 0) разрешима и матрица [Н* — /¿*] является её решением, то задача БшИ^1 также разрешима и .матрица [Я* — /г*] является её решением.

Во второй главе, основываясь на методе Бройдена-Флетчера-Гольдфарба-Шенно, получен алгоритм минимизации целевых функции задачи оптимальной матричной коррекции данных несобственной задачи ЛП первого рода для всех перечисленннных в предыдущей главе постановок: Рн: Ф (£) = ¡¡Я||2, Я = (Ь - Ах) х+,

р1» -Ч: Ф (х) = ¡¡Я - А||2, [Я - к] = (Ь~А^-[хТ ^

хтх + 1

5РЯ: Ф (х) = ||Я||2, Я = Я (Х+(х) • (Ь - Ах)),

ЗР[Н -А]. Ф (г) = ||Я - ДЦ2, [я -Л] = [Я -к] ( Х+

(Ь - Ах)

Би>Рн: Ф (х) = ЦИ; о Я||2, Я = Я (П"1^) ■ (X (х) ГГ1(И>)) + - (Ъ - Ас)),

SwPW -Ч: Ф(®) = ||[W го]°[H -h]f, [H —h] — [Я —h] (n-'flVV го])-

ir4[VV го]) -{b-Ax) ,

где x — x (x) = jî'f • • • .

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

В третьей главе в качастве примера рассмотрена задача средней размерности bgdbgl из системы netlib. Левая часть данной задачи представляет собой матрицу размером 348 х 407, включающую 1485 ненулевых элементов. Так же в задаче имеются дополнительные верхние ограничения на х. При представлении данной задачи в каноническом виде с учетом дополнительных верхних ограничений на аргумент, задача имеет размерность 393 x G74.

Так же, в качастве примера, рассмотрена задача средней mondou2 из хранилища несобственных задач линейного программирования netlib. Левая часть данной задачи представляет собой матрицу размером 312 х 604, включающую 1G23 ненулевых элементов.

Используемый для матричной коррекции алгоритм был реализован в системе MATLAB 7.9 для компьютера с процессором Intel Core i3 М370, тактовой -частотой 2,4 ГГц, оперативной памятью 3 Гб. Для указанных задач были найдены матрица коррекции, значение соответствующего ей аргумента и целевой функции. Основные результаты матричной коррекции описанных выше задач, рассмотренных во всех постановках, прере-численных в первой главе, представлены в таблице 1. Z - решаемая задача матричной коррекции, начальное приближение для которой генерировалось по правилу: 6 R", х° = — Sx Vî 6 1.2,... п. При этом для задач структурной коррекции корректировались только ненулевые элементы. Для задач структурной взвешенной коррекции вес элемента матрицы коррекции определялся как квадрат обратного значения соответствующего элемента расширенной матрицы ограничений. Параметр сходимости для всех примеров s — le — 8. Т - время решения задачи в секундах. It - количество выполненных алгоритмом Бройдена-Флстчсра-Гольдфарба-Шешю итераций. ||fi|] - евклидова норма полученной матрицы коррекции.

Таблица 1. Результаты вычислительных экспериментов

ъ Эх 1С Т.с №11

Ь8(1Ь81 Р" 16 860 1741,026 0,03004226

bgdbgl Р1" 16 863 1831,044 0,03007555

Ьй(1Ьё1 БР" 1 50000 54943,508 6,35600584

1 50000 55034,749 5,93852587

БиР" 1 34389 40772,617 6,12242995

Ьесад Бп-Р'-" ->ч 1 3277 4005.330 122.82760499

гпоп(1ои2 Р" 104 99 188,352 0,01388127

гаоп(1ои2 Р-" -''1 104 98 172,147 0,01396059

нюп(1оц2 БРН ю4 240 238,166 1,41423658

топс1оц2 БРШ ю4 242 235,778 1,41423658

топс1он2 Би'Р" ю4 240 313,639 1,41423658

топ<1ои2 БюР^ ю4 245 245,485 1147,79139297

В заключении приведены основные результаты:

1. Теоретически обосновано достаточное условие существования решения задачи матричной кор!>екцш) несобственной задачи линейного программирования 1-го рода, выражающееся в существовании решения задачи матричной коррекции допустимой области указанной задачи. Рассматриваются следующие разновидности матричной коррекции задач ЛП:

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

- со структурными ограничениями по минимуму евклидовой нормы;

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

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

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

- алгоритмический учет неотрицательности части переменных;

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

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

- применение расчетной схемы Бройдена-Флетчера-Гольдфарба-

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

3. В результате тестирования на несобственных задачах линейного программирования средней размерности из репозитория netlib/lp/iiifeas показана работоспособность полученного алгоритма.

Основное содержание диссертационной работы изложено в следующих публикациях:

1. Ерохип В.И., Красников A.C., Хвостов М.Н. Минимальные по евклидовой норме матричные коррекции задач линейного программирования // Автоматика и Телемеханика. 2012. №2. С. 11-24. - 0,88 п.л. (авторский вклад - 33%).

2. Ерохип В.И., Красников А. С., Хвостов М.Н. О достаточных условиях разрешимости задач линейного программирования при матричной коррекции их ограничений // Труды Института математики и механики. 2013. Т. 19. №2. С. 144-156. — 0,81 п.л. (авторский вклад — 33%).

3. Ерохин В.И., Красников A.C., Хвостов М.Н. Квазиныото-иовские алгоритмы матричной коррекции несобственных задач линейного программирования с произвольным множеством корректируемых коэффициентов // Известия Санкт-Петербургского государственного технологического института (технического университета). 2014. №23. С. 87-92. - 0,75 п.л. (авторский вклад — 33%).

4. Хвостов М.Н. О достаточных условиях разрешимости несобственных задач ЛП 1-го рода после матричной коррекции их допустимой области по минимуму взвешенной евклидовой нормы с учетом структурных ограничений // Вестник Воронежского государственного университета. Серия: Физика. Математика. 2015. №2. С. 150-167. - 1,06 п.л. (авторский вклад-100%).

5. Ерохин В.И.. Красников A.C., Хвостов M.II. Минимальное матричное решение обратной задачи линейного программирования с использованием векторизации // Информационные и коммуникационные

технологии в образовании. Сборник материалов X Международной научно-практической конференции в 2-х томах. Т. 2. Борисоглебск: ГОУ ВПО БГПИ, 2009. С. 207-211. (авторский вклад - 33%).

6. Ерсхин В.И., Хвостов М.Н. Достаточные условия разрешимости несобственных задач линейного программирования после матричной коррекции их допустимой области // Материалы научно-практической конференции, посвященной 184-й годовщине образования СПбГТИ(ТУ). 2012. С 169-170. (авторский вклад - 50%).

7. Ерохин В.И., Красников A.C.. Хвостов М.Н. Коррекция несобственных задач линейного программирования с разреженными матрицами коэффициентов // Материалы научной конференции, посвященной 185-й годовщине образования СПбГТИ(ТУ). 2013. С 264-265. (авторский вклад - 33%).

8. Ерохин В.И., Красников A.C.. Хвостов М.Н. О разрешимости задачи линейного программирования при матричной коррекции ее допустимой области // VII Московская международная конференция по исследованию операций (ORM2013): Москва, 15 - 19 октября 2013 г.: Труды: Том 2 - М.: МАКС Пресс, 2013. С. 37-39. (авторский вклад -33%).

9. Хвостов М.Н. Применение штрафной функции при решении задачи структурной матричной коррекции несобственной задачи линейного программирования первого рода // Математические чтения РГСУ. Сборник материалов XXIII математической пшолы-ссмииара (28 января - 1 февраля 2014 года). - М.: Издательство РГСУ, 2015. С. 174 - 177. (авторский вклад - 100%).

10. Ерохин В.И., Красников A.C., Хвостов М.Н. Квазиныотоповский алгоритм структурной матричной коррекции несобственных задач линейного программирования с разреженными матрицами коэффициентов // Объединенный фонд электронных ресурсов «Наука и образование». Свидетельство о регистрации электронного ресурса №19696. 21 ноября 2013 г. (государственный информационный фонд неопубликованных документов ФИГУ ЦИТИС №50201351112). (авторский вклад - 33%).

Хвостоп Михаил Николаевич Матричная коррекция несобственных задач линейного программирования со специальной структурой Подписано в печать 06.05.2015. Формат бумаги 60 х 84 Бумага офсетная. Уч.-нзд. л. 1. Усл.гтет.л. 1,25.

_Тираж 100 ш. Заказ _

♦Оператипгтая полиграфия» И.П. Паутин К).С. Сп. о регистрации ^31136041-1500023, выдало 25.05.2011 г. 3971С0, г. Борисоглебск, ул. Народная, 50/1.