В. 50 Обоснование решения задачи о коммивояжере методом ветвей и границ (2 теоремы)

Когда решаем задачу предполагаем, что все цены с_ij≥0_.

u_i =min c_ij, j=1…n - в каждой i-ой строке найдем минимальное число и сделаем преобразование. Назначим новые цены.

с_ij’=с_ij-u_i вычитаем из с_ij минимальный элемент.

v_j=min с_ij’ j=1…n в каждом столбце ищем минимум

с_ij”= с_ij’-v_j. Новая матрица называется приведенной матрицей

- константа приведения.

Т1: решение задачи с матрицей с_ij’ совпадает с решением задачи с матрицей с.

Док-во: ;

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

Т2: Константа φ является нижней границей решения задачи, т.е оптимальное значение ≥φ (Z*≥φ). Z* - оптимальное значение целевой функции (если мы решаем задачу о коммивояжере, то ответ будет точно не меньше, чем это значение).

Док-во: с_ij”≥0 В частности последнее неравенство верно и для Z^*

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

Date: 2015-12-12; view: 404; Нарушение авторских прав