This page is hosted for free by zzz.com.ua, if you are owner of this page, you can remove this message and gain access to many additional features by upgrading your hosting to PRO or VIP for just 32.50 UAH.
Do you want to support owner of this site? Click here and donate to his account some amount, he will be able to use it to pay for any of our services, including removing this ad.

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

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