8.1. Определение разрешающей колонки.

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

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

8.2. Определение разрешающей строки.

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

(5.20)

где r – индекс разрешающей колонки;

l – количество строк, в которых свободные числа и элементы разрешающей колонки - одного знака.

В качестве разрешающей выбирается та строка, для которой найденное оценочное отношение минимальное, т.е.

(5.21)

где s – индекс разрешающей строки.

8.3. Определение разрешающего элемента.

Разрешающий элемент находится на пересечении разрешающей колонки и разрешающей строки.

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

9. Преобразование симплекс-таблицы.

Преобразования исходной симплекс-таблицы удобно осуществлять параллельно с заполнением новой. С целью снижения погрешности вычислений результаты расчетов рекомендуется представлять в виде обыкновенных дробей.

Пусть в результате предыдущего этапа были определены разрешающая строка – s и разрешающая колонка – r. Тогда преобразования исходной симплекс-таблицы можно представить следующей последовательностью действий:

9.1. Переменные, соответствующие разрешающей строке (x_s) и разрешающей колонке (x_r), меняют местами в новой симплекс-таблице. При этом базисная переменная становится свободной и наоборот.

9.2. В новой симплекс-таблице в клетку, где находился разрешающий элемент исходной симплекс-таблицы, записывают величину, обратную ему, т.е.:

. (5.22)

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

. (5.23)

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

(5.24)

9.5. Остальные элементы новой симплекс-таблицы рассчитываются по правилу «прямоугольника»:

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

Данное правило может быть записано в следующем формульном варианте.

Для элементов колонки свободных чисел:

(5.25)

(5.26)

где , – значения преобразованных элементов колонки свободных чисел, расположенных соответственно в i-й и строке целевой функции новой симплекс-таблицы.

Для остальных элементов симплекс-таблицы:

(5.27)

(5.28)

где – значение преобразованного элемента, расположенного в i-й строке и j-й колонке новой симплекс-таблицы;

– значение преобразованного элемента, расположенного в строке целевой функции в j-й колонке новой симплекс-таблицы.

В результате преобразований получим новую симплекс-таблицу (таблица 5.2).

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

Таблица 5.2

Преобразованная симплекс-таблица

СП БП
										–

Пример 5.4. Решить следующую задачу линейного программирования симплекс-методом:

Решение: