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

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

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

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

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

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

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

1 этап: формирование исходной симплекс-таблицы.

Исходная задача линейного программирования задана в стандартной форме. Приведем ее к каноническому виду путем введения в каждое из ограничений-неравенств дополнительной неотрицательной переменной, т.е.

В полученной системе уравнений примем в качестве разрешенных (базисных) переменные х₃, х₄, х₅, х₆, тогда свободными переменными будут х₁, х₂. Выразим базисные переменные через свободные:

Приведем целевую функциюк следующему виду:

На основе полученной задачи сформируем исходную симплекс-таблицу:

Таблица 5.3

Исходная симплекс-таблица

СП БП				Оценочные отношения
		–2	–3

2 этап: определение базисного решения.

Согласно определению базисного решения свободные переменные равны нулю, а значения базисных переменных – соответствующим значениям свободных чисел, т.е.:

.

3 этап: проверка совместности системы ограничений ЗЛП.

На данной итерации (в таблице 5.3) признак несовместности системы ограничений (признак 1) не выявлен (т.е. нет строки с отрицательным свободным числом (кроме строки целевой функции), в которой не было бы хотя бы одного отрицательного элемента (т.е. отрицательного коэффициента при свободной переменной)).

4 этап: проверка ограниченности целевой функции.

На данной итерации (в таблице 5.3) признак неограниченности целевой функции (признак 2) не выявлен (т.е. нет колонки с отрицательным элементом в строке целевой функции (кроме колонки свободных чисел), в которой не было бы хотя бы одного положительного элемента).

5 этап: проверка допустимости найденного базисного решения.

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

6 этап: проверка оптимальности.

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

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

Так как найденное базисное решение допустимое, то поиск разрешающей колонки будем производить по следующей схеме: определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.3, таких колонок две: колонка «х₁» и колонка «х₂». Из таких колонок выбирается та, которая содержит наименьший элемент в строке целевой функции. Она и будет разрешающей. Колонка «х₂» содержит наименьший элемент (–3) в сравнении с колонкой «х₁». Следовательно, ее принимаем в качестве разрешенной.

Дата добавления: 2014-01-04