Решение задачи линейного программирования.
    Рассмотрим задачу линейного программирования
    (1)
    Теорема. Если множество планов задачи (1) не пусто и целевая функция сверху ограничена на этом множестве, то задача (1) имеет решение.
    Теорема. Если множество допустимых планов имеет крайние точки и задача (1) имеет решение, то среди крайних точек найдется оптимальная.
    
    Метод исключения Жордана-Гаусса для системы линейных уравнений.
    Большинство из существующих численных методов решения задач линейного программирования использует идею приведения системы линейных уравнений
     которая в матричной форме записывается в виде , к более удобному виду с помощью так называемого метода Жордада-Гаусса.
    В первом уравнении системы отыскивается коэффициент , отличный от нуля. С помощью этого коэффициента обращаются в нуль коэффициенты при переменной в остальных уравнениях системы. Для этого первое уравнение умножается на число и прибавляется к уравнению с номером , . Затем первое уравнение делится на число . Это преобразование называется элементарным преобразованием. Полученная эквивалентная система обладает тем свойством, что переменная присутствует только в первом уравнении, и притом с коэффициентом 1. Переменная называется базисной переменной.
    Аналогичная операция совершается поочередно с каждым уравнением системы; при этом всякий раз преобразуются все уравнения и выполняется список базисных переменных.
    Результатом применения метода Жордада-Гаусса является следующее: либо устанавливается, что система несовместна, либо выявляются и отбрасываются все "лишние" уравнения; при этом итоговая система уравнений имеет вид
    , , где - список номеров базисных переменных, - множество номеров небазисных переменных. Здесь - ранг матрицы коэффициентов исходной системы уравнений.
    Полученную системы уравнений называют приведенной системой, соответствующей множеству номеров базисных переменных.
    
    Симплекс-метод.
    Симплекс -метод, метод последовательного улучшения плана, является в настоящее время основным методом решения задач ЛП.
    Рассмотрим каноническую задачу ЛП
    (2) где векторы , матрица и . Множество планов в задаче (2) будем обозначать через и будем предполагать, что все угловые точки являются невырожденными. , где вектор определяется формулой .
    Теорема. Если в угловой точке выполняется условие , то - решение задачи (2).
    Теорема. Для того, чтобы угловая точка являлась решением задачи (2), необходимо и достаточно, чтобы в ней выполнялось условие .
    Алгоритм симплекс-метода.
    Переход из старой угловой точки в новую угловую точку состоит, в сущности, лишь в изменении базисной матрицы , в которую вместо вектора вводится вектор . Новая базисная матрица может быть теперь использована для вычисления базисных компонентов вектора . Таким образом, алгоритм симплекс-метода может быть представлен в следующей форме.
    Шаг 0. Задать целевой вектор , матрицу условий , вектор ограничений и множество базисных индексов . Сформировать базисную матрицу и вектор .
    Шаг 1. ............