Транспортная задача

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

Определение 1. Если суммарное количество грузов, имеющихся у поставщиков, совпадает с суммарным количеством грузов, необходимых потребителям, то такая транспортная задача называется закрытой. Если эти объемы не совпадают - транспортная задача называется открытой.

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

либо «ложных потребителей», если

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

Методы решения транспортных задач также реализуются с помощью таблиц.

Для построения первоначального опорного плана существуют различные методы.

1. Метод северо-западного угла.

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

Пример. Поставщики имеют: А₁ - 100 ед. груза, А₂ – 250, А₃ – 200,

А₄ - 300. Потребители запрашивают: В₁ - 200 ед. груза, В₂ – 200, В₃ – 100, В₄ – 100, В₅ - 250.

Матрица стоимостей имеет вид

Составить первоначальный опорный план транспортной задачи методом северо-западного угла.

Проверим суммы грузов поставщиков и потребителей:

100 + 250 + 200 + 300 = 850

200 + 200 + 100 + 100 + 250 = 850.

Следовательно, транспортная задача закрытая. Составляем таблицу:

В клетку А₁В₁ проставляем данные (все, что есть у А₁). Другим потребителям от него ничего не достанется, в остальных клетках первой строки ставим прочерки. Так как В₁ запрашивает 200 единиц, добавляем ему 100 ед.груза от второго поставщика, у которого после этого остается еще 150 единиц. Остаток мы полностью отгружаем второму потребителю. И так далее по всей таблице.

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

Определим стоимость перевозок по нашему плану:

2. Метод минимальной стоимости.

Он состоит в последовательном полном удовлетворении потребителей при наименьшей стоимости перевозок. Для той же задачи имеем:

Определим стоимость перевозок:

По сравнению с методом северо-западного угла получили меньшую стоимость перевозок.

3. Метод двойного предпочтения.

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

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

Для той же задачи получим таблицу:

Определим стоимость перевозок по этому плану:

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

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

Условия оптимальности плана транспортной задачи

Теорема 1. Ранг матрицы транспортной задачи на единицу меньше числа уравнений.

Из этой теоремы следует, что транспортная задача всегда имеет множество решений. Но цель решающего задачу - найти из них оптимальное.

Определение. План транспортной задачи называется невырожденным, если количество заполненных клеток равно k + п - 1, где k - количество поставщиков; п - количество потребителей. План называется вырожденным, если число заполненных клеток меньше, чем k + п - 1.

Если план является вырожденным, то его дополняют условно заполненной клеткой, вписывая в нее груз в объеме нуль единиц.

Теорема 2 (условие оптимальности плана транспортной задачи).

Для того чтобы план транспортной задачи был оптимальным, необходимо и достаточно выполнить следующие условия:

- для занятых клеток

- для свободных клеток

где , — переменные задачи двойственной данной.

Коэффициент называют потенциалом поставщика, а ~. потенциалом потребителя.

Построение системы потенциалов и проверка плана на оптимальность.

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

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

Пример. Рассмотрим опорный план для транспортной задачи п. 5, построенный по методу двойного предпочтения, и проверим его на оптимальность.

Условий у нас 9, а заполненных клеток – 7. Следовательно, план является вырожденным.

Пусть потенциал U₂ будет равен 0. Тогда потенциал V₁ = U₂+ С₂₁ = 0 +2 = 2, а потенциал V₃= U₂ + c₂₃ = 0 + 10 = 10.

От потенциала V₃ перейдем к потенциалу U₄, исходя из уравнения

V₃ = U₄ + c₄₃. Получим 10 = U₄ + 12, или U₄ = -2. От этого потенциала перейдем к V₅ = 11 и V₂ = 6. Потенциал V₅ дает возможность вычислить U₃ ⁼ 9.

На этом процесс остановился в силу вырожденности задачи. Чтобы найти остальные потенциалы, необходимо заполнить нулем клетку, первой строки или четвертого столбца. Пусть это будет клетка с наименьшей стоимостью перевозок - 2. Тогда от U₃ = 9 переходим к V₄ =9 + 2 = 11, а от него к U₁= 10.

Система потенциалов построена.

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

Отмечаем в клетке A₂B₄ нарушение условия оптимальности. Это значит, что план не является оптимальным. Нужно перераспределить поставки, чтобы стоимость перевозок оказалась меньше, чем в данном плане.