Вычислительная схема симплекс-метода для решения задач ЛП. Особенности симплекс-метода

1.1. Вычислительная схема симплекс-метода для решения задач  ЛП

1.1.1. Особенности симплекс-метода

Симплекс-метод известен с 1947 года, когда  появилась первая публикация Джона Данцига,  посвященная этому  методу. В советской литературе 60-80-х гг. прошлого столетия этот метод был известен также как метод последовательного улучшения плана.

За прошедшие с тех пор годы было предложено не только много разновидностей симплекс-метода, учитывающих особенности различных подклассов задачи ЛП (блочные задачи, задачи со слабо заполненной матрицей условий A ={a_{i, j}}), но и   несколько принципиально иных методов решения задачи ЛП. Некоторые из предложенных методов в теоретическом плане, например, с точки зрения характеристики сложности алгоритма, превосходят симплекс-метод (известно, что симплекс-метод обладает экспоненциальной сложностью, т.е. имеет экспоненциальную  оценку трудоемкости на всем классе задач ЛП,  тогда как такие алгоритмы, как метод эллипсоидов Хачияна (советского математика) и метод Крамаркара (американского исследователя)  характеризуются полиномиальной сложностью).  И, тем не менее, по утверждению многих специалистов в теории линейного программирования симплекс-метод и после десятилетий всесторонней апробации с точки зрения алгоритмической реализации и универсальности применимости на классе задач ЛП остается наиболее предпочтительным, а потому наиболее распространенным методом решения задач ЛП.

Основная идея симплекс-метода достаточно просто иллюстрируется геометрически. Как уже говорилось выше, допустимое множество задачи ЛП (1.2- 1.3) представляет собой выпуклый многогранник (в случае, если множество не ограничено – выпуклое многогранное множество) с конечным числом вершин этого многогранника, т.е. его крайних точек.  В том случае, если задача ЛП имеет единственное решение, то решение находится в одной из этих вершин.  Симплекс-метод состоит в таком направленном переборе вершин, при котором  значение целевой функции улучшается  (не ухудшается) при переходе от вершины к вершине. Каждая вершина многогранника является пересечением плоскостей (в n-мерном случае – гиперплоскостей), каждая из которых задается уравнением, определенным  соответствующим ограничением исходной задачи ЛП. Другими словами, каждая вершина определяется системой уравнений, выбираемой специальным образом из системы неравенств (1.1). Таким образом, симплекс-метод, по сути дела, представляет собой вычислительную процедуру последовательного решения систем линейных уравнений.  Поэтому этот метод содержит в себе правила формирования систем уравнений (в терминах разобранной ниже схемы – правило выбора разрешающего элемента) и схему решения систем линейных уравнений (в терминах приведенной ниже схемы – жордановы исключения).

Так как число вершин в многограннике  - на  множестве допустимых решений – конечно, и можно показать, что при решении задачи ЛП симплекс-методом значение целевой функции от вершины к вершине улучшается (не ухудшается), то алгоритм метода является конечным.  Это означает, что  теоретически (без учета вычислительных погрешностей машинной реализации алгоритма)  метод сходится за конечное число итераций.  Причем считается, что число итераций зависит в основном от числа ограничений m, а не числа  переменных  n, в грубом приближении число итераций лежит в пределах от 1,5m до 2m.

1.1.2. Вычислительная схема симплекс-метода для решения задач  ЛП

В задачи данного пособия не входит рассмотрение теоретического обоснования симплекс-метода, но предполагается, что  изучение вычислительной  схемы должно способствовать более глубокому пониманию вычислений, реализуемых с помощью программного обеспечения (например, в программной системе Excel) и, следовательно,  способствовать формированию навыков решения задач ЛП с использованием вычислительной техники. Ниже рассмотрена вычислительная схема, приведенная в ряде известных учебников по математическому программированию и исследованию операций [3,5].

При этом сначала рассматривается аппарат жордановых исключений, с помощью которых осуществляется переход от одного опорного решения к другому, т.е. от одной крайней точки выпуклого многогранника – допустимого множества ЗЛП,  к другой. После описания жордановых исключений приведены правила выбора разрешающего элемента для определения опорного решения – крайней точки, к которым необходимо перейти из тех или иных соображений.

1.1.3. Обыкновенные жордановы исключения. Основные понятия

Пусть рассматривается система

    y_i  = a_i1* x₁ +  a_{i2 *} x₂ +  … + a_{i n *} x_n ,         i = 1, … , m              (2.5)

из m линейных форм с n независимыми переменными x₁, x₂, …,x_n. Эта система может быть представлена в виде следующей таблицы:

Такое табличное представление системы (2.5) позволяет в дальнейшем производить различные действия над системой схематизировано, т.е. осуществлять пересчет коэффициентов таблицы  а_ij по определенному алгоритму, а именно с помощью аппарата жордановых[1] исключений.

Пусть, например, возникла необходимость выразить независимую переменную  x_s  из уравнения

y_r  = a _r1 * x₁ +  a _r2 * x₂ +  … a _rs * x_s +  … + a _{r n *} x_n ,                   (2.7)

где y_r является переменной, которая  зависитот переменных x₁, x₂, …, x_n, и подставить полученное выражение во все остальные уравнения