Содержание к диссертации
Введение
Глава I. Мультипликативные алгоритмы для задач линейного программирования с матрицами разветвленной блочной структуры ..
1. Матрицы с разветвленной блочной структурой... 18
2. Мультипликативное представление обратных матриц 24
3. Стратегия выбора главных элементов для матриц с разветвленной блочной структурой 31
4. Алгоритм повторения для матриц разветвленной блочной структуры, основанный на алгоритме Хеллермана-Рарика. 60
5. Корректировка треугольно-мультипликативного представления Форреста-Томлина 65
6. Корректировка треугольно-мультипликативного представления Бартелса-Голуба
Глава 2. Оценка точности процедур повторения 76
1. Вводные замечания. 76
2. Основные формулы треугольно-мультипликативного разложения. Матрица эквивалентного возмущения
3. Оценки матриц ошибок одного шага алгоритмаразложения 80
4. Оценки матрицы эквивалентного возмущения 87
5. Оценка матрицы эквивалентного возмущения дляалгоритма Хеллермана-Рарика
6. Оценка матрицы эквивалентного возмущения для блочного алгоритма 92
7. О сдерживании роста элементов в процессе повторения 99
Глава 3. Программная реализация алгоритмов линейвого программирования для задач с разветвленной блочной структуры 103
1.Схема решения задач линейного программирования в Математическое программирование много мерных задач 103
2. Представление данных блочной задачи линейного программирования в пакете МАПР 107
3. Представление обратной базисной матрицы и работа с ней 113
4. Организация вычислений на этапе повторения... 119
5. Реализация алгоритма Форреста-Томлина 122
Приложение. Результаты численных экспериментов 127
Заключение 133
Литература 135
- Стратегия выбора главных элементов для матриц с разветвленной блочной структурой
- Корректировка треугольно-мультипликативного представления Форреста-Томлина
- Основные формулы треугольно-мультипликативного разложения. Матрица эквивалентного возмущения
- Представление данных блочной задачи линейного программирования в пакете МАПР
Введение к работе
Задачи линейного программирования (ЛП) представляют собой один из важнейших классов задач оптимизации, встречающихся в приложениях. Особенно часто задачи ЛП возникают при исследовании экономических систем. Кроме того, многие методы нелинейного программирования при поиске направления спуска на каждой итерации предусматривают решение вспомогательной задачи ЛП. К задачам ЛП приводят, также, методы решения линейных динамических задач оптимизации, основанные на дискретизации.
Несмотря на высокую производительность современных ЭВМ, проблема построения эффективных алгоритмов для решения задач • ЛП большого размера остается актуальной и ей уделяется большое внимание в литературе.
Один из подходов к решению этой проблемы состоит в учете специфики строения матрицы ограничений задачи ЛП. Так, например, при исследовании иерархических систем управления в экономике, часто возникают задачи ЛП большого размера с разреженными матрицами разветвленной блочной структуры. Построению эффективных алгоритмов для решения таких задач, их исследованию и программной реализации и посвящена настоящая работа.
Таким образом, для повышения эффективности мультипликативного алгоритма важнейшее значение имеет уменьшение заполненности мультипликативного представления ненулевыми элементами, т.к. от их числа непосредственно зависит объем памяти, необходимой для хранения мультипликаторов, объем вычислений и, как следствие, скорость работы алгоритма и точность получаемого решения. Степень заполненности мультипликаторов определяется, в основном, выбором главных элементов в процессе построения мультипликативного представления.
В [1Ь] были изложены алгоритмы выбора главного элемента, обеспечивающие минимальное локальное заполнение ненулевыми элементами на каждом шаге (то есть, при построении очередного М -мультипликатора или пары LU - мультипликаторов). Однако, эти алгоритмы требуют больших вычислительных затрат и, кроме того, минимальность локального заполнения не гарантирует общей минимальности получаемого мультипликативного представления.
Там же рассматриваются алгоритмы с априорным упорядочением строк и столбцов. Недостаток этих алгоритмов состоит в том, что они не учитывают роста заполненности в процессе разложения и дают, вообще говоря, худшие результаты (в смысле числа нену - 10 левых элементов), чем алгоритмы локальной минимизации.
Алгоритмы выбора главного элемента, учитывающие разреженность базисной матрицы, рассматривались, также, в работах С10, II, 16, 17, 18] и др.
Алгоритм, предложенный в [10J , на практике дает мультипликативное представление с числом нетривиальных элементов не более чем вдвое превышающим число ненулевых элементов в базисной матрице.
Очень интересен, с точки зрения минимальности получаемого мультипликативного представления, алгоритм Хеллермана-Рарика [16J . Этот алгоритм допускает преобразование только некоторой, как правило, небольшой части столбцов, и, следовательно, новые ненулевые элементы возникают только в этой части столбцов.
Важным достоинством мультипликативных алгоритмов является тот факт, что при переходе к смежному базису совсем не обязательно заново получать мультипликативное разложение для новой базисной матрицы, т.к. его можно получить из старого разложения с помощью достаточно простой операции корректировки [15, 12, ІЗ, 14] .
Другой подход к использованию разреженности матрицы условий задач ЛЇЇ связан с выявлением и учетом их регулярной структуры.
Большой интерес в этом плане представляют матрицы блочно-диагональной структуры с окаймлением, т.к. задачи с матрицами такого сорта часто встречаются в приложениях: задачи распределения ресурсов в иерархической системе, задачи планирования на нескольких уровнях и другие.
Другой подход к решению задач ЛП с матрицами блочно-диаго-нальной структуры с окаймлением был развит в работах [23-35] . Основная идея этого подхода состоит в следующем. Для решения задачи применяется алгоритм симплекс-метода обычного вида, но при решении систем (0.4) и (0.6), а также при пересчете базисной информации используется специфика строения базисной матрицы. Этот подход представляется более эффективным в вычислительном отношении, чем метод Данцига-Вулфа ([36]).
Важное достоинство этого подхода состоит в том, что его можно эффективно применять к задачам с матрицами ограничений разветвленной блочной структуры, т.е. этот подход позволяет учитывать многократную вложенность блоков и наличие окаймлений раз - 12 личных видов (вертикальных, горизонтальных и двухсторонних).
Представляется перспективным сочетание в алгоритмах симплекс-метода учета регулярной структуры матрицы ограничений и ее разреженности в целом на основе использования мультипликативных форм представления обратных базисных матриц.
Малковым и Ахметовым в работе С 37 J был предложен мультипликативный алгоритм для задач ЛП, матрица ограничений которых имеет вид (0.10). Этот алгоритм предусматривает решение последовательности усеченных задач, составленных из переменных какого-либо блока и базисных переменных других блоков, занимающих позиции базиса, соответствующие связующим строкам. В этом алгоритме хранению подлежит не вся обратная матрица, а лишь ее незначительная часть (речь идет, разумеется, о мультипликативном представлении). Соответственно сокращается и трудоемкость работы с ней. Этот алгоритм, однако, неприменим в случае наличия двухстороннего окаймления и не учитывает многократной вложенности блоков.
Настоящая работа посвящена разработке мультипликативных алгоритмов симплекс-метода, сочетающих учет разреженности матрицы условий задачи ЛП в целом и наложенной на нее разветвленной блочной структуры.
В первой главе строится глобальная стратегия выбора главных элементов при построении мультипликативного представления для базисных матриц разветвленной блочной структуры. Основная идея этой стратегии заключается в том, что главные элементы выбираются сначала в самых внутренних блоках, затем в объемлющих их блоках и т.д. Доказывается, что мультипликаторы, построенные с помощью алгоритмов, основанных на данной стратегии,
- ІЗ имеют структуру заполнения, по большей части, соответствующую структуре породивших их столбцов.
Далее, на основе этой стратегии строится алгоритм, использующий идеи алгоритма Хеллермана-Рарика.
В конце первой главы рассматриваются операции корректировки разложения вида (0.9), выполняемые по методам Форреста-Том-лина [12] и Бартелса-Голуба [13] , применительно к задачам с матрицами ограничений разветвленной блочной структуры. Доказывается, что новые мультипликаторы, получаемые в результате операций корректировки имеют, по большей части, блочную структуру заполнения ненулевыми элементами.
Полученные результаты обосновывают эффективность алгоритмов ЛП, построенных на основе предлагаемой стратегии, в смысле малой заполненности мультипликативного представления ненулевыми элементами.
Вторая глава посвящена исследованию вопросов точности алгоритмов построения мультипликативного представления. В основе мультипликативных алгоритмов лежат преобразования, поэтому эти алгоритмы не обладают естественной вычислительной устойчивостью ( [38J) . Это обстоятельство обуславливает важнейшую роль борьбы с погрешностями вычислений в процедурах построения мультипликативного представления.
Здесь проводится обратный анализ ошибок различных алгоритмов выбора главного элемента в предположении, что используется машинная арифметика с плавающей запятой.
В конце второй главы рассматривается вариант частичного выбора главного элемента в строке, который не выводит за рамки блочной стратегии, поэтому при его применении рост числа ненулевых элементов ограничен наложенной на матрицу структурой.
Третья глава посвящена численной реализации мультипликативных алгоритмов симплекс - метода, использующих предлагаемую блочную стратегию.
Эта стратегия реализована в функциональном наполнении пакета прикладных программ "Математическое программирование многомерных задач" (МАПР), разработанном в Иркутском ВЦ СО АН СССР (регистрационный номер ГОСІАП П00667І) [41J .
Здесь описывается общая функциональная схема решения задачи ЛП в пакете МАПР, излагаются способы представления информации и рассматриваются вопросы организации вычислений. Наиболее подробно здесь освещаются вопросы, связанные с эффективным использованием внешней памяти при решении блочных задач ЛП и с обработкой информации о структуре матрицы ограничений.
Кроме того, здесь предлагается способ реализации алгоритма Форреста-Томлина для случая, когда мультипликативное представление (0.9) хранится в компактном виде во внешней памяти. Этот способ требует минимального изменения информации при переходе к смежному базису.
В приложении приводятся результаты численных экспериментов, проводившихся в рамках пакета МАПР. При проведении экспериментов применялась следующая методика. С помощью генератора случайных чисел формировалась матрица условий задачи ЛП заданных размеров, с заданной структурой и процентом заполнения. Затем строилась задача ЛЇЇ с известным оптимальным решением. Эта задача решалась с помощью программ пакета МАПР, учитывающих структуру матрицы и не учитывающих ее. В процессе решения задачи измерялись такие показатели: среднее время повторения, время решения задачи, число ненулевых элементов в мультипликаторах, число арифметических операций с элементами мультипликаторов и норма ошибки в полученном оптимальном решении.
Результаты этих экспериментов эффективность предлагаемой стратегии использования разветвленной блочной структуры матрицы ограничений задачи ЛП.
В заключении приводятся основные результаты настоящей работы.
В библиографию включены работы, имеющие непосредственное отношение к настоящей диссертации, поэтому ее нельзя считать исчерпывающей по рассматриваемому кругу вопросов.
Стратегия выбора главных элементов для матриц с разветвленной блочной структурой
Этот метод предусматривает сведение исходной задачи ЛП к задаче с числом строк матрицы ограничений,равным т0 1 (в другом варианте т0+р ) и с большим числом столбцов, причем ведущий столбец генерируется в результате решения серии задач ЛП, каждая из которых соответствует одному диагональному блоку.
Другой подход к решению задач ЛП с матрицами блочно-диаго-нальной структуры с окаймлением был развит в работах [23-35] . Основная идея этого подхода состоит в следующем. Для решения задачи применяется алгоритм симплекс-метода обычного вида, но при решении систем (0.4) и (0.6), а также при пересчете базисной информации используется специфика строения базисной матрицы. Этот подход представляется более эффективным в вычислительном отношении, чем метод Данцига-Вулфа ([36]).
Важное достоинство этого подхода состоит в том, что его можно эффективно применять к задачам с матрицами ограничений разветвленной блочной структуры, т.е. этот подход позволяет учитывать многократную вложенность блоков и наличие окаймлений различных видов (вертикальных, горизонтальных и двухсторонних).
Представляется перспективным сочетание в алгоритмах симплекс-метода учета регулярной структуры матрицы ограничений и ее разреженности в целом на основе использования мультипликативных форм представления обратных базисных матриц.
Малковым и Ахметовым в работе С 37 J был предложен мультипликативный алгоритм для задач ЛП, матрица ограничений которых имеет вид (0.10). Этот алгоритм предусматривает решение последовательности усеченных задач, составленных из переменных какого-либо блока и базисных переменных других блоков, занимающих позиции базиса, соответствующие связующим строкам. В этом алгоритме хранению подлежит не вся обратная матрица, а лишь ее незначительная часть (речь идет, разумеется, о мультипликативном представлении). Соответственно сокращается и трудоемкость работы с ней. Этот алгоритм, однако, неприменим в случае наличия двухстороннего окаймления и не учитывает многократной вложенности блоков.
Настоящая работа посвящена разработке мультипликативных алгоритмов симплекс-метода, сочетающих учет разреженности матрицы условий задачи ЛП в целом и наложенной на нее разветвленной блочной структуры.
В первой главе строится глобальная стратегия выбора главных элементов при построении мультипликативного представления для базисных матриц разветвленной блочной структуры. Основная идея этой стратегии заключается в том, что главные элементы выбираются сначала в самых внутренних блоках, затем в объемлющих их блоках и т.д. Доказывается, что мультипликаторы, построенные с помощью алгоритмов, основанных на данной стратегии, имеют структуру заполнения, по большей части, соответствующую структуре породивших их столбцов.
Далее, на основе этой стратегии строится алгоритм, использующий идеи алгоритма Хеллермана-Рарика. В конце первой главы рассматриваются операции корректировки разложения вида (0.9), выполняемые по методам Форреста-Том-лина [12] и Бартелса-Голуба [13] , применительно к задачам с матрицами ограничений разветвленной блочной структуры. Доказывается, что новые мультипликаторы, получаемые в результате операций корректировки имеют, по большей части, блочную структуру заполнения ненулевыми элементами. Полученные результаты обосновывают эффективность алгоритмов ЛП, построенных на основе предлагаемой стратегии, в смысле малой заполненности мультипликативного представления ненулевыми элементами. Вторая глава посвящена исследованию вопросов точности алгоритмов построения мультипликативного представления. В основе мультипликативных алгоритмов лежат неунитарные преобразования, поэтому эти алгоритмы не обладают естественной вычислительной устойчивостью ( [38J) . Это обстоятельство обуславливает важнейшую роль борьбы с погрешностями вычислений в процедурах построения мультипликативного представления. Здесь проводится обратный анализ ошибок различных алгоритмов выбора главного элемента в предположении, что используется машинная арифметика с плавающей запятой. Подобные исследования для алгоритма треугольного разложения проводились в работах [38, 39, 40] . Но, полученные в этих работах оценки погрешностей во-первых, не охватывают фазы мультипликативного разложения верхнетреугольной матрицы JJ , а,во-вторых, они сильно завышены, т.к. не учитывают реальной степени преобразуемости элементов базисной матрицы, хотя и носят апостериорный характер. В настоящей работе с помощью обратного анализа ошибок для всего процесса построения представления (0.9) построены оценки вида: где Yj - элементы матрицы эквивалентного возмущения; У.. -- число преобразований элемента базисной матрицы 2г-; в процессе разложения; СС: - максимальный модуль, которого дости-гает элемент Z/y в процессе преобразований; р и Z - соответственно основание системы счисления и разрядность мантиссы используемой машинной арифметики. Полученная оценка (0.11) гораздо ближе к практике вычислений, чем оценки из [38, 39, 40j . Далее величины fa; оцениваются сверху для различных алгоритмов и из (0.11) получаются верхние оценки погрешностей этих алгоритмов, которые показывают, что алгоритмы, основанные на предлагаемой в первой главе стратегии, точнее их общих аналогов.
Корректировка треугольно-мультипликативного представления Форреста-Томлина
Отметим еще одну особенность изложенной стратегии. На этапе I мы получаем р независимых друг от друга групп мультипликаторов (в том смысле, что мультипликаторы, построенные из столбцов одного блока,никак не влияют на столбцы других блоков). Это справедливо как для представления (1.2), так и для представления (1.8). Поэтому порядок просмотра блоков на этапе I не играет роли.
Заметим, что мультипликаторы к -й группы С к = 4, 2,-, р) преобразуют, при левом умножении на них матрицы д L М, /\TJ, только подматрицу: Таким образом, использование в алгоритмах повторения изложенной стратегии позволяет "локализовать" не только возникновение новых элементов (как это следует из доказанных утверждений), но и преобразования элементов матрицы в процессе повторения. Каждую группу мультипликаторов, построенных на этапе I, сопоставим соответствующей данному блоку вершине дерева, задающего иерархию, а группу мультипликаторов, построенных на этапе 2, сопоставим вершине с номером 0. Последнюю группу будем называть корневой. Нумерацию вершин дерева будем использовать также и для соответствующих групп мультипликаторов. Если некоторый вектор-столбец й, требуется умножить на представление (1.2) слева, построенное согласно одноуровневой стратегии, то его нужно последовательно умножить на группы мультипликаторов с номерами: р , р - 4, , 2- , {, О. А если требуется умножить вектор-строку с I 14J на представление (1.2) справа, то она умножается на группы мультипликаторов в обратном порядке. В случае представления (1.8), каждой вершине дерева ставится в соответствие две группы мультипликаторов (группа L -мультипликаторов и группа и - мультипликаторов). Если некоторый вектор-столбец умножается на представление (1.8) слева, то его нужно последовательно умножить на группы L - мультипликаторов с номерами р , р -d, ..., i,0 , а затем на группы U - мультипликаторов с номерами О, І, 2, --, Р При умножении вектор-строки на представление (1.8) справа, группы мультипликаторов просматриваются в обратном порядке. Свойство I. Если некоторый вектор-столбец OL I М] требуется умножить слева на представление (1.2), то его достаточно умножить только на /с -ю и корневую группы мультипликаторов ( к = 1,2, -,р) Свойство 2. Если некоторый вектор-столбец й такой, что а требуется умножить на все и - мультипликаторы представления (1.8) слева-то его достаточно умножить только на /с -ю и корневую группы L - мультипликаторов. Свойство 3. Если некоторую вектор-строку с [ /VJ , такую, что , требуется умножить на все U - мультипликаторы представления (1.8) справа, то ее достаточно умножить только на К -ю и корневую группы (/- мультипликаторов. Справедливость свойств I, 2 и 3 непосредственно следует из формул (1.5) и (1.6) и структуры главных столбцов мультипликаторов (см. рис. 3, 4, 5). Перейдем теперь к обобщению стратегии выбора главных элементов на случай разветвленной блочной структуры матрицы АШ,Ю. Итак, пусть имеется некоторая квадратная неособенная матрица А 1М, rlj , структура которой задана с помощью некоторого дерева, пронумерованного согласно алгоритму из I настоящей главы. Пусть максимальный из номеров вершин равен а. Введем обозначения: Для окончательных блоков, очевидно, имеем: Перейдем к изложению стратегии выбора главных элементов. (Эту стратегию для краткости будем называть многоуровневой стратегией). Шаг I. Полагаем k=fy Шаг 2. Рассмотрим поддерево с корнем в к -й вершине. Найдем на этом поддереве вершину с максимальным номером t. (Очевидно, блок A LM, Ml окончательный). Полагаем Шаг 3. Если 4 к , идем на шаг 7. Шаг 4. Строим мультипликаторы из столбцов А іМ, Hal, выбирая индексы главных строк из множества Мс , используя при этом какой-либо конкретный алгоритм выбора главных элементов, как и в случае одноуровневой стратегии. По мере построения мультипликаторов, индексы ведущих столбцов вычеркиваем из множества nfcg » & индексы главных строк - из множества М. cg. Работу на данном шаге заканчиваем при реализации любой из следующих трех ситуаций: а) все множество Hcg оказалось вычеркнутым; б) все множество Мcg оказалось вычеркнутым; в) все "кандидаты" на роль главного элемента недопустимо малы по абсолютной величине. В случае реализации ситуации б) идем на шаг 6, а при реализации ситуации а) или в) - на шаг 5. В случае реализации ситуации в) будем говорить, что при данных 4 и к реализовался неудачный исход. Шаг 5. Полагаем 6 = 4-4 и возвращаемся на шаг 3. Шаг 6. Полагаем 4 = Шаг 7. Строим мультипликаторы из столбцов A LM, IV agJt выбирая главные строки с индексами из множества Mcg применяя при этом какой-либо конкретный алгоритм выбора главных элементов. По мере построения мультипликаторов, индексы ведущих столбцов вычеркиваем из множества Ncg, а индексы главных строк - из множества М cg. Работу на данном шаге прекращаем при реализации любой из следующих трех ситуаций:
Основные формулы треугольно-мультипликативного разложения. Матрица эквивалентного возмущения
Рассмотрим случай, когда при работе с некоторым п -м блоком, где к Л 4 и h Є б (к,б) для столбцов реализовался неудачный исход, причем не все "кандидаты" на роль главного элемента, при этом, были равны нулю. Тогда оставшиеся связующие столбцы К -го блока могут быть преобразованы мультипликаторами, построенными из столбцов блоков к-і к -2 ,..., к - п +4 с индексами главных строк из множества пе$ и из столбцов АШ, Hal с индексами главных строк из множества М . Поэтому, в данном случае, U - муль типликаторы, построенные из столбцов с индекса ми главных строк из множества Мс9 могут содервкать нетривиаль ные элементы не только в строках с индексами из множества мки и MU, но и в тех строках множества М , которые были выбраны в качестве главных при построении мультипликаторов из столбцов Многоуровневая стратегия предусматривает группировку мультипликаторов по вершинам дерева, задающего иерархию блоков матрицы АШ, Ю. Исходя из структуры мультипликаторов, получаемых при использовании многоуровневой стратегии, можно обобщить свойства групп мультипликаторов, выявленные при рассмотрении одноуровневой стратегии (см. свойства I, 2, 3). Свойство 4. Если некоторый вектор-столбец й СМ] такой j что й. требуется умножить слева на пред ставление (1.2), то его достаточно умножить на группы мультипликаторов с номерами из У (к) и &(к,0) в порядке убывания номеров групп ( к = О, І,..., (], Л Свойство 5, Если некоторый вектор-столбец а С Ml такой, что а , требуется умножить слева на все L мультипликаторы представления (1.8), то его достаточно умножить на группы L - мультипликаторов с номерами из УУк) и d (к,0) в порядке убывания их номеров С к О, , - -?ty ). Свойство 6. Если некоторую вектор-строку с [ №] такую, что СIН\ U № .$] =0 , требуется умножить на все U - мультипликаторы представления (1.8) справа, то ее достаточно умножить на группы U - мультипликаторов с номерами из & СК,0 ) в порядке убывания номеров групп ( k =0,4, — ty). Справедливость этих свойств непосредственно вытекает из структуры главных столбцов мультипликаторов. Эти свойства имеют важное значение для мультипликативных алгоритмов симплекс-метода, т.к. если матрица условий задачи ЛП имеет разветвленную блочную структуру, то на любой итерации базисная матрица будет иметь ту же структуру, с той лишь оговоркой, что некоторые блоки могут оказаться пустыми. Ведущие столбцы на всех итерациях также подчинены структуре матрицы ограничений. Поэтому, при решении системы (0.6)? можно воспользоваться свойствами 4 и 5. Свойство 6 можно эффективно использовать при реализации алгоритма Форреста-Томлина, который предусматривает вычеркивание строки в и - мультипликаторах и ее умножение на U - мультипликаторы справа. (Этот алгоритм будет рассмотрен в 5 настоя - 59 щей главы). Если новые мультипликаторы, получаемые в процессе корректировки мультипликативного представления при переходе к смежному базису, включать в корневую группу, то свойства 4, 5 и б будут иметь место на всех итерациях симплекс-метода. При решении задач ЛП процедура повторения применяется многократно. При этом, если между двумя соседними повторениями столбцы и строки какого-либо, скажем к -го, блока не выбирались в качестве ведущих, то группу мультипликаторов, соответствующую к -й вершине и все группы с номерами из {/(к) при новом повторении можно не строить заново. Эти группы можно взять из старого мультипликативного представления. Скажем несколько слов о возможной модификации многоуровневой стратегии. Если для некоторого блока /М / 7 /V / ( К =4,2,. ,ф) и работа с к -м блоком закончилась из-за исчерпания столбцов, то оставшиеся строки можно сразу же использовать для построения мультипликаторов из связующих столбцов блоков, объемлющих к -й, в порядке убывания их номеров. Такая модификация позволяет несколько уменьшить число преобразований элементов в связующих столбцах, однако, свойства 4, 5 и 6 в данном случае уже не будут, вообще говоря, иметь места.
Представление данных блочной задачи линейного программирования в пакете МАПР
Изложенная в главе I стратегия учета многоуровневого блочного строения матрицы ограничений в задачах линейного программирования была реализована в пакете прикладных программ "Математическое программирование многомерных задач" (МАПР), разработанном в Иркутском вычислительном центре СО АН СССР ( f4lj ). Данный пакет ориентирован на решение задач линейного программирования и некоторых классов задач оптимального управления.
Автором настоящей работы в рамках этого пакета разработано программное обеспечение для решения задач ЛП, системные компоненты пакета и его входной язык.
Пакет МАПР работает на ЭВМ БЭСМ-6 под управлением монитор-ной системы "Дубна". Он построен по модульному принципу таким образом, что модули, решающие одну и ту же подзадачу (естественно, с помощью различных алгоритмов) взаимозаменяемы в программном отношении.
Для решения задач линейного программирования в пакете МАПР имеется набор модулей, реализующих несколько вариантов симплексного и адаптивного ( 42 J ) методов, ряд процедур повторения (алгоритмы с выбором главного элемента в столбце и Хеллермана-Рарика и их блочные аналоги), модули, выполняющие работу с традиционными и с треугольными мультипликаторами, а также модули, формирующие начальный базис в зависимости от типов основных и прямых ограничений. Кроме того, в пакете имеется ряд вспомогательных модулей о назначении которых будет сказано ниже.
Реализованные в ППП МАПР варианты симплекс-метода позволяют программно учитывать различные типы прямых и основных ограничений, а также работать не только с базисными, но и с небазисными планами, что дает возможность использовать начальный небазисный план.
В Г15] показано, что треугольно-мультипликативная схема обладает более высокой вычислительной эффективностью, чем традиционная, в смысле числа ненулевых элементов и точности. Пакет МАПР предусматривает хранение обратной базисной матрицы на внешнем носителе и наличие в нем традиционной схемы обусловлено тем, что ее реализация требует несколько меньших затрат оперативной памяти ЭВМ, по сравнению с треугольной схемой, ввиду простоты ее логики.
Выбор конкретных модулей осуществляется монитором пакета. Монитор выбирает алгоритм решения задачи автоматически, на основе анализа ее исходных данных (размерностей, процента заполненности матрицы ограничений, типов основных и прямых ограничений и т.п.), или следуя прямым указаниям пользователя. Эти указания оформляются в виде задания пакету, в соответствии с требованиями входного языка. Монитор, кроме того, управляет всем процессом прохождения задачи. Он распределяет ресурсы оперативной и внешней памяти, осуществляет, по мере надобности, вызов вспомогательных модулей, которые приводят задачу it каноническому виду, масштабируют ее, сортируют столбцы матрицы ограничений по блокам, а также осуществляют преобразование и вывод полученного решения. Кроме того, монитор, в зависимости от размеров решаемой задачи, определяет способ загрузки основных функциональных модулей - статический или динамический и загружает их надлежащим образом.
Ввод и первичную обработку пользовательской информации о задаче осуществляет транслятор входного языка. Транслятор состоит из ряда блоков, каждый из которых отвечает за определенную часть этой информации. Вызов блоков транслятора производится монитором.
Схему прохождения задачи ЛП в пакете МАПР можно изобразить следующим образом (Рис. 10).
