Методы решения транспортной задачи сводятся к простым операциям с транспортной таблицей, которая имеет вид:
… | n | |||
… | ||||
… | … | … | … | … |
m | … | |||
… | = |
Базисными клетками транспортной таблицы являются клетки с отличными от нуля положительными перевозками, остальные клетки – свободные. Базисные клетки образуют опорный план транспортной задачи, еcли выполняются два условия:
сумма перевозок в каждой строке равна запасу в данной строке;
сумма перевозок в каждом столбце равна соответствующему спросу .
Опорный план транспортной задачи содержит не более отличных от нуля перевозок .
Опорный план называется вырожденным, если число ненулевых перевозок меньше , опорный план – невырожденный, если число ненулевых перевозок равно
Рассмотрим способы построения опорного плана в невырожденном и вырожденном случаях [1,3].