Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Идея Венгерского метода



Определение. Пусть имеется матрица с неотрицательными элементами, и пусть в ней содержатся и нулевые элементы. В некоторых наборах нулевых элементов матрицы будем называть системой независимых нулей, если никакие два нуля не стоят в одной строке или одном столбце. Система независимых нулей будет называться полной, если количество нулей будет n.

Идея заключается в том, что исходная задача максимизации в начале меняется на эквивалентную задачу минимизации (умножается целевая функция на –1), затем элементы эквивалентной матрицы С путем эквивалентных преобразований из теоремы делаются не отрицательными. Затем с помощью эквивалентных преобразований у матрицы С строится полная система независимых нулей и записывается ответ. Строится план задачи, у которой единицы строятся как раз на месте независимых нулей.

Определение. Элементы матрицы С, заданные на некотором этапе, которые стоят или в строке, или в столбце, выделяются знаком “+” будем называть выделенными элементами, а остальные будем называть невыделенными.

Замечание к блоку 8. На самом деле, при построении новых невыделенных нулей, число h отнимается от элементов в невыделенных строках и прибавляется к элементам в выделенных столбцах. И поэтому это преобразование является эквивалентным.





Дата публикования: 2014-11-18; Прочитано: 279 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...