Симплекс-метод решения задачи лп

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

Сущность метода: построение базисных решений, на которых монотонно убывает линейный функционал, до ситуации, когда выполняются необходимые условия локальной оптимальности.

Симплекс-метод позволяет эффективно найти оптимальное решение, избегая простой перебор всех возможных узловых точек. Основной принцип метода: вычисления начинаются с какого-то «стартового» базисного решения, а затем ведется поиск решений, «улучшающих» значение целевой функции. Это возможно только в том случае, если возрастание какой-то переменной приведет к увеличению значения функционала.

____________________Вопрос 43____________________

Метод искусственных переменных

Идея использования искусственных переменных предполагает включение неотрицательных переменных в левую часть каждого из уравнений, в которых не содержится очевидных начальных базисных переменных (когда неравенство имеет знак ≥ или задано в виде равенства). Эти дополнительно вводимые переменные выполняют ту же роль, что и остаточные переменные. Но так как искусственные переменные не имеют отношения к поставленной задаче (отсюда их название - искусственные), то их введение допустимо только в том случае, если симплекс метод будет обеспечивать получение оптимального решения, в котором все искусственные переменные будут равны 0, то есть эти переменные следует использовать только для стартовой точки, причем итерационный метод оптимизации должен "вынуждать" эти переменные принимать нулевые значения в конечном оптимальном решении, обеспечивая допустимость оптимума

Если в оптимальном решение Т-задачи все искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи.

Если имеется оптимальное решение Т-задачи, в котором хотя бы одна из искусственных переменных отлична от 0, то система ограничений исходной задачи несовместна.

Если максимум Т-функции равен бесконечности, то исходная задача неразрешима (либо система несовместна, либо максимум неограничен)

Расчетные задачи на тестирование

Вычисления Nрасч по заданной точности для методов:

Метод перебора.

Алгоритм оптимального пассивного поиска.

Метод дихотомии.

Метод деления отрезка пополам.

Метод золотого сечения.

Метод чисел Фибоначчи.

Решение:

Метод	Nрасч
М/д перебора	N = Nрасч = minNZ{N:Nb-a-1}
Опт. пассивный поиск
М/д дихотомии
М/д деления отрезка пополам
М/д золотого сечения
М/д чисел Фибоначчи

Вычисления расчетной точности Ерасч по заданному N для методов: