Курсовая работа: Дискретное программирование

else

{ dp[w, j] = dp[w, j - 1];}

}

}

return dp[needed, n];}

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

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

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

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

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

дискретный программирование итерация комбинаторный

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

1, если в маршруте предусмотрен переезд из пункта i в j, xi,j = 0, если в маршруте не предусмотрен переезд из пункта i в j, причем по условию задачи xii =0, i<1:n.

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

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

перестановкам взаимно однозначно соответствуют матрицы X, у которых в каждой строке и каждом столбце содержится точно одна единица.

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

Условия 6 и 7 с содержательной точки зрения означают, что в каждый пункт можно въехать и выехать только один раз. Приведенная форма записи задачи коммивояжера 4-8 не является самой рациональной и предназначена только для того, чтобы подчеркнуть ее общность с другими задачами дискретного программирования. Существует и другая форма, которая более ярко отражает комбинаторный характер данной проблемы:

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

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

4. Задачи с разрывными целевыми функциями