Описание алгоритма однократного замещения

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

При таком замещении свободная переменная объявляется базисной и подлежит определению, а некоторая базисная (безразлично какая) становится свободной. В математике доказано, что в каждом опорном решении задачи линейного программирования, размещённом в распределительной таблице, можно построить цикл, (и притом только один), однократного замещения одной свободной переменной на одну базисную переменную. При этом продуцируется новый опорный план с новым значением целевой функции. Матрица «единичных стоимостей», обеспечивает общий расчёт затрат по любому полученному решению. То есть она обеспечивает оценку решения записанного в таблице.

При целенаправленном преобразовании начальной таблицы-матрицы можно достигать как минимизации затрат. Рассмотрим методику названного алгоритма.

Циклом называют набор клеток, в котором две и только две клетки расположены в одной строке или в одном столбце, причём, последняя клетка столбца образует первую клетку строки, и так далее, вплоть до замыкания цепочки в цикле (см. табл. 9.1.1).

Таблица 9.1.1.