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

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

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

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

(5.20)

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

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

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

(5.21)

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

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

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

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

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

Дата добавления: 2013-12-12