НОВОСТИ   БИБЛИОТЕКА   ЮМОР   КАРТА САЙТА   ССЫЛКИ   О САЙТЕ  




предыдущая главасодержаниеследующая глава

в) Задача о коммивояжере (бродячем торговце)

Имеется n + 1 городов и заданы расстояния между ними cij. Выезжая из одного города (обозначаемого индексом 0), коммивояжер должен побывать в каждом городе по одному разу и вернуться в город 0. Требуется определить порядок, в котором следует объезжать города, чтобы суммарное расстояние было бы минимальным. Если ввести переменные


то данная задача сведется к следующей:


где


Условия (18-30) и (18-31) означают, что коммивояжер один раз выезжает из каждого города и въезжает в каждый город один раз. Соотношения (18-29), (18-30) и (18-31) определяют задачу о назначении, которая отличается от задачи коммивояжера отсутствием требования цикличности пути решения.

Аналитически требование цикличности записывается в виде (18-32), где переменные ui могут принимать произвольные вещественные значения. Допустим обратное: имеется подцикл τ с числом ребер k < n, не проходящий через город 0. Складывая все неравенства (18-32) при xij = 1 вдоль подцикла τ, получаем противоречивое неравенство: nk ≤ (n - 1) k, так как все разности ui-uj уничтожаются. Таким образом, условие (18-32) не допускает цикла, не проходящего через город 0. Покажем, что можно выбрать значения uif при которых для цикла, проходящего через город 0 (i = 0), удовлетворяются соотношения (18-32). Для этого предположим, что ui = p, если город i посещается на р-м шаге, где р = 1, 2, ..., n. Очевидно, при этом ui-uj≤n-1 для любых i и j. Тем самым доказано, что соотношения (18-32) для xij = 0 удовлетворяются. При xij = 1 эти соотношения превращаются в равенства. Действительно, учитывая (18-28), имеем:

ui-uj+nij=p-(p+1)+n=n-1 (18-33)

Задача о коммивояжере из-за условия цикличности не сводится к транспортной и является типичной задачей дискретной математики с резко выраженными комбинаторными свойствами.

предыдущая главасодержаниеследующая глава








© Злыгостев А.С., 2001-2019
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'
Рейтинг@Mail.ru
Поможем с курсовой, контрольной, дипломной
1500+ квалифицированных специалистов готовы вам помочь