Реферат

В данной работе изложены основные принципы решения транспортной задачи, в частности ¾ задача о коммивояжере.

В работе использовано 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) - узлы, лежащие на первой вертикали, мы соединим со всеми узлами второй вертикали, длинам отрезков мы припишем значения и т. ............