n="justify"> (3.1)
На кожну роботу призначається тільки один виконавець
(3.2)
Умови невід'ємності і цілочисельності (Логічний):
(3.3)
Легко бачити, що завдання про призначення - окремий випадок транспортної задачі при Однак з урахуванням специфіки задачі для її рішення розроблені спеціальні, більш ефективні алгоритми.
Задача про призначення має саме широке застосування. Наприклад, при закріпленні машин за маршрутами, розподілі інструментів для обробки різних марок сталі, робітників або бригад і т. д. У кожному конкретному випадку математична модель задачі може мати специфіку. Наприклад, в задачі розподілу алгоритмів між обчислювальними машинами на ОЦ число розподіляються алгоритмів, як правило, не дорівнює числу машин. При призначенні на посади для деяких виконавців існують обмеження. Насамперед необхідно зазначити, що якщо задача про призначення ставиться за умови отримання максимального ефекту, то її зводять до задачі на мінімум. Нехай дана матриця ефективності C = [cij]. У кожному стовпці знайдемо максимальний елемент Побудуємо матрицю С '= [lj-cij]
Задача
В
де - область допустимих рішень системи (3.1) - (3.3), еквівалентна задачі
В
Справді,
В
Функція Z 'досягає мінімуму за умови, що Z досягає максимуму,
Якщо в задачі про призначення число виконавців дорівнює числу робіт, то говорять про закритої моделі, в іншому випадку - про відкритої моделі задачі про призначення. Якщо число m менше числа виконавців n (m n вводять mn фіктивних виконавців. Відповідні елементи cij матриці втрат можна вважати дуже великими (В«блокують нескінченністюВ»). p align="justify"> І ще одна деталь. Якщо з якихось причин забороняється виконання будь-якої роботи яких-небудь виконавцем, то і в цьому випадку відповідну клітку В«блокують нескінченністюВ» (ставлять велику вартість М). Точне рішення задачі про призначення можна знайти угорським методом, методом динамічного програмування та ін Існує також багато наближених методів. Хороше наближення дає модифікація способу Фогеля для визначення опорного плану транспортної задачі. p align="justify"> Приклад. При закріпленні транспортних засобів за маршрутами визначена матриця прибутків
В
Знайти план закріплення, максимізує сумарний ефект.
Рішення. Насампере...
