Математична постановка задачі про призначення
Перш ніж вирішувати таке завдання, необхідно ліквідувати дисбаланс, додавши фіктивні роботи або верстати в залежності від початкових умов. Тому без втрати спільності можна покласти m = n.
Нехай xij = 0, якщо j-я робота не виконується на i-му верстаті,
xij = 1, есліj-я робота виконується на i-му верстаті.
Таким чином, рішення задачі може бути записано у вигляді двовимірного масиву X = (xij). Допустиме рішення називається призначенням. Допустиме рішення будується шляхом вибору одного елемента в кожному рядку матриці X = (xij) і одного елемента в кожному стовпці цієї матриці. Для заданого значення n існує n! допустимих рішень.
Тепер завдання буде формулюватися таким чином:
Обмеження першої групи необхідні для того, щоб кожна робота виконувалася один раз. Обмеження другої групи гарантують, що кожному стану буде приписана одна робота.
Для ілюстрації задачі про призначення розглянемо таблицю з трьома роботами і трьома верстатами.
Специфічна структура задачі про призначення дозволяє використовувати ефективний метод для її вирішення.
Примітка. Оптимальне рішення задачі не зміниться, якщо з будь-якого рядка або стовпця матриці вартостей відняти довільну постійну величину (редукція).
Наведене зауваження показує, що якщо можна побудувати нову матрицю з нульовими елементами і ці нульові елементи або їх підмножина відповідають допустимому рішенням, то таке рішення буде оптимальним:
5 7 9 5 0 2 4 0 2 2
С = 14 10 12 10 4 0 2 4 0 0
15 13 16 13 2 0 3 2 0 1
Так як завдання про призначення є окремим випадком ТЗ, для її вирішення можна скористатися будь-яким алгоритмом лінійного програмування, однак більш ефективним є угорський метод (алгоритм).
Сутність угорського алгоритму полягає в тому, щоб у вихідній матриці cij отримати т = п незалежних нулів, т. Е. Щоб в кожному рядку або стовпці повинен бути тільки один нуль.
Крок 1.Редукція рядків і стовпців.
Мета цього кроку полягає в отриманні максимально можливого числа нульових елементів в матриці вартостей. Для цього з усіх елементів кожного рядка віднімають мінімальний елемент відповідного рядка, а потім з усіх елементів кожного стовпця отриманої матриці віднімають мінімальний елемент відповідного стовпця. В результаті отримують редуцированную матрицю вартостей і переходять до пошуку призначень.
Крок 2.Модіфікація скороченої матриці.
Для скороченої матриці вартостей:
а) Викреслити всі рядки і стовпці, що містять максимальну кількість нулів. Далі, рухаючись по рядках (зверху вниз) і по стовпчиках (зліва направо) викреслюємо відповідно рядки, а потім стовпчики, що містять нульові елементи.
б) У отриманої скороченої матриці вибираємо мінімальний елемент і:
- віднімаємо його з всіх не викреслених елементів;
- додаємо його до елементу, розташованого на перетині двох ліній.
Крок 3.Проверяем план на оптимальність.
Якщо він не оптимальний, повторюємо процедури кроку 2.
1) Якщо число ліній, необхідне для того, щоб викреслити нульові елементи, дорівнює числу рядків (стовпців), то існує повне призначення.
2) Якщо вихідна задача є задачею максимізації, то всі елементи матриці вартостей слід помножити на (- 1) і скласти їх з досить великим числом так, щоб матриця не містила негативних елементів. Потім завдання слід вирішувати як завдання мінімізації.
Покажемо роботу угорського алгоритму на прикладі задачі про призначення з наступною матрицею вартостей:
Необхідно спрямувати ресурси на об'єкти так, щоб сумарна вартість була мінімальна
Крок 1.Редукція рядків і стовпців.
Значення мінімальних елементів рядків 1, 2, 3 і 4 рівні 2, 4, 11 і 4 відповідно. Віднімаючи з елементів кожного рядка відповідне мінімальне значення, отримаємо наступну матрицю:
Значення мінімальних елементів стовпців 1, 2, 3 і 4 рівні 0, 0, 5 і 0 відповідно. Віднімаючи з елементів кожного стовпця відповідне мінімальне значення, отримаємо наступну матрицю:
=
У цій матриці в рядку 3 і стовпці 1 по два нуля, т. Е. Необхідно провести подальшу модифікацію скороченої матриці вартостей (оптимальний план не отримано).
Крок 2.Модіфікація скороченої матриці.
Отримаємо скорочену матрицю вартостей:
Цей мінімум додаємо до елементів скороченої матриці, що стоять на перетині викреслених рядків і стовпців (11, 2). В результаті отримуємо модифіковану матрицю:
Крок 3.Проверяем отриманий план на оптимальність і виробляємо призначення.
Шукаємо рядки з одним нулем і відзначаємо його. Це рядок 2. Наступний рядок-4. Відзначаємо нуль в цьому рядку, одночасно викреслюємо залишився нуль в першому стовпці. Наступний рядок, що містить один 0-1, відзначаємо цей нуль, одночасно викреслюємо нуль в 3 стовпці. Відзначаємо нуль в 4 стовпці. Всі нулі незалежні, т. Е. Отримано оптимальний план. Накладаючи модифіковану матрицю на вихідну матрицю вартості, бачимо, що всі призначення зробили.
Накладаємо модифіковану матрицю на вихідну, одержимо F (x) = 9 + 4 + 11 + 4 = 28
Відповідь: Перший ресурс направляємо на 3-й об'єкт, другий - на 2-й об'єкт, четвертий - на 1-й об'єкт, третій ресурс - на 4-й об'єкт. Вартість призначення: 9 + 4 + 11 + 4 = 28.
Примітки 1: Якщо вихідна матриця не є квадратної, то потрібно ввести фіктивні ресурси або фіктивні об'єкти, щоб матриця стала квадратної.
Таким чином, суть угорського методу полягає в наступному: Шляхом додавання певним чином знайдених чисел до деяких стовпцях і вирахування з них деяких чисел знаходять систему так званих незалежних нулів. Набір нулів називається системою незалежних нулів, якщо ніякі два (або більше) нуля чи не лежать на одній лінії (в рядку або стовпці). Якщо число незалежних нулів одно n, то, прийнявши відповідні їм змінні хij рівними 1, а всі інші - рівними 0, отримаємо оптимальний план призначення.