Методы решения транспортной задачи

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

Под потенциалами подразумевается произвольная система чисел, рассчитанных по правилу: для всех (т+п-1) заполненных клеток транспортной таблицы сумма потенциалов соответствующей строки и столбца должна равняться величине оценки этой клетки, то есть Общее количество потенциалов должно равняться величине (т+п), поскольку потенциалы определяются для каждого поставщика и потребителя, а количество заполненных клеток в таблице, как указывалось выше, должно быть равно величине (т+п-1) или на единицу меньше числа потенциалов. Поэтому на первом этапе расчета одному любому потенциалу разрешается придавать произвольное значение. Для удобства проведения расчетов рекомендуется потенциалу первой строки или первого столбца придавать нулевое значение.

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

Существует ряд приемов определения опорного плана, общим для которых является соблюдение правила:

количество заполненных клеток должно соответствовать величине (т+п-1), где т— количество потребителей, п — количество поставщиков. [4].

Метод «северо-западного угла». Первая строка вычеркивается, и двигается по столбику вниз. В клетку, находящуюся на пересечение первого столбца и второй строки, помещается максимально возможное число единиц, размешенное ограничениями на предложение и спрос: х₁₂= min (a₂, b₁-a₁).Если b₁-a₁₂, то х₂₁=b₁— a₁. спрос первого потребителя удовлетворен. Первый столбец вычеркивают и двигаются по второй строке вправо. Заполнив клетку, стоящую на пересечение второй строки и второго столбца, переходят к заполнению следующей третьей клетки строки второй строки, либо второго столбца. Процесс продолжают до тех пор, пока не исчерпается предложение и не удовлетворится спрос. Последняя заполненная клетка находится в последнем n-ой строке. [3]

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

Метод Фогеля. Составляют транспортную таблицу. Для каждой строки и каждого столбца транспортной таблицы определяют разность между наименьшим тарифом и ближайшим к нему значением. В строке или в столбце, которым соответствует наибольшая разность, выбирают клетку с наименьшим тарифом. В выбранную клетку, аналогично предыдущим методам, записывают максимально возможное число единиц продукции, которое разрешается ограничениями на предложение и спрос. После этого вычеркивают либо строку, если предложение поставщика исчерпано, либо столбец, если спрос потребителя удовлетворен. Если все клетки таблицы заполнены или вычеркнуты, то план перевозок построен. В противном случае переходят к шагу 2 без учета вычеркнутых и заполненных клеток. В методе Фогеля используются штрафы, взимаемые за неудачный выбор маршрута. Рассчитанные на шаге 2 разности между двумя уровнями затрат на перевозку являются штрафами за неверно выбранный маршрут перевозки. Метод Фогеля — наиболее трудоемкий, однако начальный план перевозок, построенный с его использованием, обычно бывает, близок к оптимальному плану, а в некоторых случаях является оптимальным планом.

Изложенные методы нахождения начального решения не единственные. В качестве начального решения может быть взят любой набор чисел, удовлетворяющих множеству допустимых планов (4.6) и условию баланса (4.7) (например, полученный по методу «юго-восточного» угла). Заметим, что для всех полученных решений число заполненных (отличных от нуля) клеток транспортной таблицы в точности равно числу базисных переменных задачи.

Определение 1. Если при решении транспортной задачи число заполненных клеток транспортной таблицы равно m+n-1, где т — число поставщиков, п — число потребителей, то план перевозок невырожденный.

Определение 2. Если число заполненных клеток транспортной таблицы меньше га+п-1, то план перевозок вырожденный.

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

Для нахождения оптимального плана перевозок необходимо уметь оценивать полученный план на оптимальность. Как это сделать, не имея в распоряжении всех возможных планов перевозок, которые можно было бы сравнить между собой? Для оценки плана на оптимальность вводится понятие косвенных затрат. Косвенные затраты — это затраты, получаемые для маршрутов, по которым не осуществляются перевозки при данном плане. Рассчитанные косвенные затраты сравниваются с реальными затратами, которые имели бы место, если бы перевозки по данным маршрутам осуществлялись. Если для всех невыбранных маршрутов косвенные затраты не больше реальных, то данный план перевозок является оптимальным. Если хотя бы для одного маршрута косвенные затраты больше реальных, то план перевозок может быть улучшен путем введения в него данного маршрута. Ввод нового маршрута в план перевозок соответствует вводу в список базисных переменных переменной транспортной задачи, соответствующей этому маршруту. Эти рассуждения лежат в основе ряда методов, применяемых для нахождения оптимального плана перевозок. Рассмотрим один из них — метод потенциалов. [4].