♟️ Теория игр

Симплекс-метод или транспортная задача: что и когда применять

Q: Как проверить план транспортной задачи на оптимальность?

Методом потенциалов: для базисных клеток подберите $u_i$ и $v_j$ так, чтобы $u_i + v_j = c_{ij}$, зафиксировав один потенциал нулём. Затем для каждой свободной клетки проверьте $u_i + v_j \le c_{ij}$. Всё прошло — план оптимален; нашлось превышение — пускайте цикл перераспределения через эту клетку: сдвиг ограничен самой скудной из убывающих клеток.

Симплекс-методТранспортная задача

Коротко: Транспортная задача — частный случай линейного программирования с матрицей из нулей и единиц: циклы перераспределения и потенциалы решают её быстрее и проще общего симплекса. Общий симплекс возвращают, когда появляются нецелые мощности, фиксированные маршруты и прочие ограничения сверх баланса.

План на семестр Вердикт: с чего начать

Задача в одну строку: два склада с запасами 30 и 40 тонн, три магазина с потребностями 20, 25 и 25, тарифы перевозки — таблица два на три. Можно садиться и решать симплексом: шесть переменных, пять ограничений баланса, час аккуратной возни со столбцами отношений. А можно заметить структуру — и закрыть задачу четырьмя клетками транспортной таблицы, вообще без симплексной механики. Разберём, почему здесь работает укороченный путь, посчитаем два стартовых плана (140 и 200 за один и тот же груз) и честно скажем, когда без общего симплекса не обойтись.

Рамка общая: транспортная задача — частный случай линейного программирования, а не отдельная наука. Формулировка:

min i = 1 \sum m j = 1 \sum n c_{ij} x_{ij} при j = 1 \sum n x_{ij} = a_{i}, i = 1 \sum m x_{ij} = b_{j}, x_{ij} \geq 0

c_{ij}

— тариф перевозки от поставщика

i

потребителю

j

x_{ij}

— объём,

a_{i}

— запасы,

b_{j}

— потребности; суммы по строкам и столбцам фиксированы

Матрица ограничений здесь из нулей и единиц: каждая переменная входит ровно в два уравнения — баланс своей строки и своего столбца. Уравнений m + n, но одно из них лишнее: сумма запасов равна сумме потребностей, поэтому ранг равен m + n − 1, и базисный план несёт ровно m + n − 1 заполненных клеток. Для нашей задачи 2 + 3 − 1 = 4. Эта вырожденность — не дефект, а структура, которую спец-алгоритм использует на полную; общий алгоритм — в уроке симплекс-метод, частный — в уроке транспортная задача.

Критерий	Общий симплекс	Транспортная задача
Форма ограничений	любая матрица: дробные коэффициенты, любые знаки	матрица из нулей и единиц, балансы строк и столбцов
Размер базиса	m переменных при m ограничениях	m + n − 1 клеток при m·n тарифах
Шаг алгоритма	выбор вводимого столбца, пересчёт всей таблицы	цикл перераспределения: плюс-минус по замкнутому маршруту
Оценки ценности	теневые цены из двойственной задачи	потенциалы $u_{i}$ и $v_{j}$ — те же цены в табличной упаковке
Арифметика	столбцы отношений, ведущий элемент	сложение и вычитание в клетках
Когда выбирают	произвольные задачи ЛП	перевозки, распределение, назначение ресурсов

Транспортный алгоритм — тот же симплекс, переписанный под таблицу перевозок

Почему специальный алгоритм обыгрывает общий#

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

Проверка оптимальности тоже упрощается до сложения. В симплексе теневые цены достают из двойственной задачи — её разбор в уроке двойственность в ЛП; в транспортной таблице те же числа называют потенциалами: для базисной клетки потенциал строки плюс потенциал столбца дают тариф, $u_{i} + v_{j} = c_{ij}$ . Один потенциал фиксируют нулём, остальные вычитаются по цепочке. Кто решал матричную игру через линейное программирование — узнаёт ту же двойственную кухню в профиль.

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

Любому методу потенциалов нужен стартовый опорный план с m + n − 1 заполненными клетками. Классических способа два. Северо-западный угол — механический: заполняем таблицу с левого верхнего угла, не глядя на тарифы. Метод минимального элемента — жадный: каждый раз везём по самому дешёвому доступному тарифу. Ни тот ни другой не обязан дать оптимум — они дают точку старта. Но качество старта экономит циклы перераспределения. Считаем оба на нашей задаче.

Шаг 1: самый дешёвый тариф во всей таблице — 1, клетка второй строки и третьего столбца. Перевозим всё, что можно: min(40, 25) = 25. Потребитель 3 закрыт целиком, у второго поставщика остаток 15.
Шаг 2: из оставшихся клеток дешевле всех тариф 2 — первая строка, второй столбец: min(30, 25) = 25. Потребитель 2 закрыт, у первого поставщика остаток 5.
Шаг 3: далее самый дешёвый доступный тариф 3 — вторая строка, первый столбец: min(15, 20) = 15. Второй поставщик исчерпан, у первого потребителя недобор 5.
Шаг 4: последняя клетка — тариф 4, первая строка, первый столбец: min(30, 5) = 5. Все запасы распределены, все потребности закрыты, заполнено ровно 4 клетки.
Шаг 5: стоимость: 5·4 + 25·2 + 15·3 + 25·1 = 20 + 50 + 45 + 25 = 140.

	Потребитель 1	Потребитель 2	Потребитель 3	Запасы
Поставщик 1	5 (тариф 4)	25 (тариф 2)	—	30
Поставщик 2	15 (тариф 3)	—	25 (тариф 1)	40
Потребности	20	25	25	70

Опорный план методом минимального элемента: 4 базисные клетки, стоимость 140

Шаг 1: клетка (1, 1), тариф 4: min(30, 20) = 20. Потребитель 1 закрыт, у поставщика 1 остаток 10.
Шаг 2: двигаемся вправо, клетка (1, 2), тариф 2: min(10, 25) = 10. Поставщик 1 исчерпан, у потребителя 2 остаток 15.
Шаг 3: спускаемся вниз, клетка (2, 2), тариф 5: min(40, 15) = 15. Потребитель 2 закрыт, у поставщика 2 остаток 25.
Шаг 4: клетка (2, 3), тариф 1: min(25, 25) = 25. Таблица закрыта.
Шаг 5: стоимость: 20·4 + 10·2 + 15·5 + 25·1 = 80 + 20 + 75 + 25 = 200.

	Потребитель 1	Потребитель 2	Потребитель 3	Запасы
Поставщик 1	20 (тариф 4)	10 (тариф 2)	—	30
Поставщик 2	—	15 (тариф 5)	25 (тариф 1)	40
Потребности	20	25	25	70

Опорный план северо-западным углом: та же структура, стоимость 200

Разница — 140 против 200 — целиком заслуга выбора клеток: жадный метод повёз груз по дешёвым тарифам, механический — как пришлось. Проверьте суммы сами: по строкам 30 и 40, по столбцам 20, 25 и 25 — баланс сошёлся в обеих таблицах. Заметьте и это: клетку с самым дорогим тарифом 5 северо-западный угол загрузил пятнадцатью единицами, минимальный элемент — ни одной. На экзамене обычно просят оба плана и сравнение: разница в 60 единиц стоимости наглядно показывает, что стартовый план — это ещё не решение.

Проверка оптимальности: потенциалы u + v = c#

Механика проверки. Потенциалы вводятся для базисных клеток равенством $u_{i} + v_{j} = c_{ij}$ : неизвестных m + n, независимых уравнений m + n − 1, поэтому один потенциал фиксируют нулём — обычно $u_{1} = 0$ — и вычитают остальные. Для плана минимального элемента цепочка короткая:

u_{1} + v_{1} = 4, u_{1} + v_{2} = 2, u_{2} + v_{1} = 3, u_{2} + v_{3} = 1

равенства по четырём базисным клеткам; при

u_{1} = 0

получается

v_{1} = 4

v_{2} = 2

u_{2} = - 1

v_{3} = 2

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

u_{i} + v_{j} \leq c_{ij} для всех свободных клеток

критерий оптимальности: превышение означает, что по циклу через эту клетку стоимость можно снизить

Подставляем. Клетка (1, 3): 0 + 2 = 2 ≤ 5 — запас 3. Клетка (2, 2): −1 + 2 = 1 ≤ 5 — запас 4. Обе свободные клетки прошли, значит план со стоимостью 140 оптимален: жадный старт здесь попал в цель с первого раза, перераспределений не понадобилось. Рассчитывать на такое всегда нельзя — минимальный элемент даёт хорошую точку старта, но проверка потенциалами обязательна в любом случае. И приятный факт для контроля: полный перебор всех допустимых планов этой маленькой задачи подтверждает, что дешевле 140 не бывает.

Связь с общим симплексом прямая. Потенциалы — те же двойственные переменные, теневые цены строк и столбцов; проверка $u_{i} + v_{j} \leq c_{ij}$ — та же проверка знаков оценок, записанная в терминах таблицы. Экономия не в идее, а в объёме арифметики: вместо пересчёта столбцов отношений — вычитание в шести клетках и два коротких вектора.

Когда без общего симплекса не обойтись#

Транспортный аппарат работает, пока ограничения укладываются в схему «сумма по строке, сумма по столбцу, x ≥ 0». Добавьте что-то сверх — и задача перестаёт быть транспортной в узком смысле: циклы перераспределения больше не описывают допустимые шаги. Типовые поводы вернуться к общему симплекс-методу:

Что появилось в задаче	Почему таблица ломается	Что делать
нецелые мощности и потребности	вычёркивание строк и столбцов становится кропотливым, вырожденные базисы множатся	общий симплекс
минимальные объёмы по маршрутам ( $x_{ij} \geq l_{ij}$ )	нижняя граница сверх двух балансов на переменную	общий симплекс или сдвиг переменных
фиксированные маршруты ( $x_{ij} = v$ )	равенство третье по счёту — таблица его не видит	общий симплекс
транзит через промежуточные пункты	переменная получает третий баланс	сетевые постановки, общий симплекс
несколько продуктов на одной сети	тариф зависит уже не только от клетки	общий симплекс

Появилась строка в ограничениях сверх балансов — транспортная таблица уступает место симплексу

Проверь себя+15 XP

План минимального элемента дал стоимость 140. Как проверить, оптимален ли он?

Проверь себя+15 XP

Почему базисный план транспортной задачи несёт ровно m + n − 1 заполненную клетку?

Как это спрашивают на зачёте

Типовой номер: постройте опорный план двумя способами и сравните стоимости — любят проверять, не перепутали ли вы вычёркивание строк и столбцов. Второй: проверьте план на оптимальность потенциалами — сначала зафиксируйте один потенциал нулём, затем проверьте свободные клетки. Третий вопрос-ловушка: «почему в базисе ровно m + n − 1 клеток» — правильный ответ про ранг матрицы ограничений, а не про количество тарифов; возражение «а если тарифы дробные» — мимо.

Частые вопросы

Чем транспортная задача отличается от задачи, решаемой симплекс-методом?

Транспортная — частный случай линейного программирования с матрицей ограничений из нулей и единиц: каждая переменная сидит ровно в двух балансах, базис всегда m + n − 1. На этой структуре общий симплекс ускоряют: шаг становится циклом перераспределения, а теневые цены — потенциалами. Решать её общим симплексом можно, но это как вскапывать грядку экскаватором: получится, только медленнее.

Как построить опорное решение транспортной задачи?

Два классических способа: северо-западный угол — заполняем таблицу слева направо по остаткам, не глядя на тарифы; метод минимального элемента — каждый раз везём по самому дешёвому доступному тарифу. Оба дают ровно m + n − 1 заполненную клетку. В примере из статьи минимальный элемент дал 140 против 200 у северо-западного угла — при одинаковых запасах и потребностях.

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

Методом потенциалов: для базисных клеток подберите $u_{i}$ и $v_{j}$ так, чтобы $u_{i} + v_{j} = c_{ij}$ , зафиксировав один потенциал нулём. Затем для каждой свободной клетки проверьте $u_{i} + v_{j} \leq c_{ij}$ . Всё прошло — план оптимален; нашлось превышение — пускайте цикл перераспределения через эту клетку: сдвиг ограничен самой скудной из убывающих клеток.

Когда транспортную задачу нельзя решать методом потенциалов?

Когда ограничения выходят за рамки балансов: минимальные или фиксированные объёмы по отдельным маршрутам, транзит через промежуточные узлы, несколько продуктов на одной сети, связка с производством. Матрица ограничений перестаёт быть из нулей и единиц — берите общий симплекс. Проверка простая: если модель не описывается строками и столбцами таблицы, потенциалы не подойдут.

Следующий шаг: возьмите ту же задачу и добавьте запрет «второй поставщик не возит первому потребителю» — и почувствуете, где кончается уютная таблица и начинается общий симплекс. Тренировка — в тренажёре по симплекс-методу и тренажёре по транспортной задаче; начала теории — в уроке введение в теорию игр, двойственные оценки под микроскопом — в уроке двойственность в ЛП, а точка, где ни один план не лучше, — в терминах седловая точка.