книги из ГПНТБ / Большие системы и управление

81

На этом и основан предложенный В.И. Чернецким алгоритм на­ хождения квазиоптималъного плана»

Данный алгоритм в применении к матрице

а п, а Р2 ‘ * * ^пп

заключается в следующем.

П е р в ы й ша г а л г о р и т м а. С левого верхнего угла исходной матрица начинают подсчет и сравнение сумм вида

а'п + а'пп^ ат + а Pi *

После этого, считая, что в левом верхнем углу матрица ||л,| стоит число о\)9 представляющее компоненту искомого вектора 5 , вычеркиваем первую строку и первый столбец матрица ||Д?|| и рас­ сматриваем матрицу

82

Второй шаг в точности повторяет первый шаг с той разницей, что все действия производятся над матрицей || Аг|| п -1-го по­ рядка*

Каждый следующий шаг представляет собой точную копию пре­ дыдущего над матрицей все более низкого порядка*

В результате /? - I шагов у нас определятся п чисел, пред­ ставляющих квазиоптимальное решение* Анализ показывает, что в наиболее благоприятном случае для отыскания квазиоптимального решения требуется ( п - I) п простых операций (сложения

двух чисел и сравнения двух чисел). Как показывает практика, для отыскания квазиоптимального решения в общем случае требу­

84

Таким образом, средняя величина диагонального члена матри­ цы || А „- Р|| больше или равна средней величине общего члена этой

матрица* Аналитически это выражается так:

то никаких преобразований в матрице не делаем* Далее

3 + I < 4 + 2.

Поэтому переставляем местами первую и третго строки матрицы:

Проводим все операции над этой матрицей:

На этом первый шаг кончился* Считаем, что число 4, стоящее в первом столбце второй строки исходной матрицы, является, компо­ нентой искомого решения. В соответствии с принятым алгоритмом вычеркиваем первую строку и первый столбец матрицы, полученной в результате первого шага, и рассматриваем матрицу:

86

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

Найденное решение

S = 2 + 5 + 4 + 2+ 2 = I 5

является оптимальным.

В результате анализа рассмотренного примера можно сделать следующие выводы:

1.Алгоритм весьма удобен для его реализации на вычисли­ тельных устройствах, Это обстоятельство является важным досто­ йнотсвом данного алгоритма, так как все известные алгоритмы решения рассматриваемой задачи встречают те или иные трудности при их машинной реализации. Сами операции достаточно просты: сложение и вычитание двух чисел.

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

5 = 4 + 3 + 4 + 2 + 2=15 .

S = 4 + 3+ 4+ 2+ 2=15 .

87

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

S = 4 + 5 + 2 + 2 + I = 14.

S = 4 + 3 + 2 + 2 + 3 = 14.

S = з + 3 + 2 + 2 + 3 = 13.

Никаких других решений при применении данного алгоритма

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

3. После получения перестроенной матрицы, содержащей по главной диагонали оптимальное решение, в соответствии с идеями построения алгоритма мы можем получить все остальные оптималь­ ные решения. Поясним сказанное на уже рассмотренном примере.

Перестроенная матрица, содержащая по главной диагонали од­ но из оптимальных решений, имеет вид:

Для нее, естественно, выполняются все неравенства, рассмот­ рение которых подразумевается предложенным алгоритмом* Рассмот­ рим нестрогие неравенства (равенства), которые содержит матри­ ца. Таких равенств только одно:

5 + 2 = 3 + 4.

Если теперь поменяем местами первую и последнюю строки, содержащие рассматриваемые числа, то получим другое оптималь­ ное решение, матрица которого имеет вцд:

Эта матрица имеет два не строгих неравенства (равенства): - содержащее те же элементы, что и предыдущая матрица:

4+ 3 = 2 + 5;

-состоящее из элементов третьей и пятой строк

2+ 3 * 2 + 3.

Если мы поменяем местами эти строки, то подучим матрицу, содержащую последнее оптимальное решение:

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

Пр и м е ч а н и е I . То обстоятельство, что матрица

А2 , полученная из матрицы А 1 путем перестановки двух строк,

89

относится и к матрице А39 пожученной из матрица Агтакже

перестановкой двух строк.

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

решение.

4. Два из трех полученных оптимальных решений: £ = 4 + 3 + 4 + 2 + 2 (Аг),

S = 4 + 3 + 4 + 2 +2 (А3)

очень интересны тем, что не содержат независимого элемента - числа 5,Таким образом, независимые элементы не являются обяза­ тельными компонентами оптимального решения.

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

6.Как уже отмечалось, число операций, необходимых,для на­ хождения квазиоптималшого решения, невелико. Оно не превосхо­

пришлось сделать 39 арифметических действий, из которых 26 сло­ жений двух чисел и 13 сравнений двух чисел ( С =1,56).

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

7. В связи с относительно небольшим числом операций, тре­ буемых для отыскания квазиоптимальнсго решения, предложенный алгоритм может найти применение при нахождении оптимальных ре­ шений матриц высокого порядка на ЦВМ. Экспериментальная провер­ ка подтверждает высокую эффективность алгоритма для больших матриц. Так, для матрицы 50-го порядка при помощи данного алго­ ритма и разумно построенной программы удавалось найти квазноптимальное решение за время, не превосходящее 1 - 2 мин. При этом отличие найденного квазиоптимального решения от оптималь­ ного не превосходило 2 - 3 $ .

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