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

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

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

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

При решении задач ЛП на ЭВМ используются, как правило, различные варианты модифицированного симплекс-метода [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 Д-fG '.

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

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

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

Wp иг. т-о Щ.

0 о где X q — подвектор плана X, составленный из базисных компонент. Если окажется, что, i = 2,. tm% то целевая функция в задаче (0.1 — 0.3) неограничена снизу. В противном случае вычисляется новый базисный план X * по формулам: XG — в иг, при J е GXj — О, при 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СФАП П6 671) [41J .

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

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

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

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

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

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

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

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

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

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

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

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

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

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