(Оффтоп)
0. "В Вики не написано".
При отсылках к Вики мне вспоминается мошеннический приём пасечников - ставить близ улья сахарный сироп. Мёда будет много и быстро, определить его неполноценность обычный покупатель не сможет, но пчёлы способность собирать нектар с цветов утрачивают.
1. Венгерский метод вполне пригоден для решения ТЗ, его обобщение на неё было сделано в 1957 году. Однако к этому времени уже был вполне разработан метод потенциалов. Который был проще в реализации, весьма ясен по логике действий (что существенно для объяснения экономистам и т.п.), а сравнительно редко встречающаяся в общей ТЗ проблема вырожденности (или зацикливания) обходилась незначительным усложнением программы (если пользуются эмпирическими приёмами; строгий и всегда работающий метод борьбы с зацикливанием - усложнение существенное).
2. Венгерский метод и метод потенциалов принадлежат к двум существенно разным классам - "последовательного сокращения невязок" и "последовательного улучшения плана" (что, соответственно, разновидности "прямо-двойственных" и "прямых" методов; метод решения ТЗ, относящийся к двойственным, мне неизвестен, но в принципе возможен). Это определяет некоторые второстепенные преимущества одного метода перед другим (оценка отклонения плана от оптимального, возможность прервать расчёт, получая допустимый, хотя не обязательно оптимальный план и т.п.;подробнее в книгах по ссылкам).
3. Основное же преимущество венгерского метода проявляется в ситуации вырожденности, когда есть группа поставщиков, суммарный объём по которой равен суммарному объёму по некоей группе потребителей. В случае метода потенциалов это может вызывать ситуацию, когда, построив цепочку и перераспределяя перевозки в ней, мы обнаруживаем, что перераспределяемая величина равна нулю, и на следующем шаге матрица не изменилась, и мы вновь обрабатываем ту же цепочку (зацикливаемся). Преодолевается это либо существенным усложнением алгоритма, гарантирующим отсутствие зацикливания, либо эмпирическими приёмами, не дающими полной гарантии, но вероятность зацикливания снижающими до пренебрежимо малой. Однако в задаче о назначениях такое совпадение объёмов поставок частью поставщиков с объёмом потребления частью потребителей не редкость, как в ТЗ общего вида, а правило. Любые m поставщиков имеют "объём поставок", равный объёму потребления любыми m потребителями, так что эмпирические приёмы оказываются бесполезны, а строгое правило для избавления метода потенциалов от зацикливания оказывается никак не проще венгерского алгоритма. Поэтому на практике общая ТЗ - метод потенциалов, задача о назначении - венгерский.
08.12.2013, 18:03 
