Задача о коммивояжере

| Категория реферата: Рефераты по экономико-математическому моделированию
| Теги реферата: рефератов, женщины реферат
| Добавил(а) на сайт: Анисья.

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.

Критерий:

[pic] (1)

Ограничения:

[pic], i = 1..N (2)

[pic], 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