MоP

______________________________________________________________________________________________

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

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

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

3)Нахождение значений потенциалов строк и столбцов.

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

перепутатьсобъёмамиперевозок, они(оценки) заключаютсявкружки.

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

132 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

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

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

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

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

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

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

Для того, чтобы эти условия выполнялись, необходимо выбрать следующий объём перемещаемой продукции: θ =min {хij}–, где {хij}– – объёмы перево-

зок из клеток цикла пересчёта, помеченных знаком «–». θ = min{20; 30} = 20

8) Построение новой таблицы.

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

______________________________________________________________________________________________

Для того, чтобы вычислить значение целевой функции, достаточно вос-

пользоваться формулой: z1 = z0 – θ × бij, z1 = 320 – 2 × 20 = 280

Поскольку в последней таблице нет положительных оценок, то данное

Данное распределение является оптимальным, но не единственным, так как имеются нулевые оценки. Так как пятый потребитель является фиктивным, то соответствующий столбец в оптимальной матрице перевозок можно не записывать. Для нашего примера фиктивный объём перевозок (x25 = 60), показывает, что 60 единицпродукцииостанутсяневостребованными увторогопоставщика.

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

7.4. Усложнённые постановки транспортных задач

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

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

134 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

Сохранение установившихся связей

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

Например: пусть второй поставщик связан договором с третьим потребителем на поставку продукции в объёме 30 тонн. Перед решением задачи уменьшим запасы второго поставщика и потребность третьего потребителя на 30 тонн. После решения задачи увеличим значение клетки (2,3) последней таблицы на 30 тонн.

Условие полного обеспечения некоторого потребителя или полный вывоз продукции от некоторого поставщика

Такие условия возникают, когда исходная задача является открытой. Пусть суммарные объёмы запасов продукции, имеющейся у поставщи-

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

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