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

Необхідно для виконання робіт розподілити т виконавців А_i, i = 1,2, ..., n по n робочим місцям B_j, j = 1,2, ..., n. Розглянемо ситуацію за умови, що кожен виконавець А_i може працювати тільки на одному робочому місці B_j, причому вартість роботи або час очікування визначається матрицею С= . У даній задачі змінні інтерпретуються як призначення відповідного виконавця на певне робоче місце.

Математична модель задачі про призначення має вигляд:

(4.3.1)

(4.3.2)

(4.3.3)

де , якщо i-й виконавець може зайняти j-е робоче місце

, якщо i-й виконавець не може зайняти j-е робоче місце.

Якщо коефіцієнт с_ij представляє собою час очікування (наприклад, час необхідний для того, щоб змінити професію, або витрати на перепідготовку), то слід робити такі призначення, при яких цільова функція, що виражає загальний час або витрати, була б мінімальною.

Якщо коефіцієнт с_ij представляє собою вартість роботи (наприклад, професійний рівень, або ефективність роботи даного виконавця), то слід робити такі призначення, при яких цільова функція, що виражає загальну вартість роботи, була б максимальною.

Задачу про призначення можна сформулювати як транспортну, в якій ролі виконавців А_i аналогічні ролям пунктів постачання А_i, робочі місця B_j, – пунктам споживання B_j. Оскільки кожен виконавець повинен працювати тільки на одному робочому місці, то запаси a_i і заявки b_j відповідно пунктів постачання А_i і пунктів споживання B_j вважаються одиничними a_i = 1, b_j = 1. Вартості робіт с_ij визначають тарифи перевезень і змінні х_ij є аналогами перевезень х_ij, для яких потрібно мінімізувати витрати .

Для розв’язання задачі про призначення з установкою на мінімум може бути використано метод потенціалів.

Задачу про призначення називають закритою (збалансованою), якщо число виконавців т дорівнює числу робочих місць п. У випадку, якщо число виконавців т не дорівнює числу робочих місць п, то задача про призначення зводиться до відкритої транспортної задачі.

Зауваження. Для побудови початкового опорного плану в задачі про призначення доцільно використовувати метод Фогеля.

Приклад 4.3.1. Розподілити 5 виконавців на 5 робочих місць. Матриця часу очікування представлена в таблиці 4.3.1.

Таблиця 4.3.1.

Початкові данні

Місця Виконавці	B1	B2	B3	B4	B5
А1	10	13	9	11	2
А2	9	12	8	3	4
А3	7	5	4	5	8
А4	4	6	4	7	9
А5	8	1	3	2	6

Для побудови початкового опорного плану в задачі про призначення скористаємося методом Фогеля.