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

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

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

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

[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.