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

Задача 4. В таблице даны запасы (в тоннах) однородного сыпучего груза у поставщиков ( , , ), спрос на него потребителей ( , , , ), а также матрица тарифов перевозок, элементы которой равны стоимостям перевозок одной тонны груза из пункта отправления в пункт назначения (в условных денежных единицах)

Требуется:

1) Составить математическую модель транспортной задачи, заданной таблицей.

2) Найти оптимальный план перевозок груза, минимизирующий общую стоимость всех перевозок.

Решение:

1) Для составления математической модели данной транспортной задачи сначала введем переменные:

- количество единиц (тонн) груза, планируемое к перевозке из пункта отправления в пункт назначения ( ).

Затем запишем выражение целевой функции, имеющей смысл суммарной стоимости всех перевозок:

.

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

- все запасы груза должны быть вывезены;

- все потребности в грузе должны быть удовлетворены. Получаем следующую систему уравнений:

По смыслу задачи все переменные должны быть неотрицательными:

( )

Таким образом, приходим к следующей математической формулировке данной транспортной задачи:

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

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

2) Основными этапами решения поставленной транспортной задачи являются следующие:

- определение начального опорного плана;

- проверка полученного начального опорного плана на оптимальность;

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

Для нахождения начального опорного плана применим метод Фогеля. Приведем алгоритм метода Фогеля, следуя работе [4].

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

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

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

Обычно начальный опорный план, полученный методом Фогеля. Будет оптимальным или близким к оптимальному.

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

В результате реализации метода Фогеля все переменные оказываются разбитыми на 2 группы:

- базисные переменные : , , , , , , которые соответствуют ненулевым (загруженным) клеткам;

- свободные переменные : , , , , , , которые соответствуют нулевым (прочеркнутым) клеткам.

Проверим полученный методом Фогеля начальный опорный план на оптимальность. Для этого применим метод потенциалов, краткое изложение которого содержится, например, в работе [5].

Введем так называемые потенциалы пунктов отправления ( ) и потенциалы пунктов назначения ( ). Потенциалы найдем, решая систему линейных уравнений

,

где индексы и соответствуют группе базисных переменных .

В данном случае система уравнений для потенциалов имеет вид:

Составленная система содержит 6 уравнений и 7 неизвестных. Ранг системы равен . Следовательно, одна из неизвестных является свободной. Выберем в качестве этой переменной и примем ее равной нулю: .

Последовательно решая систему, найдем потенциалы всех поставщиков и потребителей:

, , , , , , .

Далее найдем так называемые косвенные стоимости в соответствии с формулой

,

где индексы и соответствуют группе свободных переменных :

, , ,

, , .

Затем вычисляем разности стоимостей (оценки свободных клеток) по формуле

.

Получим следующие значения оценок:

, ,

, ,

, .

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

Таким образом, искомый оптимальный план перевозок выражается равенствами

, , , ,

, , , ,

, , , .

Наименьшая суммарная стоимость всех перевозок, соответствующая найденному оптимальному плану, равна

(усл. ден. ед.)