Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Комбинаторные задачи

Комбинаторные задачи. К данному классу относятся задачи оптимизации функции, заданной на конечном множестве, элементами которого служат выборки из n объектов.

Классическим представителем математических проблем такого рода стала задача о коммивояжере. Она состоит в составлении маршрута посещения торговым агентом, находящимся в некотором начальном пункте, n других городов при условии, что задана матрица стоимостей переездов из города в город

(с учетом начального). Причем допустимым является такой маршрут, который предусматривает однократное посещение всех городов и возвращение в исходный пункт. Очевидно, что наилучший маршрут должен минимизировать суммарную стоимость переездов.

Планом задачи является маршрут коммивояжера, и его можно задать с помощью так называемой матрицы смежности

элементы которой определяются следующим образом:


1, если в маршруте предусмотрен переезд из пункта i в j,

xi,j = 0, если в маршруте не предусмотрен переезд из пункта i в j,


причем по условию задачи xii =0, i∊1: n.

Допустимыми планами служат связные маршруты, однозначно определяемые упорядоченным набором посещаемых пунктов:

Каждый такой маршрут можно отождествить с перестановкой n чисел (упорядоченной выборкой из n элементов по n). В свою очередь, таким перестановкам взаимно однозначно соответствуют матрицы X, у которых в каждой строке и каждом столбце содержится точно одна единица.

С учетом сказанного задача коммивояжера принимает вид целочисленной задачи линейного программирования:

Условия (4.8) и (4.9) с содержательной точки зрения означают, что в каждый пункт можно въехать и выехать только один раз. Приведенная форма записи задачи коммивояжера (4.6)-(4.10) не является самой рациональной и предназначена только для того, чтобы подчеркнуть ее общность с другими задачами дискретного программирования. Существует и другая форма, которая более ярко отражает комбинаторный характер данной проблемы:

где D — множество перестановок чисел от 1 до n.

Отдельно следует остановиться на том, что задача коммивояжера имеет большое количество содержательных аналогов. Скажем, к аналогичной модели приведет задача разработки графика переналадки оборудования, которое может выпускать разные типы изделий, но требует определенных затрат (временных или материальных) при переходе с одного технологического режима на другой.