Основные принципы решения транспортной задачи

1.Постановка задачи о коммивояжере

Рассмотрим задачу о коммивояжере (бродячем торговце). Предположим, что бродячий торговец должен, покинув город, которому мы присвоим номер 1 (рис. 1), объехать еще N-1 городов и вернуться снова в город номер 1. В его распоряжении есть дороги, соединяющие эти города. Он должен выбрать свой маршрут - порядок посещения городов так, чтобы путь, который ему придется пройти, был как можно короче. Основное условие этой задачи состоит в том, что коммивояжер не имеет права возвращаться снова в тот город, в котором он однажды уже побывал. Это условие будем называть условием (a). Мы считаем, что расстояние между двумя городами - функция - определено. Разумеется, функция может означать не только расстояние, но, например, время или издержки в пути и т. д. Поэтому в общем случае , а функции естественно приписать значение ¥. Длина l пути S определяется формулой:

. (1)

Сумма в выражении (1) распространена по всем индексам i и j, удовлетворяющим условию (a), т. е. условию, что каждый из индексов i и j входит в выражение (1) один и только один раз. Функция является, таким образом, аддитивной - она представима в виде суммы слагаемых, однако сама задача - задача отыскания минимума l - в силу ограничения (a) не является аддитивной и не удовлетворяет принципу оптимальности.

Рис.1.

Рассмотрим плоскость t, х, где t - дискретный аргумент, принимающий значения

0, 1, 2, . . . , N, соответствующие этапам путешествия бродячего торговца. Значение t=0 соответствует его начальному положению в городе номер 1, t - 1 - переходу из города номер 1 в город, который он выбрал первым для посещения, и т. д., t = N означает последний этап его путешествия - возвращение в город номер 1. Аргумент х теперь также принимает дискретные значения 1, 2,. . . , N (рис. 2). Соединим точку (0,1) с точками (1,1), (1,2), ..., (,1N) и длинам отрезков, соединяющих эти точки, припишем значения . Далее точки (1, s) - узлы, лежащие на первой вертикали, мы соединим со всеми узлами второй вертикали, длинам отрезков мы припишем значения и т. д. Точки (N-1, s) соединим с точкой (N, 1). В результате мы построили некоторый граф, каждая ломаная которого, соединяющая точку (0,1) с точкой (N, 1), описывает путь коммивояжера. Нашу задачу мы можем теперь сформулировать следующим образом. Среди всех ломаных, принадлежащих этому графу и соединяющих точки (0,1) и (N,1), и удовлетворяющих условию (a), найти ломаную кратчайшей длины. Условие (a) состоит теперь в том, что искомая ломаная пересекает (в узле) каждую из прямых х = i один и только один раз.

Рис. 2.

Рассмотрим узел Р, лежащий на третьей вертикали (см. рис. 2). Если бы условие (a) отсутствовало, то выбор траектории, которая соединяет точку Р с точкой (N, 1), не зависел бы от того пути, который привел нас в точку Р. В данном случае ситуация иная, и если два коммивояжера находятся в точке Р, но один из них пришел в это состояние, двигаясь вдоль траектории, проходящей через точку Q, а второй через точку R, то их состояния существенно отличаются друг от друга. Коммивояжер, который двигался по второй траектории, уже побывал в городах номер 2 и номер 5 и в будущем он уже не имеет права снова заезжать, в эти города. Что касается коммивояжера, который двигался вдоль первой траектории, то он побывал в городах номер 3 и номер 6; он не имеет права возвращаться в эти города, но зато он еще обязан посетить города номер 2 и номер 5 и т.д.

Поскольку функция определена на конечном множестве точек, то и функция также определена на конечном множестве точек. Следовательно, задача определения минимума функции l сводится к перебору некоторого конечного множества значений этой функции, и проблема носит чисто вычислительный характер. Однако именно вычислительные трудности здесь огромны. Легко подсчитать, что число возможных вариантов (число значений функции l) равно (N-1)!. Таким образом, непосредственно перебрать и сравнить между собой все возможные пути, по которым может следовать бродячий торговец, для достаточно большого количества городов практически невозможно. Возникает проблема построения такого метода последовательного анализа вариантов, который выделял бы по возможности большое количество неперспективных вариантов и сводил задачу к перебору относительно небольшого количества "подозрительных" вариантов.

2. Метод ветвей и границ

Основа этого, ныне широко распространенного метода состоит в построении нижних оценок решения, которые затем используются для отбраковки неконкурентоспособных вариантов.

Функция принимает конечное число значений , которые мы можем представить в виде таблицы (рис. 3). Предположим, что мы выбрали некоторый путь S. Его длина будет равна

(2)

причем сумма (2) распространена по i, j так, что каждый из индексов встречается в ней один и только один раз. Величины с двумя одинаковыми индексами мы приняли равными ¥.

Так как в каждый из вариантов s входит только один элемент из каждой строки и столбца, то мы можем проделать следующую операцию, которая здесь называется приведением матрицы. Обозначим через h, наименьший элемент из строки номера i и построим новую матрицу C элементами

.

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

Заметим, что в

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать