Приближенные методы

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

Метод ближайшего соседа реализует требование включить в искомый замкнутый контур вершину ближайшую к только что найденной.Алгоритм состоит в последовательном добавлении к начальной вершине следующей ближайшей к ней и т.д.

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

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

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

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

В том случае если известны решения задачи и полученное одним из точных методов можно оценить погрешность решения. При этом различают абсолютную погрешность

Δ =Fпр-Fточн, где Fпр и Fточн – значение целевой функции полученное приближенным и точным методом соответственно.

Относительная погрешность:

δ = Δ/ Fточн = (Fпр-Fточн)/ Fточн;которая может быть так же выражена в %

δ%= δ*100%

Симплекс-метод. Основная идея, этапы поиска решений, алгоритм метода.

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

Основная идея симплекс-метода заключается в том, чтобы так переходить от одной вершины ОДР к другой, чтобы при каждом переходе значение ЦФ уменьшалось. Именно так из любой вершины можно добраться до оптимальной и получить оптимальный план.

Например: пусть известен опорный план X =(x₁,x₂,…,x_m,0,0,…,0) и связанная с ним система линейно независимых векторов: А₁,А₂,…,А_m, тогда для этого опорного плана можно подсчитать значение ЦФ Z=(c₁x₁+c₂x₂+…+c_mx_m) и записать условия ограничения в следующем виде x₁A₁+x₂A₂+…+x_mA_m=b

Поскольку векторы А₁,А₂,…,А_m линейно независимые любой вектор A_j можно разложить по этим векторам: A_j=x_1jA₁+x_2jA₂+…+x_mjA_m (*) Введем величины Z_j Z_j=x_1jc₁+x_2jc₂+…+x_mjc_m, где x_ij коэффициент соответствующий A_i в разложении вектора A_j по базисным векторам

Теорема1: улучшение опорного плана

Если для некоторого индекса j выполняется условие Z_j-C_j>0, то можно уменьшить значение ЦФ причем:

· если ЦФ ограничена снизу, то можно построить опорный план с меньшим значением ЦФ, сем предыдущий

· если ЦФ не ограничена снизу, то можно построить план соответствующий сколь угодно малому значению ЦФ

Теорема2: критерий оптимальности опорного плана

Если для некоторого индекса j в опорном плане неравенство Z_j-C_j<=0, то полученный опорный план является оптимальным.

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

Примечание: