Транспортная задача: опорный план и метод потенциалов с примером

Три склада с цементом: 30, 40 и 20 тонн. Четыре стройки с заявками: 20, 25, 35 и 10 тонн. Перевозка тонны с каждого склада на каждую стройку стоит своих денег — тарифов двенадцать, и они все разные. Диспетчеры спорят о плане: один грузит «по порядку, пока не кончится», другой — «по самой дешёвой клетке». Первый план обойдётся в 285 тысяч, второй — в 185. Оптимум же — 175, и до него можно добраться за один ход. Как именно — вопрос метода потенциалов.

Постановка: тарифы, запасы, заявки#

Поставщиков $m$, потребителей $n$. У поставщика $i$ запас $a_i$, у потребителя $j$ — заявка $b_j$. Перевозка тонны от $i$ к $j$ стоит $c_{ij}$, а переменная $x_{ij}$ — сколько тонн везём. Цель — минимизировать общую стоимость:

Ограничения двоякие: из каждого склада всё вывезти (${\sum }_j{x}_{ij}=a_i$), каждую заявку закрыть (${\sum }_i{x}_{ij}=b_j$). Это линейная задача с особой структурой: в каждом ограничении участвуют переменные только одной строки или одного столбца таблицы. Именно эта ленивая структура и порождает отдельный метод вместо общего симплекса.

Модель называется закрытой, когда суммарный запас равен суммарной заявке: $\sum a_i=\sum b_j=90$. Равенство не декоративное: без него не бывает планов, закрывающих и склады, и заявки одновременно. Если запасов больше, вводят фиктивного потребителя с нулевыми тарифами — «склад остатков»; если заявок больше — фиктивного поставщика. Открытая модель сводится к закрытой и дальше решается по общей схеме.

Фиктивные строки и столбцы безобидны: нулевой тариф не влияет на сумму, а фиктивные перевозки лишь показывают, сколько груза останется на складе или сколько заявки не будет закрыто. В выводе их аккуратно отбрасывают, но при расчёте потенциалов они участвуют наравне с настоящими — пропуск этого нюанса ломает проверки на полпути. Держите таблицу полной: $m$ строк, $n$ столбцов, ни одной дырки.

Опорный план: северо-западный угол против минимального элемента#

Опорный план — допустимый план, у которого занятых клеток ровно $m+n-1$: у нас $3+4-1=6$. Занятая клетка — перевозка, вошедшая в базис. Классических способа построить стартовый план два, и они исповедуют разные философии.

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

1. 1
   Клетка (1,1): $x_{11}=\min (30,20)=20$. Заявка Б1 закрыта, у А1 остаток 10.
2. 2
   Клетка (1,2): $x_{12}=\min (10,25)=10$. Склад А1 пуст, у Б2 остаток 15.
3. 3
   Клетка (2,2): $x_{22}=\min (40,15)=15$. Б2 закрыта, у А2 остаток 25.
4. 4
   Клетка (2,3): $x_{23}=\min (25,35)=25$. А2 пуст, у Б3 остаток 10.
5. 5
   Клетка (3,3): $x_{33}=\min (20,10)=10$. Б3 закрыта, у А3 остаток 10.
6. 6
   Клетка (3,4): $x_{34}=\min (10,10)=10$. Всё вывезено, всё доставлено.

Занятых клеток шесть — план невырожден. Стоимость: $20\cdot 2+10\cdot 3+15\cdot 2+25\cdot 5+10\cdot 2+10\cdot 4=285$ тысяч. Метод ни разу не взглянул на тарифы — он просто заполняет матрицу слева направо, сверху вниз.

Метод минимального элемента

1. 1
   Минимальный тариф 1 — клетка (2,4): $x_{24}=\min (40,10)=10$. Заявка Б4 закрыта.
2. 2
   Среди оставшихся тариф 2 стоит в (1,1), (1,3), (2,2), (3,3). Берём (1,1): $x_{11}=\min (30,20)=20$. Б1 закрыта.
3. 3
   Клетка (1,3): $x_{13}=\min (10,35)=10$. Склад А1 пуст.
4. 4
   Клетка (2,2): $x_{22}=\min (30,25)=25$. Б2 закрыта.
5. 5
   Клетка (3,3): $x_{33}=\min (20,25)=20$. Склад А3 пуст, у Б3 остаток 5.
6. 6
   Остатки встречаются в клетке (2,3): $x_{23}=5$. План построен.

Занятых клеток снова шесть. Стоимость: $10\cdot 1+20\cdot 2+10\cdot 2+25\cdot 2+20\cdot 2+5\cdot 5=185$ тысяч — на сто дешевле северо-западного. Жадный выбор работает лучше слепого, но оптимума не гарантирует: дешёвые клетки набиты, а дорогая (2,3) с тарифом 5 всё равно в плане.

Проверка на невырожденность: m + n − 1 занятых клеток#

Число $m+n-1$ — не прихоть, а размер базиса: столько уравнений содержит система для потенциалов. В обоих наших планах занято 6 клеток — проверка пройдена. Если клеток меньше, план вырожден: потенциалы восстановить не удастся, система распадётся на куски. Лечение — нулевая перевозка: в подходящую клетку помещают формально пустую, но «базисную» поставку, и счёт продолжается. Если клеток больше — план содержит цикл и опорным не является.

Метод потенциалов: оценки клеток#

Присвоим каждому складу потенциал $u_i$, каждой стройке $v_j$ так, чтобы для занятых клеток выполнялось $u_i+v_j=c_{ij}$. Уравнений $m+n-1=6$, неизвестных $m+n=7$ — одного не хватает, поэтому $u_1$ фиксируем нулём, остальные определяются последовательно.

1. 1
   $u_1=0$. Из клетки (1,1): $v_1=2$; из клетки (1,3): $v_3=2$.
2. 2
   Из (2,3): $u_2=5-v_3=3$; из (2,2): $v_2=2-3=-1$; из (2,4): $v_4=1-3=-2$.
3. 3
   Из (3,3): $u_3=2-v_3=0$. Итого $u=(0,3,0)$, $v=(2,-1,2,-2)$.

Теперь оцениваем свободные клетки: ${\Delta }_{ij}=c_{ij}-u_i-v_j$. Оценка отвечает на вопрос: что произойдёт с суммой, если протащить тонну через эту клетку?

Одна клетка с минусом: (2,1), $\Delta =-2$. Каждая тонна, пропущенная через неё, экономит две тысячи. План не оптимален — улучшаем.

Цикл перераспределения: одна итерация#

Строим цикл: замкнутую ломаную по строкам и столбцам с вершинами в занятых клетках, стартующую в клетке (2,1). Здесь цикл прямоугольный: (2,1) → (1,1) → (1,3) → (2,3) → обратно в (2,1). Расставляем знаки поочерёдно: плюс в стартовой клетке, минус в следующей — и так по кругу.

1. 1
   Знаки: $(2,1{)}^{+}$, $(1,1{)}^{-}$, $(1,3{)}^{+}$, $(2,3{)}^{-}$.
2. 2
   Сдвиг $\theta$ — минимум по минусовым клеткам: $\min (x_{11},x_{23})=\min (20,5)=5$.
3. 3
   Прибавляем 5 к плюсовым клеткам, вычитаем из минусовых: $x_{21}=5$, $x_{11}=15$, $x_{13}=15$, $x_{23}=0$ — клетка (2,3) уходит из базиса.
4. 4
   Новая стоимость: $185+(-2)\cdot 5=175$ тысяч — оценка клетки в точности предсказала выигрыш.

Проверка балансов обязательна: А1 отгружает $15+15=30$, А2 — $5+25+10=40$, А3 — $20$; заявки закрыты: $20$, $25$, $35$, $10$. Контрольный пересчёт потенциалов нового плана даёт $u=(0,1,0)$, $v=(2,1,2,0)$, и все шесть свободных клеток получают оценки $2,4,2,2,2,6$ — ни одной отрицательной. План оптимален, $Z^{\ast }=175$.

Когда план оптимален и что это даёт#

• Критерий метода потенциалов: план оптимален, если все оценки свободных клеток ${\Delta }_{ij}\ge 0$.
• Вырожденность: занятых клеток меньше $m+n-1$ — добавляют нулевую перевозку, иначе потенциалы не восстановятся.
• Потенциалы — двойственные оценки: склады и заявки получают цены, и критерий ${\Delta }_{ij}\ge 0$ — это условие двойственности в действии. Мостик — двойственность в ЛП.
• Связь с симплексом: транспортная задача — частный случай ЛП, и симплекс-метод решает её тоже, просто медленнее: клеточная структура экономит сотни нулей в таблице.

Родственная классика — потоки в сетях: там тоже двигают «тонны» по рёбрам и ищут бутылочное горлышко; см. потоки в сетях и словарную статью про поток в сети. Начало всей линии — линейное программирование с полуплоскостями и вершинами.

Следующий шаг: измените условие — уменьшите запас склада А3 с 20 до 15 тонн. Баланс сломается: запасов 85, заявок 90. Добавьте фиктивного поставщика с запасом 5 и нулевыми тарифами, постройте опорный план минимальным элементом и доведите его до оптимума потенциалами. Одна-две итерации улучшения — лучшая тренировка перед контрольной.