Методы ветвей и границ первого и второго порядка. Оптимальный и пассивный поиск. Недостатки метода Ньютона. Метод золотого сечения. Примеры унимодальных функций. Динамическое и линейное программирование. Метод Жордана-Гаусса. Решение задачи коммивояжера.
Аннотация к работе
Имеется N пунктов, расстояние между которыми известны. Запишем исходные данные в виде таблицы C0 = (Cij). Найдем Cj для всех j и выполним приведение C01 по столбцам. В приведенном примере все Сj = 0, поэтому C02 = C01, константа приведения по столбцам d02 = 0, d0 = d01 d02 = 23. Длина любого пути LS(C0) и LS(C02) связаны формулой LS(C0) = LS(C02) d0. что следует из условия a. Величину d0 можно использовать в качестве нижней границы при оценке всех возможных путей. Одно из них содержит переход (ij) (ему соответствует оценка g1 = d0 q1), другое (ij) (ему соответствует оценка g2 = d0 q2).