В вычислительной схеме симплекс-метода реализуется упорядоченный процесс , при котором , начиная с некоторой исходной допустимой угловой точки ( обычно начало координат ) , осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех пор , пока не будет найдена точка , соответствующая оптимальному решению .
Общую идею симплекс-метода можно проиллюстрировать на примере модели , посроенной для нашей задачи . Пространство решений этой задачи представим на рис. 1 . Исходной точкой алгоритма является начало координат ( точка А на рис. 1 ) . Решение , соответствующее этой точке , обычно называют начальным решением . От исходной точки осуществляется переход к некоторой смежной угловой точке .
Выбор каждой последующей экстремальной точки при использовании симплекс-метода определяется следующими двумя правилами .
1. Каждая последующая угловая точка должна быть смежной с предыдущей . Этот переход осуществляется по границам ( ребрам ) пространства решений .
2. Обратный переход к предшествующей экстремальной точке не может производиться .
Таким образом , отыскание оптимального решения начинается с некоторой допустимой угловой точки , и все переходы осуществляются только к смежным точкам , причем перед новым переходом каждая из полученных точек проверяется на оптимальность .
Определим пространство решений и угловые точки агебраически . Требуемые соотнощшения устанавливаются из указанного в таблице соответствия геометрических и алгебраических определений
.
| Геометрическое определение | Алгебраическое определение ( симплекс метод ) |
| Пространство решений | Ограничения модели стандартной формы |
| Угловые точки | Базисное решение задачи в стандартной форме |
Линейная модель , построенная для нашей задачи и приведенная к стандартной форме , имеет следующий вид :
Максимизировать
Z = X1 + 25X2 + 0S1 + 0S2
При ограничениях
5X1 + 100X2 + S1 = 1000
- X1 + 2X2 + S2 = 0
X1=>0 , X2=>0 , S1=>0 , S2=>0
Каждую точку пространства решений данной задачи , представленную на рис.1 , можно определить с помощью переменных 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.Смежные экстремальные точки отличаются только одной пе-
ременной в каждой группе ( нулевых и ненулевых переменных ) ,
Первая закономерность свидетельствует о возможности опре-
деления экстремальных точек алгебраическим способом путем при-
равнивания нулю такого количества переменных , которое равно
разности между количеством неизвестных и числом уравнений .
В этом состоит сущность свойства однозначности экстремальных
точе на рис 1 каждой неэкстремальной точке соответствует
не более одной нулевой переменной. Так, любая точка внутренней
области пространства решений вообще не имеет ни одной нулевой
переменной, а любая неэкстремальная точка, лежащая на границе,
всегда имеет лишь одну нулевую переменную.
Свойство однозначности экстремальных точек позволяет опре-
делить их алгебраическим методом. Будем считать, что линейная
модель стандартной формы содержит т уравнений и п(т <= п) не-
известных (правые части ограничений — неотрицательные). Тогда
все допустимые экстремальные точки определяются как все одно-
значные неотрицательные решения системыm уравнений, в ко-
торых п — m переменных равны нулю.
Однозначные решения такой системы уравнений, получаемые
путем приравнивания к нулю (п — т) переменных, называются
базисными решениями. Если базисное решение удовлетворяет
требованию неотрицательности правых частей, оно называется
допустимым базисным решением. Переменные, имеющие нулевое
значение, называются небазисными переменными, остальные —
базисными переменными.
Из вышеизложенного следует, что при реализации симплекс-
метода алгебраическое определение базисных решений соответст-
вует идентификации экстремальных точек, осуществляемой при
геометрическом представлении пространства решений. Таким об-
разом, максимальное число итераций при использовании симплекс-
метода равно максимальному числу базисных решений задачи ЛП,
представленной в стандартной форме. Это означает, что количество
итерационных процедур симплекс-метода не превышает
Cпт= n! / [ ( n - m )!m! ]
Вторая из ранее отмеченных закономерностей оказывается
весьма полезной для построения вычислительных процедур симп-
лекс-метода, при реализации которого осуществляется последова-
тельный переход от однойэкстремальной точки к другой, смежнойс ней. Так как смежные экстремальные точки отличаются только
однойпеременной, можно определить каждую последующую ( смеж-
ную) экстремальную точку путем замены одной из текущих не-
базисных ( нулевых ) переменных текущей базисной переменной.
В нашем случае получено решение, соответствующее точке А , откуда следует осуществить переход в точку В . Для этого нужно увеличивать небазисную переменную X2 от исходного нулевого значения до значе-
ния, соответствующего точке В ( см. рис. 1 ). В точкеB переменная
S1 ( которая в точке А была базисной ) автоматически обращается в
нуль и , следовательно , становится небазиснойпеременной. Таким
образом , между множеством небазисныхи множеством базисных
переменных происходит взаимообмен переменными X2 иS1 . Этот
процесс можно наглядно представить в видеследующей таблицы.
| Экстремальная точка | Нулевые переменные | Ненулевые переменные |
| А | S2 , X2 | S1 , X1 |
| В | S1 , X2 | S2 , X1 |
Применяя аналогичную процедуру ко всем экстремальным точкам
рис. 1 , можно убедиться в том, что любую последующую экстре-
мальную точку всегда можно определить путем взаимной замены
по одной переменной в составе базисных и небазисных переменных
( предыдущей смежной точки ) . Этот фактор существенно упрощает
реализацию вычислительных процедур симплекс-метода.
Рассмотренный процесс взаимной замены переменных приводит
к необходимости введения двух новых терминов. Включаемой пе-
ременной называется небазисная в данный момент переменная ,
которая будет включена в множество базисных переменных на сле-
дующей итерации ( при переходе к смежной экстремальной точке ) .
Исключаемая переменная — это та базисная переменная , которая
на следующей итерации подлежит исключению из множества ба-
зисных переменных .