Симплекс метод

    i-я  строка может  быть отброшена.

    Перебрав  одну за другой все строки матрицы A(l), которые не являлись направляющими, либо устанавливают неразрешимость системы уравнений, либо отбрасывают все нулевые строки.

    Таким образом, в системе окажется равно l уравнений. Примем для определенности, что это первые по порядку l уравнений. Тогда полученную систему уравнений  можно записать в виде

      i=1, 2, .,l.              (2.2.11)

    Пусть i-й направляющей строке соответствует i-й направляющий столбец вследствие соответствующего выбора направляющего  элемента. Тогда

    aij(l)= i=1, 2, ., l.                      (2.2.12)

    Следовательно, (2.2.11) можно записать в виде:

    xi = ai0(l) -  i=1, 2, ., l,                   (2...2.13)

    причем  переменные xi ( i =1, ., l) являются базисными, а переменные xj  

    ( j=l+1, ., n) - небазисными.

    При xj = 0 ( j=l+1, ., n) получим одно из базисных решений системы уравнений

    xi = ai0(l),  i =1, 2, ., l, xj=0; j=l+1,.,n.

    Задавая для xj произвольные значения , получим полное множество решений.

    Если xi   - i-я компонента этого решения, то

                               (2.2.14)

    Обозначим

    x0= (a10, a20,., al0,0,.,0 )

    xj= (-a1j, -a2j,., -aij, 0 ,., 0, 1, 0 ,.,0 ), 1 £ j £ n.                                                                      

      j         n

    Тогда общее (полное) решение системы линейных уравнений определяется соотношением, аналогичным (2.2.14):

    x общ = x0 +                         (2.2.15)

    где x0- базисное решение начальной системы  уравнений;

      - полное решение соответствующей  однородной системы уравнений (то есть при A0=0).

    Обозначим расширенную матрицу системы  уравнений после k-й итерации через

    Ap(k)=[ai0(k), ai1(k),.,ain(k)],i=1,2,.,m.

    Пусть aij(k)- направляющий элемент преобразования на (k + 1)-й итерации. Тогда в результате (k + 1)-й итерации метода полного исключения Гаусса получим матрицу Ap(k+1), элементы которой определяются следующими соотношениями:

    1) для всех элементов направляющей  строки

      l=1, 2,.,n;                         (2...2.16)

    2) для элементов направляющего  столбца

    arj(k+1)=0; r=1,.,n, причем r¹и; aij(k+1)=1;                  (2.2.17)

    3) для всех остальных элементов  матрицы

                      (2.2.18)

    Пример 2.3. Применим метод полного исключения Гаусса для исследования системы  уравнений

    x1 + 2x2 + x3 + x4 = 3;

    2x1 + x2 + x3 + 3x4 = 3;

    4x1 + 5x2 + 3x3 + 5x4 = 9.

    Расширенная матрица имеет вид:

    

    Первая  итерация. В качестве первого направляющего  элемента возьмем a11= 1 , умножим первую строку матрицы А на 2 и на 4 , затем  вычитая результаты из второй и  третьей строк,  получим

    

    Вторая  итерация. Поскольку главная часть  матрицы Ap(1) содержит ненулевые элементы, продолжим процесс исключения. Выберем  элемент a22(1)=-3.

    После аналогичных преобразований получим

    

    Как видим, главная часть матрицы Ap(2), состоящая из элементов a33(2) и a34(2) , содержит только нули. Следовательно, процесс  исключения заканчивается.

    Исследуем матрицу A(2). Поскольку третья строка содержит лишь нулевые элементы, то она  может быть  отброшена. Тогда эквивалентная матрица системы уравнений будет иметь вид

    

    Соответственно  формулам (2.2.13), (2.2.14) имеем базисное решение

    x1*=1; x2*=1; x3=0; x4=0.

    Общее решение данной системы имеет  такой вид:

    X1=1- X2=1- X3= X4=

    где a3, a4- произвольные скаляры.

 

3. Табличный симплекс метод.

   Основная  идея симплекса-метода состоит в  переходе от одного допустимого базисного  решения к другому таким образом, что значения целевой функции при этом непрерывно возрастают (для задач максимизации).

   Предположим, что ограничения задачи сведены  к такому виду, что в матрице  А иеется единичная подматриця и  все свободные члены положительные. Иными словами, пусть матрица  ограничений имеет вид

   A1x1+.+Anxn+e1xn+e1xn+1+.+emxn+m=A0=[ai0],

   где

     . - единичный базис, ai0³0

   для всех i = 1, 2,., n.

   Применим  одну итерацию метода полного исключения к расширенной матрице ограничений Ap=[A1, ., An, e1, ., em, A0].

   Пусть aij- направляющий элемент преобразования на данной итерации. Тогда в результате преобразований в соответствии с (3.3.18) получим новые значения свободных членов:

   

    .                               (3.3.19)

   Исследуем выражения (3.3.19). и выясним условия, при которых al0(k+1)>0 для всех l, то есть новое базисное решение будет также допустимым.

   По  предположению al0(k)>0; l=1,.,m,

   aij(k)>0,

   тогда

   

   Если alj(k)<0, тогда al0(k+1) > 0, поскольку ai0(k) > 0 , aij(k) > 0.

   Если alj(k)>0, то

   

   будет больше нуля при всех l=1, 3. ..., m тогда и только тогда, когда

                              (3.3.20)

   Преобразование  Гаусса называют симплексным преобразованием, когда направляющий элемент определяют по следующим правилам:

   a) направляющий столбец j выбирают  из условия, что в нем имеется  хотя бы один положительный  элемент;

   б) направляющую строку i выбирают так, чтобы  отношение   было минимально при условии, что aij>0.

   При таком преобразовании в базис  вводится вектор Aj и выводится вектор Аi. Теперь надо определить, как выбрать  вектор, вводимый в базис, чтобы при этом значение целевой функции увеличилось.

   Для этого используют так называемые оценки векторов Dj:

                        (3.3.21)

   где Iб - множество индексов базисных векторов; xij- определяют из условия

                                       (3.3.22)

   Величины {Dj } равны симплекс-разницам для  переменных {xj} с противоположным знаком. Следовательно, для того чтобы значение целевой функции увеличилось, необходимо выбрать направляющий столбец Аj с наибольшей по модулю отрицательной оценкой, то есть

     .

    Для решения задачи симплекс-методом  на каждой итерации заполняют симплекс-таблицу  3.3.

   Таблица 3.3.

c                  c1    c2    c3    .    cj    .    cn           Bx    a00    A1    A2    A3    .    Aj    .    An    c1    x1    a1o    a11    a12    a13    .    a1j    .    a1n    c2    x2    a2o    a21    a22    a23    .    a2j    .    a2n    .    .    .    .    .    .    .    .    .    .     ci    xi    aio    ai1    ai2    ai3    .    aij    .    ain    .    .    .    .    .    .    .    .    .    .    cm    xm    amo    am1    am2    am3    .    amj    .    amn           D           D1    D2    D3    .    Dj    .    Dn

   Последняя сторока таблицы - индексная -служит для определения направляющего  столбца. Ее элементы Dj определяют по формуле (3.3.21). Очевидно, для всех базисных векторов {Ai} i=1,.,m оценки Dи=a0и=0.

   Значение  целевой функции a00  определяется из соотношения

     .

   В столбце Bx записываем базисные переменные {xi} i= 1, ..., т. Их значения определяются столбиком свободных членов ai0, то есть

   xi=ai0, i=1, 2,.,m.

   Направляющие  строка Ai и столбец Aj указываются  стрелками. Если в качестве направляющего  элемента выбран aij, то переход от данной симплекс таблицы к следующей  определяется соотношениями (3.3.16) - (3.3.18).

   Итак, алгоритм решения задачи ЛП табличным  симплексом-методом состоит из этапов.

   1. Рассчитывают и заполняют начальную  симплекс-таблицу с допустимым  единичным базисом, включая индексную  строку.

   3. В качестве направляющего столбца выбирают Aj, для которого

     .

   3. Направляющая строка Aі выбирают  из условия

   

   4. Делают один шаг (итерацию) метода  полного исключения Гаусса с  направляющим элементом aij, для  чего используют соотношения  (3.3.16) - (3.3.18). В частности, элементы индексной строки новой таблицы вычисляют в соответствии с формулой

       l=1,2, ..., n.

   Правильность  вычислений контролируют по формулам непосредственного счета:

                                 (3.3.23)

                                 (3.3.24)

   В столбце Bx новой таблицы заменяют xi на xj, а в столбце С ci на cj.

   5. Если все a0l(k+1)³0, l=1,.,n, то новое  базисное решение xi= ai0(k+1), iÎIб(k+1) - оптимально. В противном случае  переходят к этапу 2 и выполняют очередную итерацию.

   6. Второй, третий и четвертый этапы  повторяют до тех пор, пока  одна из итераций не закончится  одним из двух исходов:

   а) все a0l ³0. Это признак (критерий) оптимальности  базисного решения последней  симплекс-таблицы;

   б) найдется такой a0j=Dj<0, что все элементы этого столбца arj£0, 
  r = 1, ., m. Это признак неограниченности целевой функции z= cjxj на множестве допустимых решений задачи.

   Назовем некоторые особенности применения табличного симплекс-метода.