Решение задачи линейного программирования.
Рассмотрим задачу линейного программирования
[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.