Построение математической модели задачи.

N- число городов.

C_ij,I,J=1..N-матрица затрат, где C_ij-затраты на переход из I – го города в j-й.

X_ij-Матрица переходов с компонентами:

X_ij=1, если коммивояжер совершает переход из I – го города в j – й,

X_ij=0, если не совершает перехода, где I,J= 1..N и I< >J

 

Критерий:

Ограничения имеют вид:

(2)

(3)

(4)

Доказательство, что модель (1-4) описывает задачу о коммивояжере.

Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) – вывезут в каждый город только один раз; условие (4) – обеспечивает замкнутость маршрута, содержавшего N городов, и не содержащего замкнутых внутренних петель.

Рассмотрим условие (4). Применим метод доказательства от противного, то есть предположим, что условие (4) выполняется для некоторого под цикла T из R городов, где R<N. Сложив все неравенства (4) вдоль этого под циклом получим

Так как

то

N-R≤(N-1), где R<N, R≠0.

Следовательно не существует замкнутого под цикла с числом городов меньшем N.

Покажем, что существует U_ij которое для замкнутого цикла начинающегося в некотором начальном пункте, удовлетворяют условию (4).

При всех X_ij (J – й город не посещается после i-го), а (4) имеем U_i-U_j≤N-1, что допустимо в силу произвольных U_i и U_j.

Пусть на некотором R-ом шаге i-й город посещается перед j-м, то есть X и J=1. В силу произвольности значений U_i и U_j положим U_i-R, а U_j=R-1, тогда из (4) имеем:

U_i-U_j N- X_ij≤R-(R-1)+N=N+1

Итак, существуют такие конечные значения для U_i и U_j, что для маршрута, содержащего N городов, условие (4) удовлетворяется как неравенство или строгое равенство. А, следовательно, модель (1-4) описывает задачу о коммивояжере.

2.3 Решение задачи вручную.

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

Верхняя строка и левый столбец, выделенные затемнённым фоном, содержат номера вершин графа; символ , стоящей на главной диагонали, означает, естественно, отсутствие рёбер – петель (начинающихся и заканчивающихся в одной и той же вершине); кроме того, символ здесь и всюду в дальнейшем обозначает «компьютерную бесконечность», т.е. самое большое из возможных в рассмотрении чисел; считается, что + любое число = .

Подсчитаем фи(Г) в нашем примере. Для этого выполним приведение матрицы весов; сначала- по строкам:

Таблица 1

						A

Результат приведения по строкам:

 

Таблица 2

Определим константы по столбцам:

Таблица 3

B

результат проведения матрицы:

Сумма констант приведения фи(Г)=2+4+4+4+3+1+1=19

 

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

Таблица 5

					0^3
	0^0		0^2
		0^2		0^1
					0^2
	0^2

 

M_l

 

 

Самым длинным оказывается ноль в клетке (1,5). Следовательно, множество Г разбивается на Г_(1,5)

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

 

 

Таблица 6

Переведём теперь эту матрицу:

Таблица 7

Это – матрица M_l,l; сумма констант приведения здесь равна 2, поэтому

Фи(1,5)=19+2=21

Для М_1,2 заменяем на элемент (1,5) в М_l:

Таблица 8

после этого приводим полученную матрицу:

 

 

таблица 9

 

Это матрица М_1.2; сумма констант последнего приведения равна 3, так что фи_{1,5}=19+3=22. Следовательно, дальнейшей разработке подвергается множество Г_{1,5}. Вот нулей матрицы М_1,1 (они указаны в скобках):

Таблица 10

	0^1		0^2
		0^2		0^0
				0^2

 

Самым длинным является ноль с номером (5,4) теперь следует рассматривать множества Г_(1,5)(5,4) и Г_(1,5){5,4}.

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

Следовательно, клетки с номерами (5,2),(5,3) и (4,1) надо заполнить символом ; после этого строку номер 4 и столбец 3 следует вычеркнуть; получим:

Таблица 11

 

Приведение этой матрицы:

Таблица 12

Для оценочной функции: Фи_(1,5)(5,4)=21+2=23.

Матрица для множества Г_(1,5){5,4}:

 

Таблица 13

 

 

Результат её приведения:

Таблица 14

 

Оценочная функция фи_(1,5){5,4}=21+2=23. Следовательно, дальнейшей разработке Г_{1,5}{5,4}Взвешиваем нули:

Таблица 15

	0^3		0^0
		0^3
		0^0	0^0

 

Выбираем любую из соответствующих клеток; для клетки (2,1).

Теперь речь пойдёт о множествах Г_{{1,5}{5,2}{2,1}} и Г_{{1,5}{5,4}{2,1}}.

Как и в преждней матрице вычеркнуть строку и столбец, в ней надо заменить на числа во всех тех клетках, которые соответствуют рёбрам, заведомо на принадлежащим тем гамильтоновым циклам, которые проходят через уже отобранные ранее рёбра. Поэтому для первого множества положим в последний матрице элемент с номером (3,2) равным , вычеркнем строку номер 2 и столбец номер 1:

 

Таблица 16

 

Приведём эту матрицу:

 

 

Таблица 17

Получаем для оценочной функции: фи_{{1,5}{5,4}{2,1}}=23+0=23.

 

Таблица 18

 

Приведение этой матрицы даёт:

Таблица 19

 

Для оценочной функции:фи_{{1,5}{5,4}{2,1}=23+0=23.}

Получилось, что для дальнейшей разработки можно брать Г_{{1,5}{5,4}{2,1}}.В первом случае уже получена матрица размером 2х2; её нулевые клетки дают рёбра, которые с найденными ранее составляют обход коммивояжера, причём вес этого обхода равен значению оценочной функции-23.

Вот этот обход:

(1,5)(5,4)(2,1)(3,2) или 1→5→4→3→2→1.

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

 

2.4 Решение задачи в Excel

Вид электронной таблицы, созданной для решения задачи, представлен на рис. 1. Значения переменных x_ij располагаются в блоке А1:Е5. В данном блоке ячейки, расположенные по диагонали обнулены (пункт назначения не может быть одновременно пунктом прибытия). Целевая функция расположена в ячейке H2.

Рис.1

							ЦФ

 

 

На рис. 2 в ячейках с А8:Е12 находятся функции переменных которые нужны для того, чтобы найти целевую функцию. Найдём сумму по каждому столбцу по формуле: (=СУММ(A8:A12)) эта формула используется в сумме последующих столбцах. Так же найдём сумму для строки по формуле: (=СУММ(A8:E8)) которая используется в последующих строчках.

Рис.2

На рисунке 3 ограничения находятся в строке В15:Е15. Формулы для ограничения находятся в ячейках В17:Е20

	-1
		=$B$15C15+5*C9	=$B$15D15+5*D9	=$B$15E15+5*E9
	=$C$15B15+5*B10		=$B$15D15+5*D10	=$B$15E15+5*E10
	=$D$15B15+5*B11	=$D$15C15+5*C11		=$B$15E15+6*E11
	=$E$15B15+5*B12	=$E$15C15+5*C12	=$B$15D15+5*D12

На рис. 4 находим сумму целевой функции по формуле показанной на рисунке.

 

 

Рис.4

							ЦФ
							=СУММПРОИЗВ(A1:E5;E12)

 

Через сервис открываем Поиск решения задав ограничения и параметры выводим целевую функцию. Рис.5

По результатам поиска решения найден ответ задачи: (см. рис. 6).

 

Рис.6

ЗАКЛЮЧЕНИЕ

В данной курсовой работе были рассмотрены основные теоретические вопросы по задаче коммивояжера. Приведено решение вручную задачи методом ветвей и границ (методом Литтла). Приведено решение задачи в среде MicroSoft Office Excel 2000. Изучено практическое применение задачи коммивояжера в экономике и производстве.

 

 

Список литературы

 

1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Высшая школа, 2004. – 208 с.

2. Исследование операций в экономике/ Под ред. Кремера Н.Ш. – М.:ЮНИТИ, 2004. – 407 с.

3. Конюховский П.В. Математические методы исследования операций в экономике. Краткий курс. – СПб.: Питер, 2002. – 208 с.

4. Просветов Г.И. Математические методы в экономике: Учебно-методическое пособие. – М.: Издательство РДЛ, 2004. – 160 с.

5. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. – М.: Вузовский учебник, 2004. – 144 с.

6. Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. – Мн.: Новое знание, 2003. – 424 с.

7. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.