- •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.5. Пример
Решить задачу назначениях, которая определяется матрицей
При решении задачи знак выделения +, подлежащий уничтожению, обводим кружком. Последовательность из элементов 0' и 0* на втором шаге указываем стрелками.
Подготовительный этап. Максимальный элемент первого столбца матрицы равен 4. Поэтому для получения первого столбца необходимо из 4 вычесть элементы первого столбца матрицы. Аналогично для получения второго, третьего, четвертого и пятого столбцов вычитаем элементы этих столбцов из максимальных элементов 5, 3, 2 и 3 соответственно. В полученной матрице минимальный элемент каждой строки равен нулю, поэтому матрицанайдена. Помечаем независимые нули: в первом столбце выбираем произвольный путь, тогда во втором и в третьем столбцах независимых нулей нет, в четвертом столбце помечаем независимый нуль, в пятом столбце независимого нуля нет. Следует заметить, что в рассматриваемой задаче возможны и другие варианты выбора независимых нулей предлагается рассмотреть эти варианты самостоятельно.
Первая итерация
Шаг 0. Выделяем знаком + первый и четвертый столбцы, которые содержат 0*.
Шаг 1. Просматриваем невыделенные нули матрицы . Помечаем щтрихом нуль, расположенный во второй строке и во втором столбце. Поскольку в этой строке содержится 0*, то имеем случай а) и ставим + на вторую строку, а знак + над превым столбцом обводим кружком (убираем). Помечаем штрихом нуль этого столбца, который лежит в третьей строке, не содержащей 0*. Имеем случай б), поэтому переходим к шагу 2.
Шаг 0 Шаг 1
Шаг 2.Строим последовательность: от последнего помеченного 0' движемся к 0* (первый столбец, вторая строка), затем от 0* из второй строки переходим к 0', расположенномув той же строке и во втором столбце. Поскольку второй столбец не содержит 0*, то процесс построения последовательности закончен. Найденная последовательность состоит из элементов: . Преобразованная последовательность принимает вид:. Вносим эти изменения в матрицу , чистим ее (убираем знаки + и штрих) и получаем в результате матрицу, в которой число независимых нулей (0*) увеличено на единицу. На этом первая итерация алгоритма завершается.
Поскольку последующие итерации проводятся аналогично, ниже приводятся результаты вычислений без дополнительных пояснений.
Вторая итерация
Шаг 0 Шаг 1
Шаг 3 а), б), Шаг 3 в)
Шаг 1 Шаг 2
Шаг 2
Третья итерация
После третьей итерации количество независимых нулей (0*) стало равным размерности матрицы и поэтому процесс выбора закончен. Искомые элементы матрицы соответствуют позициям независимых нулей матрицы.
Значение целевой функции .
Оптимальное решение задачи о назначениях с соответствующей матрицей определяется наборомсо значениями:. Содержательно это означает, что первую работу выполняет второй исполнитель, вторую - третий исполнитель, третью работу - первый исполнитель, четвертую - пятый исполнитель и пятую работу выполняет четвертый исполнитель.
2.6. Задания для самостоятельной работы
Решить задачу о назначениях с матрицей:
-
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
2.12