Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 16 стр.

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


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)Т является базисной.


                                                 18