/>Реферат
В данной работе изложены основныепринципы решения транспортной задачи, в частности ¾ задача о коммивояжере.
В работе использовано 5 источников,она содержит 29 страниц, 2 приложения, программу, написанную на языке Си.
/>Содержание
Реферат
Содержание
Введение
1.Постановка задачи окоммивояжере
2. Метод ветвей и границ
3. Использование верхних оценок
4. Решение с заданной точностью
Заключение
Список используемой литературы
Приложение 1
Приложение 2
Введение
Проблема оптимизации является вопределенном смысле, пожалуй, самой острой проблемой современности. В любойсфере деятельности человек всегда ищет оптимальное решение.
Существует класс задач, которые неудовлетворяют принципу оптимальности, и, следовательно, для этих задач методдинамического программирования непосредственно использован быть не может. Ихрешение требует развития специальных способов последовательного анализавариантов. В частности, к такому классу задач относится задача о коммивояжере(бродячем торговце).
Данная работа описывает нахождениеоптимального решения задачи о коммивояжере, применяя метод ветвей и границ.
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/>определяет новую задачу коммивояжера, которая,однако, в качестве оптимальной будет иметь ту же последовательность городов.Между величинами /> и />будет существовать, очевидно,следующая связь:
/>
Заметим, что в каждой из строкматрицы C/>будет теперь, по крайней мере, одиннулевой элемент. Далее обозначим через /> наименьший элемент матрицы C/>, лежащий в столбце номера j, и построим новую матрицу С/>с элементами
/>
Величины h/>и /> называются константами приведения. Оптимальнаяпоследовательность городов для задачи коммивояжера с матрицей С/>будет, очевидно, такойже, как и для исходной задачи, а длины пути для варианта номера s в обеихзадачах будут связаны между собой равенством
/>, (3)
Где
/>, (4)
т.е. />равна сумме констант приведения.
Обозначим через l * решение задачи коммивояжера, т. е.
/>,
где минимум берется по всем вариантамs, удовлетворяющим условию (a). Тогда величина /> будет простейшей нижнейоценкой решения:
/> (5)
Будем рассматривать теперь задачукоммивояжера с матрицей С/>, которую мы будем называтьприведенной матрицей.
Рассмотрим путь, содержащийнепосредственный переход из города номера i в город номера j, тогда для пути s, содержащего этот переход, мы будем иметь, очевидно,следующую нижнюю оценку:
/>
Следовательно, для тех переходов, длякоторых />,мы будем иметь снова оценку (5). Естественно ожидать, что кратчайший путьсодержит один из таких переходов — примем это соображение в качестве рабочейгипотезы. Рассмотрим один из переходов, для которого />, и обозначим через /> множество всех техпутей, которые не содержат перехода из i в j. Таккак из города i мы должны куда-то выйти, томножество /> содержитодин из переходов i ® k, где k¹i; таккак в город номера j мы должныприйти, то множество /> содержит переход т® i, где т¹ i. Следовательно, некоторый путь />, из множества />, содержащий переходы i ® k и т® i, будет иметь следующую нижнююоценку:
/>.
Обозначимчерез
/>
Тогда очевидно, что для любого /> множествапутей /> мыбудем иметь оценку
/> (6)
Мы предполагаем исключить некотороемножество вариантов />, поэтому мы заинтересованывыбрать такой переход i®j, длякоторого оценка (6) была бы самой высокой. Другими словами, среди нулевыхэлементов матрицы С/>выберем тот, для которого /> максимально.Это число обозначим через />. Таким образом, все множествовозможных вариантов мы разбили на два множества I/>и I/>. Для путей из множества I/>, мы имеем сценку (5). Для путей из множества I/>оценка будет следующей:
/>. (7)
Рассмотрим теперь множество I/>, и матрицу С/>. Так как все пути, принадлежащиеэтому множеству, содержат переход i®j, то для его исследования нам достаточно рассмотреть задачу коммивояжера,в которой города номеров i и j совпадают. Размерность этой задачибудет уже равна N — 1, а ее матрица получится из матрицы С/>вычеркиванием столбцаномера j и строки номера i.
Поскольку переход i®j невозможен, то элемент />принимаемравным бесконечности.
Рассмотрим случай N=3 (рис. 4, а) и предположим, что мырассматриваем тот вариант, который содержит переход 3®2. Тогда задача коммивояжера послевычеркивания третьей строки и второго столбца вырождается в тривиальную. Еематрица изображена на рис. 4, б). В этом случае мы имеем единственный путь, иего длина будет, очевидно, равна сумме
1
3
1 ¥ C1
2 C2 ¥
Рис. 4б.
1
2
3
1 ¥ С1 С1
2 С2 ¥ С2
3 С3 С3 ¥
Рис. 4а. />
Итак, если в результате вычеркиваниястроки номера i и столбца номера j мы получим матрицу второго порядка,то задачу можно считать решенной.
Пусть теперь N > 3. После вычеркивания мы получим матрицу порядка N-1 >2. С этой матрицей (N-1)-го порядка совершим процедуруприведения. Матрицу, которую таким образом получим, обозначим через />, а через /> - сумму ее констант приведения. Тогда для />, мы будемиметь оценку
/>. (8)
На этом первый шаг алгоритмазакончен. В результате одного шага мы разбили множество всех возможныхвариантов на два множества />, и для путей, принадлежащих этиммножеством, мы получили оценки (8) и (7) (рис. 5).
_ EMBED Equation.3 ___
_ EMBED Equation.3 ___
_ EMBED Equation.3 ___ _ EMBED Equation.3 ___ _ EMBED Equation.3 ___ _ EMBED Equation.3 ___ _ EMBED Equation.3 /> />
/> />