Завдання. 1. Провести перетворення матриці С у матрицю С¢¢.

1. Провести перетворення матриці С у матрицю С¢ ¢.

2. Визначити за отриманою матрицею незалежні нулі.

3. При недостатній кількості незалежних нулів провести необхідну кількість ітерацій.

4. Розрахувати максимальну продуктивність при заданих значеннях.

5. Зробити висновки по роботі.

Вихідні дані до роботи видаються викладачем індивідуально.

Нехай є n видів робіт і n претендентів (робітників, механізмів та ін.) для їхнього виконання, причому кожен претендент може використовуватися на будь-якій роботі. Продуктивність і -го претендента на j -й роботі (с_ij) відома. Треба так розподілити претендентів по роботах, щоб сумарна продуктивність була максимальною. При цьому кожного претендента можна призначити тільки на одну роботу і на кожну роботу можна призначити тільки одного претендента.

Математична задача про призначення формулюється так. Потрібно вибрати таку послідовність елементів { с _{1 j 1}, с _{2 j 2}, с_njn } із квадратної матриці

(10.1)

щоб j_k ¹ j _l при k ¹ l і при цьому величина була максимальною. Інакше кажучи, необхідно з кожного рядка і кожного стовпчика матриці С вибрати по одному елементу (усього n елементів) так, щоб їхня сума була найбільшою.

Вирішення задачі вибору, таким чином, являє собою перестановку n чисел (число можливих варіантів рішень дорівнює n!), тому при великих числах n прямий перебір практично неможливий. Застосування угорського методу істотно скорочує трудомісткість розв’язання задачі.