Алгоритм розв’язання і розв’язання задачі про призначення

Нехай необхідно розв’язати задачу про призначення 4 завдань на виконання 4 ресурсам, якщо задана матриця витрат часу на виконання кожного завдання кожним ресурсом: .

1. Приведемо матрицю до такого вигляду, щоб у кожному стовпці й кожному рядку знаходився хоча б один нуль. Для цього знайдемо в кожному рядку матриці мінімальний елемент і віднімемо його з усіх елементів відповідного рядка. Аналогічні перетворення виконаємо також з елементами стовпців.

2. Якщо після першого кроку можливий вибір чотирьох незалежних нулів, тоді можна стверджувати, що задача розв’язана. Незалежні нулі для зручності будемо позначати (*). При розставленні позначок найкраще вибирати рядок або стовпець, що містять найменшу кількість нулів. У цьому рядку (стовпці) вибираємо нуль, позначаємо його і викреслюємо інші нулі в рядку або стовпці, на перетинанні яких знаходиться вибраний (або незалежний) нуль. Позначки ставимо доти, поки в матриці існують вільні (непозначені або невикреслені) нулі.

У розглянутому прикладі не вдалося відразу ж одержати оптимальне розв’язання, отже, переходимо на виконання третього кроку.

3. Проведемо мінімальне число горизонтальних і вертикальних ліній, що перетинають, принаймні, один раз усі нулі. Для задач невеликої розмірності візуально легко нанести шукані лінії, для більш складних зручно використати насупний алгоритм:

1. Позначаємо всі рядки, що не містять незалежних нулів.

2. Позначаємо всі стовпці, що містять нуль хоча б в одному позначеному рядку.

3. Позначаємо всі рядки, що містять незалежні нулі в позначених стовпцях.

Кроки 2 і 3 виконуємо доти, поки можливо ставити позначки. Далі викреслюємо непозначені рядки і позначені стовпці.

Якщо виявилося, що кількість ліній дорівнює n,тоді необхідно повернутися на попередній крок (позначки нулів) і знову вибрати незалежні нулі. Такий варіант можливий, якщо при проставленні позначок 2 або більше нулів у рядку мали «однакове право» бути незалежними.

4. Серед елементів, через які не пройшла жодна з ліній, вибираємо найменший. Віднімаємо це число зі всіх елементів, через які не пройшла жодна лінія, і додаємо його до всіх елементів, через які проведені дві лінії.

5.
Повертаємося на крок вибору незалежних нулів. У розглянутому прикладі держуємо відразу два оптимальних розв’язання:

1-е завдання ® 1-й ресурс;

2-е завдання ® 2-й ресурс (або на 4-й ресурс);

3-е завдання ® 3-й ресурс;

4-е завдання ® 4-й ресурс (або на 2-й ресурс).

У результаті такого призначення система виконає всі завдання за 17 умовних одиниць часу.

У тому випадку, якщо необхідно розв’язати задачу отримання максимального значення функції мети, можна скористатися наступною формулою переходу, що слушна для будь-якої задачі лінійного і нелінійного програмування: min (L) = - max (-L) (тобто елементи матриці С домножити на (-1)).

Запитання з теми

1. Постановка задачі про призначення.

2. Математична модель задачі про призначення.

3. Задача про призначення як різновид Т.3. зі своєю специфікою.

4. Розв’зання (план) задачі про призначення.

5. Теорема 1 про мінімізацію функціонала.

6. Теорема 2 (Фробеніуса).

7. Застосування теорем 1 і 2 для занульовання матриці С.

8. Визначення «незалежного» нуля в матриці С.

9. Зв'язок “незалежних” нулів з оптимальністю плану задачі про призначення.

10. Як занулюється матриця З при ррозв’язання задачі про призначення при міn функції мети?

11. Як зануливается матриця З при розв’язанні задачі про призначення при мах функції мети?

12. Суть угорського методу при розв’язанні задачі про призначення.

13. Якщо при розв’язанні задачі про призначення угорським методом не отриманий оптимальний план, подальше розв’язанні задачі?

Завдання для контрольних і самостійних робіт

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

Дані для розв’язання задачі про призначення.

Таблиця 5.