Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Венгерский метод решения задачи о назначениях




Алгоритм нахождения оптимального назначения максимальной стоимости

1 шаг. В каждом столбце выбрать максимальный элемент.

2 шаг. Пересчитать все элементы каждого столбца по правилу: новое значение элемента столбца = максимальный элемент столбца – старое значение элемента столбца.

3 шаг. Если в каждой строке и в каждом столбце имеется нуль, то переходим к шагу 5.

4 шаг. В каждой строке выбрать минимальный элемент и из каждого элемента строки вычесть соответствующие минимальное значение.

5 шаг. В полученной матрице найти строку или столбец с одним нулем.

6 шаг. Строку и столбец, находящиеся на пересечении выбранного нулевого элемента из дальнейшего рассмотрения исключить. Данный нулевой элемент выделить.

7 шаг. В оставшейся матрице найти строку или столбец с одним нулевым значением. Данный нулевой элемент выделить. Строку и столбец, на пересечении которых находится найденный нулевой элемент, вычеркнуть из дальнейшего рассмотрения.

8 шаг. Процесс повторять до тех пор, пока все работы не будут распределены между работниками (при этом выбираются только нулевые назначения).

9 шаг. Если распределить работы не удается, то после шага 4 в полученной матрице минимальным количеством вертикальных и горизонтальных прямых вычеркиваются все нули матрицы.

10 шаг. В оставшейся матрице найти минимальный элемент.

11 шаг. К элементам, лежащим на пересечении вертикальных и горизонтальных прямых, найденный минимальный элемент прибавить.

12 шаг. Из всех невычеркнутых элементов матрицы найденный минимальный элемент вычитается.

13 шаг. Повторить шаги 5–8.

Алгоритм определения назначения минимальной стоимости отличается от описанного двумя первыми шагами. На первом шаге в каждом столбце выбирается минимальный элемент, который вычитается из всех элементов столбца (шаг 2).

Задача 1

На автомойку приехали три машины: Ауди, Пежо и ВАЗ. На автомойке есть три поста, на каждом из которых можно обслужить любую из этих трех машин, но за различную плату (см. таблицу).

Стоимость мойки автомобиля

  Ауди Пежо ВАЗ
Пост 1      
Пост 2      
Пост 3      





Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных