Численные методы решения задач линейного программирования. Двойственный симплекс-метод.

Существуют следующие числовые методы решения задач линейного программирования:1) прямой симплекс-метода 2) модифицированный симплекс-метод 3) лексикографический прямой симплекс-метод 4) двухфазовый симплекс-метод 5) двойственный симплекс-метод 6) лексикографический двойственный симплекс-метод

Фактически в симплекс-методе на каждой итерации рассматриваются базисные решения прямой и двойственной задач с равными значениями целевых функций. Алгоритм организован таким образом, что на нулевом шаге 1-ой итерации выбирается прямо допустимый базис и затем с помощью элементарных преобразований, сохраняющих прямо допустимость, происходит перебор базисов. В тот момент, когда обнаруживается двойственно допустимый базис или неразрешимость задачи, процесс останавливается.

Теперь мы можем сформулировать идею нового алгоритма, который назовем двойственным симплекс-методом. На нулевом шаге 1-ой итерации выбирается начальный двойственно допустимый базис и затем с помощью элементарных преобразований, сохраняющих двойственную допустимость, происходит перебор базисов. В тот момент, когда обнаруживается прямо допустимый базис или неразрешимость задачи, процесс останавливается.В приведенном ниже описании алгоритма этого метода предполагается,

что используются та же форма симплекс-таблицы и то же элементарное преобразование, что и в параграфе 1. Под s(i), i =1,...,m, как и прежде, понимается набор номеров базисных столбцов (переменных).

21.Численные методы решения задач линейного программирования. Лексикографический двойственный симплекс-метод Существуют следующие числовые методы решения задач линейного программирования:1) прямой симплекс-метода 2) модифицированный симплекс-метод 3) лексикографический прямой симплекс-метод 4) двухфазовый симплекс-метод 5) двойственный симплекс-метод 6) лексикографический двойственный симплекс-метод

Пусть B – двойственно допустимый базис, S’ ={t (1)….,t (l)}, l = n - m, –

множество номеров небазисных переменных, а S – множество номеров базисных переменных.

Добавим к системе уравнений тождественные соотношения x_i = x_i для небазисных переменных Симплекс-таблица будет состоять из коэффициентов правых частей равенств

Не нашли, что искали? Воспользуйтесь поиском: