Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Задача про призначення. Угорський алгоритм
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Логістика
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „ Львівська політехніка “
Лабораторна робота № 1
з курсу „Логістика”
на тему: «Задача про призначення. Угорський алгоритм»
Мета лабораторної роботи полягає в ознайомленні з задачею про призначення та вивченні шляхів її розв’язку .
Теоретичні відомості
Для ознайомлення з задачею про призначення розглянемо її змістовну та формальну постановку.
Традиційними є наступні формулювання змістовної постановки задачі про призначення. Необхідно розподілити m робіт серед n виконавців таким чином, щоб сумарні витрати на виконання робіт були мінімальними. Відомі витрати cij - на виконання i-ї роботи j-м виконавцем для всіх робіт та виконавців. Окрім того, відомо, що кожен з виконавців може виконувати не більше, ніж одну роботу, і кожна робота може виконуватись не більше, ніж одним виконавцем.
Необхідно обрати m претендентів на n робочих місць таким чином, щоб їх сумарна ефективність функціонування була максимальною. При цьому відомі ефективності функціонування cij -роботи i-го претендента на j-му робочому місці. Кожен претендент може працювати лише на одному робочому місці і на кожному робочому місці може працювати лише один претендент.
Узагальнюючи змістовну постановку можна сказати, що задача про призначення має на меті знайти оптимальну відповідність між двома множинами об’єктів різної природи, коли задано ефективність/втрати cij їх сполучення і кожному об’єкту з однієї множини може відповідати не більше одного об’єкта з іншої.
Формальну постановку задачі про призначення можна дати у термінах лінійного програмування, транспортної задачі та графах.
Спочатку розглянемо формулювання задачі про призначення в контексті графів. Визначимо декілька допоміжних означень. Паросполучення неорієнтованого графа G=(X, A) називається підмножина M множини A ребер графа G, вибраних так, щоб довільних два ребра з M не є суміжними (тобто не мають спільної вершини). Повне паросполучення це таке паросполучення, при якому кожна вершина сполучається з деякою іншою вершиною ребром із множини M. Вага паросполучення обраховується так:
де cj вага ребра з множини M. Заданий повний двохдольний граф G=(X((X(, A), де X( і X( - незалежні множини вершин і /X(/=/X(/=n, кожне ребро aj=(xi, xk)(A має xi(X(, xk(X( і ваги cj. Знайти повне паросполучення графа G з мінімальною вагою.
В термінах лінійного програмування задачу про призначення можна сформулювати наступним чином. Мінімізувати:
(2.1)
при умові
(2.2)
де [bij] матриця інциденцій графа G і (=1 або 0 в залежності від того, чи входить ребро aij в паросполучення чи ні. Обмеження (2.2) можна записати і в іншій формі:
(2.3)
Умови цілочисельності ( у (2.2) і (2.3) взагалі кажучи є зайвими коли у графі G немає квіток (циклів з непарною кількістю ребер). Оскільки дводольні графи не мають циклів з непарною кількістю ребер то ці умови можна відкинути і розв’язувати задачу лінійного програмування у загальному вигляді.
Задачу про призначення можна завжди звести до транспортної задачі, оскільки перша є специфічним випадком другої. При цьому запаси та потреби, для транспортної задачі, що буде відповідати задачі про призначення, рівні одиниці і тарифи на перевезення рівні cij і задача прийме вигляд:
(2.4)
(2.5)
де xij приймає 1 чи 0 в залежності від того чи і-тий об’єкт першої множини сполучається з j-тим об’єктом другої. Так само як із ( умову цілочисельності xij можна відкинути в силу того, що довільна транспортна задача з цілочисельною матрицею тарифів {cij} завжди має цілочисельний розв’язок.
Як можна було побачити, задача про призначення формально будується так, щоб /X(/=/X(/ і функція мети мінімізувалася. А при змістовній постановці задачі, взагалі кажучи, не вимагається, щоб /X(/=/X(/. Крім цього, для першого варіанту змістовної постановки задачі необхідно мінімізувати, а для другого – максимізувати функцію мети.
Для розв’язування задачі, в змістовній постановці якої /X(/(/X(/ або функцію мети потрібно максимізувати, необхідно спершу здійснити приведення задачі до загального вигляду, в якій /X(/=/X(/ і функція мети мінімізується. Для цього виконуються наступні дії:
/X(/>/X(/ У такому випадку в множину X( вводять фіктивні елементи та до матриці коефіцієнтів {cij} додають стовпці заповнені нулями, що відповідають даним елементам.
/X(/</X(/ В множину X( вводять фіктивні елементи і та до матриці коефіцієнтів {cij} додають стрічки заповнені нулями, що відповідають даним фіктивним елементам.
У випадку максимізації функції мети матрицю коефіцієнтів {cij} множать на -1 та віднімають від неї її ж мінімальний елемент.
Зауважимо, що при у випадках I і II додаткові стовпці і рядки можна заповнювати не тільки нулем, але й довільним натуральним числом.
Дамо змістовну інтерпретацію фіктивним елементам які вводяться у множини X( і X(. Для першого варіанту змістовної постановки задачі, якщо в оптимальному розв’язку деякому виконавцю з множини X( відповідає фіктивна робота з множини X(, то це означає, що даний виконавець не буде виконувати жодної роботи. І навпаки, якщо деякій роботі буде поставлено у відповідність фіктивного виконавця, то це означатиме, що цю роботу недоцільно виконувати.
Для другого варіанту змістовної постановки задачі дамо аналогічну інтерпретацію: якщо деякому претенденту буде відповідати фіктивне робоче місце, то це означає, що його на роботу не прийняли, а у протилежному випадку – що робоче місце залишилось вакантним.
Як було вказано вище задачу про призначення можна подати у термінах лінійного програмування, транспортної задачі та графах. У кожному з цих випадків інтерпретації задачі про призначення для її розв’язання можна використовувати алгоритми розроблені для вказаних класів задач. Так при розгляді задачі про призначення як задачі лінійного програмування у загальному вигляді доцільно використати симплекс-метод, транспортної задачі – метод потенціалів або диференційних рент, а у випадку графів – метод потоку найменшої вартості. Але використання цих алгоритмів при задачах великої розмірності є неефективним. При цьому з збільшенням ступені загальності алгоритму ефективність різко (до кількох порядків) падає. З огляду на це для розв’язання задачі про призначення було розроблено методи, які повністю враховують її специфічні особливості. Найпоширеніший таким методом є Угорський алгоритм. Розглянемо найпростіший варіант цього алгоритму. Алгоритм будується на основі наступної теореми:
Теорема. Оптимальний розв’язок задачі про призначення не зміниться, якщо до будь-якого рядка чи стовпчика матриці {сij} додати постійну величину.
Доведення. Нехай до кожного рядка i і стовпчика j додаємо значення pi і qj відповідно. Проаналізуємо зміну функції мети (2.4):
Суть алгоритму полягає в наступному. Спочатку редукується та робиться спроба знайти на множині отриманих нулів у цій матриці повне паросполучення. Якщо це зробити не вдається, то всі нулі у редукованій {сij} матриці викреслюються мінімальною кількістю прямих, і від всіх невикреслених елементів матриці віднімається найменше значення невикресленого елементу та додається до тих елементів, які розташовані на перетині викреслюючих прямих. У зміненій таким чином матриці знову робиться спроба знайти повне паросполучення.
Крок 1. Редукція рядків і стовпчиків матриці {cik}. Послідовно для кожного рядка матриці знаходимо мінімальний елемент та зменшуємо на це значення всі елементи відповідного рядка. В отриманій таким чином матриці, виконуємо таку ж процедуру з кожним стовпчиком.
Крок 2. Реалізація призначень.
Послідовно переглядаючи рядки визначаємо ті з них в яких знаходиться рівно по одному нульовому невикресленому елементу. В кожному з таких рядків виконуємо призначення, які відповідає цьому невикресленому нульовому елементу. При виконанні призначень в кожному стовпчику, який відповідає призначеному нулеві, викреслюємо усі раніше не викреслені елементи;
Послідовно переглядаємо стовпчики, визначаємо ті з них в яких залишилося рівно по одному не викресленому нульовому елементу. В кожному з таких стовпчиків виконуємо призначення, що відповідає невикресленому нульовому елементу. При виконанні призначення в кожному рядкові, який відповідає призначеному нулеві, викреслюємо всі не викреслені раніше елементи;
Перевірка. Якщо знайдене таким чином паросполучення повне, тобто призначено n елементів, то воно й буде оптимальним розв’язком задачі. Кінець. Якщо деякі з нулів не викреслені, тобто залишилися рядки та стовпчики з більше ніж 1 не викресленим елементом, то обираємо рядок чи стовпчик з мінімальною кількістю нулів, довільно призначаємо один з них, викреслюємо всі нулі в цьому рядку чи стовпчику та відповідному стовпчику чи рядку і далі виконуємо крок 2. Якщо призначені всі нулі в матриці і знайдене паросполучення не є повним, то перехід до кроку 3.
Крок 3. Модифікація редукованої матриці. Відміняємо усі призначення та викреслення.
обчислюємо кількість нулів в кожному не викресленому рядку та кожному не викресленому стовпчику;
викреслюємо рядок чи стовпчик з максимальною кількістю нулів;
виконуємо (a) та (b) до того моменту, поки усі нулі не будуть викреслені;
від всіх невикреслених елементів віднімаємо значення мінімального невикресленого елемента та додаємо його до елементів, що знаходяться на перетині викреслюючих прямих. перехід до кроку 2.
Приклад. Вибрати чотирьох працівників з п’яти можливих для виконання чотирьох робіт так, щоб сумарні витрати часу були мінімальними. Затрати часу працівниками на виконання кожної роботи подані у матриці.
Індивідуальне завдання № 11
Функцію мети максимізувати
94 30 40 25 78
96 56 51 26 21
21 83 15 2 28
39 50 98 19 75
Р
ПР
АЦ
ІВ
НИ
К
О
Б
94
30
40
25
78
О
96
56
51
26
21
Т
21
83
15
2
28
И
39
50
98
19
75
Розв’язання. Спочатку приводимо задачу до загального вигляду, а потім розв’язуємо її за угорським алгоритмом.
Відповідь: перший працівник виконує другу роботу, другий – третю, третій – п’яту, четвертий – першу, а п’ятий - першу.
26.01.2013 16:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора