 |
 |
 |
 |
|
 |
 |
77
факт, что в литературе она также известна как задача о загрузке судна.
4.1.3. Комбинаторные задачи. К данному классу относятся задачи оптимизации функции, заданной
на конечном множестве, элементами которого служат выборки из n объектов.
Классическим представителем математических проблем такого рода стала задача о коммивояжере.
Она состоит в составлении маршрута посещения торговым агентом, находящимся в некотором
начальном пункте, n других городов при условии, что задана матрица стоимостей переездов из города в
город
(с учетом начального). Причем допустимым является такой маршрут, который предусматривает
однократное посещение всех городов и возвращение в исходный пункт. Очевидно, что наилучший
маршрут должен минимизировать суммарную стоимость переездов.
Планом задачи является маршрут коммивояжера, и его можно задать с помощью так называемой
матрицы смежности
элементы которой определяются следующим образом:
1, если в маршруте предусмотрен переезд из пункта i в j,
x
i,j
= 0, если в маршруте не предусмотрен переезд из пункта i в j,
причем по условию задачи x
ii
=0, i?1: n.
Допустимыми планами служат связные маршруты, однозначно определяемые упорядоченным
набором посещаемых пунктов:
Каждый такой маршрут можно отождествить с перестановкой n чисел (упорядоченной выборкой из n
элементов по n). В свою очередь, таким перестановкам взаимно однозначно соответствуют матрицы X,
у которых в каждой строке и каждом столбце содержится точно одна единица.
С учетом сказанного задача коммивояжера принимает вид целочисленной задачи линейного
программирования:
Условия (4.8) и (4.9) с содержательной точки зрения означают, что в каждый пункт можно въехать и
выехать только один раз. Приведенная форма записи задачи коммивояжера (4.6)-(4.10) не является
самой рациональной и предназначена только для того, чтобы подчеркнуть ее общность с другими
задачами дискретного программирования. Существует и другая форма, которая более ярко отражает
комбинаторный характер данной проблемы: