Двойственный симплекс-метод
I Теоретическое введение
В отличие от прямого симплекс-метода, который мы рассматривали ранее, двойственный симплекс-метод начинает свое решение не с какого-то допустимого, но неоптимального решения, а, наоборот, с недопустимого, но лучшего чем оптимальное решения.
Для того, чтобы существовало начальное оптимальное ("супероптимальное") и недопустимое решение, необходимо выполнение двух условий.
1. Целевая функция должна удовлетворять условию оптимальности обычного симплекс-метода.
2. Все ограничения должны быть неравенствами типа "≤".
Второе условие можно удовлетворить простым умножением на –1 неравенств типа "≥". Если есть ограничения в виде равенств, то эти равенства заменяются на два неравенства. Например, равенство 
эквивалентно двум неравенствам 
После преобразования всех ограничений в виде неравенств типа "<" начальное недопустимое решение возможно тогда и только тогда, когда, по крайней мере, в одном неравенстве правая часть будет строго отрицательной. В противном случае двойственный симплекс-метод не применяется, поскольку возможное начальное решение уже оптимально и допустимо.
В качестве исключаемой переменной 
выбирается базисная переменная, имеющая наибольшее по абсолютной величине отрицательное значение. Если таких переменных несколько, то выбор произволен. Если все базисные переменные неотрицательные, процесс вычислений заканчивается.
|
|
|
Вводимая в базис переменная определяется как переменная, на которой достигается следующий минимум:
где 
— коэффициент в z -строке симплекс-таблицы, соответствующий переменной 
; 
— отрицательный коэффициент из симплекс-таблицы, расположенный на пересечении ведущей строки (соответствующей исключаемой переменной и столбца, соответствующего небазисной переменной . При наличии нескольких альтернативных переменных выбор делается произвольно.
Дата добавления: 2015-12-17; просмотров: 17; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!