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

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

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

(1)

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

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

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

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

которая в матричной форме записывается в виде

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

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

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

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

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

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

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

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

где векторы и и будем предполагать, что все угловые точки являются невырожденными.

, где вектор определяется формулой

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

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

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

Переход из старой угловой точки в новую угловую точку состоит, в сущности, лишь в изменении базисной матрицы вводится вектор

Шаг 0. Задать целевой вектор и множество базисных индексов и вектор

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

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

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

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

Шаг 5. Если

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

Шаг 7. В множестве индекс заменить на индекс — вектор — на вектор — компоненту на