Представление пространства решений стандартной задачи линейного программирования

Линейная модель, построенная для нашей задачи и приведенная к стандартной форме, имеет следующий вид:

Максимизировать

Z = X1+25X2 + 0S1+0S2.

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

5X1 + 100X2+ S1 = 1000;

-X1 +2X2 + S2 = 0;

Х1≥0, Х2≥0, S1≥0, S2≥0.

Каждую точку пространства решений данной задачи, представленную на рис.2.1., можно определить с помощью переменных соответственно: основных X1 и Х2 и дополнительных S1 и S2, фигурирующими в модели стандартной формы. При S1 = 0 и S2 = 0 ограничения модели эквивалентны равенствам, которые представляются соответствующими ребрами пространства решений. Увеличение переменных S1 и S2 будет соответствовать смещению допустимых точек с границ пространства решений в его внутреннюю область Переменные X1, Х2, S1 и S2, ассоциированные с экстремальными точками A, B, и С можно упорядочить, исходя из того, какое значение (нулевое или ненулевое) имеет данная переменная в экстремальной точке.

Таблица 2.2

Экстремальная точка	Hyлевые переменные	Heнулевые переменные
А	S2, Х2	S1, X1
В	S1,X2	S2, X1
С	S1,S2	X1,Х2

Анализируя табл. 2.2, легко заметить две закономерности:

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

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

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

В этом состоит сущность свойства однозначности экстремальных точек.

В табл. 2.2 каждой неэкстремальной точке соответствует не более одной переменной. Так, любая точка внутренней области пространства решений вообще не имеет ни одной нулевой переменной, а любая неэкстремальная точка, лежащая на границе, всегда имеет лишь одну нулевую переменную.

Свойство однозначности экстремальных точек позволяет определить их алгебраическим методом. Будем считать, что линейная модель стандартной формы содержит т уравнений и п (т ≤ п) неизвестных (правые части ограничений — неотрицательные). Тогда все допустимые экстремальные точки определяются как все однозначные неотрицательные решения системы m уравнений, в которых п — m переменных равны нулю.

Однозначные решения такой системы уравнений, получаемые путем приравнивания к нулю (п — т) переменных, называются базисными решениями. Если базисное решение удовлетворяет требованию неотрицательности правых частей, оно называется допустимым базисным решением. Переменные, имеющие нулевое значение, называются небазисными переменными, остальные — базисными переменными.

Из вышеизложенного следует, что при реализации симплекс-метода алгебраическое определение базисных решений соответствует идентификации экстремальных точек, осуществляемой при геометрическом представлении пространства решений. Таким образом, максимальное число итераций при использовании симплекс-метода равно максимальному числу базисных решений задачи ЛП, представленной в стандартной форме. Это означает, что количество итерационных процедур симплекс-метода не превышает:

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

В нашем случае получено решение, соответствующее точке А, откуда следует осуществить переход в точку В. Для этого нужно увеличивать небазисную переменную X₂ от исходного нулевого значения до значения, соответствующего точке В (см. рис.2.1.). В точке В переменная S₁ (которая в точке А была базисной) автоматически обращается в нуль и, следовательно, становится небазисной переменной. Таким образом, между множеством небазисных и множеством базисных переменных происходит взаимообмен переменными Х₂ и S₁. Этот процесс можно наглядно представить в табл. 2.3.

Таблица 2.3

Экстремальная точка	Hyлевые переменные	Heнулевые переменные
А	S2, Х2	S1, X1
В	S1,X2	S2, X1

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

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

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