Представление пространства решений стандартной задачи ЛП.

Модель:

максимизировать целевую функцию

при ограничениях

На – пространство решений. Каждую точку можно определить с помощью

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

Анализируя , заметим, что

можно упорядочить, исходя из того, какое значение (нулевое или ненулевое) имеет данная переменная в экстремальной точке.

Экстр.	переменные
точка	нулевые	ненулевые
A
B
C
D
E
F

Из таблицы выделим закономерности:

1. Стандартная модель содержит четыре уравнения и шесть неизвестных, поэтому в каждой из экстремальных точек (6–4) переменные должны иметь нулевые значения.

2. Смежные экстремальные точки отличаются только одной переменной в каждой группе (нулевых и ненулевых переменных).

Если линейная модель стандартной формы содержит уравнений и неизвестных, то все допустимые экстремальные точки определяются как все однозначные неотрицательные решения системы уравнений, в которых m-n переменных равны нулю. Однозначные решения такой системы – базисные решения. Если они удовлетворяют требованию неотрицательности правых частей, то это – допустимое базисное решение. Переменные, равные нулю – небазисные, остальные – базисные. Каждую следующую экстремальную точку можно определить определить путём замены одной из текущих небазисных переменных текущей базисной переменной. В нашем примере при переходе из т. A в т. B необходимо увеличивать небазисную переменную от исходного нулевого значения до значения, соответствующего т. B. В т. B s2 обращается в нуль (становится небазисной). Т.о., происходит взаимообмен x­E и s2 между небазисными и базисными переменными.

Включаемая переменная – небазисная в данный момент переменная, которая будет включена в множество базисных переменных на следующей итерации. Исключаемая переменная – базисная в данный момент переменная, которая на следующей итерации подлежит исключению из множества базисных переменных.