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

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

[@викторколедин-э7ь]

вы чертовски приятный человек! К вам на пары можно ходить с удовольствием! Все понятно, ясно и интересно!

[@Kirsanov2011]

+виктор коледин Спасибо! Буду стараться не разочаровать...

[@rifazakirov9882]

Спасибо вам! Спасли перед контрольной! Здоровья и благополучия вам!

[@ВарвараГенг]

Спасибо! Получила удовольствие от Вашей лекции!

[@Kirsanov2011]

Все просто. Максимум функции F есть минимум функции A-F. Т.е. делаете так - берете наибольшее число в матрице (или еще большее, с запасом) - это аналог А. Заменяете элементы Вашей матрицы b_ij на А-b_ij. Далее по уже известному пути - ищете минимум. Элементы, дающие минимум преобразованной матрицы соответствуют элементам исходной мтрицы, дающие максимум. Проверьте на матрице 2х2 - все станет ясно.

[@olanagornaya]

Спасибо Вам огромное за помощь! У меня все получилось!!! Вашим студентам очень повезло!))

[@ИбрагимНиналалов]

спасибо очень понятно объяснено!)

[@DarkdalV]

офигеть, такой ютубер некогда в моем МЭИ работал, неожиданно)

[@Kirsanov2011]

И продолжает работать еще...

[@Kirsanov2011]

Это наиболее естественная ситуация. Значит выбрано удачное паросочетание. См. задачи с ответами на моем сайте vuz.exponenta.ru (раздел Архив задач) и мою книгу "Графы в Maple", она в сети где-то есть.

[@Kirsanov2011]

Цепь x4--y1--x1--y3 есть чередующаяся, т.е. состоит из тонких вперед (из X в У) и толстых назад (из У в Х) и всего там нечетное число. Потом мы "обращаем" эту цепь и получаем все наоборот. Так собственно и надо - мы увеличили число "толстых" ребер.

[@Kirsanov2011]

X(m) - множество вершин, не входящие в паросочетание. Множество X' - вершины в цепях из X(m) в X по тонким вперед, по толстым назад. X(m) обычно включено в X'. Иногда бывают длинные цепи, по несколько раз заходящие в Х.

[@MrDemda]

Здравствуйте! Поправьте если ошибаюсь. Но , насколько я помню, задача о назначениях частный случай транспортной сбалансированной задачи. Матрица назначений , насколько я помню, должна быть бинарная (0 или 1). Вы очень хорошо и понятно объясняете, спасибо Вам. Но , как по мне, так проще составить ЗЛП и решить ее при помощи Его Величества Экселя (попробовал для интереса и получил в результате Вами же полученную матрицу)). Удачи Вам в Вашем деле!

[@Kirsanov2011]

Матрица назначений, естественно, 0 или 1 (назначили или нет). А начальная матрица весов (оценок, затрат и проч) - любая. Спасибо за Эксель (Excel). Забыл про него

[@MrDemda]

@@Kirsanov2011 , только не подумайте, что я с претензией или укором. Я нисколько не сомневаюсь в Вашем профессионализме. Просто я человек ленивый и иду по принципу: пусть машина считает она же железная))) Я в свое время транспортную задачу решал с помощью поиска решений Эксель, потому, что запутался в потенциалах в силу невнимательности. Преподаватель сказал: объяснишь как - зачту. Объяснил, что достаточно правильно составить ЗЛП и натравить на нее Эксель с его знаменитым симплекс-методом. Показал как составил. Зачел. Прошу не подумайте, что я Вас как-то укорял. Просто рассказал решение для лентяев, таких как я)))

[@andregimmler6905]

Спасибо, очень доступно)

[@думдум-б2д]

Дядька очень старательно и детально объясняет, но че-то я тупой😕 завтра еще раз посмотрю

[@Kirsanov2011]

Да, это сразу не поймешь...

[@olanagornaya]

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

[@sobolmx]

Супер! Спасибо.

[@daurenmaskeugaliev823]

очень познавательное видео и хотелось бы уточнить можно ли ее решать с помощью метода имитации отжига

[@Kirsanov2011]

Ольга! Надо по тонким вперед, по толстым назад, а у1-х1 тонкое ребро

[@a.osethkin55]

Очень замудренный алгоритм

[@olanagornaya]

Здравствуйте. У меня возник следующий вопрос: в данном примере можно было выбрать чередующуюся цепь х2-у1-х1-у3, но ее не выбрали. Значит ли это, что можно брать любую, если количество шагов одинаковое и нечетное?

[@olanagornaya]

С этим понятно. Скажите пожалуйста, а как составить мн-ва X' и Y', если Х(m) состоит из нескольких элементов?

[@MrKhro]

а как быть если дана матрица эффективности и требуется назначать работников в соответствии с наибольшей эффективностью?

[@daryamarkova5723]

А для каких целей в процессе решения выделяется множество {Ym}, ведь оно нигде далее не используется... (Если я не ошибаюсь)

[@Kirsanov2011]

Можно и не выделять. Просто я следую традиции.

[@olanagornaya]

Если в множестве Х(m) больше одного элемента, как записывать мн-во Х'?

[@kirillpupkov6314]

У меня одного этот алгоритм давали через дерево

[@meiendorf1428]

А зачем нам множество Ym?

[@Kirsanov2011]

можно и не отмечать его.