Міністерство освіти і науки України Національний університет „ Львівська політехніка “ Лабораторна робота № 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(/ а...