Алгоритм угорського методу

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

 

Методичні вказівки та завдання

щодо виконання самостійної роботи

 

 

CУМИ

МІНІСТЕРСТВО АГРАРНОЇ ПОЛІТИКИ УКРАЇНИ

СУМСЬКИЙ НАЦІОНАЛЬНИЙ АГРАРНИЙ УНІВЕРСИТЕТ

Кафедра кібернетики та інформатики

 

ДОСЛІДЖЕННЯ ОПЕРАЦІЙ

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

 

Методичні вказівки та завдання

щодо виконання самостійної роботи

 

для студентів спеціальностей

„Менеджмент зовнішньоекономічних зв’язків”,

„Менеджмент організацій”

денної та заочної форм навчання

 

СУМИ

УДК 519.87

 

Укладачі: Воронець Л.П., ст. викладач кафедри кібернетики та інформатики

Сергієнко В.А., ст. викладач кафедри кібернетики та інформатики

 

Дослідження операцій. Задача про призначення. Методичні вказівки та завдання щодо виконання самостійної роботи. / Суми, 2008 рік 25 ст., табл. 2, бібл. 5.

 

В методичних вказівках наведено основні теоретичні відомості з теми «Задача про призначення», алгоритм угорського методу для розв’язання задач подібного типу, алгоритм розв’язання задач про призначення за допомогою табличного процесору Excel, задачі для самостійного розв’язання, тестові завдання для студентів спеціальностей „Менеджмент зовнішньоекономічних зв’язків”, „Менеджмент організацій” денної та заочної форм навчання.

 

 

Рецензенти:	Лавров Є.А., д.т.н., проф. кафедри кібернетики та інформатики Сумського національного аграрного університету
	Головань М.С., к.пед.н., доцент кафедри економічної кібернетики Української академії банківської справи

 

Відповідальний за випуск: Ободяк В.К., доцент кафедри кібернетики та інформатики.

 

 

Рекомендовано до видання навчально-методичною радою інституту економіки та менеджменту Сумського національного аграрного університету.

Протокол № ____від „____”___________2008 року.

 

Сумський національний аграрний університет, 2008
Зміст

 

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

2. Алгоритм угорського методу...........................................................................6

3. Розв’язання задачі про призначення за допомогою табличного процесору Excel ………………………………………………………………..................10

4. Задачі для самостійного розв’язання..............................................................15

5. Тестові запитання............................................................................................19

Література..............................................................................................................24

 

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

Короткий опис даної задачі – „кращій робітник для виконання даної роботи”.

В даній задачі необхідно призначити робітніків на певні види робіт. Кожен робітник може виконати бідь-яку роботу, але з різним ступенем майстерності. Якщо на деяку роботу призначаєтсья робітник саме тієї кваліфікації, яка необхідна для її виконання, тоді вартість виконання цієї роботи буде нижча, ніж при призначенні на дану роботу робітника іншої кваліфікації. Мета – знайти оптимальний розподіл робітників по всіх роботах, що маємо в наявності.

Загальна задача про призначення робітників на робіт наведена на рис. 1.

	Роботи
Робітники				...
			…
			…
.	.	.	.	.
.	.	.	.	.
.	.	.	.	.

Рис. 1. Табличний вигляд задачі про призачення

Коефіцієнт показує вартість призначення робітника на роботу ().

Якщо кількість робітників не дорівнює кількості робіт, то в модель вводять фіктивних робітників або фіктивні роботи.

Задача про призначення є частинним випадком транспортної задачі. Робітники відповідають пунктам відправлення, а роботи – пунктам призначення. Всі величини попиту та пропозиції дорівнюють одиниці.

Якщо ввести позначення

,

то математична модель даної задачі буде мати вигляд:

Знайти мінімум функції

при умовах

,

.

З врахуванням специфічних особливостей задачі про призначення розроблені специфічні алгоритми її розв’язання, одним з яких є так званий угорський метод.

Алгоритм угорського методу

Приклад 1

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

	1 проект	2 проект	3 проект
1-й робітник	15 діб	10 діб	9 діб
2-й робітник	9 діб	15 діб	10 діб
3-й робітник	10 діб	12 діб	8 діб

 

1. В кожному рядку знаходимо мінімальний елемент і віднімаємо його від йнших елементів рядка.

	1 проект	2 проект	3 проект	min
1-й робітник
2-й робітник
3-й робітник

 

	1 проект	2 проект	3 проект
1-й робітник
2-й робітник
3-й робітник

 

2. В отриманій матриці в кожному стовпчику знайдемо мінімальний елемент і віднімемо його від інших елементів відповідних стовпчиків.

	1 проект	2 проект	3 проект
1-й робітник
2-й робітник
3-й робітник
min

 

	1 проект	2 проект	3 проект
1-й робітник		0
2-й робітник	0
3-й робітник			0

 

В останній таблиці нульові елементи, що підкреслені, визначають оптимальний розв’язок: перший проект виконає 2-й робітник, 2-й проект – 1-й робітник, 3-й проект – 3-й робітник. Всі ці проекти виконаються в мінімально можливий термін діб.

В деяких випадках нульові елементи, що отимані на першому та другому кроках алгоритму угорського методу не дозволяють безпосередньо отримати припустимий розв’язок. В таких випадках застосовують додаткові кроки для отримання оптимального розв’зку.

Приклад 2

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

	1 проект	2 проект	3 проект	4 проект
1-й робітник	1 діб	4 діб	6 діб	3 доби
2-й робітник	9 діб	7 діб	10 діб	9 діб
3-й робітник	4 діб	5 діб	11 діб	7 діб
4-й робітник	8 діб	7 діб	8 діб	5 діб

 

Виконання перших двох кроків алгоритму угорського методу призводить до такої таблиці:

	1 проект	2 проект	3 проект	4 проект
1-й робітник
2-й робітник
3-й робітник
4-й робітник

 

Нульові елементи даної таблиці не дозволяють призначити кожному робітнику певний проект. Так, наприклад, якщо ми призначимо першому виконавцю роботу 1, з подальшогу розгляду виключається перший стовпчик, і тоді в рядку для третього робитника не залишиться нульових елементів. В таких випадках виконують такі додаткові кроки:

1. В останній таблиці проводять мінімальну кількість горизонтальних і вертикальних по рядках прямих з метою викреслення всіх нульових елементів.

 

	1 проект	2 проект	3 проект	4 проект
1-й робітник
2-й робітник
3-й робітник		1
4-й робітник

 

2. Знаходять найменший невикреслений елемент і віднімають його від інших невикреслених елментів і додають до елементів, що знаходяться на перетині проведених на попередньому кроці прямих.

В нашому прикладі це елемент 1 (перетин 3-го робітника і 2-го проекту). Результатом описаних вище дій є таблиця:

	1 проект	2 проект	3 проект	4 проект
1-й робітник	0
2-й робітник			0
3-й робітник		0
4-й робітник				0

Оптимальний розв’язок показаний підкресленими нулями. Отже, ми отримали таке розподілення робіт між працівниками (табл. 1):

Таблиця 1

Оптимальне розподілення робіт між працівниками

№ проекту	виконавець

 

Якщо нова отримана таблиця не дозволяє побудувати припустимий розв’язок, повторюють крок 1 додаткового алгоритму.

 

3. Розв’язання задачі про призначення за допомогою табличного процесору Excel

Розглянемо розв’язання задачі про призначення за допомогою табличного процесору Excel на першому прикладі.

1. Створимо підготовчу форму для розв’язання задачі (див рис. 2). Вартості виконня робіт (або їх термін) вказані в клітинках B2:D4. В клітинках B8:D10 після застосування Поиска решения з’являться шукані значення змінних. У чарунки В11:D11 та Е8:Е10 введено формули для лівих частин обмежень. Значення правих частин обмежень – в чарунках B12:D12, F8:F10. В чарунці В14 задана формула для розрахунку значення цільової функції (формула для обчислення загального терміну або загальної вартості виконаних робіт).

Рис. 2. Підготовча форма для розв’язання задачі про призначення

 

2. Виконаємо пункти головного меню Сервис→Поиск решения. На екрані з’явиться діалогове вікно „ Поиск решения ”, в якому треба встановити такі параметри (див. рис.3):

Рис. 3. Діалогове вікно Поиск решения

a) в полі Установить целевую ввести адресу чарунки, що містить цільову функцію (в нашому прикладі В14);

b) у полі Равной встановити перемикач в положення Минимальному значению (за спрямованістю цільової функції);

c) у полі Изменяя ячейки ввести діапазон чарунок для шуканих змінних В8:D10;

d) задати праві частини обмежень таким чином:

§ в діалоговому вікні Поиск решения клацнути на кнопці Добавить. Відкриється діалогове вікно „Добавление ограничения” (рис. 4)

Рис. 4. Діалогове вікно „Добавление ограничения”

§ у полі Ссылка на ячейку вводимо по черзі адреси чарунок з формулами для обчислення лівих частин обмежень. Якщо обмеження, що записані одне за одним, мають однаковий знак, то їх можна вводити групою (рис.5)

Рис. 5. Введеня обмежень моделі групою

e) встановити параметри пошуку рішень. Для цього в діалоговому вікні „ Поиск решения ” клацнути на кнопці Параметры. Відкриється діалогове вікно „ Параметры поиска решения ” (рис. 6), в якому необхідно встановити прапорці в полях Линейная модель і Неотрицательные значения. Псля втановлення необхідних параметрів клацать на кнопці ОК і потрапляють знов у вікно „ Поиск решения ”.

Рис. 6. Діалогове вікно Параметры поиска решения

f) клацнути на кнопці Выполнить діалогового вікна „Поиск решения”, після чого на екрані з’явиться вікно Результаты поиска решения (рис. 7).

Рис. 7. Діалогове вікно Результаты поиска решения

Можна зберегти знайдений розв’язок, якщо обрати опцію Сохранить найденное решение, або Восстановить исходные значения, якщо потрібно перейти до розв’язування іншої задачі.

Діалогове вікно „ Результаты поиска решения ” може містити й інші повідомлення. Так, наприклад, якщо виведеться повідомлення „ Значения целевой ячейки не сходятся ” або „ Поиск не может найти подходящего решения ”, то необхідно перевірити правильність складаня і введення моделі. Якщо помилок немає, то ці повідомлення означають, що задача не має розв’язку.

3. Проаналізуємо отримані результати (рис. 8), які знаходяться в чарунках B7:D9 i B13.

Рис. 8. Результати розв’язання задачі про призначення

 

 

Отримані одиниці в чарунках B7:D9 показують оптимальне розподілення робіт між працівниками. Так, першому робітнику необхідно доручити виконання 2-го проекту, другому робітнику – виконання 1-го проекту, третьому робітнику – виконання 3-го проекту (табл. 2):

Таблиця 2

Оптимальне розподілення робіт між працівниками

№ проекту	виконавець

 

Оптимальна (мінімальна) тривалість (вартість) виконання робіт становить 27 днів (27 грош. од.).

4. Задачі для самостійного розв’язання

Розв'язати запропоновані задачі двома способами: угорським методом і за допомогою табличного процесору Excel.

Правила оформлення робіт:

1. Титульний лист з вказанням виконавця роботи і варіанту.

2. Умова задачі.

3. Розв'язання задачі угрським методом.

4. Лист з розрахунками розв'язання задачі засобами табличного процесору Excel.

5. Лист з електронними формулами розв'язання задачі засобами табличного процесору Excel.

6. Економічна інтерпретація отриманих результатів.

Задача 1. Наведена матриця витрат виконання 7 робітниками певних робіт. Розподілити роботи між працівниками таким чином, щоб сумарні витрати на виконання робіт були мінімальними.

Варіант 0

Робітники	Роботи
	3	4	2	8	1	7	3
	2	3	13	9	1	6	2
	12	4	12	5	3	1	4
	5	6	1	7	11	8	6
	11	4	10	10	5	13	7
	9	6	11	12	7	1	2
	2	4	8	5	9	3	10

Варіант 1

Робітники	Роботи
	6	2	15	2	4	9	5
	12	11	1	13	8	11	13
	3	2	12	9	10	14	1
	7	1	3	4	5	6	8
	8	9	14	3	11	18	12
	1	7	5	6	15	16	2
	13	10	4	7	10	16	17

Варіант 2

Робітники	Роботи
	5	17	5	12	11	6	4
	10	9	6	10	12	16	4
	9	3	2	8	13	14	8
	13	1	7	11	7	18	19
	1	7	12	8	3	1	5
	3	11	13	9	14	20	21
	10	2	6	6	15	15	22

Варіант 3

Робітники	Роботи
	21	7	2	12	15	2	17
	23	15	24	20	12	5	11
	17	24	4	17	2	22	15
	19	7	8	1	13	14	4
	15	6	6	14	19	3	16
	23	6	5	19	15	11	19
	16	18	22	22	1	1	7

Варіант 4

Робітники	Роботи
	2	4	5	10	4	6	8
	3	6	4	13	6	7	9
	4	7	10	5	10	4	5
	6	5	12	4	7	5	4
	7	4	13	6	6	7	5
	10	8	5	2	8	9	10
	11	9	4	8	4	5	4

Варіант 5

Робітники	Роботи
	7	9	4	6	4	12	3
	2	4	4	7	8	8	5
	4	5	6	5	12	7	3
	3	6	8	4	6	6	7
	5	10	9	3	8	5	4
	6	9	5	10	9	6	7
	7	4	3	6	2	5	4

Варіант 6

Робітники	Роботи
	6	7	8	9	10	12	5
	2	3	4	8	9	16	8
	9	6	3	6	8	9	3
	5	7	6	7	10	7	8
	4	8	18	8	6	2	3
	12	9	2	10	8	4	5
	3	10	3	5	4	3	8

Варіант 7

Робітники	Роботи
	12	4	8	9	12	4	5
	6	5	10	7	3	6	8
	3	10	4	12	5	6	10
	11	12	16	5	7	8	12
	6	7	4	6	7	2	1
	12	5	7	12	9	4	5
	4	6	8	4	3	6	7

Варіант 8

Робітники	Роботи
	6	3	5	4	6	7	8
	5	2	4	3	8	9	10
	4	3	3	5	4	6	7
	7	5	3	2	1	4	5
	8	6	6	10	12	5	4
	12	7	8	7	4	8	9
	4	8	9	6	7	4	3

Варіант 9

Робітники	Роботи
	4	3	5	4	8	9	10
	7	6	2	5	12	13	4
	6	5	1	6	7	8	9
	7	4	6	10	4	7	3
	4	3	10	8	5	3	2
	3	8	12	6	3	6	12
	5	9	4	7	8	9	1

Задача 2. Нехай в попередньому прикладі можно ввести нового восьмого робітника, який може виконати будь-який вид робіт з вартістю відповідно 10, 13, 15, 11, 8, 7, 9 грош. од. Чи буде економічно вигідним замінити одного з працюючих новим?

 

Задача 3. Нехай в задачі 1 необхідно ввести нову роботу, яку може виконати будь-який робітник. Вартість виконання даної роботи відповідно 9, 13, 11, 8, 3, 15, 11 грош. од. Чи є нова робота більш вигідною в порівнянні з іншими роботами?

 

 

5. Тестові запитання