Линейное программирование. Азарнова Т.В - 15 стр.

                                                                   Линейное программирование


2. Найти все неотрицательные базисные решения следующей системы урав-
нений:
  ax 1 +x 2 +x 3 +x 4 =1
 x 1 +bx 2 +cx 3 +x 4 =1

      а     в      с           а     в      с              а   в     с            а     в     с

1     3     6      -2    6     2     4      -4        11   3   2     0     16     6     5     -3
2     2     3      0     7     3     5      -2        12   4   5     -3    17     2     6     -1
3     5     4      -1    8     3     4      -1        13   5   2     -1    18     4     2     -4
4     6     2      -3    9     2     5      0         14   4   3     -4    19     5     6     0
5     5     3      -4    10    6     3      -3        15   6   4     -2    20     4     6     -2

                         §4. Алгоритм симплексного метода

         Допустимая точка ЗЛП x =( x1 , x 2 ,..., x n ) называется базисной, если
векторы-столбцы матрицы A: Ai ,..., Ai , k ≤n , соответствующие ее нену-
                                                     1         k
левым координатам, являются линейно независимыми.
         Покажем, как проверяется, является ли заданная точка базисной, на
примере.
         Пример 1. Пусть условия (2) некоторой задачи линейного программи-
рования имеют вид
                                             � 2 x1 −x 2 +2 x3 +x 4 =3
                                              �
                                                � x1 − x 3 +2 x 4 =3
Проверить, является ли точка x=(1,0 ,0,1)Т базисной.
Решение. Так как координаты точки неотрицательны и удовлетворяют задан-
ной системе уравнений, то она по определению является допустимой. Вве-
дем в рассмотрение векторы A1 , A2 , A3 , A4 - столбцы матрицы ограничений:
      � 2�        � −1�            � 2�                � 1�
A1 =�� �� , A2 =��      �� , A3 =��      �� , A4 =�� �� . Тогда система уравнений после под-
       � 1�        � 0�             � −1�               � 2�
становки в нее координат проверяемой точки примет вид:
                                                 A1 x1 + A4 x 4 =b
         В соответствии с определением базисной точки, векторы A1 и A4 сле-
дует проверить на линейную независимость. Из курса линейной алгебры из-
вестно, что векторы являются линейно независимыми, если ранг матрицы,
составленной из этих векторов, равен их количеству.
                                                             2 1
         Так как определитель матрицы                            ≠0 , то ее ранг равен 2, и векторы
                                                             1 2
линейно независимы. Следовательно, точка (1,0,0,1) Т является базисной.


                                                 17