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

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

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

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

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

5X1 + 100X2 + S1 = 1000

- X1 + 2X2 + S2 = 0

X1=>0, X2=>0, S1=>0, S2=>0

Каждую точку пространства решений данной задачи можно определить с помощью переменных X1 , X2 , S1 и S2 , фигурирующими в модели стандартной формы. При S1 = 0 и S2 = 0 ограничения модели эквивалентны равенствам, которые представляются соответствующими ребрами пространства решений. Увеличение переменных S1 и S2 будет соответствовать смещению допустимых точек с границ пространства решений в его внутреннюю область. Переменные X1 , X2 , S1 и S2 , ассоциированные с экстремальными точками А, В, и С можНО упорядочить, исходя из того, какое значение (нулевое ИЛИ ненулевое) Имеет данная переменная в экстремальной точке.

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

АналИЗИРуя таблИЦу, легко заметИТь две зАкономерности:

1. Стандартная модель содержИТ два уравнения и четыре неизвестных, поэтому в каждой ИЗ экстремАЛьных точек две (= 4 - 2) переменныЕ должны ИМеть нулевые значения.

2. Смежные экстремальные точки отличаются только одНОЙ переменной в каждой группе (нулевых и неНУлЕВых переменных), Первая закономерность сВИдетельствует о возможности определения экстремальных точек алгебраическИМ способом путем прИРавнивания нулю такого колИЧества перЕМенных, которое равно разностИ между количеством неизвестных и чИСлом уравнений. В этом состоИТ сущНОсть свойства ОднознАЧности экстремальных точек. Каждой Не экстремальной точке соответствует не более одной нулевой переменной. Так, любая точка внутренней области пространства решений вообще не ИМеет ни одной нулевой переменной, а любая не экстремальная точка, лежащая на границе, всегда имеет лишь одну нулевую переменную.

Свойство однозначности экстремальных точек позволяет определить их Алгебраическим методом. БуДЕм счИТать, что линейная модель стандартной формы содержИТ Т уравненИЙ и П ( т <= п ) неизвестных (пРавые части Ограничений — неотрИЦательные). Тогда все допустимые экстремальные точКи оПРедЕЛяются как все однозначные неотрицательные решения сИСтемы M уравненИЙ, в которых П — M пЕРеменных равны нулю.

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

Из вышеИЗложенного следует, что прИ рЕаЛИЗацИи сИМПЛекс метода алгебраическоЕ оПРеделенИе баЗиСных решенИЙ соответствует идентИФИКации экстремальных точек, осуществляемой при геометрическом представлении пространства решений. Таким образом, максимальное число ИТерацИЙ при использовании симплекс метода равно максимальному числу базИСных решенИЙ задачи ЛП, представленной в стандартной форме. Это Означает, что количество итерацИОнных процедур сИМплЕКс-метода нЕ превышает

Cпт= N! / [ ( N - M)!M!]

Вторая из ранЕЕ отмеченных закономЕРНОстей оказывается весьма полЕЗной для ПОстроения вычислитЕЛьных процедур симплекс-метода, при реалИЗаЦИи которого Осуществляется последовательный ПЕрЕХод от Одной ЭКстрЕМальноЙ точкИ к другой, смежной с ней. Так как смежные экстрЕМальныЕ точКИ отличаются только Одной ПЕременНОй, можно определить каждую последующую (смежную) экстремальную точку путем замЕНы одной ИЗ текущих небазисных (нулевых) переменных текущей базисНОй переменной. В нашем случае получено решение, соотвЕТствующее точке А , откуда следует осуществить переход в точку В. Для этого нужнО увелИЧиВАть небазисную переменную X2 от исходного НУлевого зНАчеНИя до значения, соответствующего точке В. В точке B переменная S1 автоматическИ обращается в нуль и, следовательно, станоВиТся Небазисной ПЕремеННой. Таким образом, между множеством Небазисных И множествОМ базисных переменных происходит ВзаимообмеН ПЕремЕнНыми X2 и S1 . Этот процесс можно наглядНО предСТавИТь В виде Следующей таблицы.

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

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

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

< Предыдущая		Следующая >