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

• Автор: Жолудев, Анатолий Иванович
• Шифр специальности: 01.01.10
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Иркутск
• Количество страниц: 141 c. : ил

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

§ I. Матрицы с разветвленной блочной структурой

§ 2. Мультипликативное представление обратных

матриц
§ 3. Стратегия выбора главных элементов для матриц с разветвленной блочной структурой

§ 4. Алгоритм повторения для матриц разветвленной

блочной структуры, основанный на алгоритме

Хеллермана-Рарика

§ 5. Корректировка треугольно-мультипликативного

представления Форреста-Томлина

§ 6. Корректировка треугольно-мультипликативного

представления Бартелса-Голуба
Глава 2. Оценка точности процедур повторения
§ I. Вводные замечания
§ 2. Основные формулы треугольно-мультипликативного разложения. Матрица эквивалентного возмущения
§ 3. Оценки матриц ошибок одного шага алгоритма
разложения
§ 4. Оценки матрицы эквивалентного возмущения
§ 5. Оценка матрицы эквивалентного возмущения для
алгоритма Хеллермана-Рарика

§ 6. Оценка матрицы эквивалентного возмущения для
блочного алгоритма
§ 7. О сдерживании роста элементов в процессе
повторения
Глава 3. Программная реализация алгоритмов линейного программирования для задач с разветвленной
блочной структуры
§ I.Схема решения задач линейного программирования в ППП "Математическое программирование многомерных задач
§ 2. Представление данных блочной задачи линейного
программирования в пакете МАПР
§ 3. Представление обратной базисной матрицы и работа с ней
§ 4. Организация вычислений на этапе повторения
§ 5. Реализация алгоритма Форреста-Томлина
Приложение. Результаты численных экспериментов
Заключение
Литература

Задачи линейного программирования (ЛП) представляют собой один из важнейших классов задач оптимизации, встречающихся в приложениях. Особенно часто задачи ЛП возникают при исследовании экономических систем. Кроме того, многие методы нелинейного программирования при поиске направления спуска на каждой итерации предусматривают решение вспомогательной задачи ЛП. К задачам ЛП приводят, также, методы решения линейных динамических задач оптимизации, основанные на дискретизации.
Несмотря на высокую производительность современных ЭВМ, проблема построения эффективных алгоритмов для решения задач • ЛП большого размера остается актуальной и ей уделяется большое внимание в литературе.
Один из подходов к решению этой проблемы состоит в учете специфики строения матрицы ограничений задачи ЛП. Так, например, при исследовании иерархических систем управления в экономике, часто возникают задачи ЛП большого размера с разреженными матрицами разветвленной блочной структуры. Построению эффективных алгоритмов для решения таких задач, их исследованию и программной реализации и посвящена настоящая работа.
При решении задач ЛП на ЭВМ используются, как правило, различные варианты модифицированного симплекс-метода С1* 2, 3]
Рассмотрим задачу ЛП в канонической форме:
СгХ-~ тш
(0.1)
при условиях
(0.2)
X О
(0.3)

Перейдем теперь к обобщению стратегии выбора главных элементов на случай разветвленной блочной структуры матрицы
АШ,Ю.
Итак, пусть имеется некоторая квадратная неособенная матрица ALM.N1 , структура которой задана с помощью некоторого дерева, пронумерованного согласно алгоритму из § I настоящей главы. Пусть максимальный из номеров вершин равен а
Введем обозначения:
Для окончательных блоков, очевидно, имеем:
Nka=Nk и Ма
Перейдем к изложению стратегии выбора главных элементов. (Эту стратегию для краткости будем называть многоуровневой стратегией).
Шаг I. Полагаем к =<^-
Шаг 2. Рассмотрим поддерево с корнем в к -й вершине. Найдем на этом поддереве вершину с максимальным номером t . (Очевидно, блок AIM, № 7 окончательный). Полагаем 4 =t.
Шаг 3. Если 4 - к , идем на шаг 7.
Шаг 4. Строим мультипликаторы из столбцов А [ М, ffcg J,
выбирая индексы главных строк из множества , используя при этом какой-либо конкретный алгоритм выбора главных элементов, как и в случае одноуровневой стратегии. По мере построения мультипликаторов, иццексы ведущих столбцов вычеркиваем из множества lfcg , а индексы главных строк - из множества МРаботу на данном ша-