Условие:
Дана матрица оценок задачи о назначениях.
| B{1} | B{2} | B{3} | B{4} | |
|---|---|---|---|---|
| A{1} | 100 | 300 | 600 | 400 |
| A{2} | 800 | 300 | 700 | 400 |
| A{3} | 200 | 200 | 1000 | 200 |
| A{4} | 100 | 600 | 600 | 200 |
Чему будет равна стоимость c2,1 после этапа получения нулей венгерским методом?
Решение:
Рассмотрим пошаговое выполнение венгерского метода до этапа получения всех нулей (то есть вычитание минимальных значений из строк и затем из столбцов) для приведённой матрицы. Исходная матрица: B₁ B₂ B₃ B₄ A₁: 100 300 600 400 A₂: 800 300 700 400 A₃: 200 200 1000 200 A₄: 100 600 600 200 Шаг 1. Вычитаем минимум каждой строки из всех её элементов. 1. Для строки A₁: Минимум = 100 Новая строка A₁: [100–100, 300–100, 600–100, 400–100] = [0, 200, 500, 300] 2. Для строки A₂: Минимум = 300 Новая строка A₂: [800...