Транспортная задача. Венгерский метод (стр. 2 из 3)
Такая структура системы (2.1) позволяет легко установить ее ранг. Действительно, покажем, что совокупность неизвестных, образующих первую строку и первый столбец матрицы перевозок, можно принять в качестве базиса. При таком выборе базиса, по крайней мере, один из двух их индексов равен единице, а, следовательно, свободные неизвестные определяются условием
, 
.Перепишем систему (2.1) в виде 
где символы
и 
означают суммирование по соответствующему индексу. Так, например,
При этом легко заметить, что под символами такого суммирования объединяются только свободные неизвестные (здесь
, ).В рассматриваемой нами системе только два уравнения, а именно первое горизонтальное и первое вертикальное, содержат более одного неизвестного из числа выбранных нами для построения базиса. Исключив из первого горизонтального уравнения базисные неизвестные
с помощью вертикальных уравнений, мы получаем уравнение
где символ
означает сумму всех свободных неизвестных. Аналогично, исключив из первого вертикального уравнения базисные неизвестные 
с помощью горизонтальных уравнений, мы получаем уравнение
Так как для закрытой модели транспортной задачи
, то полученные нами уравнения (2.2) и (2.2’) одинаковы и, исключив из одного из них неизвестное 
, мы получим уравнение-тождество 0=0, которое из системы вычеркивается.
Итак, преобразование системы (2.1) свелось к замене двух уравнений (первого горизонтального и первого вертикального) уравнением (2.2). Остальные уравнения остаются неизменными. Система приняла вид
В системе (2.3) выделен указанный выше базис: базисные неизвестные из первых т уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного
[она входит в первое уравнение системы (2.3)]. В системе (2.3) имеется 
уравнений, выделенный базис содержит неизвестных, а, следовательно, и ранг системы (2.1) 
.Для решения транспортной задачи необходимо кроме запасов и потребностей знать также и тарифы
, т. е. стоимость перевозки единицы груза с базы 
потребителю 
.Совокупность тарифов
также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу:| Пункты Отправления | Пункты назначения | Запасы | ||||||||
 |  | … |  | |||||||
 |  |  | … |  |  | |||||
| |  |  | ||||||||
 |  |  | … |  |  | |||||
 |  |  | ||||||||
| … | … | … | … | … | … | |||||
 |  |  | … |  |  | |||||
 |  |  | ||||||||
| Потребности |  |  | … |  | или  | |||||
Сумма всех затрат, т. е. стоимость реализации данного плана перевозок, является линейной функцией переменных
: 
Требуется в области допустимых решений системы уравнений (2.1) и (2.1.1) найти решение, минимизирующее линейную функцию (2.4).
Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен
то среди всех 
неизвестных выделяется базисных неизвестных, а остальные 
·