Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). Под названием транспортная задача ,определяется широкий круг задач с единой математической моделью, эти задачи относятся к задачам линейного программирования и могут быть решены оптимальным методом. Однако, спец.метод решения транспортной задачи позволяет существенно упростить её решение, поскольку транспортная задача разрабатывалась для минимизации стоимости перевозок.

Классическую транспортную задачу можно решить симплекс - методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности).

Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из A_i в B_j груза \(xij\geq 0\), а в маленькие клетки — соответствующие тарифы C_ij.

Нахождение опорного плана

Требуется определить опорный план и путём последовательных операций найти оптимальное решение. Опорный план можно найти следующими методами: "северо - западного угла", "наименьшего элемента".

Одним из способов решения задачи является метод минимального (наименьшего) элемента. Его суть заключается в сведении к минимуму побочных перераспределений товаров между потребителями. Метод получения начального решения — записывать отгрузки в первую очередь в те ячейки, где тариф минимален. Этот метод позволяет получить более приближенное к оптимальному решение, которое, однако, может потребовать дальнейшей оптимизации. Метод минимальных тарифов с его модификациями (минимальный тариф по строке или минимальный тариф по столбцу) был описан Данцигом в работе 1951 г.

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

Допустимое (но не всегда оптимальное с точки зрения стоимости доставки) начальное решение транспортной задачи можно построить, последовательно перебирая строки таблицы (то есть поставщиков) сверху вниз. В пределах каждой строки, нужно перебрать слева направо не охваченных или не полностью охваченных поставками потребителей, записывая в соответствующие ячейки объем поставляемого груза от поставщика в данной строке, и так до исчерпания возможностей поставщика. Таким образом, весь груз от поставщиков будет распределен по потребителям. Этот метод был предложен Данцигом в 1951 г. и назван Чарнесом и Купером «правилом северо-западного угла».

Алгоритм:

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

- Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.

- Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

В таблице желтым цветом отмечены ячейки с ненулевыми объемами перевозки груза (базисные ячейки).

 Метод Фогеля

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

---