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

Алгоритм преобразования:

а) базисная и свободная переменные, находящиеся в разрешающих строке и столбце, меняются местами;

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

в) ячейки разрешающей строки в новой симплекс-таблице заполняются элементами из исходной таблицы, деленными на разрешающий элемент;

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

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

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

Тогда значение искомого элемента в новой симплекс-таблице равно:

т.е. все элементы данной формулы входят в «прямоугольник».

Преобразуем следующую таблицу.

Исходная таблица

Новая преобразованная таблица

Базисные переменные	Свободные члены	Свободные переменные

а) меняем переменные и местами;

б) заполняем ячейку на пересечении значением ;

в) заполняем строку значениями: ; ;

г) заполняем столбец значениями:

; ; ;

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

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

Искомый элемент в новой симплекс-таблице на пересечении строки и столбца равен:

Внесем данное число в новую симплекс-таблицу. Таким же образом, находятся значения всех недостающих элементов.

Рассмотрение этапов алгоритма закончено.

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

Пример решения задачи линейного программирования симплекс-методом.

Исходные данные:

Решение:

I итерация:

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

Приведем ограничения-неравенства исходной стандартной задачи к виду « »; затем –к каноническому виду, и, наконец, к требуемой форме:

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

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

Таблица

Базисные переменные	Свободные члены	Свободные переменные
	-9	-3	1
	50	2	3
	-18	1	-4
	0	-6	-1

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

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

В строках и , содержащих отрицательные свободные члены (-9) и (-18) имеются отрицательные переменные (-3) и (-4), следовательно, ограничения совместны.

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

Целевая функция ограничена, поскольку в столбцах и , содержащих в строке целевой функции отрицательные переменные (-6) и (-1), имеются положительные переменные.

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

базисное решение недопустимое, т.к. имеются отрицательные переменные и .

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

8.1. определение разрешающего столбца

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

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

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

Таблица

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

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