Лабораторная работа № 3

Тема лабораторной работы: Оптимизационные задачи линейного программирования с булевыми переменными и их решение средствами Excel.

Цель лабораторной работы: Получение навыков в решении задач коммивояжера

Программное обеспечение: Microsoft Excel

Основные сведения: Задача коммивояжера (в дальнейшем сокращённо - ЗК) является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации дискретных задач) ЗК служит своеобразным полигоном, на котором испытываются всё новые методы.

ЗК является NP-полной, и по тому имеет только один абсолютно точный класс алгоритмов – перебор вариантов. Этот класс вариантов решения самый долгий (по времени выполнения), и потому является самым невыгодным при решении задачи с большим количеством городов.

ЗК (коммивояжёр – бродячий торговец) заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило указывается, что маршрут должен проходить через каждый город только один раз, в таком случае выбор осуществляется среди гамильтоновых циклов. Гамильтоновым циклом в графе называют простой цикл, содержащий все вершины графа ровно по одному разу. Существует масса разновидностей обобщённой постановки задачи, в частности геометрическая задача коммивояжёра (когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Простейшие методы решения задачи коммивояжёра: полный лексический перебор, жадные алгоритмы (метод ближайшего соседа, метод включения ближайшего города, метод самого дешёвого включения), метод минимального остовного дерева. На практике применяются различные модификации более эффективных методов: метод ветвей и границ и метод генетических алгоритмов, а так же алгоритм муравьиной колонии.

Математическая постановка задачи: Коммивояжер должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Приведем задачу к математическому виду. Города перенумерованы числами jТ=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкой t=(j₁,j₂,..,j_n,j₁), причём все j₁..j_n – разные номера; повторяющийся в начале и в конце j₁, показывает, что перестановка зациклена. Расстояния между парами вершин С_ij образуют матрицу С. Задача состоит в том, что необходимо найти такой тур t, чтобы минимизировать функционал:

(1)

Относительно данной формулировки ЗК уместно сделать два замечания.

Во-первых, в постановке С_ij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jТ:

Сij0; Cjj=∞

(2)

(последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i,j:

Сij= Сji.

(3)

и удовлетворять неравенству треугольника, т.е. для всех:

Сij+ СjkCik

(4)

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если С_ij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому можно выделить два варианта ЗК: симметричную задачу, когда условие (3) выполнено, и несимметричную - в противном случае. Условия (2)-(4) по умолчанию мы будем считать выполненными.

Второе замечание касается числа всех возможных туров. В несимметричной ЗК все туры t=(j₁,j₂,..,j_n,j₁) и t’=(j₁,j_n,..,j₂,j₁) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.

Зафиксируем на первом и последнем месте в циклической перестановке номер j₁, а оставшиеся n номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t’.

Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j) проведено, если С_ij=1 и не проведено, если С_ij=0. Тогда, если существует тур длины n+1, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).

В терминах теории графов симметричную ЗК можно сформулировать так:

Дана полная сеть с n вершинами, длина ребра (i,j)= С_ij. Найти гамильтонов цикл минимальной длины.

В несимметричной ЗК вместо «цикл» надо говорить «контур», а вместо «ребра» - «дуги».

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

Пример решения задачи коммивояжера в программной среде Microsoft Excel:

Имеется 5 городов, расстояния C_ij между которыми приведены в табл.

Номер города	1	2	3	4	5
1	∞	9	8	4	10
2	6	∞	4	5	7
3	5	3	∞	6	2
4	1	7	2	∞	8
5	2	4	5	2	∞

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

Коммивояжер выезжая из города 1, должен посетить все города, побывав в каждом из них только по одному разу и вернуться в исходный город. Необходимо определить такой маршрут объезда городов, при которой длина маршрута будет минимальной.

Математическая модель: Переменные x_ij могут принимать значения равные либо 0, либо 1

  – целевая функция

ограничения:

– условие въезда в город j только один раз

 

– условие выезда из города i только один раз

, где n = 5, т.е. , i ≠ j, i, j = 2,…, n .

Исходные данные в рабочей книге Excel приведены на рис.1. Здесь же приведены формулы для вычисления ограничений и целевой функции.

Рис.1. Исходные данные в задаче коммивояжера (пример)

На панели Поиск решения установить следующие параметры решения задачи:

Целевую ячейку – $B$10

Равной минимальному значению

Изменяя ячейки: $B$4:$F$8;$C$11:$F$11 – здесь заносятся не только ячейки, которые будут изменяться, и в которых будут занесены решение задачи (ячейки с адресами $B$4:$F$8), но и ячейки $C$11:$F$11, содержащие переменные u_i , которые также являются изменяемыми.

Ограничения:

$B$21:$E$24≤3

$B$4:$F$8 = двоичное

$B$9:$F$9=1

$G$4:$G$8=1

$B$4=0

$C$5=0

$D$6=0

$E$7=0

$F$8=0

Параметры: линейная модель, неотрицательные значения, автоматическое масштабирование

После нажатия кнопки Выполнить на диалоговой панели Сервис-Поиск решения. На рабочем листе Excel появляются результаты решения задачи (рис.2).

ЗАДАЧА КОММИВОЯЖЕРА
	Матрица переменных					Ограничения
	1	2	3	4	5
1	0	0	0	1	0	1
2	1	0	0	0	0	1
3	0	0	0	0	1	1
4	0	0	1	0	0	1
5	0	1	0	0	0	1
Ограничения	1	1	1	1	1
Целевая функция в B10	18
Переменные u в C11:F11		3	1	0	2
	Матрица расстояний
	1	2	3	4	5
1	10000	9	8	4	10
2	6	10000	4	5	7
3	5	3	10000	6	2
4	1	7	2	10000	8
5	2	4	5	2	10000
Формулы для Ограничений по дополнительным переменным u
	u2	u3	u4	u5
u2	0	2	3	1
u3	-2	0	1	3
u4	-3	3	0	-2
u5	3	1	2	0

Рис. 2. Результаты решения задачи коммивояжера

Итак, оптимальное решение таково: целевая функция F = 18, получившийся маршрут: 1 – 4 – 3 – 5 – 2 – 1.

На основании полученных данных построить Гамильтонов граф с применением программы Grafoanalizator1.3.