Решение задачи линейного программирования.

Рассмотрим задачу линейного программирования

[pic](1)

Теорема. Если множество [pic] планов задачи (1) не пусто и целевая функция [pic] сверху ограничена на этом множестве, то задача (1) имеет решение.

Теорема. Если множество [pic] допустимых планов имеет крайние точки и задача (1) имеет решение, то среди крайних точек найдется оптимальная.

Метод исключения Жордана-Гаусса для системы линейных уравнений.

Большинство из существующих численных методов решения задач линейного программирования использует идею приведения системы линейных уравнений

[pic] которая в матричной форме записывается в виде [pic], к более удобному виду с помощью так называемого метода Жордада-Гаусса.

В первом уравнении системы отыскивается коэффициент [pic], отличный от нуля. С помощью этого коэффициента обращаются в нуль коэффициенты при переменной [pic] в остальных уравнениях системы. Для этого первое уравнение умножается на число [pic] и прибавляется к уравнению с номером
[pic], [pic]. Затем первое уравнение делится на число [pic]. Это преобразование называется элементарным преобразованием. Полученная эквивалентная система обладает тем свойством, что переменная [pic] присутствует только в первом уравнении, и притом с коэффициентом 1.
Переменная [pic] называется базисной переменной.

Аналогичная операция совершается поочередно с каждым уравнением системы; при этом всякий раз преобразуются все уравнения и выполняется список базисных переменных.

Результатом применения метода Жордада-Гаусса является следующее: либо устанавливается, что система несовместна, либо выявляются и отбрасываются все «лишние» уравнения; при этом итоговая система уравнений имеет вид

[pic], [pic], где [pic] — список номеров базисных переменных, [pic] — множество номеров небазисных переменных. Здесь [pic] — ранг матрицы [pic] коэффициентов исходной системы уравнений.

Полученную системы уравнений называют приведенной системой, соответствующей множеству [pic] номеров базисных переменных.

Симплекс-метод.

Симплекс –метод, метод последовательного улучшения плана, является в настоящее время основным методом решения задач ЛП.

Рассмотрим каноническую задачу ЛП

[pic](2) где векторы [pic], матрица [pic] и [pic]. Множество планов в задаче (2) будем обозначать через [pic] и будем предполагать, что все угловые точки
[pic] являются невырожденными.
[pic], где вектор [pic] определяется формулой [pic].

Теорема. Если в угловой точке [pic] выполняется условие [pic], то
[pic] — решение задачи (2).

Теорема. Для того, чтобы угловая точка [pic] являлась решением задачи
(2), необходимо и достаточно, чтобы в ней выполнялось условие [pic].

Алгоритм симплекс-метода.

Переход из старой угловой точки [pic] в новую угловую точку [pic] состоит, в сущности, лишь в изменении базисной матрицы [pic], в которую вместо вектора [pic] вводится вектор [pic]. Новая базисная матрица может быть теперь использована для вычисления базисных компонентов вектора [pic].
Таким образом, алгоритм симплекс-метода может быть представлен в следующей форме.

Шаг 0. Задать целевой вектор [pic], матрицу условий [pic], вектор ограничений [pic] и множество базисных индексов [pic]. Сформировать базисную матрицу [pic] и вектор [pic].

Шаг 1. Вычислить матрицу [pic] и вектор [pic].

Шаг 2. Вычислить вектор потенциалов [pic] и оценки [pic].

Шаг 3. Если [pic] для всех [pic], то остановиться: вектор [pic] — базисный вектор оптимального плана; иначе перейти на шаг 4.

Шаг 4. Выбрать произвольный индекс [pic] и вычислить вектор [pic].

Шаг 5. Если [pic], то остановиться: [pic]; иначе перейти на шаг 6.

Шаг 6. Сформировать множество индексов [pic] и вычислить [pic].

Шаг 7. В множестве [pic] индекс [pic] заменить на индекс [pic], в матрице [pic] — вектор [pic] — на вектор [pic], в векторе [pic] — компоненту [pic] на [pic]. Перейти на шаг 1.