Двойственный симплекс-метод

из "Математические исследования операций в экономике "

Непосредственное приложение теории двойственности к вычислительным алгоритмам линейного программирования позволило разработать еще один метод решения ЗЛП, получивший название двойственного симплекс-метода, или метода последовательного уточнения оценок. Впервые он был предложен Лемке в 1954 г. [c.68]
По аналогии с интерпретацией решения прямой задачи процесс решения двойственной задачи может быть представлен как поиск такой гиперплоскости, которая лежит выше конуса К и пересекает прямую, проведенную через конец вектора Ъ параллельно оси аппликат, в самой нижней точке. [c.69]
План двойственной задачи и, соответствующий сопряженному базису p = ayi,a/2.aym , называют опорным планом. Его спорность заключается в том, что в системе ограничений иа1 j (je ri), задающих область определения двойственной задачи D , т неравенств с номерами je Af(P) обращаются в равенства. [c.70]
Последний факт является не чем иным, как геометрической иллюстрацией утверждения теоремы 1.5. [c.70]
Она становится ведущей и определяет номер столбца Nr(fi(q ), который должен быть выведен из базиса. Переходим к пункту 2° алгоритма. [c.74]
Таким образом, при решении задачи вида (1.66)-(1.68) двойственный симплекс-метод имеет несомненные преимущества по сравнению с прямым. [c.76]
В первом случае, т. е. при изменении вектора 6, достоинства двойственного симплекс-метода очевидны, так как ранее найденный оптимальный базис можно использовать в качестве исходного сопряженного базиса при продолжении решения. Второй случай более подробно будет рассмотрен в гл. 4 при рассмотрении методов решения целочисленных задач. [c.76]
В заключение отметим, что в настоящем параграфе был рассмотрен вариант двойственного алгоритма, соответствующий стандартному симплекс-методу. Нетрудно догадаться, что существует и вариант, построенный на базе модифицированного симплекса (схемы, связанной с преобразованием обратных матриц), но, поскольку этот вопрос представляет интерес в основном с точки зрения техники организации вычислений, мы на нем останавливаться не будем. При желании с глубоким и детальным описанием данной версии алгоритма можно ознакомиться в [1]. Отметим лишь, что она обладает теми же принципиальными преимуществами, что и модифицированный симплекс-метод. [c.77]
Как видно из таблицы Г(1), в столбце 6(Р(1)) содержатся отрицательные элементы ( j(p(1)) = -l/3 0), то есть базис р(1 = а5, а1, а3 не является оптимальным, но в то же время легко убедиться, что он обладает свойствами сопряженного базиса. Отрицательный элемент в 6(Р(1)) является единственным, поэтому номер столбца, выводимого из базиса, определяется однозначно — г = 1 и Л/1(р(1)) = 5. Далее рассматриваем строку оДр(1)) = (0,-1/6, 0,-1/6, 1). В ней имеются отрицательные элементы. Вычисляем А,2 = 42 (-(- 1 )) = 252, Х4=38 (-(-kj)) = 228. X2 X4, следовательно, номер столбца, вводимого в базис — / = 4. Осуществляем преобразование и получаем симплекс-таблицу Г(2). [c.78]

Вернуться к основной статье