Cтраница 2
Следует, однако, иметь в виду, что венгерский метод существенно использует возможность быстрого обращения к любому элементу матрицы стоимостей и его буквальное использование при решении задач большого размера ( требующих использования внешней памяти) может оказаться неэффективным. [16]
Можно оценить трудоемкость построения максимального паросочетания и получить из нее трудоемкость венгерского метода, однако приведенная нами вычислительная схема неоптимальна. Между тем венгерский метод в удачных реализациях оказывается высокоэффективным. [17]
Другой мощный метод получения оценок типа ( 48), так называемый венгерский метод, бы л предложен И. [18]
Теорема 12 следует из предыдущей ввиду того, что на каждом шаге венгерского метода строится новое паросоче-тание, соответствующее большему значению исходной целевой функции, а число наборов независимых элементов конечно. [19]
В задачах принятия оперативных решений, реализуемых в многообъектных системах управления, использование венгерского метода решения, метода Мака или КУП, отличающихся наименьшими затратами вычислительных ресурсов, допустимо далеко не всегда. Нередко требуется получить решение задачи в столь короткое сроки, что применить любой из точных методов решения невозможно. В этих условиях обычно можно удовлетвориться любым не худшим решением. [20]
Первоначальную матрицу определяют в результате проведения подготовительного этапа, аналогичного одноименному этапу в венгерском методе. [21]
В настоящее время разработано множество различных алгоритмов решения Т.з.: распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, способ двойного предпочтения, различные сетевые методы. Они относительно просты, по ним составлены десятки программ для различных вычислительных машин. Во многих снабженческих, транспортных и других организациях во всем мире с их помощью рассчитываются маршруты доставки материалов на строительные площадки, планы длительного прикрепления поставщиков металлопроката к потребителям, планы перевозок топлива. Задачи эти часто усложняются разного рода дополнительными условиями; напр. Кроме того, следует учитывать, что экономико-математическая модель Т.з. позволяет описывать множество ситуаций, весьма далеких от проблемы перевозок, в частности, находить оптимальное размещение заказов на производство изделий с разной себестоимостью. [22]
Одним из наиболее распространенных и эффективных, с вычислительной точки зрения, алгоритмов решения классической транспортной задачи является так называемый венгерский метод. [23]
Решение задачи выбора, таким образом, представляет собой перестановку п чисел ( число возможных вариантов решений равно и. Применение венгерского метода существенно сокращает трудоемкость решения задачи. [24]
Можно оценить трудоемкость построения максимального паросочетания и получить из нее трудоемкость венгерского метода, однако приведенная нами вычислительная схема неоптимальна. Между тем венгерский метод в удачных реализациях оказывается высокоэффективным. [25]
Модули решения общей задачи линейного программирования обеспечивают решение общей задачи линейного программирования симплекс-методом и модифицированным симплекс-методом. Модули решения транспортной задачи реализуют решение венгерским методом задачи выбора, замкнутой модели транспортной задачи и транспортной задачи с ограниченными пропускными способностями коммуникаций. [26]
Далее выбранные пути корректируют в сторону увеличения пропускной способности цепи по определенным ( очень несложным) правилам. Для решения задач на сетях существует также венгерский метод, являющийся модификацией метода Форда - Фалкерсона. [27]
Хотя для транспортной задачи есть методы, которые проще методов решения общей задачи линейного программирования, особенности задачи о назначениях позволяют решить ее с помощью более простых приемов. Эффективным методом решения задачи о назначениях является венгерский метод, который рассматривается ниже. [28]
Время вычисления при решении задачи о назначениях с использованием венгерского метода оценивается как kn3 ( см. гл. Самый плохой случай при вычислении границы ( что касается времени вычисления) возникает тогда, когда все циклы при каждом стягивании содержат только по две вершины. [29]
Время вычисления при решении задачи о назначениях с использованием венгерского метода оценивается как А ге3 ( см. гл. А; - некоторая постоянная, а п - порядок матрицы. Самый плохой случай при вычислении границы ( что касается времени вычисления) возникает тогда, когда все циклы при каждом стягивании содержат только по дв & вершины. [30]