Вычислительная математика
Чапуров Д.В., аспирант Московского государственного института электронной техники
ПРАКТИЧЕСКИЕ МЕТОДЫ ПОИСКА ЭКСТРЕМУМОВ СТРУКТУРНЫХ ФУНКЦИЙ
Основная задача комбинаторной оптимизации — отыскание допустимого оптимального решения по данным представлениям исходных параметров. В нашей постановке задачи — это нахождение экстремального значения структурной функции, заданной в комбинаторном пространстве своими матрицами порядка и цен. Задача поиска структурных решений имеет особенности по сравнению с аналогичной задачей при параметрическом синтезе из-за самой формы оптимизируемых структурных функций. Методы оптимизации, разработанные для функций, определенных в непрерывном пространстве поиска, не дают результатов при пошаговом численном поиске.
Форма структурных функций в комбинаторном пространстве в наибольшей степени отражает одну из самых характерных черт композиционной технологии проектирования: сами слагаемые значений структурных функций этого типа, содержащегося в матрицах цен, представляют собой не что иное, как формальное количественное отображение того выигрыша, который обнаруживается при совместном выполнении функций по сравнению с их раздельным выполнением. Другим свойством этой формы структурных функции является возможность распространения на нее некоторых обобщающих выводов, полученных при других условиях.
т т
Функции сепарабельного вида определяются суммами типа ¥ = ЕЕауХу ,где аг]- — вес пе-
Г=1 1 =1
рехода от символа с номером г к символу с номером 1, в общем случае ац ^ ап; хц — логическая
переменная, равная единице в том случае, если пара смежных символов с номерами г и 1 входит в комбинацию, и равная нулю в противоположном случае; эта же переменная всегда равна нулю при г = 1; число хг]., равных единице, всегда составляет т. Такого рода функции нашли широкое
практическое применение во многих сферах управления техническими и экономическими объектами в виде следующей детерминированной задачи принятия решений ("задачи коммивояжера" или же задачи о назначении). Вот классическая постановка такой задачи, согласно []:
Имеются два равномощных множества элементов Qi и Qj элементы, которых нумеруется
числами натурального ряда от 1 до п.
Множество управляющих воздействий и = {и, ={0,1}} характеризует наличие связи между элементами qi е Qi и qj е Qj , если иг,} = 1, и отсутствие связи, если иг,} = 0. Каждой паре
<ЧьЧ> поставлено в соответствие неотрицательное число ^, характеризующее стоимость
установления связи между qi и Требуется для каждого элемента qi найти единственный, связанный только с qi, элемент такой, при котором достигается минимум общей стоимости всех п связей, т. е. оценочная функция Е имеет вид:
п п
Е = ЕЕа, 1 • и, 1 —> т1п
г=1 1=1
£
Множество допустимых управлений и ограничено условиями неповторяемости элементов qi и qj во всех связях;
п п _
и/ = {иг 1 : Е и 1 = 1Е ии 1 = 1 i, 1 = 1 п}
г =1 1=1
Задачу на поиск экстремума для функции, представленной в такой форме, можно решать точными методами после преобразования задачи к стандартной форме задач линейного программирования.
Точные методы нахождения экстремума
Например, общее число вариантов решения, которые необходимо проанализировать за все n шагов динамического программирования, определим по формуле:
n - 1 n - 1 !
W = е Ck + 1= е , !(n! k)! + 1 k=1 k=1k!(n - k)!
Приведем оценки числа вариантов при n = 10. Методом полного перебора в этом случае необходимо проанализировать около 4gL06 вариантов решения. При использовании же динамического программирования оценка количества вариантов W приближается к 7g103 .
Однако задачу выбора в такой форме решают крайне редко, так как использование стандартных программ линейного программирования из фондов прикладного математического обеспечения универсальных ЭВМ не является эффективным. По исследованиям [1] время счета задачи выбора на ЭВМ с программой MERCI более чем на порядок превышает время счета специализированным венгерским методом.
Венгерский метод для решения задачи назначения и различные его модификации представлены во многих работах, посвященных решению задачи о назначении. Однако следует отметить, что основу метода, сформированного американским математиком Г. Куном, составляют теоремы Д. Кёнига и И. Эгервари, в честь которых метод и получил название венгерского. Теорему Кёнига применяют для решения задачи так называемого простого назначения, когда матрица А содержит только 0 или 1, Теорема Эгервари позволяет свести задачу назначения с помощью эквивалентных преобразований матрицы А к задаче простого назначения.
В последние годы широко распространена одна из модификаций венгерского метода, так называемый метод Мака. Метод Мака отличается более простой для программирования логикой выбора поэтапных решений, чем метод Куна.
В задачах принятия оперативных решений, реализуемых в многообъектных системах управления, использование венгерского метода решения, метода Мака или Кратчайшего Увеличивающегося Пути, отличающихся наименьшими затратами вычислительных ресурсов, допустимо далеко не всегда. Нередко требуется получить решение задачи в столь короткое сроки, что применить любой из точных методов решения невозможно. В этих условиях обычно можно удовлетвориться любым "не худшим" решением. Такое положение обусловило появление многочисленных методов приближенного решения. В работе [4] высказываются соображения практически приемлемых методов решения комбинаторных задач. Подходы к оптимизационным задачам включают прием, который можно назвать «снижение требований». Он заключается в отказе от поиска оптимального решения и нахождения вместо этого «хорошего» решения за приемлемое время.
Подходы, реализующие прием «снижения требований»:
— Приближенные алгоритмы, порождающие решения, которые отличаются от оптимальных заведомо не более чем на фиксированную долю;
— Вероятностные алгоритмы, работающие относительно некоторого вероятностного распределения на индивидуальных задачах;
— Алгоритмы, основанные на полном использовании особенностей частных случаев, благодаря которым так называемые «труднорешаемые» задачи оказываются упрощенными;
— Экспоненциальные алгоритмы, которые, несмотря на свой характер, могут хорошо работать в пределах достаточных размерностей или при конкретных наборах исходных данных;
— Алгоритмы локального поиска, основанного на старейшем методе «проб и ошибок»;
— Эвристические алгоритмы, в которые могут входить любые из перечисленных выше алгоритмов при отсутствии для них соответствующих формальных гарантий.
Приближенные методы решения
Метод минимального (максимального) элемента
Является одним из самых простых, понятных и эффективных методов поиска решения. Интуитивно кажется очевидным, что при формировании минимального (максимального) по затратам решения, необходимо выбирать наименьший (наибольший) элемент из матрицы, исключать строку и столбец, содержащих его, из решения и продолжать далее, ограничиваясь лишь размерностью массива данных. Метод поэтапного выбора
Также является одним из простых методов решения задачи выбора. Не требует увеличения вычислительных затрат. Но точность невысокая. Ищется максимальный элемент в каждой строке матрицы. Для повышения точности используется предварительное упорядочивание строк:
— по мере убывания сумм их элементов;
— по мере убывания минимальных элементов строк;
— по мере убывания сумм минимальных и ближайших к ним элементов строк; Метод Фогеля
Решение задачи о назначении сводится к выбору из матрицы А порядка п только одного элемента из каждой строки и каждого столбца. Сумма выбранных элементов должна быть минимальной (максимальной). Человек, осуществляющий выбор, может сформулировать некоторые условия, которым выбираемые элементы должны удовлетворять. Наиболее естест-
*
венным кажется предположение о том, что оптимальное решение Е* = { 1,1 } должно содержать минимальный элемент, принадлежащий А. Поэтому доминантное условие можно
сформулировать в виде а{ = т а{, . ^ Е , где а' — первый из включаемых в решение
элементов А. Существуют и более простые формы доминантных условий, в которых учитывается не модуль элементов а{., а их разность. Например, метод Фогеля. Основан на последовательном выборе элементов, согласно правилу
int а, . - min ai .
{i} i,J {i} i,J
int a) j - min at .
{j} {j}
min а . „ _ int a r
где 1 — элемент матрицы, наименьшим в j-м столбце; ,1 — ближаишии к нему
элемент; min a',J — элемент матрицы, наименьший в i-й строке; int a',J — ближайший к нему элемент.
Формируются вектора разницы между минимальными и наиболее близким к ним элементами в строках и столбцах. Находим минимальную разность, исключаем строку и столбец с максимальным элементом.
«Гибкий»(«Жадный») алгоритм
Этот алгоритм решения задачи выбора, объединяющий возможности применения принципа сложности и идеологии принятия решений на расширенном множестве альтернатив. Для получения решения, максимально близкого к оптимальному, за ограниченное время, наиболее перспективной является специальная модификация метода локальных вариаций:
Этап 1. Определение произвольного опорного решения. Пусть это решение составляют элементы главной диагонали матрицы А.
Этап 2. Отыскание среди элементов главной диагонали ац максимального элемента а'ц и ближайшего к нему int a'i д элемента. Пусть для определенности а i = а'к,к, int а'ц = а r ,r.
Этап 3. Решение задач и для пары элементов, которые могут составить "конкуренцию" элементам а'к,к и аг,г, т. е. для элементов ак,г и аг,к. Если неравенство
а, , + а > а, + а ,
k ,k r ,r k ,r r ,k i
' выполняется, то строки k и r меняют местами, если это неравенство не выполняется, то вместо элемента аг,г, берут ближайший к нему меньший элемент, вновь проверяют неравенство и т. д. При выполнении условия после перемены местами строк k и r осуществляют возврат к этапу 2 и начинают новую итерацию.
Сравнительный анализ работы методов
Для сравнительного анализа решений каждого метода набиралась выборка экспериментов (решений для матриц одного и того же размера различными методами). В
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.