Угорський метод онлайн калькулятор з покроковим розв'язком

B1
B2
B3
B4
S
A1
A2
A3
A4
C
Коментарі рішення
Без опису (тільки відповідь)

a

b

c

d

x

y

z

AC

i

ab
x2
xn

Randomize

Формат чисел
3131313131351515151515≈52188552198585858586
Округлити до
Знаків після коми
10
=Розв'язати

  Про калькулятор угорського методу

Розв'яжіть задачі призначення / транспортні задачі угорським методом онлайн з детальним покроковим розв'язком. з повним, детальним, покроковим описом розв'язань, що розв'язує задачі лінійного програмування розміром до 20×20 з коефіцієнтами таких типів: десяткові числа та дроби.

Щоб почати обчислення, спочатку необхідно ввести розміри задачі у поля вводу у верхній частині екрана, а також вибрати потрібну операцію з бічного меню.

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

  • Перший елемент дозволяє розгорнути вікно вводу. Це може бути особливо корисно, коли таблиця не вміщається повністю на екрані. Якщо таблиця все ще не повністю видна після розгортання вікна, можна змінити масштаб за допомогою кнопок + / -;
  • Другий елемент копіює поточні вхідні дані задачі до буфера пам'яті. Це може бути корисно, коли ви часто розв'язуєте ту саму задачу ЛП або потрібно переносити дані між операціями;
  • Останній елемент вставляє раніше скопійовані вхідні дані, що дозволяє відновити дані задачі лише кількома кліками замість повторного введення вручну;

Далі внизу знаходиться панель інструментів, яка дозволяє налаштувати калькулятор та спростити роботу з ним. Вона візуально розділена на три частини, кожна з яких відповідає за таку функціональність:

  • Перша частина дозволяє вибрати формат чисел при відображенні результату розв'язання. Також можна вимкнути покрокові коментарі, якщо ви вже розумієте метод і потребуєте лише перевірки власних обчислень, або приховати покрокове розв'язання повністю, якщо потрібна лише кінцева відповідь;
  • Друга частина містить кнопки для зміни розмірів таблиці вводу, очищення окремих коефіцієнтів або всього вводу, а також головну кнопку зі знаком рівності, що переводить на екран розв'язання. Всі ці кнопки продубльовані клавіатурними скороченнями. Наведіть курсор на кнопку, щоб побачити відповідну клавішу у підказці. Також можна використовувати клавіші зі стрілками для переміщення курсора між полями вводу;
  • Остання частина дозволяє вибрати кількість знаків після коми для округлення нецілих результатів. Попередній перегляд показує, як виглядатимуть округлені значення;

  Що таке угорський метод?

Угорський метод (алгоритм Куна-Манкреса) розв'язує задачу призначення: дано матрицю витрат n×n, знайти ідеальне зіставлення між n виконавцями та n роботами, що мінімізує загальні витрати. Задача призначення є окремим випадком транспортної задачі, де кожна пропозиція та кожен попит дорівнює 1. Алгоритм виконується за поліноміальний час і гарантовано знаходить глобально оптимальне призначення.

  Як розв'язати задачу призначення угорським методом?

Починайте з віднімання мінімуму кожного стовпця від кожного елемента стовпця (редукція стовпців), потім відніміть мінімум рядка від кожного елемента рядка (редукція рядків). Знайдіть мінімальну кількість горизонтальних і вертикальних ліній, необхідних для покриття всіх нулів у редукованій матриці. Якщо потрібно n ліній, покриті нулі містять оптимальне призначення — витягніть його. Інакше знайдіть найменший непокритий елемент, відніміть його від усіх непокритих елементів і додайте до всіх елементів, покритих двома лініями, потім повторіть крок покриття нулів. Продовжуйте, доки не вдасться вибрати n незалежних нулів, що дають оптимальне призначення.

  Приклад розв'язання задачі призначення угорським методом

Розв'язання задачі починається з попереднього етапу. Результатом якого буде матриця C0 яка називається адаптованою матрицею вартості товарів і матрицяX0, матриця обсягів вантажопотоків.

C =
0
1
2
5
3
0
5
5
5
6
0
5
3
6
6
15
15

Попередній етап починається з отримання матриці C', для якої знаходимо найменші значення у стовпцях матриці C та поелементно віднімаємо їх від відповідних стовпців.

C' =
0
1
2
3
0
5
5
6
0

Отримуємо матрицю C0 повторюючи аналогічну операцію вже для рядків матриці C'.

C0 =
0
1
2
3
0
5
5
6
0

У матрицях X0 на місці ненульових елементів матриці C0 обов'язково розташований 0. На позиціях порожніх елементів матриці записуємо найменше з двох значень: залишок запасів у рядку, де знаходиться порожня клітинка, і залишок потреб у стовпці, де вона розташована.

X0 =
3
0
0
5
2
0
5
0
5
0
0
0
5
5
0
3
6
6
15
15
0
1
1
2
2

Значення суми залишків потреб і запасів є абсолютним показником оптимального розподілу ресурсів у поточній матриці X. Для оптимального розподілу ця сума дорівнює 0.

Після попереднього етапу починаємо виконувати ітераційний процес пошуку оптимальної матриці X. Кожна ітерація завершується отриманням нової матриці X як результату успішного виконання другого етапу. Ітерація починається з першого етапу. Якщо неможливо успішно виконати другий етап, виконується третій етап, після чого повертаємося до першого.

Перший етап

Доповнюємо рядки і стовпці поточної матриці C залишками з поточної матриці X. Нулі в поточній матриці C, розташовані на місці ненульових елементів поточної матриці X, позначаємо горизонтальною рисою зверху. Позначаємо плюсами ті нулі поточної матриці C, залишок для яких дорівнює 0;

Другий етап

Другий етап передбачає побудову ланцюга. Якщо це вдається, то отримуємо нову матрицю X і завершуємо поточну ітерацію. Якщо ні — переходимо до третього етапу.

Побудова ланцюга:

Шукаємо нуль у стовпці, не позначеному зверху знаком +, позначаємо його горизонтальною рисою, а праворуч від рядка, де він знаходиться, дописуємо +. Якщо залишок рядка, де знаходиться цей нуль, ненульовий, то побудову ланцюга можна вважати завершеною; якщо ні — продовжуємо будувати ланцюг. Наступний елемент, що дозволяє продовжити ланцюг, має бути нулем, який відповідає таким вимогам:
— знаходиться в рядку, де 0' — у стовпці, позначеному зверху знаком +;
— позначений зверху горизонтальною рисою;
Якщо вдається знайти нуль, що відповідає цим вимогам, позначаємо його зірочкою (*) і переносимо + зі стовпця, де він знаходиться, беручи його в дужки. Після знаходження 0* необхідно знайти нуль у стовпці, де він знаходиться. Якщо такий є, позначаємо його горизонтальною рисою. Якщо знайдений 0' знаходиться у рядку з нульовим залишком, продовжуємо будувати ланцюг, намагаючись знайти 0* в цьому рядку. Якщо залишок рядка, де знаходиться 0' ненульовий, процес побудови ланцюга завершений. Якщо всі варіанти побудови ланцюга вичерпані і побудувати його не вдалося — переходимо до третього етапу. Ланцюг — це набір непарної кількості нулів, в якому на парних місцях завжди 0* , а на непарних 0'. Мінімальна довжина ланцюга — один нуль.

Після отримання ланцюга визначаємо Θ. Θ — це мінімум з таких чисел:
— розбіжність стовпця, де знаходиться 0' з якого починається ланцюг;
— розбіжність рядка, де знаходиться 0' в якому завершується ланцюг;
— значення з поточної матриці X, розташовані на позиціях 0* ланцюга;

Після визначення Θ переходимо до обчислення нової матриці X, додаючи Θ до елементів поточної матриці X, розташованих на позиціях 0' ланцюга, і віднімаючи Θ від елементів поточної матриці X на позиціях 0* ланцюга;

Третій етап

Включаємо до прямокутних контурів рядки та стовпці, позначені знаком +. Серед елементів, що не входять до контурів, вибираємо найменше значення. Отримуємо проміжну матрицю C~, віднімаючи найменше значення від елементів рядків, що не входять до контурів, залишаючи рядки в контурах незмінними. Отримуємо нову матрицю C, додаючи найменше значення до елементів стовпців матриці C~які входять до контурів, залишаючи стовпці, що не входять до контурів, незмінними. Отримавши нову матрицю C, третій етап завершено. Після цього застосовуємо операції першого і другого етапів до отриманої матриці.

2
Ітерація 1

Виконуємо перший і другий етапи.

Оскільки побудувати ланцюг неможливо, переходимо до третього етапу.

C0 =
+
—
0
1
2
2
3
—
'
0
5
0
+
5
6
—
'
0
0
+
0
1
1

Отримуємо проміжну матрицю.

C~ =
-1
0
1
3
0
5
5
6
0

Отримуємо нову матрицю C.

C1 =
0
0
1
4
0
5
6
6
0

Виконуємо перший і другий етапи.

C1 =
+
—
0
'
0
1
1
+
4
—
0
5
0
6
6
—
0
0
0
0
1

Знаходимо Θ.

Θ = min(1; 2) = 1

Обчислюємо нову матрицю X.

X1 =
3
1
0
5
2/1
0
5
0
5
0
0
0
5
5
0
3
6
6
15
15
0
0
1
1
1
3
Ітерація 2

Виконуємо перший і другий етапи.

Оскільки побудувати ланцюг неможливо, переходимо до третього етапу.

C1 =
+
+
—
0
—
0
1
1
4
—
0
5
0
6
6
—
'
0
0
+
0
0
1

Отримуємо проміжну матрицю.

C~ =
-1
-1
0
3
-1
4
6
6
0

Отримуємо нову матрицю C.

C2 =
0
0
0
4
0
4
7
7
0

Виконуємо перший і другий етапи.

C2 =
+
+
—
0
—
0
'
0
0
+
4
—
0
4
0
7
7
—
0
0
0
0
0

Знаходимо Θ.

Θ = min(1; 1) = 1

Обчислюємо нову матрицю X.

X2 =
3
1
1
5
2/1/0
0
5
0
5
0
0
0
5
5
0
3
6
6
15
15
0
0
0
0
0
4
Оптимальне призначення

Оскільки значення суми залишків потреб і запасів дорівнює нулю, матриця X є оптимальною, і можна отримати результат, знайшовши суму добутків ненульових елементів поточної матриці X та відповідних елементів початкової матриці C.

(3 * 0) + (1 * 1) + (1 * 2) + (5 * 0) + (5 * 0) = 3

Answer
F → min
3
Працівники3Завдання3Загальна вартість3
Умовні позначення
— ланка ланцюга;
— контур рядка або стовпця, позначеного знаком +;
x — найменше значення в рядку, стовпці або серед елементів, що не входять до контурів;

  Часті запитання

Що розв'язує угорський метод?

Він розв'язує задачу про призначення — поєднання n працівників з n завданнями так, щоб загальна вартість була мінімальною і кожному працівникові було призначено рівно одне завдання.

Чому матриця вартостей має бути квадратною?

Кожен працівник має бути зіставлений рівно з одним завданням, тож кількість працівників і завдань має бути однаковою. Коли це не так, додають фіктивні рядки або стовпці з нульовою вартістю, щоб зробити матрицю квадратною.

Як працює зведення за рядками та стовпцями?

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

Як читати результат?

Результат позначає оптимальне призначення працівників на завдання та повідомляє мінімальну загальну вартість — суму початкових вартостей обраних пар.

  Пов'язані калькулятори

  Джерела

Google PlayApp Store