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

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

Пусть в результате предыдущего этапа были определены разрешающая строка – 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. Решить следующую задачу линейного программирования симплекс-методом:

Решение:

I итерация: