EssayAI
Блог
Блог
Математика и алгоритмы

Транспортная задача по критерию времени

8 ноября 2026Время чтения: 9 минут
#транспортная задача#критерий времени#оптимальный план#максимальный поток#исследование операций
Транспортная задача по критерию времени

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

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

Как устроен критерий времени

Пусть у поставщика AiA_i имеется запас aia_i, потребителю BjB_j нужно bjb_j единиц, а tijt_{ij} - время перевозки по маршруту i→ji \to j. Переменная xijx_{ij} обозначает количество груза на нём. В закрытой модели общий запас равен общей потребности; весь запас отгружается, а каждый заказ удовлетворяется точно:

∑jxij=ai,∑ixij=bj,xij⩾0.\sum_j x_{ij}=a_i,\qquad \sum_i x_{ij}=b_j,\qquad x_{ij}\geqslant 0.

Для плана XX время завершения равно максимальному времени среди занятых маршрутов:

T(X)=max⁡i,j: xij>0tij,T∗=min⁡XT(X).T(X)=\max_{i,j:\,x_{ij}>0} t_{ij},\qquad T^*=\min_X T(X).

Условие xij>0x_{ij}>0 существенно: медленный маршрут с нулевой поставкой не задерживает выполнение плана. Время не умножают на объём груза и не суммируют по всем отправкам. Такая постановка предполагает параллельную работу маршрутов без очередей, ограничений числа машин и дополнительного времени погрузки. Если эти условия не выполняются, потребуется более подробная модель расписания.

При увеличении порога с 2 до 5 часов разрешается больше маршрутов: впервые все 50 единиц удаётся доставить при 4 часах.

Почему достаточно проверить пороги

Для выбранного срока TT оставим только маршруты, у которых tij⩽Tt_{ij}\leqslant T. Остальные временно запретим. Теперь задача другая: существует ли вообще план, который развезёт все запасы по разрешённым клеткам? Если да, срок допустим; если нет, он слишком мал.

При увеличении порога разрешённые маршруты не исчезают. Поэтому после первого допустимого порога все большие тоже допустимы. Состояние меняется только тогда, когда порог достигает очередного значения в таблице времени: проверять каждую промежуточную минуту не нужно. Отсортируйте разные значения tijt_{ij} и проверяйте их по возрастанию. Первый допустимый порог и есть оптимальное время. Для большой таблицы монотонность позволяет применять двоичный поиск по отсортированным значениям.

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

Пример: два склада и два пункта

Пусть запасы равны 20 и 30 единицам, потребности - 30 и 20 единицам. Матрица содержит время в часах, а не стоимость:

ПоставщикВ пункт B1B_1В пункт B2B_2Запас
A1A_12520
A2A_24330
Потребность302050 всего

Баланс выполнен: 20+30=30+20=5020+30=30+20=50. Различные значения времени: 2, 3, 4 и 5 часов. При пороге 2 доступен только маршрут A1→B1A_1\to B_1, поэтому доставить можно не более 20 единиц. При пороге 3 добавляется маршрут A2→B2A_2\to B_2: он способен закрыть потребность второго пункта в 20 единицах. Вместе это только 40 единиц, а 10 единиц потребности B1B_1 остаются без доставки.

При пороге 4 открывается маршрут A2→B1A_2\to B_1. По нему можно отправить недостающие 10 единиц, а остальные партии оставить прежними:

ПоставщикВ B1B_1В B2B_2Отправлено
A1A_120020
A2A_2102030
Получено302050
План из 20, 10 и 20 единиц по маршрутам длительностью 2, 4 и 3 часа
План из 20, 10 и 20 единиц по маршрутам длительностью 2, 4 и 3 часа

Все строки и столбцы дают нужные суммы, а занятые маршруты имеют времена 2, 4 и 3 часа. Значит, план завершается за 4 часа. Порог 3 часа недопустим, а между 3 и 4 новых маршрутов нет. Следовательно, T∗=4T^*=4 часа. Маршрут в 5 часов не используется и не влияет на ответ. Другие допустимые планы с тем же максимумом также могут быть оптимальными: минимальный срок не обязательно определяет единственный план.

Как проверить допустимость через поток

Для произвольной таблицы удобно построить сеть. Из истока проведите дугу к каждому поставщику с пропускной способностью, равной его запасу. Из каждого потребителя проведите дугу в сток с пропускной способностью, равной его потребности. Между поставщиком и потребителем оставьте дугу только тогда, когда соответствующий маршрут укладывается в TT. Её способность можно взять равной всему объёму груза, если отдельных ограничений на маршрут нет.

Найдите максимальный поток. В сбалансированной задаче порог допустим тогда и только тогда, когда величина потока равна общей потребности. Поток по каждой промежуточной дуге непосредственно задаёт xijx_{ij}. Если поток меньше, его величина показывает, сколько груза максимально доставляется при этом сроке, а разница с потребностью - сколько не удаётся доставить одновременно. Минимальный разрез сети может служить свидетельством ограничения.

В примере максимальные потоки для порогов 2, 3, 4 и 5 равны соответственно 20, 40, 50 и 50. Это и показано в калькуляторе. Он исследует фиксированные данные примера, а не произвольную матрицу; для своих чисел нужно заново построить сеть и найти поток на каждом проверяемом пороге.

Как записать доказательство для другого примера

В учебном решении удобно разделять ответ на две части: сначала показать нижнюю границу, затем построить план, который её достигает. Сама таблица перевозок подтверждает только вторую часть. В нашем случае при сроке меньше 4 часов пункт B1B_1 может получать груз только от A1A_1. Его запас составляет 20 единиц, тогда как пункту требуется 30. Следовательно, никакое перераспределение по другим разрешённым маршрутам не исправит дефицит в 10 единиц. Это объяснение даже короче вычисления всего максимального потока.

Затем достаточно предъявить таблицу с отправками 20, 10 и 20 и проверить суммы каждой строки и каждого столбца. Так получаются обе половины доказательства: менее 4 часов невозможно, а 4 часа достижимо. В более крупной сети узкое место может включать сразу несколько поставщиков и потребителей. Тогда вместо рассуждения об одном пункте используют максимальный поток и минимальный разрез, сохраняя ту же логику доказательства.

Если одно время в исходной таблице изменится, прежний оптимум не следует переносить автоматически. Нужно снова отсортировать времена, проверить допустимость порогов и восстановить план. Даже небольшое изменение длительности важной дуги может изменить первый допустимый порог; изменение неиспользуемой дуги, напротив, может не повлиять на ответ.

Чем срок отличается от общей стоимости

В обычной транспортной задаче с тарифами cijc_{ij} минимизируют сумму ∑i,jcijxij\sum_{i,j} c_{ij}x_{ij}. Там увеличение объёма на маршруте увеличивает его вклад в стоимость. В задаче на срок решает самый медленный используемый маршрут, даже если по нему перевезена одна единица. Поэтому план с меньшей стоимостью не обязан иметь меньший срок, и наоборот.

Методы построения начального плана полезны для понимания баланса, но сами по себе не доказывают оптимальность по времени. Например, метод северо-западного угла заполняет таблицу по положению клеток, а метод минимального элемента выбирает клетку по значению показателя. При ограниченных маршрутах план обязательно нужно проверить на допустимость. О способах получения начального плана подробнее - в статье про опорный план транспортной задачи.

Если нужно сначала минимизировать срок, а затем стоимость, сначала найдите T∗T^*, запретите маршруты дольше него и решите задачу минимальной стоимости на оставшейся сети. Это последовательность двух критериев. Метод потенциалов относится к проверке стоимости и применяется ко второму этапу при соответствующей постановке, а не заменяет доказательство минимального срока.

Если баланс не сходится

При избытке запаса можно требовать отгрузить не больше aia_i, но полностью покрыть потребности; тогда цель проверки потока - сумма потребностей. При нехватке запаса полное удовлетворение всех заказов невозможно без дополнительного источника. Фиктивный поставщик или потребитель помогает записать баланс, но его маршруты и времена должны отражать смысл исходной задачи: произвольно выбранное время способно изменить оптимальный срок. Всегда отдельно указывайте, означает ли фиктивный поток остаток, недопоставку или реальную перевозку.

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

  • Суммировать времена всех клеток. Параллельные перевозки завершаются в момент окончания самой долгой занятой партии.
  • Учитывать незанятый медленный маршрут. В максимум входят только клетки с положительным xijx_{ij}.
  • Проверять только наличие маршрута к каждому пункту. Надо одновременно учесть запасы, потребности и связность сети.
  • Назвать найденный план оптимальным без нижней оценки. Допустимость при 4 часах показывает достижимость; недопустимость предыдущего порога доказывает, что быстрее нельзя.
  • Считать модель расписанием машин. При ограниченном автопарке или последовательных рейсах формула максимума времён маршрутов может не описывать реальное завершение работ.

FAQ

Можно ли делить запас одного склада между пунктами? Да. В стандартной модели груз делим, а суммы по строкам и столбцам должны удовлетворять ограничениям. Если партии неделимы или машины имеют отдельные ограничения, условия задачи меняются.

Что делать, если несколько маршрутов имеют одинаковое время? Открывайте их одновременно при достижении этого порога. Проверять одинаковые значения по отдельности не требуется.

Почему достаточно проверить предыдущий порог? Между соседними различными временами набор разрешённых маршрутов одинаков. Если при предыдущем значении допустимого плана нет, то и при любом меньшем пороге его нет: маршрутов там не больше.

Коротко

Критерий времени минимизирует максимальную длительность занятого маршрута при одновременных перевозках. Проверка порога сводится к допустимости плана на разрешённых маршрутах, например к максимальному потоку. В разобранной таблице 3 часа дают лишь 40 из 50 единиц, а при 4 часах найден полный план, поэтому оптимальный срок равен 4 часам.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Максимальный поток: алгоритм Форда-Фалкерсона

Максимальный поток: алгоритм Форда-Фалкерсона

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

8 ноября 20269 минут
Теорема Форда-Фалкерсона о максимальном потоке

Теорема Форда-Фалкерсона о максимальном потоке

Теорема Форда-Фалкерсона связывает максимальный поток и минимальный разрез. Разбираем доказательство через остаточную сеть, пример и проверку решения.

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

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

Как построить опорный план транспортной задачи методом северо-западного угла, минимального элемента и Фогеля: пошаговые алгоритмы, проверка на вырожденность и сравнение стоимости планов на примерах.

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

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

Метод минимального элемента в транспортной задаче: пошаговый алгоритм начального плана, таблица тарифов, критерий оптимальности. Примеры и частые ошибки.

17 июня 20266 минут
Метод потенциалов: решение транспортной задачи

Метод потенциалов: решение транспортной задачи

Метод потенциалов для транспортной задачи: как построить опорный план, найти потенциалы строк и столбцов, посчитать оценки свободных клеток, проверить план на оптимальность и улучшить его по циклу.

11 июня 20268 минут
Метод северо-западного угла: транспортная задача

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

Метод северо-западного угла для транспортной задачи: как пошагово построить опорный план, проверить его на вырожденность по правилу m+n-1 и посчитать стоимость перевозок с разбором типовой задачи.

11 июня 20268 минут