На примере матрицы весов 4х4 показываем, как работает венгерский алгоритм. Строим двудольный граф, находим максимальное паросочетание, потом наибольшее, и в заключении - совершенное.
Все просто. Максимум функции F есть минимум функции A-F. Т.е. делаете так - берете наибольшее число в матрице (или еще большее, с запасом) - это аналог А. Заменяете элементы Вашей матрицы b_ij на А-b_ij. Далее по уже известному пути - ищете минимум. Элементы, дающие минимум преобразованной матрицы соответствуют элементам исходной мтрицы, дающие максимум. Проверьте на матрице 2х2 - все станет ясно.
Спасибо большое, что отвечаете на мои вопросы. Возник еще один. Может ли быть такое, что чередующуюся цепь нельзя создать так, чтобы увеличилось число толстых линий после обращения, т.е. в итоге пропускаем процесс обращения и переходим к созданию множеств?
Здравствуйте. У меня возник следующий вопрос: в данном примере можно было выбрать чередующуюся цепь х2-у1-х1-у3, но ее не выбрали. Значит ли это, что можно брать любую, если количество шагов одинаковое и нечетное?
X(m) - множество вершин, не входящие в паросочетание. Множество X' - вершины в цепях из X(m) в X по тонким вперед, по толстым назад. X(m) обычно включено в X'. Иногда бывают длинные цепи, по несколько раз заходящие в Х.
Здравствуйте! Поправьте если ошибаюсь. Но , насколько я помню, задача о назначениях частный случай транспортной сбалансированной задачи. Матрица назначений , насколько я помню, должна быть бинарная (0 или 1). Вы очень хорошо и понятно объясняете, спасибо Вам. Но , как по мне, так проще составить ЗЛП и решить ее при помощи Его Величества Экселя (попробовал для интереса и получил в результате Вами же полученную матрицу)). Удачи Вам в Вашем деле!
Матрица назначений, естественно, 0 или 1 (назначили или нет). А начальная матрица весов (оценок, затрат и проч) - любая. Спасибо за Эксель (Excel). Забыл про него
@@Kirsanov2011 , только не подумайте, что я с претензией или укором. Я нисколько не сомневаюсь в Вашем профессионализме. Просто я человек ленивый и иду по принципу: пусть машина считает она же железная))) Я в свое время транспортную задачу решал с помощью поиска решений Эксель, потому, что запутался в потенциалах в силу невнимательности. Преподаватель сказал: объяснишь как - зачту. Объяснил, что достаточно правильно составить ЗЛП и натравить на нее Эксель с его знаменитым симплекс-методом. Показал как составил. Зачел. Прошу не подумайте, что я Вас как-то укорял. Просто рассказал решение для лентяев, таких как я)))
Цепь x4--y1--x1--y3 есть чередующаяся, т.е. состоит из тонких вперед (из X в У) и толстых назад (из У в Х) и всего там нечетное число. Потом мы "обращаем" эту цепь и получаем все наоборот. Так собственно и надо - мы увеличили число "толстых" ребер.
Это наиболее естественная ситуация. Значит выбрано удачное паросочетание. См. задачи с ответами на моем сайте vuz.exponenta.ru (раздел Архив задач) и мою книгу "Графы в Maple", она в сети где-то есть.
