Транспортная задача заключается в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А1, А2, … , Аm в n пунктов потребления B1, B2,…, Bn.
Рассмотрим транспортную задачу, где в качестве критерия оптимальности является стоимость перевозок всего груза, которая должна быть минимальной.
Введем обозначения:
аi – запасы груза в i-ом пункте отправления ( 
);
bi – величина заказа на этот груз в j-ом пункте назначения
сij – стоимость перевозки единицы груза из A i-гo пункта отправления в В j-ый пункт потребления (тариф перевозок);
xij – количество груза, доставленного из i пункта в j пункт, хij?0.
Определить план перевозок груза из пунктов отправления в пункты назначения так, чтобы: вывести все грузы от поставщиков; удовлетворить заявки каждого потребителя; обеспечить минимальные транспортные расходы на перевозку груза.
Все исходные данные транспортной задачи можно записать в виде транспортной таблицы 4.
где 
— суммарный запас груза у поставщиков;
— суммарная величина заявок потребителей
Математическая постановка транспортной задачи заключается в определении матрицы 
; которая удовлетворяет следующим условиям:
Таблица 4
| Пункты от- правления | Пункты назначения | Запасы a1 | |||||
| В1 | В2 | … | B1 | … | Bn | ||
| A1 | с11 x11 | с12 x12 | … | с1i x1i | … | с1n x1n | a1 |
| А2 | с21 x21 | с22 x22 | … | с1i x1i | … | с1n x1n | a2 |
| … | … | … | … | … | … | … | … |
| Ai | сi1 xi1 | сi2 xi2 | … | сij xij | … | сin xin | ai |
| … | … | … | … | … | … | … | … |
| Аm | сm1 xm1 | сm2 xm2 | … | сmj xmj | сmn xmn | am | |
| Заявки b1 | b1 | b2 | … | bj | … | bn |   |
И обеспечивает минимальное значение целевой функции
а) всякое неотрицательное решение системы линейных уравнений, определяемое матрицей ; называется допустимым планом транспортной задачи:
б) Ранг матрицы, составленный из коэффициентов при неизвестных системы линейных уравнений транспортной задачи, на единицу меньше числа уравнений, т.е. равен (m+n-1). Следователь-число линейно независимых уравнений равно (m+n-1), они образует базис, а соответствующие им (m+n-1) переменных будут являться базисными.
в) Допустимый план транспортной задачи, имеющий не более (m+n-1) отличных от нуля величин xij, называется опорным.
г) Если в опорном плане число отличных от нуля компонент равно в точности (m+n-1), то план является невырожденным, если меньше, то план называется вырожденным.
д) План . При котором функция 4 принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
е) Для решения транспортной задачи необходимо и достаточно, чтобы суммарные запасы груза в пунктах отправления были равны сумме заявок пунктов назначения
ж) Модель транспортной задачи, удовлетворяющая этому условию, называется закрытой. Если же указанное условие не выполняется, то модель называется открытой.
В случае превышения запаса над заявками: 
вводится фиктивный (n+1) пункт назначения с потребностью 
и соответствующие тарифы считаются равными нулю: 
При 
вводится фиктивный (m+1) пункт отправления с запасом груза , и тарифы принимаются равными нулю: 
.
Рассмотрим один из методов построение первого опорного плана — метод наименьших тарифов.
з) Наилучшим элементом матрицы тарифов называется наименьший тариф, если задача поставлена на минимум, наибольший тариф — если задача поставлена на максимум целевой функции.
Алгоритм построения первого опорного плана методом наименьшей стоимости включает следующие этапы.
1. Среди тарифов находится наименьший.
2. Клетку с выбранным тарифом заполняем максимально возможным объемом груза с учетом ограничений по строке и столбцу, при этом либо весь груз вывозится от соответствующего поставщика, либо полностью удовлетворяется заявка потребителя. Строка или столбец таблицы вычеркивается ив дальнейшем распределении не участвует.
3. Из оставшихся тарифов вновь находим наилучший, и процесс продолжается до тех пор, пока не будет распределен весь груз.
Если модель транспортной задачи открытая и введены фиктивный поставщик или потребитель, то распределение осуществляется сначала для действительных поставщиков и потребителей, и в последнююочередь нераспределенный груз направляется от фиктивного поставщика или к фиктивному потребителю.
Дальнейшее улучшение первого опорного плана и получение оптимального плана производим методом потенциалов.
и) План X=(xij) транспортной задачи будет являться оптимальным, если существует система m+n чисел ?i, ?j называемых потенциалами, удовлетворяющая условиям:
?i +?j ? сij для занятых клеток, где xij0
?i + ?j ?cijдля свободных клеток, где хij=0
при решении задачи на минимум, а при решении задачи на максимум:
?j – ?i =сij для занятых клеток, где xij0
?j – ?i ?сij для свободных клеток, где хij=0
Потенциалы ?i и ?j являются переменными двойственной транспортной задачи и обозначают оценку единицы груза в пунктах отправления и назначения соответственно.
Введем обозначение оценки свободной клетки таблицы:
?ij=cij–( ?i +?j)
Если среди оценок ?ij нет отрицательной (задача поставлена на минимум), то опорный план является оптимальным и все свободные клетки потенциальны.
Алгоритм метода потенциалов включает следующие этапы.
1. Построение первого опорного плана.
2. Проверка вырожденности плана.
Потенциалы ?i и ?j могут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане меньше, чем (m+n+1) . то вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным (m+n+1). Нуль вводят в клетку с наилучшим тарифом одного из одновременно вычеркиваемых рядов таблицы. При этом фиктивно занятая нулем клетка не должна образовывать замкнутого контура с другими клетками таблицы.
3. Определение значения функций цели путем суммирования произведений тарифов (удельных затрат) на объем перевозимого груза по всем занятым клеткам таблицы
4. Проверка условия оптимальности
Определением потенциалы ?i и ?j. Для каждой занятой клетки таблицы записываем уравнение ?j – ?i =сij 
. Получим систему (m+n+1) уравнений с (m+n) переменными.
Так как число переменных больше числа уравнений (m+nm+n+1) . то система не определена и имеет бесчисленное множество решений. Одному из неизвестных ?i ?j. придают произвольное значение, например, для простоты вычислений полагаем ?i=0. Тогда остальные потенциалы определяются из приведенных соотношений.
В транспортную таблицу добавляется дополнительная строка и столбец, куда заносятся потенциалы.
Определяем оценки свободных клеток ?ij.
Если все ?ij.?0 (задача решается на минимум целевой функции) либо все ?ij?0 (задача решается на максимум целевой функции), то оптимальный план найден. Если хотя бы одна оценка свободной клетки ?ij0 (задача поставлена на максимум), план не оптимальный, его можно улучшить, осуществив перераспределение груза.
5. Построение нового опорного плана
Из всех положительных оценок свободных клеток выбираем наибольшую (если задача поставлена на минимум), из отрицательных — наибольшую по абсолютной величине (если задача поставлена на максимум). Клетку, которой соответствует наибольшая оценка, следует заполнить, т.е. направить груз. Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде, других занятых клеток и связанных с заполнением так называемым циклом.
Циклом — или прямоугольным контуром в таблице условий, транспортной задачи называется ломанная линия, вершины которой расположены в занятых клетках таблицы, а звенья — вдоль строк и столбцов, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, другое — в столбце. Если ломанная линия, образующая цикл, пересекается, то точки пересечения не являются вершинами. Для каждой свободной клетки таблицы можно построить единственный цикл.
Вершинам цикла, начиная от вершины, находящейся в свободной клетке, присваиваем поочередно знаки + и -.
Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее и обозначим его ?. Перераспределяем величину ? по циклy, прибавляя ее к соответствующим объемам грузов, стоящим в минусовых клетках. Клетка, которая ранее была свободной, становится занятой, а одна из занятых клеток цикла становится свободной. В результате получаем новый опорный план и возвращаемся к четвертому этапу алгоритма.
ЗАМЕЧАНИЯ
1. Если в минусовых клетках построенного цикла находятся два (или несколько) одинаковых минимальных значения хij, то при перераспределении объемов груза освобождаются две (или несколько) клеток, и план становится вырожденным. Для продолжения решения необходимо в одну (или несколько) одновременно освобождающихся клеток направить нуль, причем предпочтение отдается клетке с наилучшим тарифом. Нулей вводится столько, чтобы во вновь полученном опорном плане число занятых клеток было равно (m+n-1).
2. Если в оптимальном плане транспортной задачи оценка для некоторой свободной клетки ?ij=0, то задача имеет множество оптимальных планов. Для клетки с нулевой оценкой можно построить цикл и перераспределить груз. В результате полученный план будет также оптимальным.
3. Значение функции цели на каждой интерации можно рассчитать следующим образом:
F(Xk)=?(Xk-1)–0• ?ij. задача поставлена на min,
F(Xk)=(Хk-1)+0• ?ij. задача поставлена на max, где при переходе к новому плану;
F(Xk) — значение функции цели на k интерации;
Хk-1- значение функции цели на предыдущей (k-1) — интерации.
