Пример решения задачи о назначениях.

Пусть в виде таблицы дана матрица несоответствия «претендентов» ,,,,имеющимся «должностям» ,,,,():

Таблица 1.


⁷	²	¹	⁹	⁴
⁹	⁶	⁹	⁵	⁵
	⁸	³	¹	⁸
⁷	⁹	⁴	²	²
⁸	⁴	⁷	⁴	⁸

Если вначале дана матрица соответствия , то элементы матрицы определим по формулам .

Определим начальные значения потенциалов, положив и . Другими словами, потенциал положим равным наименьшему из тарифов в - том столбце. Нетрудно проверить, что так определенные потенциалы удовлетворяют условиям : , поскольку . Значения потенциалов запишем в добавленный справа к таблице столбец, а потенциалов в добавленную снизу строку. Кроме того, в клетки таблицы, удовлетворяющие условию запишем «потенциальные» единицы.

Таблица 2.


⁷	1 ²	1 ¹	⁹	⁴
⁹	⁶	⁹	⁵	⁵
1 ³	⁸	³	1 ¹	⁸
⁷	⁹	⁴	²	1 ²
⁸	⁴	⁷	⁴	⁸

Очевидно, что в силу определения и равенство будет выполняться в тех клетках - того столбца, в которых значение тарифа является наименьшим в соответствующем столбце (именно в этих клетках мы и поставили единицы). Заметим, что если бы оказалось ровно по одной единице в каждом столбце и в каждой строке, то есть всего 5 допустимых единиц, то согласно п.7.3 мы получили бы оптимальное решение задачи, положив для соответствующих допустимых единиц (а все остальные полагая равными нулю). Выберем теперь из имеющихся 6 потенциальных единиц максимально возможное число единиц так, чтобы в каждом столбце и в каждой строке стояло не более одной (допустимой) единицы. Разумеется, это можно сделать методом полного перебора, но мы хотим указать не метод «тыка», а способ, дающий эффективное решение задачи выбора допустимых единиц, основванный на известном алгоритме Форда-Фалкерсона. Для этого будем считать переменные ,,,,и ,,,,вершинами некоторой сети. Снабдим эту сеть (фиктивным) входом и (фиктивным) выходом , соединив вход дугами с вершинами ,,,,и вершины ,,,,с выходом (см. рис. 1). Кроме того, каждой потенциальной единице, стоящей в -той строке и -том столбце таблицы 2, сопоставим дугу с началом и концом . В результате получим следующую сеть.

Рис.1. Сеть для таблицы 2.

Кроме того, в таблицу снизу добавлена строка для определяемой ниже невязки и одна вспомогательная строка, смысл которых прояснится в дальнейшем и

С помощью условия (3) определим заполненные клетки таблицы. В первом столбце () равенство будет иметь место

добавив столбец для переменных , строку для переменных и две специальных строки, назначение которых станет ясно


	⁷	²	¹	⁹	⁴
	⁹	⁶	⁹	⁵	⁵
	⁷	⁸	³	¹	⁸
	⁷	⁹	⁴	²	²
	⁸	⁴	⁷	⁴	⁸

невязка
строка

						α
α₁	⁷	1²	1¹	⁹	⁴
α₂	⁹	⁶	⁹	⁵	⁵
α₃	1 ³	⁸	³	¹	⁸
α₄	⁷	⁹	⁴	²	1²
α₅	⁸	⁴	⁷	⁴	⁸
min β_j
невязка
строка

5rik.ru

Материалы для учебы и работы

Пример решения задачи о назначениях.