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