В задаче о назначениях нужно распределить m работников на n работ, при этом каждого работника нужно направить не более чем на одну работу, и на каждую работу нужно назначить не более чем одного работника. Задана матрица производительностей C размером m×n, каждый элемент которой cij − это производительность i-го работника на j-й работе. Работников нужно распределить так, чтобы максимизировать общую производительность.

Задачу о назначениях можно рассматривать как задачу о максимальном взвешенном паросочетании на полном двудольном графе Km,n. Первая доля вершин V, |V|=m − это работники, вторая доля W, |W|=n − это работы, а матрица производительностей C − это веса рёбер. Как известно, задача о максимальном паросочетании может быть сформулирована и решена как задача бинарного линейного программирования.

Для правильной работы с этой страницей Ваш браузер должен поддерживать сценарии Java Script. Включите их.

Введите исходные данные в находящиеся ниже поля ввода. В первых двух областях нужно ввести количество работников m и количество работ n. В следующей области ввода введите матрицу производительностей C размером m×n. Числа разделяйте пробелами и переносами на новую строку.

m=       n=

C=