Симплексный метод решения задач линейного программи­рования

Симплексный метод решения задач линейного программи­рования (симплекс-метод) [sim­p­lex method] — вычислительная  процедура,  основанная на принципе последовательного улучшения решений — перехода от одной базисной точки (см. Базисное решение) к другой, для которой значение целевой функции больше (эти операции фиксируются в симплексной таблице). Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов (за исключением так называемой вырожденной задачи, при которой возможно явление “зацикливания”, т.е. многократного возврата к одному и тому же положению). Название метод получил от термина “n-мерный симплекс”. Геометрическая интерпретация метода состоит в последовательном движении по вершинам симплекса.

C.м., разработанный Дж.Дан­­цигом, послужил исходным пунктом для разработки целого семейства алгоритмов решения как линейных, так и нелинейных выпуклых задач оптимизации.

Реализация решения симплекс-методом наглядно показана на блок-схеме, рис. C.4.

Рис. С.4 Симплексный метод(блок-схема)