Решение задачи о назначениях алгоритмом Куна

Рассмотрим формальную постановку задачи о назначениях:

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

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

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

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

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

Двойственная к ней задача имеет вид:

y(i) + z(j) r(i,j), i=1,2,...,n, j=1,2,...,n. (6)

Q(y,z) = y(i) + z(j) min. (7)

Здесь m=n.

Не уменьшая общности, будем считать, что коэффициенты r(i,j) целые.

Пусть y’ и z’ - допустимое решение задачи (6),(7), т.е. y’(i) + z’(j) r(i,j), i=1,2,...,n, j=1,2,...,n. Допустимое решение может быть построено, например, так:

y’(i) = max r(i,j), где максимум берется по всем j=1,2,...,n, z’(j) = 0, j=1,2,...,n.

Начало процедуры решения задачи.

Обозначим через P множество тех пар (i,j), для которых y’(i) + z’(j) = r(i,j).

Рассмотрим простейшую задачу о назначениях с матрицей D, элементы которой d(i,j) = 1, если (i,j) P и d(i,j) =0 в противном случае.

Вариант 1.

Простейшая задача о назначениях с матрицей D имеет решение, т.е. каждый исполнитель назначен на свою работу и каждая работа получает своего исполнителя. Пусть X’ - оптимальное решения простейшей задачи о назначениях, тогда X’ - будет оптимальным решением и исходной задачи (1) -(5). Действительно, x’(i,j) = 1, если (i,j) P, т.е. y’(i) + z’(i,j) = r(i,j), отсюда

r(i,j) x’(i,j) = y’(i) + z’(j), т.е. по теореме о равенстве линейных форм прямой и двойственной задач, X’ - оптимальное решение исходной задачи.

Вариант 2.

Простейшая задача о назначениях с матрицей D не имеет решения. Тогда найдется множество исполнителей K, которые могут выполнять согласно матрице D работы из множества Q, причем мощности множеств равны, соответственно, k и q и при этом k>q. Рассмотрим новые двойственные переменные:

y’’(i) = y’(i) - 1, если i K и y’’(i) = y’(i) в противном случае;

z’’(j) = z’(j) +1, если j Q и z’’(j) = z’(j) в противном случае.

Тогда нетрудно показать, что новые значения двойственных переменных удовлетворяют условиям задач (6), (7) и при этом уменьшают значения критерия двойственной задачи.

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

Конечность алгоритма Куна следует из того, что по теореме о соотношениях линейных форм прямой и двойственной задач,

r(i,j) x’(i,j) y’(i) + z’(j).

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