Лекція 6 Задача про призначення, постановка задачі. Метод Мака рішення задачі про призначення.

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

Маємо n робітників та стільки ж видів роботи; відома продуктивність - тобто виробіток кожного робітника з кожного виду роботи, наприклад, в %. Потрібно так розподілити робітників за видами роботи, щоб загальна продуктивність була максимальною.

Така задача є частковим випадком транспортної задачі і може бути вирішена за допомогою методу потенціалів. Але це не самий зручний метод рішення.

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

Нехай буде завдано добовий графік руху поїздів, який можна розглядати як частково упорядковану множину R рейсів r_i (i = 1, 2,..., n), пов¢ язаних поміж собою відношенням порядку <. [ Знак < означає, що рейс r_i є попереднім перед рейсом r_j ]. Під рейсом розуміють рух поїзду від пункту А до пункту Б незалежно від часу знаходження на шляху слідування.

А

Б

Рейс r_i Î R є попереднім відносно до рейсу r_j Î R (де j = 1, 2,..., n), якщо бригада може спочатку зробити рейс r_i, а потім рейс r_j, а це можливе лише тоді, коли

де t_i^K - закінчення рейсу r_i;

t_j^H - початок рейсу r_j;

Е - найменший час, який потрібен на операції, які пов¢ язані з переходом від рейсу r_i до рейсу r_j (min час знаходження локомотивної бригади у пункті оберту);

d_ij - час простою бригади, яка виконала рейс r_i та очікує початок рейсу r_j, за винятком часу, який потрібен на операції Е; d_ij ³ 0.

Відношення порядку < володіє властивістю транзитивності, тобто, якщо r_i < r_j при i¹ j та r_j < r_к при j¹ К, то r_i < r_К, а також властивістю асиметричності, тобто, якщо r_i < r_j, то рейс r_j не є попереднім перед r_i.

Потрібно визначити таку перестановку, яку складено із рейсів r_i Î R, щоб сумарний простій в пунктах оберту (å d_ij) був найменшим.

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

В матриці вартість С_ij = 0 в тому випадку, якщо рейс r_i Î R є попереднім перед рейсом r_j Î R; та С_ij = 1, якщо рейс r_i Î R не є попереднім перед рейсом r_j Î R.

Таким чином, задача полягає в тому, щоб визначити цілі невід¢ ємні x_ij , які мінімізують цільову функцію:

å å С_ij x_ij ® min, де x_ij ³ 0.

Матриця для вирішення задачі має вигляд квадрату n´ n (наприклад, якщо є 7 непарних та 7 парних поїздів - тоді 7´ 7).

Допустиме рішення задачі - це те, при якому в кожному стовпчику і в кожній строчці буде тільки 1 зайнятий елемент. Таких рішень може бути n! (При 7! - 5040 допустимих рішень).

Оптимальне рішення задачі - це одне з допустимих рішень, при якому простій бригад (загальний) буде мінімальним.

Якщо прийняти до уваги, що задача завідомо вироджена і в матриці не може бути більше ніж n зайнятих клітинок (клітинку називають зайнятою, якщо в ній x_ij> 0), краще її вирішувати таким методом, в якому не зустрі-чається труднощів в випадках виродження матриці, наприклад методом Мака.

Метод Мака рішення задачі про призначення.

Виділити в кожнім рядку по одному мінімальному елементу. Стовпці, у яких немає виділених елементів називаються вільними, а інші - зайнятими.

Крок 1. Перевірка оптимальності плану. Якщо в таблиці немає жодного вільного стовпця, то отримане рішення є оптимальним, інакше перейти до кроку 2.

Крок 2. Позначити * (зірочкою) будь-який стовпець, у якому більш одного виділеного елемента.

Крок 3. Для всіх рядків, у яких є виділені елементи в позначених * стовпцях, знайти різницю між мінімальним елементом серед непозначених * стовпців ai і мінімальним елементом серед позначених * стовпців bi (Di = ai - bi).

Крок 4. Знайти мінімальну різницю D=min{Di}серед знайдених на кроці 3 різниць.

Крок 5. Перетворити поточну таблицю, додавши до всіх елементів усіх позначених * стовпців D. Непозначені стовпці залишаються без змін.

Крок 6. Елемент ai у непозначеному стовпці який використовувався для розрахунку мінімальної різниці виділити підкресленням як альтернативний (тепер він має ту ж вартість, що й елемент bi у позначеному стовпці).

Крок 7. Якщо альтернативний елемент ai, отриманий на кроці 6, знаходиться у зайнятому стовпці, то позначити цей стовпець * і перейти до кроку 3, інакше перейти до кроку 8.

Крок 8. У вільний стовпець в клітку з альтернативним елементом показати стрілочкою перенесення по рядку виділеного елементу в альтернативну клітину.

Крок 9. Якщо стовпець, з якого було перенесено виділений елемент, став вільним, перейти до кроку 8, інакше перейти до кроку 10.

Крок 10. Кінець даної ітерації. Перетворити таблицю, зробивши виділеними відповідні альтернативні елементи. Прибрати всі позначки * і підкреслення та перейти до кроку 1.