# ЛР-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` работает с вектором переменных. Поэтому матрицу перевозок нужно развернуть в один длинный вектор. Если $$ 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}, $$ то для 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. Итоговая стоимость и её содержательная интерпретация.