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

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


10. Перейти к новой базисной точке. Осуществить преобразования Жордана -
    Гаусса с направляющим элементом alk. Выбросить из рассмотрения искус-
    ственный вектор, если он на данной итерации стал небазисным. Перейти к
    п.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, то в задаче име-
  ется бесчисленное множество решений. Исключение составляет случай,
  когда была сделана замена переменных xs=xs'-xs''. В этом случае, если од-
  на из переменных xs' или xs'' является базисной, то оценка второй обяза-
  тельно равна нулю. Этот факт означает бесчисленное множество пар, с
  помощью которых может быть получено значение переменной xs. Если
  среди небазисных векторов, кроме тех, о которых сказано выше, нет та-
  ких, которые имеют нулевые оценки, то в задаче существует единственное
  решение. Если имеет место случай, когда для всех небазисных векторов
  ∆ j ≥0,то задача имеет единственное решение. Перейти к п.15.
13. Останов. Задача не имеет решения из-за неограниченности целевой функ-
    ции на допустимом множестве. Перейти к п.15.
14. Останов. Задача не имеет решения из-за пустоты исходного допустимого
    множества.
15. Выписать ответ.

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

                                    27