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

Для решения задач симплекс-методом необходимо наличие исходного опорного плана. Решение транспортной задачи также начинается с построения исходного опорного плана, который в транспортной задаче называется исходным распределением.

Определим, какое количество базисных переменных должно быть в опорном плане. Так как ограничения транспортной задачи содержат n+m уравнений, то количество базисных переменных также должно быть n+m, если все уравнения являются линейно независимыми. Однако в транспортной задаче эти уравнения линейно зависимы. Чтобы показать это, найдём суммы всех ограничений 1.8 и 1.9.

В каждом полученном уравнении мы будем иметь в левой части сумму всех неизвестных переменных х, а в правой части в одном из уравнений, , в другом . Поскольку задача закрытая, то эти суммы равны, то есть мы получили два одинаковых уравнения (линейно зависимых). Удалив любое из ограничений, мы получим систему из m+n-1линейно независимых уравнений. Таким образом, количество переменных в опорном плане должно быть m+n-1.

Метод северо-западного угла.При построении исходного распределения с помощью данного метода, из оставшихся клеток выбирается левая верхняя клетка (северо-западная). На первом этапе выбирается клетка (1, 1). В эту клетку записывается объём поставки х11= min {А1, В1}. Величины А1 и В1 уменьшаются на данную величину. Ту строку или столбец, где будет получен 0, удаляют из рассмотрения. Затем из оставшихся клеток, рассматривают левую верхнюю клетку и поступают аналогично. Продолжая данный процесс, мы заполним клетку (m, n), причем удалим из рассмотрения и строку и столбец. Если в процессе заполнения клеток придётся вычеркнуть и строку, и столбец, то мы получим вырожденное распределение (количество занятых клеток меньше, чем m+n-1). Чтобы этого не произошло, из рассмотрения удаляем что–то одно: или строку, или столбец, а оставшийся столбец или строку считают с нулевой потребностью или запасами.

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

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

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

Величины u_i называют потенциалами строк, а величины v_j называют потенциалами столбцов.

Алгоритм решения транспортной задачи.

1) Проверка типа транспортной задачи. Если транспортная задача открытая, то её необходимо преобразовать к закрытому типу.

2) Построение исходного распределения транспортной задачи любым из известных методов.

3) Нахождение значений потенциалов строк и столбцов. Количество уравнений, удовлетворяющих условию равняется m+n-1 (так как распределение должно быть невырожденным), а количество неизвестных u_i и v_j равняется m+n. Таким образом, количество переменных больше количества уравнений, причём все уравнения линейно независимы. Решение такой системы линейных уравнений является неопределённым, поэтому одному из потенциалов нужно присвоить любое значение. По традиции u_i =0. Получается система из m+n-1 уравнений с m+n-1 неизвестными переменными.

Эту систему можно решить любым методом и получить определённое решение.

На практике значения потенциалов вычисляется ещё проще. Рассматриваются занятые клетки, для которых один из потенциалов известен, и для них вычисляются значения неизвестных потенциалов.

4) Вычисление оценок для свободных клеток. Исходя из соотношения можно записать следующую формулу для вычисления оценок свободных клеток: . Для того чтобы оценки не перепутать с объёмами перевозок, они (оценки) заключаются в кружки.

5) Проверка распределения на оптимальность. Если оценки всех свободных клеток меньше или равны нулю, то данное распределение является оптимальным.

Необходимо вычислить оптимальное значение целевой функции Z и выписать оптимальные объёмы перевозок в виде матрицы. Если распределение не является оптимальным, то переходим к пункту 6.

6) Построение цикла пересчёта. В качестве исходной клетки выбирается клетка с наибольшей положительной оценкой. Эта клетка помечается знаком «+». В неё необходимо записать некоторый объём поставки. Но тогда нарушится баланс по данному столбцу, следовательно, одну из занятых клеток данного столбца необходимо пометить знаком «–», то есть уменьшить объём поставки на такую же величину. Но тогда изменится баланс по данной строке, следовательно, какую-то занятую клетку данной строки необходимо пометить знаком «+». Данный процесс продолжается до тех пор, пока не будет поставлен знак «–» в строке, где находилась исходная клетка.

Для любой свободной клетки существует цикл пересчёта и притом единственный.

7) Определение объёма перемещаемой продукции. При определении объёма продукции, перемещаемого по циклу пересчёта, мы должны исходить из следующих двух соображений:

а) после преобразования в клетках таблицы не должны получиться отрицательные числа;

б) одна из занятых клеток должна стать свободной.

Для того, чтобы эти условия выполнялись, необходимо выбрать следующий объём перемещаемой продукции: – где – объемы перевозок из клеток цикла пересчета, помеченных знаком «–».

8) Построение новой таблицы. К значениям клеток, помеченных знаком «+», прибавляется θ. От значений клеток, помеченных знаком «–» вычитается θ. Значение поставок остальных клеток переписывается без изменений. Переходим к выполнению пункта 3.

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