Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Имеется n городов, пронумерованных числами 1, 2,..., n. Для любой пары городов (i, j) задано расстояние (время, путевые расходы) C(i,j) ³ 0 между ними. Поэтому в общем случае C(i, j) ¹ C(j, i). Коммивояжер, выезжая из какого-либо города, должен посетить все города по одному разу и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута была бы минимальной.
Другая интерпретация этой задачи связана с минимизацией времени переналадок при обработке на одном станке партии из n различных деталей. Здесь C(i, j) – время переналадки при переходе от обработки детали i к обработке детали j. Требуется найти последовательность обработки деталей, минимизирующую общее время переналадок.
Для записи постановки задачи в терминах целочисленного линейного программирования определим переменные следующим образом: = 1, если коммивояжер переезжает и i -го города в j -й; , в противном случае. Тогда задача заключается в отыскании значений переменных , удовлетворяющих следующим соотношениям:
(5.15)
при условиях
(въезд в город j); (5.16)
(выезд из города i); (5.17)
(i ¹ j); (5.18)
xij = {0,1}, , целые, i = 1,..., m, j = 1,..., n. (5.19)
Ограничения (5.18) требуют, чтобы маршрут образовывал контур.
Дата публикования: 2015-10-09; Прочитано: 234 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!