Теория Принятия Решения

                                                                     (4.2)

где x_ir соответствующие коэффициенты.

          Предположим что хотя бы одна  из величин x_ir больше нуля.

          Решение уравнения

                                                          (4.3)

           Тогда очевидно:

                                                      (4.4)

           Умножив уравнение (4.2) на x_r и вычтя полученное уравнение из уравнения (4.1) получим:

                                                              (4.5)

           Сравнив уравнения (4.5) и (4.4) находим связь нового решения со старым базисным решением.

            Чтобы новое решение оставалось  допустимым, нужно выбрать значение  x_r таким, чтобы не одна из величин не стала меньше нуля. Следовательно, максимальное значение переменной x_r определяется соотношением

                                                                                                         (4.7)

            Чтобы сделать новое допустимое решение базисным, нужно одну переменную вывести из базисного решения, а соответствующий вектор из базиса. В этом случае новый базис будет содержать также m векторов.

   Для этого  выбираем значения в соответствии  с (4.7). Тогда новое базисное  решение имеет вид:

x_j – опущен

x_{r max}

         А новый базис – (А₁,A₂,…,A_j-1,A_j+1,..,A_m,A_r)/

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

         Таким образом, алгоритм симплекс-метода  состоит из следующих этапов:

1. находят начальный базис и связанное с ним допустимое базисное решение;
2. вычисляют симплекс разность для каждой переменной, не входящей в базисное решение;
3. вводят в базис наиболее выгодную переменную с максимальной положительной симплекс-разностью; ее значение определяют из соотношения

          для всех x_ir>0;

4. выводят из базисного решения переменную x_j, соответствующую

а из базиса –  вектор A_j;

5.    переходят  к этапу 2 новой интерации.

         Этапы 2-4 повторяют до тех пор,  пока симплекс разности для  всех переменных, не входящих  в базис, не станут отрицательными.

         Это и есть признак оптимальности текущего базисного решения. 
 
 
 
 
 
 
 
 

3.    Блок схема алгоритма решения задачи. 
 
 
 
 
 
 
 
 
 

│