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

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 01.10.2009
Размер файла 167,8 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

1

Реферат

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

В работе использовано 5 источников, она содержит 29 страниц, 2 приложения, программу, написанную на языке Си.

Содержание

  • Реферат
  • Содержание
  • Введение
  • 1.Постановка задачи о коммивояжере
  • 2. Метод ветвей и границ
  • 3. Использование верхних оценок
  • 4. Решение с заданной точностью
  • Заключение
  • Список используемой литературы
  • Приложение 1
  • Приложение 2

Введение

Проблема оптимизации является в определенном смысле, пожалуй, самой острой проблемой современности. В любой сфере деятельности человек всегда ищет оптимальное решение.

Существует класс задач, которые не удовлетворяют принципу оптимальности, и, следовательно, для этих задач метод динамического программирования непосредственно использован быть не может. Их решение требует развития специальных способов последовательного анализа вариантов. В частности, к такому классу задач относится задача о коммивояжере (бродячем торговце).

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

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

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

. (1)

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

Рис.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), и удовлетворяющих условию (), найти ломаную кратчайшей длины. Условие () состоит теперь в том, что искомая ломаная пересекает (в узле) каждую из прямых х = i один и только один раз.

Рис. 2.

Рассмотрим узел Р, лежащий на третьей вертикали (см. рис. 2). Если бы условие () отсутствовало, то выбор траектории, которая соединяет точку Р с точкой (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, удовлетворяющим условию (). Тогда величина будет простейшей нижней оценкой решения:

(5)

Будем рассматривать теперь задачу коммивояжера с матрицей С, которую мы будем называть приведенной матрицей.

Рассмотрим путь, содержащий непосредственный переход из города номера i в город номера j , тогда для пути s , содержащего этот переход, мы будем иметь, очевидно, следующую нижнюю оценку:

Следовательно, для тех переходов, для которых , мы будем иметь снова оценку (5). Естественно ожидать, что кратчайший путь содержит один из таких переходов - примем это соображение в качестве рабочей гипотезы. Рассмотрим один из переходов, для которого , и обозначим через множество всех тех путей, которые не содержат перехода из i в j. Так как из города i мы должны куда-то выйти, то множество содержит один из переходов i k, где ki; так как в город номера j мы должны прийти, то множество содержит переход т i, где т i. Следовательно, некоторый путь , из множества , содержащий переходы i k и т i , будет иметь следующую нижнюю оценку:

.

Обозначим через

Тогда очевидно, что для любого множества путей мы будем иметь оценку

(6)

Мы предполагаем исключить некоторое множество вариантов , поэтому мы заинтересованы выбрать такой переход ij, для которого оценка (6) была бы самой высокой. Другими словами, среди нулевых элементов матрицы С выберем тот, для которого максимально. Это число обозначим через . Таким образом, все множество возможных вариантов мы разбили на два множества I и I . Для путей из множества I, мы имеем сценку (5). Для путей из множества Iоценка будет следующей:

. (7)

Рассмотрим теперь множество I, и матрицу С. Так как все пути, принадлежащие этому множеству, содержат переход ij, то для его исследования нам достаточно рассмотреть задачу коммивояжера, в которой города номеров i и j совпадают. Размерность этой задачи будет уже равна N - 1, а ее матрица получится из матрицы С вычеркиванием столбца номера j и строки номера i.

Поскольку переход ij невозможен, то элемент принимаем равным бесконечности.

Рассмотрим случай N=3 (рис. 4, а) и предположим, что мы рассматриваем тот вариант, который содержит переход 32. Тогда задача коммивояжера после вычеркивания третьей строки и второго столбца вырождается в тривиальную. Ее матрица изображена на рис. 4, б). В этом случае мы имеем единственный путь, и его длина будет, очевидно, равна сумме

Итак, если в результате вычеркивания строки номера i и столбца номера j мы получим матрицу второго порядка, то задачу можно считать решенной.

Пусть теперь N > 3. После вычеркивания мы получим матрицу порядка N-1 >2. С этой матрицей (N-1)-го порядка совершим процедуру приведения. Матрицу, которую таким образом получим, обозначим через , а через - сумму ее констант приведения. Тогда для , мы будем иметь оценку

. (8)

На этом первый шаг алгоритма закончен. В результате одного шага мы разбили множество всех возможных вариантов на два множества , и для путей, принадлежащих этим множеством, мы получили оценки (8) и (7) (рис. 5).


Подобные документы

  • Особенности метода ветвей и границ как одного из распространенных методов решения целочисленных задач. Декомпозиция задачи линейного программирования в алгоритме метода ветвей и границ. Графический, симплекс-метод решения задач линейного программирования.

    курсовая работа [4,0 M], добавлен 05.03.2012

  • Сущность и особенности выполнения метода динамического программирования. Решение математической задачи, принцип оптимальности по затратам, ручной счёт и листинг программы. Применение метода ветвей и границ, его основные преимущества и недостатки.

    курсовая работа [38,9 K], добавлен 15.11.2009

  • Постановка линейной целочисленной задачи. Метод отсекающих плоскостей. Дробный алгоритм решения полностью целочисленных задач. Эффективность отсечения Гомори. Сравнение вычислительных возможностей метода отсекающих плоскостей и метода ветвей и границ.

    курсовая работа [178,2 K], добавлен 25.11.2011

  • Основные этапы решения транспортной задачи, использование метода потенциалов. Алгоритм решения методом аппроксимации Фогеля. Процедура построения цикла. Планирование перевозок из конечного числа пунктов отправления в конечное число пунктов назначения.

    контрольная работа [32,6 K], добавлен 26.04.2011

  • Определение наиболее выгодного соотношения сортов сырой нефти, используемой для производства бензина. Математическая постановка задачи. Выбор метода решения задачи. Описание алгоритма решения задачи (симплекс-метода) и вычислительного эксперимента.

    курсовая работа [1,1 M], добавлен 08.12.2010

  • Постановка и решение дискретных оптимизационных задач методом дискретного программирования и методом ветвей и границ на примере классической задачи коммивояжера. Этапы построения алгоритма ветвей и границ и его эффективность, построение дерева графов.

    курсовая работа [195,5 K], добавлен 08.11.2009

  • Поиск верхних и нижних границ для оптимального значения на подобласти допустимых решений. Методы и проблемы решения задач нелинейного программирования. Написание и отладка программы. Создание программы для решения задачи "коммивояжёра" прямым алгоритмом.

    курсовая работа [176,9 K], добавлен 22.01.2016

  • Концептуальная модель операции. Математическая постановка задачи. Описание метода ветвей и границ, прямого перебора. Проектирование сценария диалога. Описание структур данных. Ручная реализация решения задачи с помощью алгоритма Литла и перебора.

    курсовая работа [202,6 K], добавлен 14.12.2013

  • Сущность теории графов и сетевого моделирования. Выбор оптимального пути и стоимости переезда коммивояжера с помощью метода ветвей и границ. Разработка программы выбора самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу.

    курсовая работа [3,5 M], добавлен 08.08.2013

  • Классы задач P и NP, их сводимость. Примеры NP-полных и NP-трудных задач. Сущность метода поиска с возвратом. Алгоритмы решения классических задач комбинаторного поиска. Решение задачи о восьми ферзях. Поиск оптимального решения методом ветвей и границ.

    презентация [441,5 K], добавлен 19.10.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.