Приближённые методы решения классической задачи выбора
В задачах принятия оперативных решений требуется получить решение в столь короткие сроки, что применить точные методы невозможно. Используются методы приближённого решения, но оперативные.
Методы локальных вариаций «текущей величины» и их вариации
В основе метода для задачи назначения лежит общая идея метода локальных вариаций Ф.Л.Черноусько. Предположим, что для задачи (3.1)…(3.3) известно опорное решение, элементы которого удобно расположить на главной диагонали матрицы А.
Метод локальных вариаций состоит в последовательном сравнении каждой пары элементов, принадлежащих опорному решению , с парой элементов для всех i от 1 до n-1.
Если для некоторого i получено < , то строки i и i+1 меняют местами, значение i увеличивают на 1 и процесс сравнения продолжают до i=n-1.
Данное решение - первое приближение - подвергают той же процедуре проверки и так до тех пор, пока для некоторого приближения в течение всего цикла вариаций от i=1 до i=n-1 лучших решений не обнаружится.
Метод локальных вариаций чувствителен к локальным экстремумам и не гарантирует достижения абсолютного минимума.
Для увеличения точности используют метод «бегущей волны», который отличается следующим:
сравниваются локальные стратегии, составленные не из 2, а из n'<n элементов;
при сравнении стратегий (особенно если n' велико) используется не прямой перебор, а один из точных методов решения задачи выбора с матрицей размером n'n'.
Точность с увеличением n' возрастает, но увеличиваются и вычислительные трудности.
Оценка числа вычислительных операций:
- коэффициент пропорциональности, зависящий от ЭВМ и языка программирования;
- среднее число вычислительных операций, необходимое для сравнения двух локальных решений, перестановки строк матрицы А и перехода к следующему сравнению;
k - число итераций.
Для метода «бегущей волны»:
(n')3 - свидетельствует о том, что был использован метод Куна или метод Мака (венгерский метод).
Методы, основанные на доминантных условиях первого типа
Использование доминантных условий значительно снижает вычислительные трудности решения комбинаторных задач. Рассмотрим 3 приближённых метода решения задачи выбора, сформированные на некоторых эвристических предположениях о характере искомого решения, которые относятся к методам, основанным на доминантных условиях 1-го типа.
Проанализируем ещё раз задачу назначения. Решение сводится к выбору из матрицы A порядка n только одного элемента из каждой строки и каждого столбца. Сумма выбранных элементов должна быть минимальной.
Сформулируем некоторые условия, которым должны удовлетворять выбираемые элементы.
Наиболее естественным кажется предположение о том, что оптимальное решение , должно содержать минимальный элемент, принадлежащий А.
Поэтому доминантное условие сформулируем в виде
(3.9)
где - первый из включаемых в решение элементов А.
Если элемент выбран, то из матрицы А можно исключить ту строку и тот столбец, на пересечении которых находится . К полученной матрице порядка (n-1) также можно применить условие выбора вида (3.9) и т.д.
Это доминантное условие формализуется так называемым методом минимального элемента, который получил широкое распространение, т.к. характеризуется незначительным вычислительными затратами и приемлемой точностью решения.
В то же время существуют классы матриц задачи выбора и могут встретиться случаи, когда использование метода минимального элемента недопустимо.
Рассмотрим, например, задачу с матрицей особого вида:
(3.10)
Используя доминантные условия в форме (3.9), получим , затем , затем , после чего в решение включим единственный из оставшихся элементов . Легко установить, что найденное решение не минимизирует, а максимизирует заданный критерий.
Другая форма доминантных условий и вытекающий из неё метод решения задачи назначения предусматривает выбор не просто минимального, а взвешенного минимального элемента
(3.11)
В этом случае матрицу А преобразуем в матрицу D по следующим формулам:
Приведённые преобразования в D являются эквивалентными в том смысле, что оптимальные стратегии для D и A совпадают.
Для задачи выбора с матрицей (3.10), используя данный метод, можно получить оптимальное решение. Отличительная особенность метода - увеличение объёма вычислений.
Существуют и более простые формы доминантных условий первого типа, в которых учитывается не модуль элементов , а их разность. Например, метод Фогеля основан на последовательном выборе элементов согласно правилу:
(3.12)
где - элемент матрицы А, наименьший в j-м столбце;
- ближайший к нему элемент.
- элемент матрицы А, наименьший в i-й строке.
- ближайший к элемент.
Для задачи с матрицей (3.10) по методу Фогеля получено оптимальное решение.
