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

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

КОНДРАТЬЕВА Викторин Александровна

?ГБ ОД

2 л.'Дй 200

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

Специальность 05.13.17 —-теоретические основы информатики

АВТОРЕФЕРАТ

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

Москва 2000

Работа выполнена на кафедре информатики и дискретной математики Московского педагогического государственного университета.

Научный руководитель:

доктор физико-математических наук, профессор ГОРЕЛИК В.А.

Официальные оппоненты:

заслуженный деятель науки РФ, доктор физико-математических наук, профессор ЖУКОВСКИЙ В.И.

доктор физико-математических наук, профессор ВАСИЛЬЕВ Н.С.

Ведущая организация: Институт микропроцессорных вычислительных систем Российской Академии наук.

Защита состоится . ЛШ-.Р 2000 г. в 15.00 часов на засе-

дании Диссертационного Совета К 053.01.16 в Московском педагогичен ском государственном университете по адресу: 107140, Москва, ул. Краснопрудная, д. 14, математический факультет МПГУ, ауд. 301.

С диссертацией можно ознакомиться в библиотеке Московского педагогического государственного университета по адресу: 119435, Москва, ул. М. Пироговская, д. 1.

Автореферат разослан "Л" (?ЛДУ<Сб 2000 г.

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

Диссертационного Совета.

ЧИКАНЦЕВА Н.И.

¿из, а- £ з <

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

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

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

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

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

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

Задачи оптимизации, не обладающие по тем или иным причинам решением, получили название несобственных задач.

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

Представляется важным подчеркнуть следующие положения.

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

2. Противоречивые модели могут быть не менее, а в ряде случаев и более, богатыми по содержанию, чем совместные.

3. К математическому анализу противоречивых моделей вынуждает практика их конструктивного использования.

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

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

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

7. Для несобственных задач принятия решения необходима разработка эффективных методов коррекции.

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

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

Цели работы:

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

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

- анализ и получение аналитического выражения значения и решения (в случае его существования) задач коррекции.

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

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

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

В основу исследования положена следующая гипотеза: для задачи линейной оптимизации с пустым множеством допустимых планов можно

- сформулировать и решить задачу коррекции (аппроксимации) — задачу минимизации некоторой функции отклонения коэффициентов системы ограничений возмущенной задачи от коэффициентов системы ограничений исходной задачи;

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

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

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

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

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

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

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

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

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

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

Научная новизна. Проблема коррекции противоречивых систем линейных уравнений, а также аппроксимации несобственных задач выпуклого программирования формулировалась Тихоновым А.Н., а позднее исследовалась в работах таких современных авторов, как Еремин И.И., Ватолин A.A., Астафьев H.H. и др. При этом основным и наиболее изученным приемом коррекции несовместных систем ограничений задач линейного программирования явился способ вариации столбца свободных членов системы ограничений. В настоящее время работ, посвященных коррекции системы ограничений путем вариации всего массива исходных коэффициентов (матричной коррекции), существует немного. Кроме того, они не охватывают всего спектра вопросов, возникающих при постановке задачи матричной коррекции.

Отличие данной работы состоит в следующем:

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

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

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

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

- иллюстрируются случаи, когда задача аппроксимации не имеет решения;

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

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

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

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

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

Апробация работы. Результаты исследования были представлены на 2-й Московской международной конференции по исследованию операций (Москва, 17-20 ноября 1998 года), на научно-методических семинарах кафедры информатики и дискретной математики Mill У, кафедры информатики и прикладной математики МГЛУ.

Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения и списка литературы, содержащего 49 источников. Всего 106 страниц.

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

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

Первая глава (§1.1-§1.2) посвящена описанию несобственных задач линейного программирования (ЛП) и постановке задач их коррекции. В §1.1 содержится определение и классификация несобственных задач линейной оптимизации.

В §1.2 формализуется проблема коррекции задач ЛП с противоречивой системой ограничений. Рассматривается задача линейного программирования с противоречивой системой ограничений:

тах

М = {хе Ып|Лх = Ъ,х> о]= 0, т.е. несобственная задача 1-го рода по классификации, данной в §1.1.

С целью коррекции данной задачи ей ставится в соответствие задача

М{Н, А) = {хеГ \(Л + Н)х = Ъ + И,х>о\ где Я и А — матрица и вектор параметров, и формулируется двухкритери-альная проблема аппроксимации:

тт{ф(Я,А)|Л/(Я, А) * 0}; тах{(с,х)Ь е М{Н,К)\

в которой функция Ф(Я,А) — критерий качества аппроксимации.

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

критерия в разряд ограничений задачи минимизации критерия качества аппроксимации с пороговым значением Со: {с,х)>с0; 2) введение в рассмотрение лексикографической проблемы, представляющей собой две последовательно решаемые однокритериальные задачи, первая из которых заключается в минимизации критерия качества аппроксимации, вторая — в максимизации основного критерия (с,х) на множестве решений первой. Анализируется последовательность вспомогательных задач, которые необходимо исследовать для решения сформулированных проблем.

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

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

В §2.1 рассматривается задача вариации левой части противоречивой системы уравнений

тш{|Я||Мо(Я)*0}, (1)

где ||Я|| — норма матрицы, соответствующая евклидовой норме векторов, Ма(Н) = \хе Н"|(Л + Н)х - ь\. Доказывается теорема о значении и решении

^ , \ь,ьт\

этой задачи. Пусть Рь — матрица проектирования на вектор Ь, т.е. Рь = \—Л

(Ъ,Ь)

где [•,•] — произведение матриц, Е— единичная матрица.

Теорема 2.1. Всегда справедливо следующее равенство

где /¿ттС4 Т(Е-РЬ)Л) — минимальное собственное значение матрицы А\Е-РЬ)А.

Если нижняя грань достигается, т.е. задача (1) имеет решение, то это решение представимо в виде Н =

-\(Е - Рь)Ае',е"Т \, где е — единичный собственный вектор матрицы АТ(Е-Рь)А, соответствующий минимальному собственному значению Т(Е-Рь)А).

Формулируется ряд следствий и замечаний, в частности доказывается,

(М) .

что решением скорректированной системы является вектор х = 7—5——те .

(■АтЬ,е)

Далее доказывается теорема о необходимых и достаточных условиях существования решения задачи (1). Пусть 0~-Ат{Е-Рь)А.

Теорема 2.2. Задача (1) имеет решение тогда и только тогда, когда существует единичный собственный вектор е матрицы Д соответствующий минимальному собственному значению ф), такой что

В следующем параграфе (§2.2) исследуется задача параметризации и левой, и правой части системы линейных уравнений

тт||(-/2,Я)||2 \М0(Н,И) Ф 0(2) где М0(Н,И)={хе^\(А + Н)х = Ь + ь}.

Для нее получены достаточные условия существования решения.

Теорема 2.4. Если существует единичный собственный вектор матрицы ВТВ (В=(-Ь,А)), соответствующий /^\„(ВТВ), первая компонента которого отлична от нуля: <?о 0, то задача (2) разрешгша. Ее значение

а решение имеет вид (-/г*, Н*) = -

Ве ,е

, х

( * • *\г

£1

♦ > * >"Ч *

20 2о

где е

единичный собственный вектор матрицы соответствующий ргг;т(ВТВ), такой что ео & 0, а г = = ае , а*О.

Для задачи

тш||Я||2+И2|Мо(Я,А)^0}, (3)

эквивалентной задаче (2), получен следующий результат.

Теорема 2.5. £сяи нижняя грань выражения т£ --— не <)ос-

-сс<Л<-ко 1 + X1

тигается, то задача (3) не имеет решения, при этом

(Н,Ь,х):(А+Н)х=Ь+к* 11 11 11 1 ш,п

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

В третьей главе (§3.1—§3.2) осуществляется переход к задаче коррекции системы ограничений задачи ЛП, которая, помимо системы уравнений, содержит ограничение на знак вектора допустимых планов (§3.1), а также может содержать директивные ограничения, не подлежащие коррекции (§3.2).

В §3.1 рассматривается задача аппроксимации системы ограничений канонической задачи ЛП

тт|#||2|М(#)*0}, (4)

где М(Н) = е И" |(Л + Н)х = Ь, х > о).

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

Задача (4) сводится к двум задачам квадратичного программирования 51: 4 =шт|де,е)|е>0,||е||=1,(^гЬ,е)>0} и 52: йг =шт^02е,е)|е > 0,||е||= 1, {лтЪ,е^ < о|,

где ВЫ\Е-РЪ)А, Ог=АтА.

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

Теорема 3.1. Значение задачи (4) вычисляется по формуле

М ||#||2=тт{</„<*2}, (5)

причем нижняя грань в (5) достигается тогда и только тогда, когда < с!г и для решения первой задачи квадратичного программирования е* справедливо неравенство {АТЬ, е\ )>0.

Введем следующие обозначения:Ц (е, Л) = (Д е,е)~ \ (е, е) - Л2 АТЬ, е^, /-1,2 — функции Лагранжа, определенные для задач 51 и 52 соответственно; {<7} — множество квадратных подматриц (7 произвольной квадратной матрицы С?, полученных вычеркиванием строк и столбцов с одинаковыми номерами, включая саму матрицу (7;

' Е [АТЪ,ЬТА]

('АтЪ,АтЪ)

А;

Л'тш (О) — минимальное собственное значение матрицы (?, которому соответствует, по крайней мере, один неотрицательный собственный вектор е*,

удовлетворяющий условию graciL¡(e', Л'тт (£) )>0; = ш А^ (И,), /' = 0,2.

А® В)

Доказывается, что значения задач 51, 52 и исследуемой задачи (4) можно определить следующим образом:

=ттЙи(2}, ¿2 =тт{я^пД^), Ятш =тт{А«| ¿ = 0,1,2 ).

Справедлива следующая теорема.

Теорема 3.2. В общем случае значение задачи (4) выражается формулой тГ !|#| = .

(Н,х)М(Н)ф& 11 41 шт

Если АгЬ>0, то Ш^-ДК', если АТЬ<0, то

(Н,х):М(Н)*0] 11 4 т

м \т=Ш-

Если с1\<с1г и для решения е\ задачи 51 справедливо неравенство (А1 Ъ, е\ ^ > 0, то решение задачи (4) представимо в виде

Н' =\Е-Рь)Ле[,е\Т[ х

АтЬ,е\)

где е, может быть найден как единичный неотрицательный собственный вектор матрицы А или некоторой квадратной подматрицы матрицы А, полученной вычеркиванием строк и столбцов с одинаковыми номерами (в последнем случае дополненный нулевыми компонентами на соответствующих местах), соответствующий минимальному из собственных чисел этих матриц для которых существуют неотрииагпелъные собственные векторы удовлетворяющие неравенству 2расИ,\(еу, Я^|п)>0.

Далее в §3.2 исследуется задача коррекции системы линейных уравнений с фиксированными строками

шт||Я||2+И2|М(Я1,/г1)^0}, (6)

где М(Н) ,/г,) = [дсбК'!|(Л1 + Я,)х = ЬХ + А1х~Ь1\), и доказывается следующая теорема.

Теорема 3.3. Если ¿С1(В2В1) Ф 0, то значением задачи (6) является число МтЬ (£>), где1>={Е - Ъ\(ВгВ1гВ2)Й1ТВ1, В^-Ь.Ах), ВН^Аг)-

Если существует собственный вектор е матрицы Д соответствующий минимальному собственному значению, с отличной от нуля первой компонентой, то исходная задача (б) разрешима, при этом параметрические матрица и вектор П\ и /г* являются соответствующими компонентами матрицы (-/г,*,//,*) =— [^е* ,е* Решением возмущенной системы уравнений

С * * ^

• \ еп

является вектор х = -7-,...,— 1е0 е0 у

, где (е"0,е\,...,еп) — собственный вектор

матрицы Д соответствующий минимальному собственному значению, с отличной от нуля первой компонентой е'0 Ф 0.

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

х

II2

М -т—^—. Второй — сводится к исследованию соотношения, которое

может быть названо обобщенным отношением Рэлея

м |я||г = м

Результатов, полученных в §3.1, достаточно для решения проблемы коррекции несобственной задачи ЛП 1-го рода лексикографическим способом. Выводы §3.2 позволяют исследовать проблему коррекции несобственной задачи путем введения фиксированного ограничения (с,х)>с0 в задачу минимизации критерия качества аппроксимации противоречивой системы ограничений задачи ЛП.

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

В последней, четвертой, главе (§4.1—§4.2) исследуются два частных способа параметризации системы ограничений. В §4.1 рассматривается коррекция с помощью матрицы специального вида, ранг которой равен единице,

тах{(е,х)|х е М(А)}, ЩЛ) = {г е Ы (А1 - Яа°Т )х = А1 + Я6°, Агх = Ъ1 ,х > о}

где ДеИ*, А1 — матрица размерности sx.fi, А2 —• параметрически независимая матрица размерности (т-й)хп, б'еН*, Ь2ёЯС"~\ а°еК", и 0<5</я<лг — це-

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

А]х-Ьх

Гиперболическое преобразование Нр(х)=—?-еЫ* описывает

а0 х + Ь°

множество Л = ¡Я е Н/|М(Л) поскольку Нр(х) есть параметр Л, соответствующий элементу х таким образом, что М(Л)±0, т.е. является допустимым

параметром. Обозначим = |х е Ь а0 х + Ьа >о|, I" = € £

айТх + Ь0 <01

Тогда справедлива следующая теорема.

Теорема 4.1. Множество допустимых для задачи (7) параметров есть объединение множеств Лр(1+) и Нр(Ь~): Л = Ир (Х+ ) и Нр (17 ).

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

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

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

В работе рассмотрены примеры, иллюстрирующие некоторые понятия и определения.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

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

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

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

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

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

Основное содержание диссертации отражено в работах:

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

2. Кондратьева В. A. Hyperbolic transformations in solution of LP problem with empty set. // Тезисы докладов 2-й международной конференции по исследованию операций. М.: ВЦ РАН, 1998. С. 17.

3. Кондратьева В.А. Использование гиперболических преобразований для решения задачи линейного программирования с пустым множеством допустимых планов. // Научные труды Московского педагогического государственного университета. Серия: Естественные науки. М.: Прометей, 1999. С. 8-9.

ВВЕДЕНИЕ.

ГЛАВА 1. Несобственные задачи линейного программирования с противоречивой системой ограничений.

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

§1.2. Постановки задач коррекции несобственной задачи ЛП.

ГЛАВА 2. Многопараметрическая аппроксимация противоречивой системы линейных уравнений.

§2.1. Параметризация матрицы системы линейных уравнений.

§2.2. Коррекция матрицы системы линейных уравнений и столбца свободных членов.

ГЛАВА 3. Устранение несовместности системы ограничений в задаче ЛП.

§3.1. Коррекция системы ограничений канонической задачи линейного программирования.

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

ГЛАВА 4. Некоторые частные способы параметризации несобственной задачи ЛП.

§4.1. Параметризация с помощью матрицы, ранг которой равен единице.

§4.2. Многошаговая коррекция задачи ЛП с противоречивой системой ограничений.

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

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

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

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

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

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

Задачи оптимизации, не обладающие по тем или иным причинам решением, получили название несобственных задач.

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

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

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

- противоречивость, несогласованность ограничений и целей;

- неустойчивость модели, т.е. эволюцию и моделируемого объекта, и наших знаний о нем.

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

В математике изучение и использование противоречивых моделей имеет давнюю историю. Так, К. Гаусс при разработке метода наименьших квадратов исследовал переопределенную несовместную систему линейных уравнений [25]. Несовместные системы линейных неравенств в связи с задачами проектирования механических систем рассматривал П.Л. Чебышев [48]. Позднее системы противоречивых неравенств исследовались такими учеными, как Еремин И.И., Ватолин A.A., Черников С.Н. и др. [7], [8], [15]—[20], [24], [34]—[38], [49].

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

Итак, представляется важным подчеркнуть следующие положения.

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

2. Противоречивые модели могут быть не менее, а в ряде случаев и более богатыми по содержанию, чем совместные.

3. К математическому анализу противоречивых моделей вынуждает практика их конструктивного использования.

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

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

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

7. Для несобственных задач принятия решения необходима разработка эффективных методов коррекции.

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

Для коррекции несобственных моделей предлагается использовать метод параметрического программирования, который заключается в погружении исходной задачи оптимизации max{/(x)|x е м], (*) где / — критерий эффективности, М — множество допустимых стратегий, в класс задач оптимизации max{/(x,z)\x е M(z),z е z}, (**) где и критерий эффективности, и множество допустимых стратегий зависят от вектора параметров zeZ.

Предметом исследования параметрического программирования является нахождение в пространстве параметров Z определенных подмножеств, для элементов которых из задачи (**) получают подклассы задач оптимизации с определенными заданными свойствами. Важным примером такого подмножества является, так называемое, допустимое множество параметров (z е Z\M(z) Ф 0}, которое состоит из таких векторов zeZ, что

M{z) не пусто [31]. Именно это множество параметров будет рассматриваться при решении задач коррекции несобственных задач.

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

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

Цели работы:

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

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

- анализ и получение аналитического выражения значения и решения (в случае его существования) задач коррекции.

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

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

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

В основу исследования положена следующая гипотеза: для задачи линейной оптимизации с пустым множеством допустимых планов можно

- сформулировать и решить задачу коррекции (аппроксимации) — задачу минимизации некоторой функции отклонения коэффициентов системы ограничений возмущенной задачи от коэффициентов системы ограничений исходной задачи;

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

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

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

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

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

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

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

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

Методологическую основу работы составляют современные методы математического программирования, теории исследования операций [4]-[6], [13], [26], [32], [33], [39], [42], многокритериальной оптимизации [21]—[23], параметрического программирования [3], [9]-[11], [14], [30], [31], [36], линейной алгебры [2], [43], [47] и математического анализа [41].

Научная новизна. Проблема коррекции противоречивых систем линейных уравнений, а также аппроксимации несобственных задач выпуклого программирования формулировалась Тихоновым А.Н. [44]-[46], а позднее исследовалась в работах таких современных авторов, как Еремин И.И., Ватолин A.A., Астафьев H.H. [1] и др. При этом основным и наиболее изученным приемом коррекции несовместных систем ограничений задач линейного программирования явился способ вариации столбца свободных членов системы ограничений. В настоящее время работ, посвященных коррекции системы ограничений путем вариации всего массива исходных коэффициентов (матричной коррекции), существует немного. Кроме того, они не охватывают всего спектра вопросов, возникающих при постановке задачи матричной коррекции.

Отличие данной работы состоит в следующем:

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

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

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

- иллюстрируются случаи, когда задача аппроксимации не имеет решения;

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

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

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

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

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

Апробация работы. Результаты исследования были представлены на 2-й Московской международной конференции по исследованию операций (Москва, 17-20 ноября 1998 года), на научно-методических семинарах кафедры информатики и дискретной математики МПГУ, кафедры информатики и прикладной математики МГПУ.

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

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

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

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

В третьей главе (§3.1—§3.2) осуществляется переход к задаче коррекции системы ограничений задачи ЛП, которая, помимо системы уравнений, содержит ограничение на знак вектора допустимых планов (§3.1), а также может содержать директивные ограничения, не подлежащие коррекции (§3.2).

В последней, четвертой, главе (§4.1—§4.2) исследуются два частных способа параметризации системы ограничений. Рассматривается коррекция с помощью матрицы, ранг которой равен единице, и изучается связь между указанным методом параметризации и основным способом, изложенным в главах 2 и 3 (§4.1). Кроме того, предлагается один из методов последовательной коррекции системы ограничений задачи ЛП (§4.2).

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

Основное содержание диссертации отражено в работах: [12], [27],

28].

ЗАКЛЮЧЕНИЕ

Подведем некоторые итоги исследования.

В работе рассмотрена задача линейного программирования с противоречивой системой ограничений, т.е. несобственная задача 1-го рода по классификации, данной в § 1.1.

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

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

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

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

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

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

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

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

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

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

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

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

1. Беллман Р. Введение в теорию матриц. М.: Наука, 1976. Булатов В.П. Методы погружения в задачах оптимизации. Новосибирск: Наука, 1977.

2. Васильев Н.С. Об одном классе динамических задач распределения ресурсов. // Неантагонистические дифференциальные игры и их приложения. М., 1986. С. 114-119.

3. Васильев Ф.П. Методы решения экстремальных задач. М.: Наука, 1981.

4. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980.

5. Ватолин А.А. Об обобщенном решении несовместных систем линейных алгебраических уравнений. II Методы мат. программирования и их прогр. обеспечение. Тез. докл. научно-техн. конф. Свердловск, 1981. С. 33-34.

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

7. Вильяме Н.Н. Параметрическое программирование в экономике. М.: Статистика, 1976.

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

9. Горелик В.А., Ушаков И.А. Исследование операций. М.: Машиностроение, 1986.

10. Гуддат Ю., Вендлер К., Вернсдорф Р. О решении задач векторной оптимизации с помощью параметрического программирования. II Humboldt Universität zu Berlin. Section mathematik Seminarberichte, 1981. № 37. P. 11-24. Пер. с нем.

11. Еремин H.H. Двойственность для несобственных задач линейного и выпуклого программирования. Свердловск: УНЦ АН СССР, 1981.

12. Еремин И.И. О задачах выпуклого программирования с противоречивыми ограничениями. //Кибернетика, 1971, №4. С. 124-129.

13. Еремин И.И. Непрерывная аппроксимация несобственных задач линейного и выпуклого программирования. II Классификация и оптимизация в задачах управления. Свердловск: УНЦ АН СССР, 1981. С. 3-14.

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

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

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

17. Жуковский В.И., Молоствов B.C. Многокритериальное принятие решений в условиях неопредленности.М.: МНИИПУ, 1988.

18. Жуковский В.П., Салуквадзе М.Е. Метод решения одного класса многокритериальных линейных задач. Тбилиси: ИСУ АН Грузии, 1990.

19. Жуковский В.И., Салуквадзе М.Е. Многокритериальные задачи управления в условиях неопределенности. Тбилиси: Мецниереба, 1991.

20. Исследования по несобственным задачам оптимизации: Сб. науч. тр. / Под ред. И.И. Еремина. Свердловск: УНЦ АН СССР, 1988.

21. Карл Фридрих Гаусс. I Под ред. И.М. Виноградова. М.: АН СССР, 1956.

22. Карманов В.Г. Математическое программирование. М.: Наука, 1980.

23. Кондратьева В. A. Hyperbolic transformations in solution of LP problem with empty set. II Тезисы докладов 2-й международной конференции по исследованию операций. М.: ВЦ РАН, 1998. С. 17.

24. Курицкий Б. Поиск оптимальных решений средствами Excel 7.0. Спб.: BHV. Санкт-Петербург, 1997.

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

26. Ломатч К. Понятия и результаты параметрического программирования. // Способы решения и анализа задач линейной оптимизации векторов. Stuttgart, Basel: Birkhauser, 1979. Пер. с нем. Дробенок Л.А. Минск, 1985.

27. Мину М. Математическое программирование: теория и алгоритмы. М.: Наука, 1990.

28. Миронов A.A. Цурков В.И. Минимакс в транспортных задачах. М.: Наука, 1997.

29. Несобственные модели математического программирования: Сб. ст. / Под ред. И.И. Еремина. Свердловск. Ин-т матем. и механ. УНЦ АН СССР, 1980.

30. Несобственные задачи оптимизации/ Под ред. И.И. Еремина. Свердловск. Ин-т матем. и механ. УНЦ АН СССР, 1982.

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

32. Противоречивые модели оптимизации: Сб. науч. тр. / Под ред. И.И. Еремина. Свердловск. УНЦ АН СССР, 1987.

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

34. Пшеничный Б.Н. Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука, 1975.

35. Решетников В.Н., Сотников А.Н. Информатика — что это? М.: Радио и связь, 1989.

36. Рокафеллар Р.Т. Выпуклый анализ. М.: Мир, 1973.

37. Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977.

38. Стренг Г. Линейная алгебра и ее применения. М.: Мир, 1980.

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

40. Тихонов А.Н. О некорректных задачах оптимального планирования. II ЖВМиМФ, 1966, 6, №1. С. 81-89.

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

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