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

Транспортная задача решается в два этапа. На первом этапе находят любое допустимое решение, удовлетворяющее системам (1.1)-(1.3). Такое решение называется первоначальным базисным распределением поставок. Затем, с помощью метода потенциалов, делают такие преобразования с первоначальным распределением поставок, чтобы получить оптимальное распределение поставок. Рассмотрим вначале нахождение первоначального базисного распределения поставок.

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

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

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

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

Затем двигаемся по первой строке таблицы и заносим в клетку (1,2) . Если , то запасы первого поставщика исчерпаны и из дальнейшего рассмотрения выпадает первая строка.

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

Метод наименьших затрат

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

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

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

Метод Фогеля

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

Покажем на примере, как находится первоначальное базисное распределение поставок методом наименьших затрат.

2.2 Пример закрытой транспортной задачи

Имеется три поставщика некоторого товара А1, А2, А3, у которых соответственно имеются 160, 310 и 250 условных единиц (у. е.) товара. В данном товаре нуждаются города B1, B2, B3, B4 в количествах, равных, соответственно, 100, 170, 200 и 250 у. е. Стоимость перевозки единицы продукции от поставщиков к потребителям задается следующей таблицей:

Поставщики	Мощность Поставщиков	Потребители и их спрос
		B1	B2	B3	B4
		100	170	200	250
А1	160	5	8	24	16
А2	310	7	12	9	5
А3	250	15	17	10	7

Составим экономико-математическую модель данной задачи.

Обозначим через - объём перевозки от поставщика А_i к потребителю B_j.

Тогда суммарные затраты на перевозку F составят:

Заданные мощности поставщиков и спрос потребителей накладывают ограничения на значения объемов перевозок :

мощности всех поставщиков должны быть реализованы:

Спросы потребителей должны быть удовлетворены:

Объемы перевозимых грузов не могут быть отрицательными:

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

В силу того, что

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

Находим первоначальное базисное распределение поставок методом наименьших затрат.

Находим в таблице клетку с наименьшим коэффициентом затрат. Таких клеток у нас две, а именно: (1,1) и (2,4). В этих клетках коэффициент затрат равен 5. Находим максимально возможные поставки в эти клетки:

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

.

Наибольшая максимально возможная поставка будет в клетку (2,4). Поэтому реализуем эту поставку в клетку (2,4), т. е. даем этой клетке груз в количестве 250 у.е. Тогда, спрос четвертого потребителя полностью будет удовлетворен. Клетку (2,4) считаем заполненной, и перечеркиваем ее жирной сплошной линией. При этом выпадают из дальнейшего рассмотрения остальные клетки четвертого столбца (спрос четвертого потребителя полностью удовлетворен), их перечеркиваем тонкими линиями.

Поставщики	Мощность Поставщиков	Потребители и их спрос
		B1	B2	B3	B4
		100	170	200	250
А1	160	5	8	24	16
А2	310	7	12	9	5 250
А3	250	15	17	10	7

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

Поставщики	Мощность Поставщиков	Потребители и их спрос
		B1	B2	B3	B4
		100	170	200	250
А1	160	5 100	8	24	16
А2	310	7	12	9	5 250
А3	250	15	17	10	7

В оставшихся не перечеркнутых никакой линией клетках находим клетку с наименьшим коэффициентом затрат. Это клетка (1,2), коэффициент затрат в которой равен 8. Максимально возможная поставка в эту клетку будет:

.

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

Поставщики	Мощность Поставщиков	Потребители и их спрос
		B1	B2	B3	B4
		100	170	200	250
А1	160	5 100	8 60	24	16
А2	310	7	12	9	5 250
А3	250	15	17	10	7

В оставшихся не перечеркнутых никакой линией клетках находим клетку с наименьшим коэффициентом затрат. Это клетка (2,3), коэффициент затрат в которой равен 9. Максимально возможная поставка в эту клетку будет:

.

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

Поставщики	Мощность Поставщиков	Потребители и их спрос
		B1	B2	B3	B4
		100	170	200	250
А1	160	5 100	8 60	24	16
А2	310	7	12	9 60	5 250
А3	250	15	17	10	7

В оставшихся не перечеркнутых никакой линией клетках находим клетку с наименьшим коэффициентом затрат. Это клетка (3,3), коэффициент затрат в которой равен 10. Максимально возможная поставка в эту клетку будет:

.

Реализуем эту поставку, при этом спрос третьего потребителя полностью будет удовлетворен, и таблица будет иметь вид:

Поставщики	Мощность Поставщиков	Потребители и их спрос
		B1	B2	B3	B4
		100	170	200	250
А1	160	5 100	8 60	24	16
А2	310	7	12	9 60	5 250
А3	250	15	17	10 140	7

Из не перечеркнутых никакой линией клетках осталась одна клетка. Это клетка (3,2), коэффициент затрат в которой равен 17. Максимально возможная поставка в эту клетку будет:

.

Реализуем эту поставку, при этом получим первоначальное базисное распределение поставок:

Поставщики	Мощность Поставщиков	Потребители и их спрос
		B1	B2	B3	B4
		100	170	200	250
А1	160	5 100	8 60	24	16
А2	310	7	12	9 60	5 250
А3	250	15	17 110	10 140	7

Проверка (обязательна!).

После нахождения первоначального распределения поставок необходимо выполнить две проверки.

1 проверка. Необходимо проверить суммы по строкам, которые должны совпадать с мощностями поставщиков и суммы по столбцам, которые должны совпадать со спросами потребителей. Для нашего примера:

суммы по строкам:

100+60=160

60+250=310

110+140=250

суммы по столбцам:

100=100

60+110=170

60+140=200

250=250.

Видим, что совпадают.

2 проверка. Количество заполненных клеток должно быть равно m+n-1.

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

Проверяем количество заполненных клеток (перечеркнутых жирной линией). Их 6, а m+n-1=4+3-1=6. В нашем примере не нужно вводить фиктивные нулевые поставки.

Найдем суммарные затраты на перевозку груза при первоначальном распределении поставок: