Решение задачи линейного программирования
Рассмотрим задачу линейного программирования
(1)
Теорема.
Если множество
планов задачи
(1) не пусто и
целевая функция
сверху ограничена
на этом множестве,
то задача (1) имеет
решение.
Теорема.
Если множество
допустимых
планов имеет
крайние точки
и задача (1) имеет
решение, то
среди крайних
точек найдется
оптимальная.
Метод исключения Жордана-Гаусса для системы линейных уравнений.
Большинство из существующих численных методов решения задач линейного программирования использует идею приведения системы линейных уравнений

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