Лекция 3. Транспортная задача

План.

3.1.Экономико-математическая модель транспортной задачи.

3.2. Нахождение первоначального базисного распределения поставок.

3.3. Решение транспортной задачи методом потенциалов.

3.1.Экономико-математическая модель транспортной задачи

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

В общем виде транспортную задачу можно представить следующим образом: в m пунктах производства А₁, А_2, , А_m имеется однородный груз в количествах соответственно а₁, а_2, , а_m. Этот груз необходимо доставить в n пунктов назначения В₁, В₂, , В_n в количествах, соответственно b₁, b₂, , b_n. Стоимость перевозки 1 ед. груза (тариф) из пункта А_i в пункт B_j равна с_ij ден. ед.

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

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

Определение 1. Если сумма запасов груза равна суммарной потребности в нем:

,

то транспортная задача называется закрытой.

Определение 2. Если сумма запасов груза не равна суммарной потребности в нем:

,

то транспортная задача называется открытой.

Рассмотрим закрытую транспортную задачу. Обозначим x_ij – количество груза, перевозимого из пункта А_i в пункт B_j.

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

при ограничениях:

.

Оптимальным решением является матрица

,

удовлетворяющая системе ограничений и доставляющая минимум целевой функции.

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

1) нахождение исходного опорного решения;

2) проверка этого решения на оптимальность;

3) переход от одного опорного решения к другому.

Рассмотри каждый из этапов.

3.2. Нахождение первоначального базисного распределения поставок

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

Существует несколько способов нахождения исходного опорного решения. Рассмотрим один из них – метод минимальной стоимости. В соответствии с этим методом грузы распределяются в первую очередь в те клетки, которым соответствует минимальный тариф перевозок с_ij. Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учетом оставшихся запасов у поставщиков и удовлетворения спроса потребителей. Процесс распределения продолжают до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены. При распределении грузов может оказаться, что количество занятых клеток меньше, чем m + n – 1. В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называются условно занятыми.

Рассмотрим нахождение исходного опорного решения транспортной задачи на примере.

На складах А₁, А₂, А₃, имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители В₁, В₂, В₃ должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Найти такой вариант перевозки, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей (ден. ед): .

Решение. Проверим, является ли данная транспортная задача закрытой.

,

.

,

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

bj ai		1	2	3
		140/50/0	300/0	160/60/0
1	90/0	2 90	5 -	2 -
2	400/100/0	4 -	1 300	5 100
3	110/60/0	3 50	6 -	8 60

Число занятых клеток в таблице равно 5, m + n – 1 = 3 + 3 – 1 = 5, т.е. условие невырожденности выполнено. Получено исходное опорное решение, которое запишем в виде матрицы:

.

Стоимость перевозки при исходном опорном решении составляет:

L(X) = 902 + 3001 + 1005 + 503 + 608 = 1610 ден. ед.