Требования к отчету

Отчет должен содержать:

а) постановку задачи;

б) последовательность решений (кончая оптимальным) и их стои­мостей;

в) обоснование действий по улучшению начального решения;

г) ответы на контрольные вопросы.

Контрольные вопросы

1. Почему базисное решение должно содержать m+n-1компонент?

2. Приведите пример транспортной задачи, одно из базисных ре­шений которой содержит нулевые компоненты.

3. Почему один из потенциалов можно положить равным О?

4. Почему характеристические разности вычисляются только для небазисных клеток?

5. Почему величина перераспределяемого потока определяется формулой (5.6)?

Лабораторная работа 6 задача 0 коммивояжере

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

Постановка задачи

Коммивояжер должен побывать в каждом из nгородов в точности по одному разу и закончить свое путешествие в том городе, откуда

- 25 -

он его начал. Задача коммивояжера состоит в минимизации суммарных дорожных расходов.

Формально она может быть поставлена так:

Минимизировать

при условиях

(6.1)

(6.2)

перестановка

(6.3)

где (i₁, j₁), ..., (i_n, j_n) -индексы ненулевых переменныхX_ij

не содержит внутренних циклов.

Здесь

C_ij- стоимость переезда изi-го города вj-й,

1, если путь из i-го городаj-й включается в марш-

X_ij = ­рут коммивояжера,

О, иначе.

Краткие общие сведения

Поставленная задача очень напоминает задачу о назначениях и отличается от последней лишь наличием дополнительного условия (6.3). Это обстоятельство, однако, делает ее нелинейной и не позволяет применить к ее решению методы линейного программирования (служащие, в частности, базой классического "венгерского" метода решения за­дачи о назначениях). Тем не менее, задача коммивояжера может ус­пешно решаться с помощью весьма общего метода решения переборных задач - метода ветвей и границ.

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

- 26 -

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

а) если оценка снизу целевой функции на каком-либо подмножест­ве больше, чем "рекорд", то соответствующее подмножество можно ис­ключить из дальнейшего рассмотрения;

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

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

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

а) способ выбора очередного подмножества, подлежащего разбие­нию, и правило, по которому оно осуществляется.

б) метод получения оценки.

1. Правило разбиения:

а) любое подмножество разбивается на две части;

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

в) правило выбора упомянутого пути будет приведено ниже.

2. Способ получения оценки снизу стоимости маршрутов, входящих в подмножество.

Подмножество маршрутов удобно кодировать с помощью пары:

а) (i⁽¹⁾,j⁽¹⁾), ..., (i^(l),j^(l))- набора путей, включаемых во все маршруты подмножества;

б) матрицы вида:

	j1		jn-l+1
i1	C'i1,j1		C'i1,jn-l+1
...	...
in-l+1	C'in-l+1,j1	...	C'in-l+1,jn-l+1

- 27 -

Здесь {i₁,i₂,...,i_n-l+1} = {1,2,...,n} \ {i⁽¹⁾,i⁽²⁾,...,i^(l)}- номера городов, для которых в рамках данного подмножества остается откры­тым вопрос о том, куда из них двигаться; аналогичный смысл имеет множество{j₁,j₂,...,j_n-l+1}. ЧислаC'_ip,jq- это модифицированные стоимости переездов (см.ниже). Некоторые из них могут быть равны бесконечности, что означает запрет движения по соответствующим путям.

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

1. Редуцировать матрицу стоимостей, т.е. последовательно вы­честь из каждой строки ее минимальный элемент, после чего осущест­вить ту же процедуру применительно к столбцам. Сумма вычитаемых в процессе редукции чиселХ – редукционная сумма - даст искомую оценку.

2. Для каждого из нулевых элементов редуцированной матрицы С'_ij вычислить

3. Осуществить разбиение по тому пути, для которого величина Δ_ijмаксимальна.

4. В подмножестве маршрутов, исключающих путь (i, j),соответ-ствующую стоимость положить равной бесконечности и провести редук-цию поi-й строке иj-му столбцу. СуммаX + Δ_ij даст оценку снизу.

5. В подмножестве маршрутов, включающих путь (i, j), осущест-вить следующую последовательность действий:

а) вычеркнуть элементы i-й строки иj -го столбца;

б) найти путь, движение по которому может привести к образова­нию внутреннего цикла, и положить его стоимость равной бесконеч-нос­ти (в простейшем случае, в частности, при разбиении исходного мно­жества, - это путь (j,i));

в) провести редукцию получившейся матрицы;

г) добавить редукционную сумму к Xи получить оценку снизу для рассматриваемого подмножества.

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

- 28 –