Метод минимального элемента: транспортная задача

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

Постановка транспортной задачи

Дано $m$ поставщиков с запасами $a_i$ ($i = 1, \ldots, m$) и $n$ потребителей со спросом $b_j$ ($j = 1, \ldots, n$). Стоимость перевозки единицы груза из $i$ в $j$ равна $c_{ij}$. Нужно найти план перевозок $x_{ij} \geq 0$ такой, что:

$\sum_{j=1}^{n} x_{ij} = a_i, \quad \sum_{i=1}^{m} x_{ij} = b_j, \quad Z = \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij} x_{ij} \to \min$

Задача сбалансирована, если $\sum a_i = \sum b_j$. Если нет - добавляют фиктивного поставщика или потребителя с нулевыми тарифами.

Рассчитать для своей задачи

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

Метод строит начальный план «жадным» способом: на каждом шаге заполняет клетку с наименьшим тарифом.

Шаг 1. В таблице тарифов $[c_{ij}]$ найти клетку с минимальным значением $c_{ij}^*$.

Шаг 2. Назначить перевозку $x_{ij}^* = \min(a_i, b_j)$.

Шаг 3. Уменьшить остаток соответствующего поставщика и потребителя: $a_i \leftarrow a_i - x_{ij}^*, \quad b_j \leftarrow b_j - x_{ij}^*$

Шаг 4. Если $a_i = 0$ - вычеркнуть строку $i$; если $b_j = 0$ - вычеркнуть столбец $j$; если оба равны нулю - вычеркнуть одно из двух (оставив вырожденную базисную клетку с нулём).

Шаг 5. Повторять шаги 1-4 до полного распределения грузов.

Итог: базисных клеток ровно $m + n - 1$ (условие невырожденности). Суммарная стоимость начального плана, как правило, далека от оптимума - она служит отправной точкой для метода потенциалов.

Рассчитать для своей задачи

Числовой пример

Рассмотрим задачу $3 \times 3$: поставщики $A_1, A_2, A_3$ (запасы 30, 40, 20) и потребители $B_1, B_2, B_3$ (спрос 20, 50, 20).

Матрица тарифов: $C = \begin{pmatrix} 2 & 3 & 5 \\ 7 & 4 & 1 \\ 6 & 8 & 3 \end{pmatrix}$

Итерация 1: минимум $c_{23} = 1$. $x_{23} = \min(40, 20) = 20$. Вычеркиваем столбец 3. Остаток $a_2 = 20$.

Итерация 2: из оставшихся минимум $c_{11} = 2$. $x_{11} = \min(30, 20) = 20$. Вычеркиваем столбец 1. Остаток $a_1 = 10$.

Итерация 3: минимум $c_{12} = 3$. $x_{12} = \min(10, 50) = 10$. Вычеркиваем строку 1. Остаток $b_2 = 40$.

Итерация 4: минимум $c_{22} = 4$. $x_{22} = \min(20, 40) = 20$. Вычеркиваем строку 2. Остаток $b_2 = 20$.

Итерация 5: $x_{32} = 20$. Вычеркиваем строку 3 и столбец 2.

Начальный план: $Z = 2\cdot20 + 3\cdot10 + 1\cdot20 + 4\cdot20 + 8\cdot20 = 40+30+20+80+160 = 330$.

Число базисных переменных: $5 = 3 + 3 - 1$ - план невырожден.

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

Метод северо-западного угла заполняет клетки по диагонали таблицы, не смотря на тарифы. Для нашего примера он дал бы:

$x_{11}=20,\; x_{12}=10,\; x_{22}=40,\; x_{23}=0^*,\; x_{32}=20 \quad Z_{\text{СЗУ}} = 2\cdot20+3\cdot10+4\cdot40+\ldots$

Метод минимального элемента обычно даёт более дешёвый начальный план - разрыв в 15-30 % типичен, что сокращает число итераций в методе потенциалов.

Условие невырожденности и вырожденный план

Если на шаге одновременно обнуляются и $a_i$, и $b_j$, одну из строк (или столбцов) не вычёркивают, а оставляют с нулевой перевозкой $x_{ij}^* = 0$. Эта базисная клетка с нулём - вырожденная - всё равно учитывается в счётчике базисных переменных: их ровно $m+n-1$.

Вырожденность не запрещена, но при циклировании (бесконечном переходе между планами одной стоимости) в методе потенциалов к нулевым базисным клеткам прибавляют $\varepsilon > 0$.

Проверка оптимальности: метод потенциалов

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

1. Системе $u_i + v_j = c_{ij}$ для всех базисных клеток $(i,j)$ решают относительно потенциалов $u_i, v_j$ (полагая $u_1 = 0$).
2. Для небазисных клеток вычисляют оценку $\Delta_{ij} = c_{ij} - u_i - v_j$.
3. Если все $\Delta_{ij} \geq 0$ - план оптимален.
4. Иначе находят клетку с $\Delta_{ij} < 0$, строят цикл и перераспределяют перевозки.

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

Частые ошибки

• Не проверяют баланс. Перед применением метода нужно убедиться, что $\sum a_i = \sum b_j$. Если не так - добавляют фиктивный поставщик или потребитель с нулевыми тарифами и нулевой перевозкой.
• Вычёркивают оба при одновременном обнулении. Правильно оставить одно из них «открытым» с остатком 0 - иначе число базисных переменных будет меньше $m+n-1$ и план непригоден для метода потенциалов.
• Выбирают разные минимумы при одинаковых тарифах случайно. Лучше придерживаться правила: при равных тарифах - выбирать наибольший возможный объём перевозки.
• Путают начальный план с оптимальным. Метод минимального элемента даёт только начальный план. Он редко оптимален сам по себе - требуется проверка по методу потенциалов или распределительному методу.
• Неверно считают количество базисных переменных. Их должно быть ровно $m+n-1$; если меньше - план вырожден неправильно и метод потенциалов зависнет.

FAQ

Почему метод минимального элемента лучше метода северо-западного угла?

Метод северо-западного угла заполняет клетки без учёта тарифов - он гарантирует только допустимость плана. Метод минимального элемента на каждом шаге минимизирует «местные» затраты, что в среднем даёт план на 15-30 % дешевле и требует меньше итераций для выхода на оптимум.

Гарантирует ли метод минимального элемента оптимальный план?

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

Что делать, если задача несбалансирована?

Добавить фиктивного поставщика с запасом $\sum b_j - \sum a_i > 0$ (или потребителя, если запасы превышают спрос) и нулевыми тарифами. После решения перевозки в фиктивные клетки означают неудовлетворённый спрос (или нераспределённые запасы) и в реальности не выполняются.

Коротко

Метод минимального элемента строит начальный опорный план транспортной задачи, жадно заполняя клетки с наименьшим тарифом. Алгоритм прост: найти минимальный $c_{ij}$, назначить максимально возможную перевозку, вычеркнуть насыщенную строку или столбец - и повторять до заполнения. Результат - $m+n-1$ базисных клеток, план, близкий к оптимуму, и быстрый старт для метода потенциалов.