80
Задача заключается в определении матрицы целых неотрицательных зна-
чений переменных
x
ij
, минимизирующих целевую функцию вида:
n jm i
xa
X
F
m
i
n
j
ij
ij
,1 , ,1 min,
1 1
при ограничениях;
1)
для въезда в город
j
только один раз:
m
i
ij
x
1
;1
2)
для выезда из города
i
только один раз:
n
j
ij
x
1
.1
В такой постановке задача коммивояжера представляет собой задачу це-
лочисленного линейного программирования. Действительно, условия
ij
a
исключают в оптимальном решении значения
x
ij
= 1 как не имеющие смысла, а
ограничения требуют:
1)
чтобы маршрут включал только один въезд в каждый город;
2)
чтобы маршрут включал лишь один выезд из каждого города, а целевая
функция включала длину маршрута коммивояжера;
3)
чтобы маршрут образовывал контур и проходил через все города.
Таким образом, формируется экономный вариант маршрута в виде коль-
ца. Решение этой задачи строится, например, методом ветвей и границ цело-
численного программирования.
4.5. Методы решения задач линейного программирования
Задачи линейного программирования решаются различными методами,
простейшим из которых является графический метод, который применим при
наличии не более двух независимых переменных.
Свойства основной задачи линейного программирования связаны со
свойствами выпуклых множеств.
Множество точек называется выпуклым, если оно вместе с любыми
двумя точками содержит и их произвольную выпуклую комбинацию.
Геометрический смысл этого определения состоит в том, что множеству
вместе с его произвольными точками полностью принадлежит и прямолиней-
ный отрезок, их соединяющий. Примерами выпуклых множеств являются пря-
молинейный отрезок, полуплоскость, круг, шар, куб, полупространство и др.
