- •Міністерство освіти і науки, молоді та спорту україни
- •ЕкономіКо-математиЧні моделі та методи: оптимізаційні моделі та методи
- •Класифікація оптимізаційних методів та моделей
- •1.1. Постановка задачі лінійного програмування
- •Алгоритм графічного методу розв’язання злп
- •1.3. Симплекс-метод розв’язання задачі лінійного програмування
- •Алгоритм симплекс-метода розв’язання злп
- •Критерій оптимальності опорного плану:
- •Правила переходу до наступної симплекс-таблиці
- •1.4. Цілочислове програмування
- •Контрольні питання до змістового модуля і
- •2.1. Двоїста задача лінійного програмування
- •2.2. Елементи теорії матричних ігор
- •Алгоритм принципу максиміну (мінімаксу)
- •Розв’язання. Ця матрична гра має розмірність (3х4), тобто гравець а має три стратегії, а гравець в – чотири. Запишемо її в нормальній формі.
- •Послідовність дій при розв’язанні гри
- •Контрольні питання до змістового модуля іі
- •3.1. Дробово-лінійне програмування
- •Правила розв’язання задачі дробово-лінійного програмування графічним методом
- •3.2. Параметричне програмування
- •Алгоритм розв’язання задачі параметричного програмування
- •3.3. Динамічне програмування
- •Алгоритм розв’язання задачі динамічного програмування
- •Контрольні питання до змістового модуля ііі
- •4.1. Транспортна задача
- •Алгоритм методу потенціалів:
- •Критерій оптимальності плану перевезень
- •4.2. Ускладнена транспортна задача
- •4.3. Задача про призначення
- •Алгоритм методу Фогеля
- •Алгоритм угорського методу розв’язання задачі про призначення
- •Контрольні питання до змістового модуля іv
- •Індивідуальні завдання для самостійної роботи зі змістового модулю і
- •Індивідуальні завдання для самостійної роботи зі змістового модулю іі
- •Індивідуальні завдання для самостійної роботи зі змістового модулю ііі
- •Індивідуальні завдання для самостійної роботи зі змістового модулю іv
- •Література
- •Предметний покажчик
Алгоритм угорського методу розв’язання задачі про призначення
У початковій матриці визначити в кожному рядку найменше число і відняти його зі всіх елементів цього рядка.
У матриці, що отримана на першому кроці, знайти в кожному стовпці найменше число і відняти його зі всіх елементів цього стовпця.
Оптимальним призначенням відповідатимуть нульові елементи, отримані на попередньому кроці.
Якщо не отримано оптимальне рішення, то потрібно виконати дії:
а) У останній матриці виділити мінімальне число горизонтальних і вертикальних рядків і стовпців з тим, щоб виділити в матриці всі нульові елементи.
б) Знайти найменший невиділений елемент і відняти його з решти невиділених елементів і додати до елементів, що розташовані на перетині виділених рядків і стовпців.
в) Якщо новий розподіл нульових елементів не дозволяє побудувати рішення, повторити крок 4 а).
Приклад 4.3.2. Розв’язати задачу про призначення 4.3.1. угорським методом.
-
Місця
виконавці
B1
B2
B3
B4
B5
А1
10
13
9
11
2
А2
9
12
8
3
4
А3
7
5
4
5
8
А4
4
6
4
7
9
А5
8
1
3
2
6
Розв’язання.
У рядку А1 мінімальне число 2, віднімемо його зі всіх елементів цій стоки. Аналогічно, в рядку А2 – 3, А3 – 4, А4 – 4, А5 – 1. В результаті отримаємо таблицю 4.3.3.
Таблиця 4.3.3.
Перша таблиця задачі про призначення
-
Місця
Виконавці
B1
B2
B3
B4
B5
А1
8
11
7
9
0
А2
7
9
5
0
1
А3
3
1
0
1
4
А4
0
2
0
3
5
А5
7
0
2
1
5
Таким чином, розв’язки завдання про призначення, що отримані різними методами співпали.
Приклад 4.3.3. Розв’язати задачу про призначення угорським методом.
-
Місця
Виконавці
B1
B2
B3
B4
B5
B6
B7
А1
2
3
4
1
5
6
7
А2
4
3
1
2
5
6
9
А3
3
3
9
10
5
5
4
А4
4
5
4
6
7
9
10
А5
3
4
4
5
6
9
8
А6
4
5
5
7
8
1
2
А7
4
3
4
1
2
3
5
Розв’язання.
У кожному рядку знайдемо мінімальне число і віднімемо його з решти елементів цього рядка. В результаті отримаємо таблицю 4.3.4.
Таблиця 4.3.4
Перша таблиця задачі про призначення
-
Місця
Виконавці
B1
B2
B3
B4
B5
B6
B7
А1
1
2
3
0
4
5
6
А2
3
2
0
1
4
5
8
А3
0
0
6
7
2
2
1
А4
0
1
0
2
3
5
6
А5
0
1
1
2
3
6
5
А6
3
4
4
6
7
0
1
А7
3
2
3
0
1
2
4
У стовпцях, які не містять нульових значень, знайдемо мінімальні числа, і, віднімемо їх з елементів відповідного стовпця. Це стовпці B5 і B7. В результаті отримаємо таблицю 4.3.5, в якій не отримано оптимальний розв’язок. У таблиці 4.3.5 виділимо мінімальне число горизонтальних і вертикальних рядків і стовпців з тим, щоб виділити всі нульові елементи. Це стовпці B1, B3, B4, і, рядки А3, А6, А7.
Таблиця 4.3.5
Друга таблиця задачі про призначення
-
Місця
виконавці
B1
B2
B3
B4
B5
B6
B7
А1
1
2
3
0
3
5
5
А2
3
2
0
1
3
5
7
А3
0
0
6
7
1
2
0
А4
0
1
0
2
2
5
5
А5
0
1
1
2
2
6
4
А6
3
4
4
6
6
0
0
А7
3
2
3
0
0
2
3
Найменший невиділений елемент 1. Віднімемо його з невиділених елементів і додамо до елементів, розташованих на перетині виділених рядків і стовпців. В результаті отримаємо таблицю 4.3.6, в якій отримано оптимальне рішення.
Таблиця 4.3.6
Третя таблиця задачі про призначення
-
Місця
Виконавці
B1
B2
B3
B4
B5
B6
B7
А1
1
1
3
0
2
4
4
А2
3
1
0
1
2
4
6
А3
1
0
7
8
1
2
0
А4
0
0
0
2
1
4
4
А5
0
0
1
2
1
5
3
А6
4
4
5
7
6
0
0
А7
4
2
4
1
0
2
3
Сумарні витрати при таких призначеннях визначаються початковими витратами:
z = 1 + 1 + 4 + 4 + 4 + 1 + 2 = 17.