Транспортная задача: постановка и решение

Что такое транспортная задача? 🎯

Представь, что у тебя есть несколько складов с товаром и несколько магазинов, которые хотят этот товар получить. Твоя задача — перевезти товар со складов в магазины так, чтобы затраты на перевозку были минимальными, при этом удовлетворив все запросы магазинов и не превысив запасы на складах. Это и есть классическая транспортная задача!

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

Ключевые элементы задачи

Чтобы формально описать задачу, нам нужно определить её основные части:

Поставщики (склады): Те, у кого есть товар. У каждого поставщика есть определенный запас (мощность).
Потребители (магазины): Те, кто нуждается в товаре. У каждого потребителя есть определенная потребность (спрос).
Тарифы (стоимости перевозки): Стоимость перевозки единицы товара от каждого поставщика к каждому потребителю.

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

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

Математическая модель 📐

Давай запишем всё это на математическом языке. Это поможет четко понять, что мы ищем.

Пусть:

m — количество поставщиков (складов)
n — количество потребителей (магазинов)
a_i — запас товара у i-го поставщика, где i = 1, 2, ..., m
b_j — потребность в товаре j-го потребителя, где j = 1, 2, ..., n
c_ij — стоимость перевозки единицы товара от поставщика i к потребителю j

Нам нужно найти такие объемы перевозок x_ij (сколько товара повезем от i-го склада в j-й магазин), чтобы:

Целевая функция (общая стоимость) была минимальна:

Z = ∑(i=1 to m)∑(j=1 to n) c_ij * x_ij  →  min

При следующих ограничениях:

1. Все со складов должно быть вывезено:
   ∑(j=1 to n) x_ij = a_i   для всех i = 1, 2, ..., m

2. Все запросы магазинов должны быть удовлетворены:
   ∑(i=1 to m) x_ij = b_j   для всех j = 1, 2, ..., n

3. Объемы перевозок не могут быть отрицательными:
   x_ij ≥ 0   для всех i и j

📘 Обрати внимание: если сумма запасов равна сумме потребностей, то все ограничения выполняются как строгие равенства. Это и есть закрытая модель.

Решение методом северо-западного угла 🧭

Один из самых простых и наглядных методов поиска начального опорного плана — метод северо-западного угла. Название говорит само за себя: мы начинаем заполнять таблицу перевозок с самой верхней левой ячейки (как будто это северо-запад на карте).

Алгоритм:

Создай таблицу, где строки — это поставщики, а столбцы — потребители.
Начни с ячейки (1,1) — самого "северо-западного" угла.
Выбери минимальное значение между запасом поставщика a₁ и потребностью потребителя b₁.
Запиши это значение в ячейку (1,1). Это и будет объем первой перевозки.
Вычти это значение из a₁ и b₁.
Если запас поставщика исчерпан, переходи к следующей строке (следующему поставщику).
Если потребность потребителя удовлетворена, переходи к следующему столбцу (следующему потребителю).
Повторяй шаги, пока не распределишь весь товар.

Решим задачу вместе! ✨

Условие:

У нас есть два склада и три магазина.

Запасы на складах: Склад 1 = 60 единиц, Склад 2 = 80 единиц.
Потребности магазинов: Магазин 1 = 40 ед., Магазин 2 = 60 ед., Магазин 3 = 40 ед.
Стоимости перевозок заданы таблицей:

	Магазин 1	Магазин 2	Магазин 3
Склад 1	5	3	4
Склад 2	7	2	6

Проверим, закрытая ли модель:

Сумма запасов = 60 + 80 = 140
Сумма потребностей = 40 + 60 + 40 = 140
140 = 140 → модель закрытая. ✔️

Шаг 1: Находим начальный опорный план методом северо-западного угла.

Строим таблицу для плана перевозок x_ij:

	Магазин 1	Магазин 2	Магазин 3	Запасы (a_i)
Склад 1	❓	❓	❓	60
Склад 2	❓	❓	❓	80
Потребности (b_j)	40	60	40