Главная Войти О сайте

Как решить задачу о назначениях

Задача о назначениях является частным случаем транспортной задачи, в которой число пунктов производства и пунктов назначения одинаково. В этом случае матрица транспортной таблицы будет иметь квадратную форму. Естественно, что для каждого пункта назначения объем потребности будет равен 1, а для каждого пункта производства величина предложения также будет равна 1. Чтобы решить задачу о назначениях, воспользуйтесь венгерским методом.Как решить задачу о назначениях

Решайте задачу о назначениях аналогично любой транспортной задаче и формализуйте ее в виде транспортной таблицы, в строках которой отражаются назначения, а в столбцах – расстояния до потребителей. В каждом столбце таблицы найдите минимальное значение и вычтите его из каждого элемента данной строки, затем проделайте эту же операцию для столбцов. Получается, что теперь в каждом столбце и каждой строке вы имеете, по крайней мере, по одному нулевому значению.

Найдите строку, которая содержит только одно нулевое значение стоимости, и поместите в эту ячейку один элемент. Если нет такой строки, то допускается начать решение задачи о назначении с любой ячейки, имеющей нулевую стоимость.

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

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

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

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


CompleteRepair.Ru