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

• Автор: Хвостов, Михаил Николаевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Москва
• Количество страниц: 116 с. : ил.

Оглавление
Введение
1 Матричная коррекция несобственных задач линейного программирования по минимуму евклидовой нормы

1.1 Постановки задачи матричной коррекции

1.2 Достаточные условия разрешимости несобственных задач

ЛП 1-го рода после матричной коррекции их допустимой области без учета структурных ограничений

1.3 Постановка задачи структурной матричной коррекции

1.4 Достаточные условия разрешимости несобственных задач

ЛП 1-го рода после матричной коррекции их допустимой области с учетом структурных ограничений

1.5 Постановка задачи структурной взвешенной матричной коррекции

1.6 Достаточные условия разрешимости несобственных задач
ЛП 1-го рода после взвешенной матричной коррекции их допустимой области с учетом структурных ограничений
2 Построение эффективного алгоритма решения задач матричной коррекции несобственных задач линейного программирования первого рода
2.1 Квазиньтоновский алгоритм матричной коррекции несобственных задач линейного программирования первого рода .
2.2 Производные целевых функций задачи матричной коррекции
без учета структурных ограничений
2.3 Производные целевых функций задачи матричной коррекции
с учетом структурных ограничений

2.4 Производные целевых функций структурной взвешенной задачи матричной коррекции
2.5 Использование штрафа для адаптации алгоритма коррекции к задачам, постановка которых допускает наличие некорректируемых строк матрицы коэффициентов
3 Вычислительные эксперименты
3.1 Постановка и решение задачи bgdbgl
3.2 Постановка и решение задачи топс1ои
3.3 Анализ результатов вычислительных экспериментов
Заключение
Литература

Введение
Актуальность темы исследования. Линейные оптимизационные модели широко применяются в экономике и технике fll], [13j [14], [33], [411, |67], [79], [107], [109] - fill], [126], [130], ]158] - [160], задачах помехоустойчивого анализа экспериментальных данных, гарантирующего оценивания параметров [12], [123] - [125], [131], [179], [199], распознавания образов и классификации [15], |16], [39], [42], [63], [66], |68], |103] - [105], [127], [146], [147], [162], [163], [175], [180], [183], [187], [198]. В связи с высокой востребованностью в приложениях, фундаментальные свойства, эффективные методы и алгоритмы построения, анализа и применения рассматриваемых моделей являются объектом интенсивных исследований [34], [35], [371, [38], [70], [71]. Указанные модели представляют собой совокупность объектов двух классов: систем линейных алгебраических уравнений и задач линейного программирования, которые объединяет совместная математическая теория. Так, результаты, полученные для систем линейных алгебраических уравнений, имеют важное значение и для задач линейного программирования. Таким образом, для решения задач линейного программирования имеется достаточно мощный математический аппарат.
Однако на практике часто встречаются неразрешимые задачи линейного программирования. Основными причинами их возникновения являются погрешности (шум) в экспериментальных данных, ошибки округления, возникающие при вычислениях в арифметике с конечной разрядностью, а также нечеткость и противоречивость информации, использующейся при построении указанных моделей. Такие задачи принято называть противоречивыми или несобственными.
В связи с тем, что несобственная задача линейного программирования не позволяет получить содержательную информацию об исследуемом процессе или явлении непосредственно, возникает необходимость в ее уточнении, изменении, в результате чего должна быть получена собственная задача, в некотором смысле «близкая» к исходной. Т.е. возникает зада-

Таким образом, в силу леммы 1.2.3,
|и>г| ^ 1Ы1 • llv.ll V* € 1п(ж*), Эг е 1.1(2:*)\ujvtl < ||мг|| • ||иг||
откуда, в свою очередь, /г Е 1ч(ж*)
|(6 — Ах*)г > |(Аг),| 1(5-Аж*)г[^ |(Аг),|
\иг|2 ^ ||м(|| • ||г>г|| ' ||мг|| |Ы|
причем в приведенной цепочке неравенств обязательно присутствуют строгие неравенства.
Следовательно, в силу (1.29),
IIя! =

(6- Аж*)2 ^ геЧ*') 1|Иг|

(6- Ах*)
у- (Лг)г2 у-
^ Ни II2 + ^ Нм II
гЄЬЦж*) 11 г'1 ,еТ.„Ґ,*їі |Т.Л,<Ч II НІ
гбЬ2(а,*)иЬз(а,*)
Рассмотрим
Я7,г = Н(Х+(х* + 72) • (Ъ - Аж* - уАг)).
Очевидно, что Яг7 - допустимое решение задачи ЯР, поскольку (ж* + уг) £ X (А + Яг,7, 6). Кроме того, в силу (1.3) и (1.22)
|(6 - Аж* - ^Аг)г
II (#г,7)і* II =
з (ж* +7^,Ягт*)|| ’
причем
||(ЯЪ7)г*|| = ° У7 ПРИ * І ЦЯ*).
4^11(^7.11 =
(12А1 VI є Ьі(х"), 0 Уг є Ь2(і*), |(Ь~_4р,.І VI є Ьз(х*)
Следовательно, для Я* — Ііш Яг,7 имеем
7—>+оо
ИЯ7ІІ = 4^117,11 =

Е Ш + Е
(6 - Аж*)
гЄЬЦж*)
геІЩгЕ*)

Таким образом,
|яд||<||я*ц.