Минимаксные задачи о назначениях

Математическая модель.

Пусть i=1,2,...,m, - номера работ, j=1,2,...,n - номера исполнителей.

R= r(i,j) mn матрица, элемент которой r(i,j) - время выполнения работы с номером i исполнителем с номером j.

Через X= x(i,j) - обозначим mn матрицу, элементы которой x(i,j) {0,1}, причем, если x(i,j) = 1, то работа с номером i будет закреплена за исполнителем с номером j, если x(i,j) =0, то работа с номером i не будет закреплена за исполнителем с номером j.

Ограничения математической модели.

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

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

x(i,j) {0,1}, i=1,2,...m. j=1,2,...,n.

Постановка оптимизационной задачи.

В качестве критерия оптимальности возьмем функционал

F(X) = max r(i,j) x(i,j) min, где max берется по всем i=1,2,...,m, j=1,2,...,n.

Поставленная задача называется минимаксной задачей о назначениях. Для ее решения может быть предложен алгоритм, основанный на последовательном решении ряда простейших задач о назначениях.

Обозначим через M=max r(i,j), где максимум берется по всем i, i=1,2,...,m, j=1,2,...,n;

m= max{max(min r(i,j)), max(min r(i,j))}.

Пусть m’ [m, M].

Рассмотрим простейшую задачу о назначениях с матрицей R’, элемент которой r(i,j) = 1, если r(i,j) m’; r(i,j) = 0, если r(i,j) > m’.

Тогда, если простейшая задача о назначениях с матрицей R’ имеет решение, то время перемещения конвейера будет не более чем m’. Если простейшая задача о назначениях с матрицей R’ не имеет решения, то время перемещения конвейера будет больше, чем m’. Осуществив, например, двоичный поиск, через порядка N решений простейших задач о назначениях, где N= log (M-m), будет решена исходная задача.

Дата добавления: 2017-02-01