ЛР-02: Транспортная задача

ЛР-02: Транспортная задача#

1) Что это за задача#

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

  • закрыть весь спрос;

  • не превысить запасы у поставщиков;

  • получить минимальную суммарную стоимость перевозки.

В отличие от общей производственной задачи, здесь переменные означают не объёмы выпуска, а объёмы перевозок между конкретными парами узлов.

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

Если есть \(m\) поставщиков и \(n\) потребителей, то переменных становится \(m \cdot n\):

\[ x_{ij} = \text{сколько везём от поставщика } i \text{ к потребителю } j. \]

2) Из чего состоит модель#

Поставщики#

Пусть у нас есть запасы:

\[ a_1, a_2, \dots, a_m \]

Здесь \(a_i\) — доступный объём у поставщика \(i\).

Потребители#

Пусть есть спрос:

\[ b_1, b_2, \dots, b_n \]

Здесь \(b_j\) — потребность потребителя \(j\).

Стоимости перевозки#

Для каждой пары \((i, j)\) задаётся стоимость:

\[ c_{ij} \]

Это стоимость доставки одной единицы груза от поставщика \(i\) к потребителю \(j\).

Переменные решения#

\[ x_{ij} \ge 0 \]

Это объём потока по маршруту \((i, j)\).

3) Целевая функция#

Обычно транспортная задача формулируется как задача минимизации полной стоимости:

\[ \min Z = \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}x_{ij} \]

Здесь каждая перевозка умножается на свою стоимость, а затем все затраты суммируются.

4) Ограничения#

Ограничения по запасам#

Если поставщик должен распределить весь свой запас, то:

\[ \sum_{j=1}^{n} x_{ij} = a_i, \quad i = 1,\dots,m \]

Смысл: всё, что есть у поставщика \(i\), должно быть отправлено.

Ограничения по спросу#

Если весь спрос должен быть закрыт, то:

\[ \sum_{i=1}^{m} x_{ij} = b_j, \quad j = 1,\dots,n \]

Смысл: каждый потребитель получает ровно столько, сколько ему нужно.

Неотрицательность#

\[ x_{ij} \ge 0 \]

Отрицательная перевозка невозможна.

5) Закрытая и открытая транспортная задача#

Закрытая задача#

Если суммарный запас равен суммарному спросу:

\[ \sum_{i=1}^{m} a_i = \sum_{j=1}^{n} b_j \]

то задача называется закрытой или сбалансированной.

В этом случае можно использовать равенства и интерпретировать задачу буквально: весь груз распределён, весь спрос удовлетворён.

Открытая задача#

Если суммы не совпадают:

\[ \sum_{i=1}^{m} a_i \ne \sum_{j=1}^{n} b_j \]

то задача открытая.

Чтобы привести её к стандартной транспортной форме, добавляют фиктивный узел.

6) Фиктивный поставщик и фиктивный потребитель#

Если запасов больше, чем спроса#

Когда:

\[ \sum a_i > \sum b_j \]

добавляют фиктивного потребителя с потребностью

\[ b_{n+1} = \sum a_i - \sum b_j \]

Смысл: часть груза формально остаётся невостребованной или уходит в резерв.

Если спрос больше, чем запасов#

Когда:

\[ \sum a_i < \sum b_j \]

добавляют фиктивного поставщика с запасом

\[ a_{m+1} = \sum b_j - \sum a_i \]

Смысл: недостающий объём покрывается условным источником, который показывает дефицит системы.

Какие брать стоимости для фиктивного узла#

Методически важно заранее договориться о смысле:

  1. Если фиктивный узел означает нейтральный остаток или резерв, часто ставят нулевую стоимость.

  2. Если фиктивный узел означает дефицит, штраф или аварийное покрытие, стоимость можно сделать положительной.

В этой лабораторной главное — корректно сбалансировать задачу и объяснить смысл выбранной стоимости.

7) Матричная постановка для linprog#

Библиотека scipy.optimize.linprog работает с вектором переменных. Поэтому матрицу перевозок нужно развернуть в один длинный вектор.

Если

\[\begin{split} X = \begin{pmatrix} x_{11} & x_{12} & \dots & x_{1n}\\ x_{21} & x_{22} & \dots & x_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ x_{m1} & x_{m2} & \dots & x_{mn} \end{pmatrix}, \end{split}\]

то для Python удобно использовать развертку по строкам:

\[ x = (x_{11}, x_{12}, \dots, x_{1n}, x_{21}, \dots, x_{mn})^T \]

Тогда:

  • вектор цели c — это те же стоимости costs.flatten();

  • ограничения по поставщикам дают строки матрицы A_eq, где для каждого поставщика суммируются все его исходящие перевозки;

  • ограничения по потребителям дают строки A_eq, где для каждого потребителя суммируются входящие перевозки;

  • вектор правых частей b_eq составляется из запасов и спроса.

Если по-человечески, Python не хранит красивую таблицу перевозок у себя в голове. Для решателя мы временно превращаем таблицу в одну длинную ленту чисел, решаем задачу, а потом снова собираем ответ обратно в привычную таблицу.

8) Почему здесь удобно использовать linprog#

В этой лабораторной нам важна не табличная техника сама по себе, а корректная постановка и проверяемость результата.

linprog полезен потому, что:

  1. позволяет решить задачу как обычное ЛП;

  2. помогает проверить, что модель действительно собрана правильно;

  3. даёт воспроизводимый результат, который удобно обсуждать в отчёте;

  4. легко расширяется на прикладные сценарии, где есть штрафы, дефицитные маршруты и фиктивные узлы.

9) Как интерпретировать решение#

После решения важно не ограничиваться ответом “минимальная стоимость равна …”.

Нужно ответить на вопросы:

  1. Какие маршруты реально используются?

  2. Какие маршруты остаются нулевыми?

  3. Выполнен ли баланс по строкам и столбцам?

  4. Есть ли перегруженные или дорогие направления?

  5. Если использовался фиктивный узел, что он означает на языке предметной области?

Именно эта интерпретация превращает математический ответ в управленческий вывод.

10) Что изучаем в этой ЛР#

В этой работе целенаправленно изучаем:

  1. построение транспортной модели из прикладной ситуации;

  2. проверку баланса спроса и предложения;

  3. переход к закрытой постановке через фиктивный узел;

  4. подготовку c, A_eq, b_eq, bounds для linprog;

  5. анализ полученного плана перевозок и суммарной стоимости.

Не изучаем:

  1. транспортный симплекс;

  2. MODI;

  3. Vogel;

  4. другие табличные эвристики как основной инструмент этой ЛР.

11) Типичные ошибки#

  1. Перепутали строки и столбцы матрицы затрат.

  2. Неверно проверили баланс запасов и спроса.

  3. Забыли добавить фиктивный узел в открытой задаче.

  4. Добавили фиктивный узел, но не объяснили смысл его стоимости.

  5. Неправильно развернули матрицу перевозок в вектор.

  6. В A_eq потеряли часть переменных или перепутали индексы.

  7. Посмотрели только на целевую функцию и не проверили суммы по строкам и столбцам.

  8. Увидели дорогой маршрут, но не объяснили, почему solver всё равно его использует или избегает.

12) Что должно быть в отчёте#

  1. Таблица запасов поставщиков.

  2. Таблица спроса потребителей.

  3. Матрица затрат.

  4. Проверка баланса задачи.

  5. Если задача открытая — объяснение, какой фиктивный узел добавлен и зачем.

  6. Линейная постановка задачи через \(x_{ij}\).

  7. Векторно-матричная запись для linprog.

  8. Листинг Python-кода.

  9. Итоговая матрица плана перевозок.

  10. Проверка допустимости по строкам и столбцам.

  11. Итоговая стоимость и её содержательная интерпретация.