Задача комивояжера

Содержание

Введение

1 Дискретные оптимизационные задачи              5

1.2 Постановка задач дискретного программирования              5

1.3 Алгоритм метода ветвей и границ              6

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

3 Задача коммивояжера методом динамического программирования              9

4 Задача коммивояжера методом ветвей и границ

Заключение……………………………………………………………………….18

Список использованных источников              20

Введение

Дискретная оптимизация как раздел математики существует достаточно давно. Оптимизация - это выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. По этому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.

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

Возьмем пример: человек вышел утром из дому, чтобы ехать на работу. По ходу дела ему приходится принять целый ряд решений: брать ли с собой зонтик? В каком месте перейти улицу? Каким видом транспорта воспользоваться? И так далее. Разумеется, все эти решения человек принимает без специальных расчетов, просто опираясь на имеющийся у него опыт и на здравый смысл. Для обоснования таких решений никакая наука не нужна, да вряд ли понадобится и в дальнейшем.

Однако возьмем другой пример. Допусти, организуется работа городского транспорта. В нашем распоряжении имеется какое-то количество транспортных средств. Необходимо принять ряд решений, например: какое количество и каких транспортных средств направить по тому или другому маршруту? Как изменять частоту следования машин в зависимости от времени суток? Где поместить остановки? И так далее.

Эти решения являются гораздо более ответственными, чем решения предыдущего примера. В силу сложности явления последствия каждого из них не столь ясны; для того, чтобы представить себе эти последствия, нужно провести расчеты. А главное, от этих решений гораздо больше зависит. В первом примере неправильный выбор решения затронет интересы одного человека; во втором - может отразиться на деловой жизни целого города.

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

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

1 Дискретные оптимизационные задачи

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

для анализа происходящих там процессов. Необходимость решения

таких задач приводит к тому, что дискретная оптимизация становится важным элементом образования специалистов, связанных с её

применением при решении задач, возникающих в приложениях. Поэтому нам представляется, что технология решения задач дискретного

программирования должна стать одной из важных составных частей

современного математического образования для специалистов по прикладной математике.

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

1.2 Постановка задач дискретного программирования

Под задачей дискретного программирования (дискретной оптимизации) понимается задача математического программирования

F(x0) = min f(x), x є G,

множество допустимых решений которой конечно, т.е. О ≤ |G| =  N < ∞, где |G| — число элементов множества G. В силу конечности G все допустимые решения можно пронумеровать: x1, x2, . . . . ., xN, вычислить f(xi), i= 1,2,..., N, и найти наименьшее значение.

Во многих задачах условия дискретности отделены от других условий, т.е. если х = (х1, х2, ... ,хn), то xj є Gj = (х j 1, хj2, ...,хjki), kj > 2. Поэтому N = = = > 2n, отсюда видно, что с ростом числа переменных объем вычислительной работы резко возрастает.

1.3 Алгоритм метода ветвей и границ

Рассмотрим задачу в виде:

f(x0)=min f(x), x є G, |G|=N < ∞.

Алгоритм ветвей и границ основан на следующих построениях, позволяющих уменьшить объем перебора.

1.      Вычисление оценки. Пусть G' G, тогда φ(G') называется нижней

оценкой, если для любого х є G' выполняется неравенство f(x) ≥ φ(G').

2.      Ветвление (разбиение множества G на подмножества). Положим

G0 = G и разобьем множество G0 на r1 непересекающихся подмножеств

G0 =      , i ≠ j.

Этот шаг алгоритма считаем начальным, имеющим номер 0. Рассмотрим шаг алгоритма с номером k. Пусть — множества, еще не подвергавшиеся разбиению. Выберем одно из этих множеств и разобьем его на непересекающиеся подмножества:

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

Эти множества образуют список задач для ветвления. Выберем одно из них и снова повторим процедуру разбиения.

Описанную процедуру разбиения можно представить в виде дере-

дерева (рис. 1)

Рис. 1

3.      Пересчет оценок. Если G1 G2, то

Поэтому, разбивая в процессе ветвления подмножество G’ G на непересекающиеся подмножества G's, G' = , будем

предполагать, что φ(G1’)  ≥  φ (G’), причем хотя бы для некоторых номеров i0 выполняется строгое неравенство φ()  ≥  φ (G’).

4.      Вычисление планов (допустимых решений). Если на шаге ветвления

с номером k известен план хk, на шаге с номером (k + 1) — план хk+1 и если f(xk+1) < f(xk), то план хk забывается и вместо него сохраняется план хk+1. Наилучшее из полученных допустимых решений принято называть рекордом.

5.      Признак оптимальности. Пусть G = . Тогда план является

оптимальным, т.е. , если выполняется условие

f() = φ(Gv) ≤ φ(Gi), i=1, 2, . . . . , s.

6.      Оценка точности приближенных решений. Пусть G = ,

φ0 = φ(Gj), xk — рекорд; тогда имеет место следующее неравенство:

φ0 ≤ f(x0) ≤ f(xk).

Разность ∆ = f(xk) - φ0  является оценкой гарантированного отклонения рекорда хk от оптимума х0. Из приведенного неравенства следует, что для ветвления необходимо выбрать множество с минимальным значением нижней оценки.

7.     Правило отсева. Пусть снова G = , x0 — оптимум,

хk — рекорд. Если  φ(Gr) > f(xk), то множество Gr можно отсеять, т.е. исключить из дальнейшего рассмотрения, так как оно не может содержать оптимальных решений. Действительно, пусть x є G; тогда в силу определения оценки f(x) ≥ φ(G') имеем f(x) ≥ φ(Gr) > f(xk) ≥ f(x0).

Правило φ(Gr) > f(xk) гарантирует, что в процессе работы алгоритма ни

одно из подмножеств Gr, в которых содержится точное решение x0, не будет отсеяно. Более сильное правило φ(Gr) ≥ f(xk) гарантирует, что хотя бы одно оптимальное решение будет найдено, оно и применяется при практическом решении задач.

8.      Конечность алгоритма. Конечность алгоритма следует из

конечности множества G.

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

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

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

Классическая задача коммивояжера (ЗК) формулируется следующим образом: имеется полный взвешенный ориентированный граф без петель G с множеством вершин N = {1, 2,…, n}; веса всех дуг неотрицательны; в этом графе требуется найти гамильтонов цикл минимального веса.

Исходную информацию по ЗК считаем представленной в виде матрицы размера nxn. S = {sij}, где sij – вес дуги (i, j) графа G, i = , j = , i ≠ j; все элементы главной диагонали матрицы S являются нулями.

В типовой интерпретации вершины 1, 2,…, n графа G – это города. Дуги отображают возможные элементарные переходы. Коммивояжеру, изначально находящемуся в городе 1, необходимо обойти все остальные города, побывав в каждом из них ровно по одному разу, и затем вернуться в город 1. Веса дуг графа трактуются как длины соответствующих элементарных переходов. Требуется найти имеющий минимальную длину допустимый (т.е. удовлетворяющий наложенным требованиям) маршрут коммивояжера. С учетом других возможных интерпретаций, на матрицу S требование симметричности не налагается, не считается обязательным и выполнение неравенства треугольника.

3 Задача коммивояжера методом динамического программирования

Под методом ветвей и границ понимается алгоритм решения зада-

задачи, имеющий древовидную структуру поиска оптимального решения

и использующий результаты решения оценочных задач. Древовидная

структура называется обычно деревом ветвления.

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

Пусть i – произвольный город (i  N), а V – любое подмножество городов, не содержащее города 1 и города i. Через М(i, V ) обозначим совокупность путей, каждый из которых начинается в городе i, завершается в городе 1 и проходит в качестве промежуточных только через города множества V, заходя в каждый из них ровно по одному разу. Через В(i, V ) обозначим длину кратчайшего пути множества М(i, V ). Для решаемой задачи В(i, V ) – функция Беллмана. Как очевидно, В(1, {2, 3, …, n}) – искомая минимальная длина простого (без самопересечений) замкнутого пути, проходящего через все города.

Если V – одноэлементное множество, V ={j}, где j ≠ 1 и j ≠ i, то совокупность М (i, V) состоит из единственного пути µ   = (i, j, 1). Поэтому

       i N,  j  {2, 3,…, n},   j ≠ i.              (1.1)

Предположим, что значения функции В(i, V ) для всех i N \ {1} и всех возможных k-элементных (k < n – 1) множеств V уже вычислены. Тогда значение В(i, V'), где V' – произвольное (k + 1)-элементное подмножество совокупности N \ {1, i}, вычисляется по формуле

(1.2)

Уравнения (1.1)–(1.12) – рекуррентные соотношения динамического программирования для решения задачи коммивояжера, они обеспечивают реализацию обратного метода Беллмана. Вычислительная сложность задачи равна ,где С – произвольная константа (С > 0), n – число городов.

Пример 1.1 Решить задачу коммивояжера, определяемую матрицей:

Сначала, пользуясь формулой (1.1), определяем значения В(i, {j}):

В(2, {3}) = 5 + 6 = 11;    В(3, {2}) = 2 + 2 = 4;        В(4, {2}) = 5 + 2 = 7;

      В(2, {4}) = 2 + 1 = 3;       В(3, {4}) = 1 + 1 = 2;        В(4, {3}) = 4 + 6 = 10.

Далее по формуле (1.2) последовательно получаем (в левой части каждого из ниже записанных равенств выделены те значения параметра j, на которых при подсчете реализуется указанный в правой части (1.2) минимум):

В(2, {3, 4}) = min [s23 + B(3,{4}); s24 + B(4,{3})] = min(5 + 2; 2 + 10)=7;

В(3, {2, 4}) = min [s32 +B(2,{ 4}); s34 + B(4,{ 2})] = min(2 + 3; 1 + 7 )=5;

В(4, {2, 3}) = min [s42 + B(2,{ 3}); s43 + B(3,{ 2})] = min(5 + 11; 4 +4)=8;

В(1, {2, 3, 4}) = min [s12 + B(2,{3,4}) s13 + B(3,{ 2,4}) s14 + B(4,{2,3 })] =