Линейное программирование (стр. 3 из 8)
2. Смежные экстремальные точки отличаются только одной переменной в каждой группе (нулевых и ненулевых переменных).
Если линейная модель стандартной формы содержит
уравнений и 
неизвестных, то все допустимые экстремальные точки определяются как все однозначные неотрицательные решения системы уравнений, в которых m-n переменных равны нулю. Однозначные решения такой системы – базисные решения. Если они удовлетворяют требованию неотрицательности правых частей, то это – допустимое базисное решение. Переменные, равные нулю – небазисные, остальные – базисные. Каждую следующую экстремальную точку можно определить определить путём замены одной из текущих небазисных переменных текущей базисной переменной. В нашем примере при переходе из т. A в т. B необходимо увеличивать небазисную переменную от исходного нулевого значения до значения, соответствующего т. B. В т. B s2 обращается в нуль (становится небазисной). Т.о., происходит взаимообмен xE и s2 между небазисными и базисными переменными.Включаемая переменная – небазисная в данный момент переменная, которая будет включена в множество базисных переменных на следующей итерации. Исключаемая переменная – базисная в данный момент переменная, которая на следующей итерации подлежит исключению из множества базисных переменных.
4.2.2 Вычислительные процедуры симплекс-метода
Симплекс-алгоритм:
Шаг 0: Используя линейную модель стандартной формы, определяют НДБР путём приравнивания к нулю n-m (небазисных) переменных.
Шаг 1: Из числа текущих небазисных переменных выбирается включаемая в новый базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если её нет -- текущее базисное решение оптимально, иначе переход к Шагу 2.
Шаг 2: Из числа переменных текущего базиса выбирается исключаемая переменная, которая должна стать небазисной при введении в состав базиса новой переменной.
Шаг 3: Находится новое базисное решение, соответствующее новым составам базисных и небазисных переменных. Переход к Шагу 1.
Если xE=xI=0, то
(соответствует точке A Ha )
– начальное допустимое решение. 
Если в задаче максимизации все небазисные переменные в
-уравнении имеют неотрицательные коэффициенты, полученное пробное решение является оптимальным. Иначе в качестве новой базисной переменной следует выбрать ту, которая имеет наибольший по абсолютной величине отрицательный коэффициент. Применяя это условие к исходной таблице – переменная, включаемая в базис.Процедура выбора подключаемой переменной предполагает проверку условия допустимости, требующего, чтобы в качестве исключаемой переменной выбиралась та (из текущего базиса), которая первой обращается в нуль при увеличении включаемой переменной вплоть до значения, соответствующего смежной экстремальной точке.
Отношение, идентифицирующее исключаемую переменную, можно определить из симплекс-таблице. Для этого в столбце вводимой переменной вычёркиваются отрицательные и нулевые элементы ограничений. Затем вычисляются отношения постоянных из правых частей ограничений к оставшимся элементам столбца. Исключаемая переменная – та, для которой это отношение минимально.
Столбец, ассоциированный с вводимой переменной – ведущий столбец; строка, соответствующая исключаемой переменной – ведущая строка; на их пересечении – ведущий элемент.