Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Курсовая работа - Решение задачи коммивояжера - файл 2.2, 2.1, 2.2, 2.3 стр19.doc


Курсовая работа - Решение задачи коммивояжера
скачать (194.4 kb.)

Доступные файлы (21):

1.1, 1.2 стр5.doc34kb.20.01.2009 14:21скачать
1.1 стр4.doc32kb.26.12.2005 12:31скачать
1.2 стр6.doc27kb.20.01.2009 14:23скачать
1.2 стр7.doc25kb.20.01.2009 14:23скачать
1.3 стр8.doc54kb.20.01.2009 14:24скачать
1.4 стр9.doc27kb.20.01.2009 14:25скачать
1.6 стр15.doc33kb.20.01.2009 14:27скачать
1.6 стр16.doc30kb.20.01.2009 14:26скачать
2.2, 2.1, 2.2, 2.3 стр19.doc322kb.01.06.2009 20:20скачать
2.4 стр20.doc33kb.01.06.2009 20:19скачать
2.4 стр21.doc25kb.20.01.2009 14:16скачать
2.5 стр22.doc25kb.20.01.2009 14:16скачать
2.5 стр23.doc25kb.20.01.2009 14:16скачать
2.5 стр24.doc25kb.20.01.2009 14:16скачать
2.5 стр25.doc23kb.20.01.2009 14:16скачать
Введение стр2.doc35kb.20.01.2009 14:17скачать
Введение стр3.doc24kb.20.01.2009 14:17скачать
Заключение стр24.doc24kb.20.01.2009 14:18скачать
Лист задания.doc33kb.07.12.2004 11:35скачать
Литература стр26.doc25kb.20.01.2009 14:19скачать
Приложение стр25.doc48kb.20.01.2009 14:19скачать

2.2, 2.1, 2.2, 2.3 стр19.doc

2 ПОСТАНОВКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ
2.1 Содержательная постановка задачи
Молочный комбинат осуществляет поставку своей продукции в ряд торговых точек города автомобильным транспортом. Требуется определит маршрут минимальной длины доставки продукции во все торговые точки и возврата на комбинат для очередной загрузки транспортного средства. Расстояние торговыми точками известны (км) и представлены в таблице 1
Таблица 1

i j

1

2

3

4

5

1

0

5

7

9

2

2

4

0

5

7

6

3

7

4

0

5

8

4

6

6

7

0

4

5

3

7

8

5

0


^ 2.2 Построение математической модели задачи
N – число городов.

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

Xi j – матрица переходов с компонентами:

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

Xi j = 0, если не совершает перехода,

где i, j = 1…N и ij.

Критерий:

(1)

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

, i = 1…N (2)

, j = 1…N (3)

Ui – Uj + N  Xi j  N–1, i, j = 1…N, i  j (4)

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

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

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



Так как



то N  R  (N – 1), где R<N, R  0

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

Покажем, что существует Ui, которое для замкнутого цикла, начинающегося в некотором начальном пункте, удовлетворяет условию (4). При всех Xi j (j-й город не посещается после i-го) в (4) имеем Ui – Uj  N – 1, что допустимо в силу произвольных Ui и Uj.

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

Ui – Uj + N  Xi j  R – (R – 1) + N = N – 1

Итак, существуют такие конечные значения для Ui и Uj, что для маршрута, содержащего N городов, условие (4) удовлетворяется как неравенство или строгое равенство, а следовательно, модель (1 – 4) описывает задачу о коммивояжере.
^ 2.3 Решение задачи вручную
Целевая функция имеет вид:

0+5+7+9+2+4+0+5+7+6+7 +4+0+5+8+6+6+7+0+4+3 +7+8+5+0

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

++++=1,

++++=1,

++++=1,

++++=1,

++++=1,

++++=1,

++++=1,

++++=1,

++++=1,

++++=1,

+42,

+42,

+42,

+42,

+42,

+42,

+42,

+42,

+42,

+42,

+42,

+42,
^ 2.3 Решение задачи вручную
Таблица 2

i j

1

2

3

4

5



1



5

7

9

2

2

2

4



5

7

6

4

3

7

4



5

8

4

4

6

6

7



4

4

5

3

7

8

5



3


Таблица 3

i j

1

2

3

4

5

1



3

5

7

0

2

0



1

3

2

3

3

0



1

4

4

2

2

3



0

5

0

4

5

2





0

0

1

1

0


Таблица 4

i j

1

2

3

4

5

a (1,5)

a (1,5)

1



3

4

6

3 () 0

3

0

2

0 0



0 2

2

2

0

0

3

3

0



0 1

4

0

0

4

2

2

2



0 2

0

0

5

0 () 1

4

4

1



0

1


Таблица 5

j i

1

2

3

4

5

1



0

1

3



2

0



0

2

2

3

3

0



0

4

4

2

2

2



0

5

0

4

4

1



b (1,5)

0

0

0

0

0


Таблица 6

j i

1

2

3

4


5

1



3

4

6

0

2

0



0

2

2

3

3

0



0

4

4

2

2

2



0

5



3

3

0



b (1,5)

0

0

0

0

0


Таблица 7

i j

1

2

3

4


a (5,4)

a (5,4)

2

0 2



0 2

2

0




3

3

0 2



0 0

0




4

2

2

2



2




5



3

3

0 3

3





Таблица 8

j i

1

2

3

4

2

0



0

2

3

3

0



0

4

0

0

0



5



0

0



b (1,5)

0

0

0

0


Таблица 9

j i

1

2

3

4

2

0



0

0

3

3

0



0

4



2

2

2


Таблица 10

j i

1

2

3

2

0 3



0

3

3

0 3




4



0 0

0 0


Таблица 11

i j

1

2

3

a (3,2)

2

0



0

0

3

3





3

4



0

0

0


Таблица 12

i j

1

2

3

2

0



0

3

0





4



0

0


Таблица 13

i j

1




2

3

a (3,2)

2

0





0

3

3

0



0

4



0

0

0


Таблица 14

i j

1

3

a

2

0 0



0

4



0 0

0


Полученная последовательность доставки продукции во все торговые точки и возврата на комбинат 1–5–4–3–2–1, при которой минимальный маршрут равен 22 километрам.


Скачать файл (194.4 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации