Математическая энциклопедия - симплексный метод

симплекс метод, метод последовательного улучшения плана,метод решения общей задачи линейного программирования:

где

С. м.наиболее распространенный метод линейного программирования (л. п.). Он состоит в движении по соседним вершинам многогранного множества задачи л. п., определяемого ее ограничениями, и реализуется в виде конечной последовательности итераций. Базисом вершины х=( х 1, . . ., х п).многогранного множества задачи наз. такая система тлинейно независимых векторов , что xj=0, если . Исходная информация для каждой итерации С. м. складывается из базиса вершины х, параметров xij, определяемых из соотношений

(в частности, г,-0=ж 5;базисные компоненты вершины х), и параметров

Если (1), то хискомое решение задачи л. п. В противном случае выбирается отрицательный параметр Dk. Отсутствие среди х ik, i=1, . . ., m, положительных величин (2) указывает на неразрешимость задачи л. п., обусловленную неограниченностью целевой функции задачи на ее многогранном множестве. В случае положительности нек-рых х ik(3) вершина хзаменяется вершиной x'=x+qx^k, где

остальные компоненты x^k - нули,

Вершина х' имеет базис А x', отличающийся от А х тем, что заменен на А k. Параметры и , связанные с А x', определяются по простым рекуррентным формулам, исходя из х ij и Dj.

Случай (1) означает, что вдоль каждого ребра многогранного множества задачи, выходящего из вершины х, целевая функция задачи не возрастает. Случаи (2) и (3) соответствуют наличию ребра, вдоль к-рого целевая функция возрастает, причем в случае (2) это ребро луч, а в случае (3) отрезок, другой конец к-рого вершина х'. Итерации проводятся до получения оптимальной вершины либо до выяснения неразрешимости задачи л. п.

Программная реализация С.