- •1. Элементы теории игр
- •1.1. Основные понятия
- •1.2. Матричные игры
- •1.3. Принцип минимакса. Седловые точки
- •1.4. Смешанные стратегии
- •1.5. Пример полного решения матричной игры
- •1.6. Задания для самостоятельной работы}
- •2.Задача о назначениях
- •2.1. Содержательная постановка
- •2.2. Математическая модель
- •2.3. Венгерский метод
- •2.4. Алгоритм венгерского метода
- •2.5. Пример
- •2.6. Задания для самостоятельной работы
- •3.Задача коммивояжера
- •Постановка задачи
- •Метод ветвей и границ
- •Метод ветвей и границ для решения задачи коммивояжера.
- •3.4 Пример
- •3.5. Задания для самостоятельной работы
- •4.Динамическое программирование
- •4.1. Постановка задачи
- •4.2. Построение модели дп
- •4.3. Построение вычислительной схемы дп
- •4.4. Несколько замечаний к методу дп
- •4.5. Задачи распределения ресурсов
- •5.6. Пример решения задачи распределения ресурсов
- •4.7. Задачи о замене оборудования.
- •4.8. Пример решения задачи о замене оборудования
- •5.9. Задания для самостоятельной работы
2.4. Алгоритм венгерского метода
Подговительный этап
Находим максимальный элемент в каждом столбце матрицы .
Для каждого столбца все его элементы последовательно вычитаем из максимального, а результат оставляем в соответствующей позиции.
Из всех элементов каждой строки вычитаем минимальный элемент этой строки. В результате получаем матрицу с неотрицательными элементами, в каждой строке и в каждом столбце которой имеется по меньшей мере один нуль.
Помечаем независимые нули символом "*" по схеме:
а) в первом столбце помечаем произвольный нуль;
б) во втром столбце помечаем (если найдется) тот нуль, в строке которого нет нуля, помеченного "*";
в) аналогично просматриваем один за другим все столбцы матрицы .
На этом подготовительный этап заканчивается.
Основной этап
Шаг 0. Получена матрица . Если в матрице отмечено ровнонулей, процесс решения заканчивается, и оптимальное решение определяется позициями независимых нулей (0*) матрицы.
Если же число независимых нулей меньше , то помечаем знаком + столбцы матрицы, содержащие 0*. Соответствующие элементы столбцов являются выделенными элементами.
Шаг 1. Если среди невыделенных элементов матрицы нет нулей, переходим к шагу 3. Если невыделенный нуль есть, то может быть один из случаев:
а) строка, содержащая невыделенный нуль, содержит также 0*;
б) строка, содержащая невыделенный нуль, не содержит 0*.
В случае а) помечаем найденный нуль штрихом, помечаем знаком + строку, содержащую этот 0', и убираем знак выделения + над столбцом, который пересекается с последней выделенной строкой по 0*. Возвращаемся на начало шага 1.
В случае б) помечаем найденный путь штрихом и переходим к шагу 2.
Таким образом, шаг 1 закончится, когда:
либо все нули будут выделены - при этом преходим к шагу 3;
либо обнаружится невыделенный нуль в строке, где нет 0* - при этом переходим к шагу 2.
Шаг 2. Строим последовательность из элементов 0' и 0* матрицы по правилу:
а) последовательность начинается с исходного 0' (последнего нуля, помеченного штрихом);
б) от 0' по столбцу идем к 0* (если такой найдется;
в) от 0* по строке идем к 0';
г) повторяем пункт б).
Итак, последовательность образуется передвижением от 0' к 0* по столбцу, от 0* к 0' по строке и т.д. при этом последовательность всегда начинается с 0' (пункт а) и заканчивается 0' (завершение построения последовательности возможно в пункте б) на элементе 0').
Полученную последовательность преобразуем так. Все 0* в последовательности заменяем на обыкновенные нули, все 0' - на 0*. Затем "чистим" матрицу : убираем все штрихи, все знаки выделения +. В результате получаем матрицу, в которой число независимых нулей (0*) увеличено на единицу. На этом итерация алгоритма завершается переходим к шагу 0.
Шаг 3. К этому шагу в матрице среди невыделенных элементов нет нулевых элементов. Поэтому:
а) выбираем среди невыделенных элементов минимальный (обозначим его значение через );
б) величину вычитаем из всех элементов матрицы, расположенных вневыделенных строках;
в) величину прибавляем ко все элементам матрицы, расположенных ввыделенных столбцах.
В результате получим эквивалентную матрицус невыделенными нулевыми элементами. Полагаем и переходим к шагу 1.