Задача вибору або про призначення

Класична постановка задачі:

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

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

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

Функція цілі min (max)

Система граничних умов:

3. ,

1 якщо i - й ресурс призначений на виконання j - й роботи; 0 - інакше.

Для розв`язку задачі про призначення застосовується угорський метод, що грунтується на двох теоремах.

Теорема 1: Якщо x_ij=X_ij мінімізує по всіх x_ij, таких, що x_ij³0 і , те x_ij=X_ij мінімізує також функціонал , де при всіх i і j = 1,…,n...

Теорема 2 (Фробеніуса): Мінімальне число ліній, що покривають усі нулі матриці, дорівнює максимальному числу незалежних нулів у ній.

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

Наведений метод розв`язку зводиться до перетворень рядків і стовпців за допомогою деяких констант доти, поки достатнє число коефіцієнтів C_ij не обернеться в нуль, що дасть шуканий результат.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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