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

симплекс - метод, метод последовательного улучшения плана,- метод решения общей задачи линейного программирования: [img: http://localhost:8080/file/041909-21.jpg] где [img: http://localhost:8080/file/041909-22.jpg] С. м.- наиболее распространенный метод линейного программирования (л. п.). Он состоит в движении по соседним вершинам многогранного множества задачи л. п., определяемого ее ограничениями, и реализуется в виде конечной последовательности итераций. Базисом вершины х=(х 1,..., х п).многогранного множества задачи наз. такая система тлинейно независимых векторов [img: http://localhost:8080/file/041909-23.jpg] [img: http://localhost:8080/file/041909-24.jpg], что xj=0, если [img: http://localhost:8080/file/041909-25.jpg]. Исходная информация для каждой итерации С. м. складывается из базиса [img: http://localhost:8080/file/041909-26.jpg] вершины х, параметров xij, определяемых из соотношений [img: http://localhost:8080/file/041909-27.jpg] (в частности, г,-0=ж 5;- базисные компоненты вершины х), и параметров [img: http://localhost:8080/file/041909-28.jpg] Если [img: http://localhost:8080/file/041909-29.jpg] (1), то х- искомое решение задачи л. п. В противном случае выбирается отрицательный параметр Dk. Отсутствие среди х ik, i=1,..., m, положительных величин (2) указывает на неразрешимость задачи л. п., обусловленную неограниченностью целевой функции задачи на ее многогранном множестве. В случае положительности нек-рых х ik(3) вершина хзаменяется вершиной x'=x+qxk, где [img: http://localhost:8080/file/041909-30.jpg] остальные компоненты xk - нули, [img: http://localhost:8080/file/041909-31.jpg] Вершина х' имеет базис А x', отличающийся от А х тем, что [img: http://localhost:8080/file/041909-32.jpg] заменен на А k. Параметры [img: http://localhost:8080/file/041909-33.jpg] и [img: http://localhost:8080/file/041909-34.jpg], связанные с А x', определяются по простым рекуррентным формулам, исходя из х ij и Dj. Случай (1) означает, что вдоль каждого ребра многогранного множества задачи, выходящего из вершины х, целевая функция задачи не возрастает. Случаи (2) и (3) соответствуют наличию ребра, вдоль к-рого целевая функция возрастает, причем в случае (2) это ребро - луч, а в случае (3) - отрезок, другой конец к-рого - вершина х'. Итерации проводятся до получения оптимальной вершины либо до выяснения неразрешимости задачи л. п. Программная реализация С. Важная часть алгоритма С. м. - стратегия выбора вектора А k для включения в базис. С одной стороны, она должна способствовать сокращению информации, необходимой для хранения [img: http://localhost:8080/file/041909-39.jpg]; с другой стороны - препятствовать попаданию в плохо обусловленный базис. Существуют программные реализации С. м., позволяющие решать на ЭВМ задачи л. п. с мало заполненной матрицей условий при тпорядка тысяч и ппорядка десятков тысяч. Разработаны многочисленные варианты С. м., учитывающие особенности различных специальных классов задач л. п. (блочные задачи, задачи транспортного типа и др.). Несмотря на то, что С. м. теоретически не достаточно эффективен (он имеет экспоненциальную оценку трудоемкости на всем классе задач л. п., хотя алгоритмич. сложность этого класса всего лишь полиномиальна), опыт его применения и сравнения с другими методами позволяет сделать вывод, что для него пока (1983) нет серьезного конкурента.