Задача про призначення

У задачі про призначення треба розподілити 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=