Симплексный Метод

Симплекс — метод, метод последовательного улучшения плана,- метод решения общей задачи линейного программирования: где С. м.- наиболее распространенный метод линейного программирования (л. п.). Он состоит в движении по соседним вершинам многогранного множества задачи л. п., определяемого ее ограничениями, и реализуется в виде конечной последовательности итераций. Базисом вершины х=( х 1, . . ., х п).многогранного множества задачи наз. такая система тлинейно независимых векторов , что xj=0, если . Исходная информация для каждой итерации С. м. складывается из базиса вершины х, параметров xij, определяемых из соотношений (в частности, г,-0=ж 5;- базисные компоненты вершины х), и параметров Если (1), то х- искомое решение задачи л. п. В противном случае выбирается отрицательный параметр Dk. Отсутствие среди х ik, i=1, . . ., m, положительных величин (2) указывает на неразрешимость задачи л. п., обусловленную неограниченностью целевой функции задачи на ее многогранном множестве. В случае положительности нек-рых х ik(3) вершина хзаменяется вершиной x'=x+qxk, где остальные компоненты xk — нули, Вершина х' имеет базис А x', отличающийся от А х тем, что заменен на А k. Параметры и , связанные с А x', определяются по простым рекуррентным формулам, исходя из х ij и Dj. Случай (1) означает, что вдоль каждого ребра многогранного множества задачи, выходящего из вершины х, целевая функция задачи не возрастает. Случаи (2) и (3) соответствуют наличию ребра, вдоль к-рого целевая функция возрастает, причем в случае (2) это ребро — луч, а в случае (3) — отрезок, другой конец к-рого — вершина х'. Итерации проводятся до получения оптимальной вершины либо до выяснения неразрешимости задачи л. п. Программная реализация С.