Элемент, стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом.

При переходе к новой симплексной таблице будем пользоваться следующими правилами:

.

Эти же правила можно сформулировать по другому:

1. Элементы разрешающей строки новой симплексной таблицы равны элементам прежней симплексной таблицы, деленным на разрешающий элемент.

2. В разрешающем столбце все элементы, кроме =1, равны 0.

3. Все остальные элементы находятся по правилу прямоугольника:

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

Аналогичное правило можно сформулировать и для нахождения элементов индексной строки и столбца свободных членов.

 

Пусть, например, имеется симплексная таблица. Тогда правило прямоугольника выглядит следующим образом:

 

БП

СБ

х1 х2 х3 х4 х5 х6

А0

θ

4 3 1 0 0 0
х3 0 1 2 3 1 0 0 15 15/1
х4 0 -7 -1 2 0 1 0 20
х5 0 2 0 4 0 0 1 4 4/2 min

Δj

-4 max по модулю -3 -1 0 0 0    

 

В табличке выделены:

  разрешающий элемент (главная диагональ)
     
  искомый элемент (главная диагональ)
     
  элементы побочной диагонали
     
  выводимая из базиса переменная
     
  вводимая в базис переменная (заменяет выводимую из базиса переменную)

 

После проведения преобразований на месте искомого элемента получим:

БП

СБ

х1 х2 х3 х4 х5  

А0

θ

4 3 1 0 0 0
х3 0 0            
х4 0 0              
х1 4 1 0 2 0 0 0,5 2  

Δj

0              

 

Таким же образом производится расчет всех остальных переменных, в том числе и в индексной строке и в столбце свободных членов.

Замечания:

1. Шаг симплексных преобразований называют итерацией.

2. Если в индексной строке среди оценок свободных переменных в оптимальном плане есть равные 0, то имеет место случай альтернативного оптимума (т.е. существует по крайней мере еще хотя бы одна угловая точка ОДР являющаяся оптимальным планом => оптимальных планов бесконечно много)

3. После каждой итерации можно делать проверку правильности вычислений по следующим формулам:

Теоремы:

1. (о существовании альтернативного оптимума)

Если в индексной строке последней симплексной таблицы, содержащей оптимальный план, имеется хотя бы одна нулевая индексная оценка, соответствующая свободной переменной, то ЗЛП имеет бесконечное число оптимальных планов.

Следствие: Если в индексной строке симплексной таблицы, содержащей оптимальный план, все оценки свободны переменных положительны, то найденный оптимальный план единственный.

2. (о неограниченности целевой функции)

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