Составители:
58
Целевая функция задачи имеет вид
11
min
.
nn
ij ij
ji
Ecx
==
=→
∑∑
Рассмотрим теперь некоторые дополнительные ограничения. Оче-
видно, что перевозка внутри одного пункта не требуется. Формально
это означает, что
0, 1
.
jj
xj
n
≡≤≤
В табл. 3.10 представлена стоимость перевозки между различными
пунктами c
ij
, а в табл. 3.11 – рассчитанный оптимальный маршрут пе-
ревозок
X
, обеспечивающий значение целевой функции 12,38.
Рассчитанный оптимальный маршрут поездок начинается в пункте
1. Затем следует поездка в пункт 2, возвращение в пункт 1, поездка в
пункт 6, поездка в пункт 5, поездка в пункт 3. Маршрут завершается в
пункте 4. Обычно в задаче коммивояжера рассматривается дополни-
тельное условие: маршрут должен начинаться и заканчиваться в пунк-
те 1. Формально это условие может быть записано как
1
0,1
,
1, .
i
i
n
x
jn
≤<
=
=
В табл. 3.12 представлен оптимальный маршрут перевозок
X
, начи-
нающихся и заканчивающихся в пункте 1 при тех же исходных данных
табл. 3.10. Значение целевой функции в этом случае увеличилось и со-
ставляет 15,25.
Таблица 3.10
Стоимость перевозки между пунктами
c
ji
123456
100,051,795,755,569,934,8
222,300,047,785,910,633,1
360,523,900,014,019,901,0
455,868,577,100,040,013,9
577,746,099,010,700,037,8
643,555,422,798,031,200,0
Страницы
- « первая
- ‹ предыдущая
- …
- 56
- 57
- 58
- 59
- 60
- …
- следующая ›
- последняя »
