Алгоритмические вопросы решения больших структурных задач линейного программирования тема диссертации и автореферата по ВАК РФ 01.01.10, кандидат физико-математических наук Жолудев, Анатолий Иванович

• Жолудев, Анатолий Иванович
• кандидат физико-математических наук
• 1984

Оглавление диссертации кандидат физико-математических наук Жолудев, Анатолий Иванович

Введение.

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

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

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

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

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

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

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

§ 6. Корректировка треугольно-мультипликативного представления Бартелса-Голуба. ?!

Глава 2. Оценка точности процедур повторения.

§ I. Вводные замечания.

§ 2. Основные формулы треугольно-мультипликативного разложения. Матрица эквивалентного возмущения.

§ 3. Оценки матриц ошибок одного шага алгоритма разложения.

§ 4. Оценки матрицы эквивалентного возмущения.

§ 5. Оценка матрицы эквивалентного возмущения для алгоритма Хеллермана-Рарика.

§ 6. Оценка матрицы эквивалентного возмущения для блочного алгоритма.

§ 7. О сдерживании роста элементов в процессе повторения.

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

§ I.Схема решения задач линейного программирования в ППП "Математическое программирование многомерных задач.

§ 2. Представление данных блочной задачи линейного программирования в пакете МАПР.

§ 3. Представление обратной базисной матрицы и работа с ней. ИЗ

§ 4. Организация вычислений на этапе повторения.

§ 5. Реализация алгоритма Форреста-Томлина.

Введение диссертации (часть автореферата) на тему «Алгоритмические вопросы решения больших структурных задач линейного программирования»

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

Несмотря на высокую производительность современных ЭВМ, проблема построения эффективных алгоритмов для решения задач • ЛП большого размера остается актуальной и ей уделяется большое внимание в литературе.

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

При решении задач ЛП на ЭВМ используются, как правило, различные варианты модифицированного симплекс-метода [I, 2, 3] .

Рассмотрим задачу ЛП в канонической форме:

СТХ — min, (0Л) при условиях:

0.2)

X ^ 0, (0.3) где С & R » ^ R - известные векторы, называемые вектором коэффициентов целевой функции и вектором правых частей основных ограничений соответственно; X € R - вектор неизвестных;

А - прямоугольная матрица, размером тхп (т^п), называемая матрицей ограничений. Основной алгоритм симплекс-метода для задачи (0.1-0.3) выгладит следующим образом. О

Пусть имеется вектор X ^-К » удовлетворяющий условиям (0.2) и (0.3) такой, что Xj - О , при k - i, 2,.,., п-т, где •••> j-n-ffi ~ некоторый набор индексов из множества

Я } . Множество индексов h> • - называют множеством базисных индексов, а вектор

X ° « удовлетворяющий перечисленным условиям, - базисным планом задачи (0.1 - 0.3). Матрицу Aq , составленную из столбцов Л^, £ & Q t матрицы А , называют базисной матрицей.

По имеющемуся базисному плану X ° и соответствующему множеству С строится новый базисный план, лучший, чем X °, в смысле функционала (0.1).

Для этого решается система линейных уравнений: ТАв - cj, (0Л) где С $ - вектор, составленный из компонент Cj вектора С таких, что J G .

По найденной из системы (0.4) вектор-строке ti вычисляются коэффициенты:

4 . = с. - uJА, у е ff\ G, (о.5)

С а "

- 6 где - столбцы матрицы Л , и находится

Л. = min Д-f\G '

Если А; 0 , то план X ° является оптимальным ресо шением задачи (0.1 - 0.3). В противном случае осуществляется переход к новому базису. Для этого решается система:

Ав иг = А (0.6) и вычисляется величина

У ° 0 л Ср . хв. (у =-— - тгп -,

Wp иг. т-о Щ

0 о где X q - подвектор плана X , составленный из базисных компонент. Если окажется, что , i = 2,. tm% то целевая функция в задаче (0.1 - 0.3) неограничена снизу. В противном случае вычисляется новый базисный план X * по формулам: XG - в иг , при J е G; Xj - О, при J ф GUj0 ; затем из множества G исключается р -й элемент, на его место вставляется индекс j0 и вся процедура повторяется для нового базисного плана.

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

Для снижения трудоемкости этих операций был предложен мультипликативный алгоритм [4, б] , развитый в работах [б, 7,. 8, 9, 10, II, 12, 14J .

Идея мультипликативного алгоритма состоит в том, что базисная матрица A q представляется в виде произведения:

Ав = М1 *Мгх .* Mm*S, to.?) где М ^ 9 i = . fm - матрицы, отличные от единичной не более чем одним стобцом, a S - матрица некоторого специального вида, с которой системы типа (0.4) и (0.6) решаются легко.

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

При наличии представления (0.7), вместо (0.4) решаем систему arS=cJ и решение системы (0.4) находим по формуле; а вместо (0.6) имеем:

S иг =

-4

Матрицы М; i-i,2t. .т % очевидно, так же как и М,-, 9 * ь * отличаются от единичной не более чем одним столбцом, поэтому достаточно хранить лишь ненулевые компоненты их неединичных столбцов, а трудоемкость решения рассматриваемых систем определяется числом нетривиальных элементов матриц Mi ( i=j(,2,.,m) и видом матрицы S .

Для случая, когда S - Е, имеем соотношение

К^^'т * ••• * М]' (0.8)

Представление (0.8) будем называть традиционным мультипликативным представлением, а матрицы (. i = i,Z, . }т) традиционными мультипликаторами.

Алгоритмы построения представления (0.8) рассматривал Тьюарсон [15] . Им же описан случай, когда S - верхнетреугольная матрица с единичной главной диагональю. Для этого случая, полагая U - S и разлагая матрицу U на элементарные матрицы, получаем:

0.9)

T-i . где li , t = {,2, . , т - нижнетреугольные элементарные матрицы (будем называть их нижнетреугольными или L - мультипликаторами), a Ui - верхнетреугольные элементарные матрицы ( i . ), которые будем называть верхнетреугольными или U - мультипликаторами.

Представление (0.9) будем называть треугольно-мультипликативным представлением.

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

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

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

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

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

Алгоритмы выбора главного элемента, учитывающие разреженность базисной матрицы, рассматривались, также, в работах [10, II, 16, 17, 18] и др.

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

Очень интересен, с точки зрения минимальности получаемого мультипликативного представления, алгоритм Хеллермана-Рарика [16J . Этот алгоритм допускает преобразование только некоторой, как правило, небольшой части столбцов, и, следовательно, новые ненулевые элементы возникают только в этой части столбцов.

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

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

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

Для задач ЛП с матрицами ограничений блочно-диагональной структуры с окаймлением в работе [19] был предложен метод декомпозиции (называемый методом Данцига-Вулфа). Этот метод получил свое дальнейшее развитие в работах [20, 21, 22] и других.

Метод декомпозиции Данцига-Вулфа работает с блочно-диаго-нальными матрицами с односторонним окаймлением, вида: А

У///////////////Ж

УМ т, ф т

0.10)

• т, т.

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

Другой подход к решению задач ЛП с матрицами блочно-диаго-нальной структуры с окаймлением был развит в работах [23-35] . Основная идея этого подхода состоит в следующем. Для решения задачи применяется алгоритм симплекс-метода обычного вида, но при решении систем (0.4) и (0.6), а также при пересчете базисной информации используется специфика строения базисной матрицы. Этот подход представляется более эффективным в вычислительном отношении, чем метод Данцига-Вулфа ([Зб]).

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

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

Малковым и Ахметовым в работе [37] был предложен мультипликативный алгоритм для задач ЛП, матрица ограничений которых имеет вид (0.10). Этот алгоритм предусматривает решение последовательности усеченных задач, составленных из переменных какого-либо блока и базисных переменных других блоков, занимающих позиции базиса, соответствующие связующим строкам. В этом алгоритме хранению подлежит не вся обратная матрица, а лишь ее незначительная часть (речь идет, разумеется, о мультипликативном представлении). Соответственно сокращается и трудоемкость работы с ней. Этот алгоритм, однако, неприменим в случае наличия двухстороннего окаймления и не учитывает многократной вложенности блоков.

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

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

Далее, на основе этой стратегии строится алгоритм, использующий идеи алгоритма Хеллермана-Рарика.

В конце первой главы рассматриваются операции корректировки разложения вида (0.9), выполняемые по методам Форреста-Том-лина [12] и Бартелса-Голуба [13] , применительно к задачам с матрицами ограничений разветвленной блочной структуры. Доказывается, что новые мультипликаторы, получаемые в результате операций корректировки имеют, по большей части, блочную структуру заполнения ненулевыми элементами.

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

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

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

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

В настоящей работе с помощью обратного анализа ошибок для всего процесса построения представления (0.9) построены оценки вида: Г

IY-I *

I I yl

J ~t+{ — f Р ' а-г/Щ^)' п?и

ПРИ (0Л1) где • - элементы матрицы эквивалентного возмущения; У.

7 " V

- число преобразований элемента базисной матрицы в процессе разложения; СС£: - максимальный модуль, которого достигает элемент d^ в процессе преобразований; р и Z - соответственно основание системы счисления и разрядность мантиссы используемой машинной арифметики.

Полученная оценка (0.11) гораздо ближе к практике вычислений, чем оценки из [38, 39, 40] .

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

Что касается величин С — i}Z9.7m)^ то имеется ряд способов их уменьшения, таких как выбор главного элемента в столбце или во всей матрице [39] , но применение этих алгоритмов приводит, вообще говоря, к росту числа ненулевых элементов в мультипликативном представлении, если используется какой-либо алгоритм, предназначенный для разреженных матриц.

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

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

Эта стратегия реализована в функциональном наполнении пакета прикладных программ "Математическое программирование многомерных задач" (МАЛР), разработанном в Иркутском ВЦ СО АН СССР (регистрационный номер Г0СФАП П006671) [41J .

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

Кроме того, здесь предлагается способ реализации алгоритма Форреста-Томлина для случая, когда мультипликативное представление (0.9) хранится в компактном виде во внешней памяти. Этот способ требует минимального изменения информации при переходе к смежному базису.

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

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

В заключении приводятся основные результаты настоящей работы.

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

Заключение диссертации по теме «Математическое обеспечение вычислительных машин и систем», Жолудев, Анатолий Иванович

- 133 -ЗАКЛЮЧЕНИЕ

В работе получены следующие основные результаты.

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

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

3. Исследованы свойства операций корректировки треугольно-мультипликативного представления Форреста-Томлина и Бартелса--Голуба, применительно к матрицам разветвленной блочной структуры. Показано, что структура новых мультипликаторов, получаемых в процессе корректировки, соответствует, по большей части, структуре базисной матрицы.

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Жолудев, Анатолий Иванович, 1984 год

1. Канторович Л.В. Экономический расчет наилучшего использования ресурсов. М., изд. АН СССР, 1959, 347 с.

2. Данциг Дж.Б. Линейное программирование, его применения и обобщения. М., Прогресс, 1966, 600 с.

3. Голыптейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. М., Сов.радио, 1966, 524 с.

4. Dantzig G.B., Orchard-Hays W. The product form for the inverse in simplex method. In Math. Tables aids сотр.,9 ' *v.8, 1954, p. 64-67.

5. Лэсдон Л.С. Оптимизация больших систем. М., Наука, 1975, 432 с.

6. Зойтендейк Г. Методы возможных направлений. М., ИЛ, 1963, 128 с.

7. Станевичюс А.-И.А. Особенности реализации вычислительной схемы мультипликативного алгоритма симплекс-метода на ЭЦВМ. Труды Всесоюз. научно-исслед. ин-та сельского хозяйства. Т.45, 1968, с. 128-136.

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

9. В кн.: Оптимальное планирование. Вып. 12, Новосибирск, Изд. ИМ СО АН СССР, 1969, с. 28-47.

10. Романовский И.В., Сурин С.С. Триангуляция базисной матрицы и мультипликативный алгоритм решения задач линейного программирования. В кн.: Оптимальное планирование. Вып. 12, Новосибирск, Изд. ИМ СО АН СССР, 1969, с. 48-51.

11. Ахметов П.А., Малков У.Х. Повышение эффективности мультипликативного алгоритма симплекс-метода при решении больших задач линейного программирования на ЭВМ. Экономика и матем. методы. Т. У1, вып. 3, 1970, с. 422-426.• ' 9

12. Beale E.M.L. Sparseness in linear programming.

13. Large sparse sets of linear equations. Acad. Press,0 У1.ndon, 1970, p. 1-15.* < *

14. Forrest J.J.H., Tomlin J.A. Updated triangular factors of the basis to maintain sparsity in the product form4 4 *simplex method. Math. Progr. v.2, Ю,. 1972, p. 263-278.

15. Bartels R.H. A stabilisation of the simplex method. Humerische Mathematik, Bd. 16, H.5, 1971, S. 414-434.

16. Reid J.K. A sparsity-exploiting variant of the Bartels-Golub decomposition for linear programming bases. Math. Progr. v.24, H1, 1982, p. 55-69.

17. Тьюарсон P. Разреженные матрицы. M., Мир, 1977, 190 с.

18. Hellerman Е., Rarick D.C. Reinversion with the preassig-ned pivot procedure. Math. Progr. v.1,U2,1971, p.195-216.

19. Orchard-Hays W. Advanced linear programming computing techniques. New York, McGraw-Hill, 1968, 355p.

20. Малков У.Х. Обзор путей повышения эффективности мультипликативного алгоритма симплекс-метода. В кн.: Математические методы решения экономических задач. Вып. 7, М., Наука, 1977, с. 30-51.

21. Данциг Дж.Б., Вольф Ф. Алгоритм разложения для задач линейного программирования. Математика, т.8, вып. I, 1964, с. I5I-I60.

22. Abadie J.M., Williams A.C. Dual and parametric methods in decomposition. In Recent advances in mathematical programming. New York, McGraw-Hill, 1963, p. 149-158.

23. Голынтейн Е.Г. Методы блочного программирования. Экономика и матем. методы. Т. II, вып. I, 1966, с. 82-114.

24. Мовшович С.М. Метод невязок для решения задач блочной структуры. Экон. и матем. методы. Т. П, вып. 4,с. 571-577.

25. Звягина Р.А. Задачи линейного программирования с блочно-диагональными матрицами. В кн.: Оптимальное планирование. Вып. 2, Новосибирск, Изд. ИМ СО АН СССР, 1964, с. 50-61.

26. Звягина Р.А. Задачи линейного программирования с матрицами узкоблочной структуры. В кн.: Оптимальное планирование. Вып. 15, Новосибирск, Изд. ИМ СО АН СССР, 1970, с.33-47.

27. Звягина Р.А. Задачи линейного программирования с матрицами произвольной блочной структуры. ДАН СССР, 196, 4, 1971, с. 755-758.

28. Звягина Р.А. Об общем методе решения задач линейного программирования блочной структуры. В кн.: Оптимизация.

29. Вып. 1(18), Новосибирск, Изд. ИМ СО АН СССР, 1971, с.22-40.

30. Звягина Р.А. 0 разложении матрицы с блочной структурой в произведение матриц треугольного вида. В кн.: Оптимизация. Вып. 5(22), Новосибирск, Изд. ИМ СО АН СССР, 1972, с.73-86.

31. Звягина Р.А. Иерархическое упорядочение в линейном программировании. В кн.: Оптимизация. Вып. 14(31), Новосибирск, Изд. ИМ СО АН СССР, 1974, с. 28-54.

32. Звягина Р.А. Многоступенчатая окаймленность в линейном программировании. В кн.: Оптимизация. Вып. 15(32), Новосибирск,

33. Изд. ИМ СО АН СССР, 1974, с. 32-49.

34. Звягина Р.А., Яковлева М.А. О методе решения задач линейного программирования на основе многоступенчатой блочной структуры с окаймлением. ДАН СССР, 217 , 2, 1974, с. 268-271.

35. Яковлева М.А. Транспортная задача с окаймлением. В кн.: Оптимизация. Вып. 15(32), Новосибирск, Изд. ИМ СО АН СССР, 1974, с. 79-89.

36. Булавский В.А., Звягина Р.А. Решение задач линейного программирования с матрицами разветвленной блочной структуры. В кн.: Оптимизация. Вып. 19(36), Новосибирск, Изд. ИМ СО АН СССР, 1977, с. 5-27.

37. Булавский В.А., Звягина Р.А., Яковлева М.А. Численные методы линейного программирования. М., Наука, 1977, 367 с.

38. Звягина Р.А. Приведение к блочно-треугольному виду матриц с симметрично-разветвленной блочностью. В кн.: Оптимизация. Вып. 26(43), Новосибирск, Изд. ИМ СО АН СССР, 1981, с. 34-44.

39. Звягина Р.А. Комбинированное использование специальныхи мультипликативного алгоритмов в линейном программировании. В кн.: Оптимизация. Вып. 26(43), Новосибирск, Изд. ИМ СО АН СССР, 1981, с. 45-57.

40. Кутиков Л.М. Декомпозиция блочных задач линейного программирования со слабо связанными блоками. Экон. и матем. методы. Т. IX,. вып. 4, 1973, с. 739-743.

41. Малков У.Х., Ахметов П.А. Использование специфики условий в мультипликативном алгоритме. Экон. и матем. методы.

42. Т. УШ, вып. I, 1972, с. I0I-I06.

43. Воеводин В.В. Вычислительные основы линейной алгебры. М., Наука, 1977, 303 с.

44. Уилкинсон Дж. X. Алгебраическая проблема собственных значений. М., Наука, 1970, 564 с.

45. Форсайт Дж.Е., Молер К. Численное решение систем линейных алгебраических уравнений. М., Мир, 1969.

46. Габасов Р., Тятюшкин А.И., Жолудев А.И., Эринчек Н.М. ППП Математическое программирование многомерных задач. Per. ном. ПАП П006671. Алгоритмы и программы, Инф. бюллет. ВНТИЦ, № 6(57), М., 1983, с. 43-44.

47. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Часть 3. Минск, Изд. БГУ им. В.И.Ленина, 1980 , 368 с.

48. Пакет прикладных программ "Линейное программирование в АСУ" (ППП ЛП АСУ). Руководство программиста. Часть 2. Входы пользователя. Калинин. Изд. НПО "Центропрограммсистем", 1978, 183 с.

49. Ларин Г. Сортировка и системы сортировки. М., Наука, 1983, 384 с.

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

51. Жолудев А.И. Процедура мультипликативного обращения матриц обобщенной блочной структуры. В кн.: Оптимизация. Вып.24(41). Новосибирск, Изд. ИМ СО АН СССР, 1980, с. 133-144.

52. Жолудев А.И., Тятюшкин А.И. Алгоритмы линейного программирования пакета оптимизации. В кн.: Пакеты прикладных программ. Методы и разработки. Новосибирск, Наука, 1981,с. 92-104.

53. Жолудев А.И. Схема повторения для блочных матриц, основанная на алгоритме Хеллермана-Рарика. В кн.: Оптимизация. Вып. 30(47). Новосибирск, Изд. ИМ СО АН СССР, 1982, с.87--97.

54. Жолудев А.И., Михайлиди И.М. 0 точности одной процедуры повторения. В кн.: Системы программного обеспечения решения задач оптимального планирования. Краткие тез.докладов на УП Всесоюз.симпозиуме. М., Изд. ЦЭМИ АН СССР, 1982,с. 18-19.

55. Жолудев А.И. Мультипликативный алгоритм в пакете прикладных программ по математическому программированию многомерных задач. В кн.: Разработка пакетов прикладных программ. Новосибирск, Наука, 1982, с. 23-33.