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