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

Представление пространства решений с помощью алгебраических методов рассмотрим на примере задачи №1. Соответствующая линейная модель, приведенная к стандартной форме, имеет следующий вид:

Максимизировать W = 3 х ₁ + 2 х ₂

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

х ₁ + 2 х ₂ £ 6 (1),

2 х ₁ + х ₂ £ 8 (2),

- х ₁ + х ₂ £ 1 (3),

х ₂ £ 2 (4),

х ₁, х ₁ ³ 0.

На Рис. 2.2 представлено пространство решений данной задачи. Каждую точку этого пространства можно определить с помощью переменных х₁, х₂, s₁, s₂, s₃ и s₄ фигурирующих в модели стандартной формы. Для идентификации нужной точки пространства решений воспользуемся тем, что при s_i = 0, i=1, 2, 3, 4, ограничения модели эквивалентны равенствам, которые представляются соответствующими ребрами пространства решений. Например, при s₁₌0 первое ограничение задачи принимает вид равенства х₁+х₂ = 6,

Рис. 3.2.

которое представляется ребром СD. Увеличение переменных s_i (s_i >0) будет соответствовать смещению допустимых точек с границ пространства решений в его внутреннюю область.

Нас интересует прежде всего алгебраическое представление экстремальных точек. Анализируя рис. 3.2, можно заметить, что переменные x ₁, x ₂, s₁, s₂, s₃, s₄ ассоциированные с экстремальными точками А, В, С, D, Е и F, можно упорядочить, исходя из того, какое значение (нулевое или ненулевое) имеет данная переменная в экстремальной точке.

Экстремальная точка	Нулевые переменные	Ненулевые переменные
А	х1, х2	s1, s2, s3, s4
В	s2, х2	s1, х1, s3, s4
С	s1, s2	х1, х2, s3, s4
D	s4, s1	х1, х2, s3, s2
E	s4, s3	х1, х2, s1, s2
F	s3, х1	х2, s2, s1, s4

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

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

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

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

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

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

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

Сⁿ_m = n!/[(n - m)! m!].

Вторая из ранее отмеченных закономерностей оказывается весьма полезной для построения вычислительных процедур симплекс-метода, при реализации которого осуществляется последовательный переход от одной экстремальной точки к другой, смежной с ней. Так как смежные экстремальные точки отличаются только одной переменной, можно определить каждую последующую (смежную) экстремальную точку путем замены одной из текущих небазисных (нулевых) переменных текущей базисной переменной. Положим, например, что при решении задачи № 1 получено решение, соответствующее точке А, откуда следует осуществить переход в точку В. Для этого нужно увеличивать небазисную переменную х ₁ от исходного нулевого значения до значения, соответствующего точке В (см. рис. 3.2). В точке В переменная s₂, (которая в точке A была базисной) автоматически обращается в нуль и, следовательно, становится небазисной переменной. Таким образом, между множеством небазисных и множеством базисных переменных происходит взаимообмен переменными х₁ и s₂, Этот процесс можно наглядно представить в виде следующей таблицы.

Экстремальная	Небазисные (нулевые)	Базисные
точка	переменные	переменные
А	x 1, x 2	s1, s2, s3, s4
В	s2, x 2	s1, x 1, s3, s4

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

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