ВУЗ:
Составители:
13
Введем переменные
x
ij
=1, если коммивояжер переезжает из города А
i
в город А
j
, i≠j;
x
ij
=0, в противном случае,
i, j=
n,1 .
Математическая модель задачи выглядит следующим образом.
Целевая функция имеет вид:
∑∑
==
⋅
n
i
n
j
ijij
xc
11
→min.
ЦФ представляет суммарную длину пути.
Ограничения имеют вид:
∑
=
=
n
j
ij
x
1
1 , i= n,1 , (1)
x
ij
i
n
=
=
∑
1
1
, j= n,1 , (2)
u
i
-u
j
+(n-1)⋅x
ij
≤ n-2, 2≤ i≠j ≤n, (3)
где u
i
, i= n,2 - неограниченные действительные переменные.
Условия (1) означает, что коммивояжер выезжает из каждого города
один раз, а условия (2)- что он въезжает один раз в каждый город.
Условия (3), выглядящие несколько искусственно, предназначены обес-
печить связность маршрута коммивояжера. Более точно эти условия запре-
щают любой цикл, не проходящий через город 1, и тем самым исключают си-
туации, подобные приведенной на рисунке.
43
21
5
7
6
Данная задача является задачей линейного булева программирования.
1.10. Задача о доставке (покрытии множества)
Фирма обслуживает некоторое количество клиентов (m). Каждый день
она доставляет своим клиентам товары на грузовых машинах (или по желез-
ной дороге, воздушным путем, на баржах и т.д.). Существует множество до-
Страницы
- « первая
- ‹ предыдущая
- …
- 11
- 12
- 13
- 14
- 15
- …
- следующая ›
- последняя »
