Базисное решение

БАЗИСНОЕ РЕШЕНИЕ (опорный план) [basic solution] — термин линейного программирования, одно из допустимых решений, находящихся в вершинах области допустимых решений, либо (если линия уровня параллельна одному из отрезков границы области) Б. р. — весь этот отрезок (см. рис. Л. 2 к ст. “Линейное программирование”). Оно является решением системы линейных ограничений, которое нельзя представить в виде линейной комбинации никаких других решений. При решении задачи линейного программирования можно поступить следующим образом: найти любое из таких “вершинных” решений — не обязательно оптимальное — и принять его за исходный пункт расчетов. Такое решение и будет базисным. Если оно окажется оптимальным, расчет на этом закончен, если нет — последовательно проверяют, не будут ли оптимальными соседние вершинные точки: ту из них, в которой план эффективнее, принимают снова за исходную точку; и так, последовательно проверяя на оптимальность аналогичные вершины, приходят к искомому оптимуму. На этом принципе строятся т. н. симплексный метод решения задач линейного программирования, а также ряд других способов, объединенных общим названием “методы последовательного улучшения допустимого решения (МПУ)”: метод обратной матрицы, или модифицированный симплекс-метод, метод потенциалов для транспортной задачи и др. Они отличаются друг от друга вычислительными особенностями перехода от одного базисного решения к другому, улучшенному.