Задачи теории расписаний

Решение задачи коммивояжера с использованием рекуррентных соотношений динамического программирования

Рассмотрим задачу коммивояжера:

x(i,j) =1, j=1,2,...,m, (1)

x(i,j) =1, i=1,2,...,m, (2)

u(i) - u(j) + m x(i,j) m-1, i=1,2,...,m, j=1,2,...,m, i j., (3)

x(i,j) {0,1}. (4)

F(X)= r(i,j) x(i,j) min. (5)

Пусть G = {0,1,...m} - множество городов.

Обозначим через W(G’, i) - расстояние, которое пройдет коммивояжер из города с номером i через все города множества G’ в начальный город с номером 0, G’ G, i G\G’ при оптимальном выборе маршрута (с точки зрения критерия задачи коммивояжера). Тогда

W(G’,i) = min [ r(i,j) + W(G’\{i}, j)], (6)

где минимум берется по всем городам с номерами j G’.

Рекуррентные соотношения (6), используя граничные условия:

W(G’,i) = r(i,0), если G’ - пустое множество, (7)

могут быть использованы для решения задачи коммивояжера (1) -(5).

Изучением вопросов оптимального планирования и управления на сетевых структурах занимается теория расписаний - раздел дискретного программирования. Задачи теории расписаний, как правило, трудноразрешимы, хотя для некоторых из них существуют эффективные алгоритмы решения., К задачам теории расписаний относятся:

- задачи упорядочения - минимизации функций на перестановках,

- задачи согласования - определение длительностей выполнения работ при конфликтующих потребностях работ в ресурсах,

- задачи распределения - при альтернативных технологиях выполнения работ.

Мы в дальнейшем будем рассматривать лишь задачи теории расписаний, связанные с упорядочением работ.

Дата добавления: 2017-02-01; Просмотров: 106; Нарушение авторских прав?; Мы поможем в написании вашей работы!