Читать реферат по эконометрике: "Задача о коммивояжере" Страница 3


назад (Назад)скачать (Cкачать работу)

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

считается очевидно неоптимальным и отсекается, иначе остается до следующей итерации.Находится множество с лучшей нижней оценкой (прогнозом) и дробится на количество равное размерность исходной матрицы минус количество уже пройденных (фиксированных для данного множества) городов.Находятся минимальные верхняя и нижняя оценка. Если они равны и достигнуты на одном и том же множестве, то это значит, что получено оптимальное решение и алгоритм заканчивает работу, иначе возврат к шагу 2.

Математическая модель задачи

N - число городов.

Ci j , i, j=1..N - матрица затрат, где Ci j - затраты на переход из i-го города в j-й. Xi j - матрица переходов с компонентами: Xi j = 1, если коммивояжер совершает переход из i-го города в j-й,

Xi j = 0, если не совершает перехода, где i, j = 1..N и i¹j. Критерий:(1) Ограничения: , i = 1..N(2)

, j = 1..N(3)

Ui - Uj + N × Xi j £ N-1,i, j = 1..N, i ¹ j.(4)

Доказательство, что модель (1-4) описывает задачу о коммивояжере: Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) - въезжает в каждый город только один раз; условие (4) - обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель.

Рассмотрим условие (4). Применим метод доказательства от противного, то есть предположим, что условие (4) выполняется для некоторого подцикла T из R городов, где R



Интересная статья: Основы написания курсовой работы