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

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


10.Перейти к новой базисной точке. Осуществить преобразования Жордана -
   Гаусса с направляющим элементом a lk. Выбросить из рассмотрения искус-
   ственный вектор, если он на данной итерации стал небазисным. Перейти к
   п.6.
11.Проанализировать значение целевой функции в данной базисной точке
   z ( x B ) =α 0 +Mβ0 . Если β0 =0 , то проверить наличие искусственных
   векторов в базисе. Если искусственных векторов в базисе нет, то вычерк-
   нуть вторую оценочную строку и перейти к выполнению п.7. Если искус-
   ственные переменные имеются среди базисных (они при этом равны ну-
   лю), то проверить неравенство α j ≥0 для тех номеров j , для которых
  β j =0 .Если неравенства выполняются, то получено решение задачи. Пе-
  рейти к п.15. Если среди α j , таких что β j =0 существуют такие, что
  α j <0 , то перейти к п.8, где проверке будут подвергаться только те век-
   торы A j , для которых α j <0 , β j =0 . Если в выражении α 0 +Mβ0 имеет
   место неравенство β0 <0 , то перейти к п.14.
12.Проверка единственности решения.
   Если среди небазисных векторов есть такие, что ∆ j = 0, то в задаче име-
  ется бесчисленное множество решений. Исключение составляет случай,
  когда была сделана замена переменных x s=xs'-xs''. В этом случае, если од-
  на из переменных xs' или xs'' является базисной, то оценка второй обяза-
  тельно равна нулю. Этот факт означает бесчисленное множество пар, с
  помощью которых может быть получено значение переменной xs. Если
  среди небазисных векторов, кроме тех, о которых сказано выше, нет та-
  ких, которые имеют нулевые оценки, то в задаче существует единственное
  решение. Если имеет место случай, когда для всех небазисных векторов
  ∆ j ≥0,то задача имеет единственное решение. Перейти к п.15.
13.Останов. Задача не имеет решения из-за неограниченности целевой функ-
   ции на допустимом множестве. Перейти к п.15.
14. Останов. Задача не имеет решения из-за пустоты исходного допустимого
   множества.
15. Выписать ответ.

     Пример 1. Решить ЗЛП .
                         3 x1 +7 x3 −x4 → max
                         x1 +x 2 +2 x 3 +x 4 =4
                            x1 −2 x2 +3x3 =5
                            3 x1 +7 x3 +2 x 4 =13
                               x j ≥0, j =1,4
     Решение.

                                    26